A list that never invalidates iterators

Question

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.
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>

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;
};

• StoryTeller - Unslander Monica: Side note, by I think this is misguided. Keeping parts of a datastructure alive after it's gone is bound to be problematic at some point. What not use std::Forward_list that holds shared_ptrs? That way the data can outlive the list, even if the list is dead. You likely want that instead.

Answer 1

1. You know, your Node can be far more general if you don't parameterize with T and a template-template, but instead directly with a pointer-to-T.

   template<class T, template<class> class shared_ptr = std::shared_ptr>
   struct Node {
    using shared_ptr_t = shared_ptr<Node<T>>;
   

   Becomes

   template<class Ptr>
   struct Node {
    using T = typename std::pointer_traits<Ptr>::element_type;
    using shared_ptr_t = typename std::pointer_traits<Ptr>::template rebind<Node<T>>;
   

2. Currently, only your Node is prepared for using a different pointer-type. You probably want to do iterator and List up the same.

3. There is no reason for defining the single ctor in Node. If you leave it out and use aggregate-initialization instead, you can emplace-construct as needed.

4. The interface of iterator should be changed:

   1. operator== and operator!= should be free functions.
   2. Implicit conversion from iterator<Ptr<T>> to iterator<Ptr<const T>> should be supported.
   3. .valid() is a curious way to ask whether you have a Sentinel. Better rename it .isEnd() or such, if you insist on retaining it.
   4. In the same vein, .insert() is a bad name as it should be .insert_after(). Also, there should be an emplace-variant. If your list supported allocators, it couldn't be a member of the iterator at all.
   5. In the same vein, the exception-message in .insert() is non-sensical. It should be "Cannot insert after the end.".
   6. .next(), aside from the bad name, should not be a member of iterator.
   7. .advance() should be a generic algorithm, and most certainly not a member.
   8. You can define .swap(). But then it should be noexcept and there should be a free-function-variant.

5. You should provide all of the container-interface your implementation of a single-linked-list reasonably can. That means provide const_iterator's, and be consistent with the standards naming.

6. The name List suggests it's a generic double-linked list, not a single-linked-list. Call it forward_list.

7. You aren't consistent in which conventions you use for types.

8. Your copy-assignment is not self-assignment-safe. Fix it.

9. The size is not updated if the list is changed using an iterator.

I'm stopping my review here, though there are more issues.