All the snippets are part of a single file as the naming will be refactored before splitting into.hpp/.cpp files.
Demo
Ps. Code requires some of C++17 features, so a somehow recent compiler is required.
INCLUDES
#include <iostream>
#include <memory>
All the snippets are part of a single file as the naming will be refactored before splitting into.hpp/.cpp files.
Demo
Ps. Code requires some of C++17 features, so a somehow recent compiler is required.
INCLUDES
#include <iostream>
#include <memory>
A list that never invalidates iterators
I need a forward list with iterators that can survive anything – from removal of pointed element to destroying whole list. I decided to implement this with shared pointers, each node in the list stores a `std::shared_ptr` to the next node and iterators have their own pointer to a given node. I think that makes all accessible data safe.
NODE
template<class T, template<class> class shared_ptr = std::shared_ptr>
struct Node {
using shared_ptr_t = shared_ptr<Node<T>>;
shared_ptr_t next;
T value;
Node(shared_ptr_t n, const T& v) {
value = v;
next = n;
}
};
ITERATOR
template<class T>
class iterator {
public:
using shared_ptr_t = typename Node<T>::shared_ptr_t;
using node_t = Node<T>;
iterator(shared_ptr_t node) {
m_node = node;
}
bool operator==(const iterator& it) const { return m_node == it.m_node; }
bool operator!=(const iterator& it) const { return !(it == *this); }
bool valid() const {
return bool(m_node);
}
T& operator*() const {
return m_node->value;
}
shared_ptr_t node() const {
return m_node;
}
void insert(const T& value) const {
if(m_node) {
m_node->next = std::make_shared<node_t>(m_node->next, value);
} else {
throw std::logic_error{"Invalid iterator can't insert"};
}
}
shared_ptr_t next(const iterator& it) const {
return std::exchange(m_node->next, it.m_node);
}
iterator& operator++() {
m_node = m_node->next;
return *this;
}
iterator& advance(int dist) {
while(dist-- > 0 && m_node) {
++(*this);
}
return *this;
}
void swap(iterator& it) {
std::swap(m_node, it.m_node);
}
template<class>
friend class List;
private:
shared_ptr_t m_node;
};
LIST
template<class T>
class List {
public:
using shared_ptr_t = typename Node<T>::shared_ptr_t;
using iterator_t = iterator<T>;
using node_t = Node<T>;
List() = default;
explicit List(const List& list) {
this->operator=(list);
}
explicit List(List&& list) {
this->operator=(std::forward(list));
}
explicit List(iterator_t&& fwd_it, size_t explicit_size = 0) {
m_size = explicit_size;
m_root = std::exchange(fwd_it.m_node, nullptr);
if(!m_size) {
for(auto it = begin(); it.valid(); ++it) {
++m_size;
}
}
}
explicit List(const iterator_t& begin, const iterator_t& end = iterator_t{nullptr}) {
auto it = begin;
while(it.valid() && it != end) {
push_back(*it);
++it;
}
}
List<T>& operator=(const List& list) {
clear();
for(auto& el: list) {
push_back(el);
}
m_size = list.size();
return *this;
}
List<T>& operator=(List&& list) {
m_root = std::exchange(list.m_root, nullptr);
m_size = std::exchange(list.m_size, 0);
return *this;
}
size_t size() const {
return m_size;
}
void insert(const size_t idx, const T& value) {
bound_check(bound_check_type::GREATER, "List<T>::insert(idx)", idx);
auto it = begin();
if(idx != 0) {
it.advance(static_cast<int>(idx) - 1);
it.insert(value);
} else {
m_root = std::make_shared<node_t>(it.node(), value);
}
++m_size;
}
void push_back(const T& val) {
insert(m_size, val);
}
void push_front(const T& val) {
insert(0, val);
}
void erase(const size_t idx) {
bound_check(bound_check_type::GREATER_EQUAL, "List<T>::erase(idx)", idx);
auto it = begin();
it.advance(static_cast<int>(idx - 1));
if(idx != 0) {
auto it_fwd = it;
it_fwd.advance(2);
it.next(it_fwd);
} else {
it.advance(1);
m_root = it.node();
}
--m_size;
}
void pop_back() {
erase(m_size - 1);
}
void pop_front() {
erase(0);
}
void clear() {
m_root = nullptr;
m_size = 0;
}
T& operator[](size_t idx) {
bound_check(bound_check_type::GREATER_EQUAL, "List<T>::operator[](idx)", idx);
return *begin().advance(idx);
}
const T& operator[](size_t idx) const {
bound_check(bound_check_type::GREATER_EQUAL, "List<T>::operator[](idx) const", idx);
return *begin().advance(idx);
}
iterator_t begin() const {
return iterator_t{m_root};
}
static iterator_t end() {
return iterator_t{nullptr};
}
private:
enum class bound_check_type {
GREATER, GREATER_EQUAL
};
void bound_check(bound_check_type type, std::string func, size_t idx) {
if(idx > size() || (type == bound_check_type::GREATER_EQUAL && idx == size())) {
throw std::logic_error{func + ": idx >" + (type == bound_check_type::GREATER ? "" : "=") + " size"};
}
}
shared_ptr_t m_root = nullptr;
size_t m_size = 0;
};
lang-cpp