Last active
May 20, 2020 00:44
-
-
Save aldanor/7f0af22a049ce2a24a3b007cf28b5cb6 to your computer and use it in GitHub Desktop.
vlist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef VLIST_H | |
#define VLIST_H | |
#include <algorithm> | |
#include <cstddef> | |
#include <cstdint> | |
#include <iterator> | |
#include <memory> | |
#include <utility> | |
#include <vector> | |
namespace vlist_ns { | |
using default_index_type = std::int32_t; | |
template<typename I> | |
inline constexpr I null_index = static_cast<I>(-1); | |
template<typename T, typename I> | |
struct node { | |
T value; | |
I next = null_index<I>; | |
I prev = null_index<I>; | |
template<typename... Args> | |
explicit node(Args&&... args) | |
: value{std::forward<Args>(args)...} | |
{} | |
}; | |
template<typename T, typename I> | |
class vlist_const_iterator { | |
public: | |
using iterator = vlist_const_iterator<T, I>; | |
using value_type = T; | |
using reference = const T&; | |
using pointer = const T*; | |
using difference_type = std::ptrdiff_t; | |
using iterator_category = std::forward_iterator_tag; | |
vlist_const_iterator() = default; | |
vlist_const_iterator(const node<T, I>* ptr, I idx) | |
: ptr_(ptr), idx_(idx) | |
{} | |
vlist_const_iterator(const vlist_const_iterator&) = default; | |
vlist_const_iterator(vlist_const_iterator&&) noexcept = default; | |
vlist_const_iterator& operator=(const vlist_const_iterator&) = default; | |
vlist_const_iterator& operator=(vlist_const_iterator&&) noexcept = default; | |
reference operator*() const { | |
return this->ptr_[static_cast<std::size_t>(this->idx_)].value; | |
} | |
pointer operator->() const { | |
return &this->ptr_[static_cast<std::size_t>(this->idx_)].value; | |
} | |
iterator& operator++() { | |
this->idx_ = this->ptr_[static_cast<std::size_t>(this->idx_)].next; | |
return *this; | |
} | |
iterator operator++(int) { | |
auto it = *this; | |
++(*this); | |
return it; | |
} | |
bool operator==(const iterator& rhs) const { | |
return this->idx_ == rhs.idx_; | |
} | |
bool operator!=(const iterator& rhs) const { | |
return !(*this == rhs); | |
} | |
private: | |
const node<T, I>* ptr_ = nullptr; | |
I idx_ = null_index<I>; | |
template<typename, typename, typename> friend class vlist; | |
}; | |
template<typename T, typename I> | |
class vlist_iterator { | |
public: | |
using iterator = vlist_iterator<T, I>; | |
using value_type = T; | |
using reference = T&; | |
using pointer = T*; | |
using difference_type = std::ptrdiff_t; | |
using iterator_category = std::forward_iterator_tag; | |
vlist_iterator() = default; | |
vlist_iterator(node<T, I>* ptr, I idx) | |
: ptr_(ptr), idx_(idx) | |
{} | |
vlist_iterator(const vlist_iterator&) = default; | |
vlist_iterator(vlist_iterator&&) noexcept = default; | |
vlist_iterator& operator=(const vlist_iterator&) = default; | |
vlist_iterator& operator=(vlist_iterator&&) noexcept = default; | |
reference operator*() { | |
return this->ptr_[static_cast<std::size_t>(this->idx_)].value; | |
} | |
pointer operator->() { | |
return &this->ptr_[static_cast<std::size_t>(this->idx_)].value; | |
} | |
iterator& operator++() { | |
this->idx_ = this->ptr_[static_cast<std::size_t>(this->idx_)].next; | |
return *this; | |
} | |
iterator operator++(int) { | |
auto it = *this; | |
++(*this); | |
return it; | |
} | |
bool operator==(const iterator& rhs) const { | |
return this->idx_ == rhs.idx_; | |
} | |
bool operator!=(const iterator& rhs) const { | |
return !(*this == rhs); | |
} | |
operator vlist_const_iterator<T, I>() const { | |
// to allow conversion from mutable to const iterator | |
return {this->ptr_, this->idx_}; | |
} | |
private: | |
node<T, I>* ptr_ = nullptr; | |
I idx_ = null_index<I>; | |
template<typename, typename, typename> friend class vlist; | |
}; | |
template< | |
typename T, | |
typename I = default_index_type, | |
typename A = std::allocator<node<T, I>> | |
> | |
class vlist { | |
static constexpr I null = null_index<I>; | |
public: | |
using value_type = T; | |
using index_type = I; | |
using allocator_type = A; | |
using node_type = node<T, I>; | |
using iterator = vlist_iterator<T, I>; | |
using const_iterator = vlist_const_iterator<T, I>; | |
vlist() = default; | |
explicit vlist(std::size_t reserve, allocator_type alloc = {}) | |
: nodes_(alloc) | |
{ | |
this->nodes_.reserve(reserve); | |
} | |
explicit vlist(allocator_type alloc) | |
: vlist(0, alloc) | |
{} | |
vlist(const vlist&) = default; | |
vlist(vlist&&) noexcept = default; | |
vlist& operator=(const vlist&) = default; | |
vlist& operator=(vlist&&) noexcept = default; | |
void clear() noexcept { | |
this->nodes_.clear(); | |
this->size_ = 0; | |
this->first_ = null; | |
} | |
std::size_t size() const noexcept { | |
return this->size_; | |
} | |
bool empty() const noexcept { | |
return this->size_ == 0; | |
} | |
template<typename... Args> | |
iterator emplace(const_iterator pos, Args&&... args) { | |
return this->emplace_(pos, std::forward<Args>(args)...); | |
} | |
iterator erase(iterator pos) { | |
return this->erase_(pos); | |
} | |
iterator erase(const_iterator pos) { | |
return this->erase_(pos); | |
} | |
iterator begin() { | |
return {this->nodes_.data(), this->first_}; | |
} | |
iterator end() { | |
return {}; | |
} | |
iterator begin() const { | |
return {this->nodes_.data(), this->first_}; | |
} | |
iterator end() const { | |
return {}; | |
} | |
const_iterator cbegin() const { | |
return {this->nodes_.data(), this->first_}; | |
} | |
const_iterator cend() const { | |
return {}; | |
} | |
template<typename A_, typename I_> | |
bool operator==(const vlist<T, I_, A_>& rhs) const { | |
return ( | |
this->size() == rhs.size() | |
&& std::equal(this->cbegin(), this->cend(), rhs.cbegin()) | |
); | |
} | |
template<typename A_, typename I_> | |
bool operator!=(const vlist<T, I_, A_>& rhs) const { | |
return !(*this == rhs); | |
} | |
public: | |
std::vector<node_type, allocator_type> nodes_; | |
I first_ = null; | |
I last_ = null; | |
std::size_t size_ = 0; | |
node_type& at(index_type idx) { | |
return this->nodes_[static_cast<std::size_t>(idx)]; | |
} | |
const node_type& at(index_type idx) const { | |
return this->nodes_[static_cast<std::size_t>(idx)]; | |
} | |
template<typename P, typename... Args> | |
iterator emplace_(P pos, Args&&... args) { | |
auto size = static_cast<index_type>(this->size()); | |
node_type node{std::forward<Args>(args)...}; | |
node.next = pos.idx_; | |
auto& prev = pos.idx_ == null ? this->last_ : this->at(pos.idx_).prev; | |
node.prev = prev; | |
if (prev == null) { | |
this->first_ = size; | |
} else { | |
this->at(prev).next = size; | |
} | |
prev = size; | |
this->nodes_.emplace_back(std::move(node)); | |
++this->size_; | |
return {this->nodes_.data(), size}; | |
} | |
template<typename P> | |
iterator erase_(P pos) { | |
if (pos.idx_ != null) { | |
auto &node = this->at(pos.idx_); | |
if (node.prev != null) { | |
this->at(node.prev).next = node.next; | |
} else { | |
this->first_ = node.next; | |
} | |
if (node.next != null) { | |
this->at(node.next).prev = node.prev; | |
} else { | |
this->last_ = node.prev; | |
} | |
node.prev = null; | |
node.next = null; | |
--this->size_; | |
if (this->size_ == 0) { | |
this->nodes_.clear(); | |
} | |
return {this->nodes_.data(), node.next}; | |
} else { | |
return this->begin(); | |
} | |
} | |
}; | |
} // namespace vlist_ns | |
using vlist_ns::vlist; | |
#endif // VLIST_H |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment