Skip to content

Instantly share code, notes, and snippets.

@aldanor
Last active May 20, 2020 00:44
Show Gist options
  • Save aldanor/7f0af22a049ce2a24a3b007cf28b5cb6 to your computer and use it in GitHub Desktop.
Save aldanor/7f0af22a049ce2a24a3b007cf28b5cb6 to your computer and use it in GitHub Desktop.
vlist
#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