std::list reimplementation for practice

Because this is an attempt to rewrite std::list, I’m not going to bother doing a design review; the design was done by the standard committee (or, perhaps Stepanov). So I’ll just jump right into the code.

    using reference = T &;
    using const_reference = const T &;

You should use C++-style declarator layout, which implies no space between the T and any decorator (like &. So, using reference = T&;. Putting a space between the type and the decorator makes it easier to confuse with bitwise AND.

You are also missing a ton of typedefs, like size_type and reverse_iterator. If you don’t have those types, it makes your list harder to use as a drop-in replacement for std::list.

    class const_iterator; /* const_iterator != const iterator */

Yes! Good catch! Too many people make the mistake that const_iterator is just const iterator!

    struct node_type {
        value_type data;
        node_type *previous;
        node_type *next;

        node_type(const value_type data_,
                  node_type *previous_,
                  node_type *next_ = nullptr) : data(data_),
                                                previous(previous_),
                                                next(next_) {};
    };

The constructor really serves no purpose here. You could just do:

struct node_type {
    value_type data;
    node_type* previous;
    node_type* next = nullptr;
};

And new node_type{value, current} would still work. But you would now be able to use designated initializers, if you like.

Also, again, you should use C++-style declarators, not C-style:

• node_type *previous; – this is C style.
• node_type* previous; – this is C++ style.

Now, you may get suggestions to use smart pointers here, but I recommend you don’t.

The reason you may be told to use smart pointers is because your class has some bugs, and using a smart pointer will fix most of them. However… it will introduce other, more insidious problems.

I’d split the argument against using smart pointers here into two parts:

• The design argument.
• The practical argument.

The design argument is that using a smart pointer in the node_type class would be implying that each node owns the following (or previous) node. But… that’s silly. Nodes don’t own other nodes. The list owns all the nodes.

The practical argument is complex. Right now, your destructor basically does this:

node_type* p_node = head;
while (p_node != nullptr)
{
    auto p_temp = p_node;
    p_node = head->next;
    delete p_temp;
}

If your list has a billion elements… no problem. The loop will run a billion times, but, that’s fine.

Now, if you changed head and node_type::next to be smart pointers, then your destructor would basically be doing this:

// implicit delete head
    // implicit delete head->next
        // implicit delete head->next->next
            // implicit delete head->next->next->next
                // implicit delete head->next->next->next->next
                    // ... and so on until next is nullptr

That is, each implicit smart pointer destruction has to then implicitly destroy the next one. Each destructor is a function call, calling another destructor, which is another function call. If you have enough elements, you could end up overlowing the function call stack. In other words, stack overflow, which is UB, and might mean a crash.

So I would advise not using smart pointers in the node_type. (Or for head.)

That means your list class is left with bugs, but we’ll get to that shortly.

    bool empty();

    int size();

    void clear();

These should all be const, and they should all be noexcept, because there is no possible way for any of them to fail.

According to the standard container interface, size() should return an unsigned integer. Now, admittedly, this was a mistake. But it’s a mistake we’re stuck with.

In my opinion you are actually correct to use a (signed) int for the size. But my opinion doesn’t really count for much. The interface is what it is, and if you don’t abide by it, you could introduce subtle bugs in code that assumes size() is unsigned.

So basically, you should probably do something like:

    using size_type = std::size_t;

    size_type count = 0;

    auto size() const -> size_type;

There are a bunch of very useful std::list functions you are missing. Some of them are pretty fundamental, too. For example, erase() is a very fundamental operation on lists; you could basically rewrite pop_front(), pop_back(), and clear() in terms of erase() (as erase(begin()), erase(prev(end())), and erase(begin(), end()) (or while (not empty()) erase(begin()))).

By the way, insert() is another fundamental operation; you could write push_front() and push_back() (and others) in terms of insert(). But we’ll get to that.

But the most important thing your list is missing: copy and move constructors and assignment.

The rule of 3/5/0 basically states that if you have do define any of the class special operations… you have to define all of them. The special operations are:

• Destruction.
• Copy construction.
• Move construction.
• Copy assignment.
• Move assignment.

You need a destructor. Therefore, you need all five (unless you don’t want to support moving, in which case, you only need three: destructor, and copy construction and assignment).

Because you have not defined the special ops, your list is buggy and dangerous. You don’t notice because in your test code, you only ever create one list; there is no copying or moving or assignment of any kind. But trust me when I say: your class is dangerous. You need the special ops.

template<typename T>
typename List<T>::reference List<T>::front() {
    if (empty()) throw std::runtime_error("Empty List");
    return head->data;
}

template<typename T>
typename List<T>::const_reference List<T>::front() const {
    if (empty()) throw std::runtime_error("Empty List");
    return rear->data;
}

If you’re going to throw an exception for this, std::runtime_error is not the right choice. std::runtime_error means… there was a problem at runtime. Which means, there was a problem that could not be diagnosed until the program was running. For example, “file not found” is a runtime error, because there is nothing you can do at compile time to make sure the file is going to be there at run time.

In other words, a runtime error is when you have no possible way of knowing whether the function is going to fail or not… until you actually try it. If you are trying to open a file, there is no possible way to know beforehand whether the file exists or not (and no, checking just before doesn’t work, because that would be a TOCTOU race condition).

But in this case, it is trivial to know beforehand whether calling front() will succeed or not. Just do this:

if (empty())
    // always unsafe to call list.front()
else
    // always safe to call list.front()

If it’s an error that can be prevented simply be changing the logic of the calling code, then it is not a std::runtime_error, it is a std::logic_error.

template<typename T>
class List<T>::iterator {
private:
    node_type *ptr;

    explicit iterator(node_type *ptr_) : ptr(ptr_) {};
public:
    iterator &operator++() {
        ptr = ptr->next;
        return *this;
    }

    bool operator!=(const iterator &other) {
        return ptr != other.ptr;
    }

    bool operator==(const iterator &other) {
        return ptr == other.ptr;
    }

    reference operator*() const {
        return ptr->data;
    }

    friend List<T>;
};

template<typename T>
class List<T>::const_iterator {
private:
    // const_iterator the const qualified field is ptr.
    node_type const *ptr;

    explicit const_iterator(node_type const *ptr_) : ptr(ptr_) {};
public:

    const_iterator operator++() {
        ptr = ptr->next;
        return *this;
    };

    bool operator!=(const const_iterator &other) {
        return ptr != other.ptr;
    }

    bool operator==(const const_iterator &other) {
        return ptr == other.ptr;
    }

    const_reference operator*() {
        return ptr->data;
    }

    friend List<T>;
};

You may have observed that these two classes are essentially identical.

There is a handy trick for writing iterators for containers. The trick is to use a bool non-type template parameter, that encodes whether the iterator is for const iteration or not. Then there are basically only two differences between iterator and const_iterator:

1. Some typedefs (for example value_type would be T for iterator and T const for const_iterator); and
2. const_iterator must be implicitly constructible from iterator… but not the other way around.

The first prerequisite is easy to achieve:

template <bool Const>
class iterator_base
{
public:
    using value_type = std::conditional_t<Const, T const, T>;
    using reference  = std::conditional_t<Const, T const&, T&>;
    using pointer    = std::conditional_t<Const, T const*, T*>;

    // ...
};

(Or use the typedefs in the list class, like conditional_t<Const, List<T>::const_reference, List<T>::reference>.)

The second was hard prior to C++20, but is now trivial:

template <bool Const>
class iterator_base
{
public:
    // ...

    iterator_base(iterator_base<false> it) requires Const
        ptr{it.ptr}
    {}

    // ...
};

(As an aside, you should really move on from C++11. It was state of the art a generation ago. The language has evolved.)

The rest of the class is pretty simple. Most functions are identical for both iterator and const_iterator. For example:

template <bool Const>
class iterator_base
{
public:
    // ...

    auto operator++() -> iterator_base& {
        ptr = ptr->next;
        return *this;
    }

    auto operator++(int) -> iterator_base {
        auto const temp = *this;
        ++(*this);
        return temp;
    }

    // same for operator--

    auto operator*() const -> reference { return ptr->data; }

    // same for operator->

    // Using iterator_base<true> here means that you can mix and match
    // comparisons between iterators and const_iterators, because iterators
    // will implicitly transform into const_iterators.
    auto operator==(iterator_base<true> const&) -> bool = default;
};

After that, all you need is:

using iterator       = iterator_base<false>;
using const_iterator = iterator_base<true>;

And everything should just work.

There are, of course, a lot of things missing from your iterators. You don’t specify the iterator category, for example, which, for a list, should be bidirectional. That also means you need operator--.

(Note: as of C++20, you don’t need the typedefs. std::iterator_traits is smart enough to figure out value_type, and the iterator category, and so on. But, if you’re stuck in C++11, you need to provide absolutely everything.)

//template<typename T>
//auto List<T>::insert(List::const_iterator &pos, value_type value) -> iterator {
//    auto currentNode = pos.ptr;
//    if (currentNode == nullptr) {
//        // Iterator(end)
//        push_back(value);
//        return iterator(rear);
//    } else if (pos == cbegin()) {
//        push_front(value);
//        return iterator(head);
//    } else {
//        auto newNode = new node_type(value, currentNode->previous, currentNode);
//        newNode->previous->next = newNode;
//        newNode->next->previous = newNode;
//        ++count;
//        return iterator(newNode);
//    }
//}

This bit was commented out, so I suspect you were having trouble with it. I can guess why. When you do auto currentNode = pos.ptr;, currentNode will be a const node_type*. Then when you do new node_type(value, currentNode->previous, currentNode); you are trying to assign it to a (non-const) node_type*… which the compiler will not allow.

The solution is simple:

auto currentNode = const_cast<node_type*>(pos.ptr);

This will strip away the const.

Now, normally, using const_cast to strip away const is a terrible idea, and you should never do it… but… you know 100% for sure it is safe here, because:

1. *this is not const. You know this because you are in a non-const member function.
2. Therefore, whatever node pos is pointing to, it must be a non-const node. Somehow a const got added along the way, but ultimately, the node pointed to must be non-const, because *this is not const.

So even though you somehow got stuck with a const_iterator, you know for certain that the list itself is not const. So you could force-cast the const_iterator to an iterator and go from there. Or you could force-cast the const pointer to a non-const pointer, like I did, which is much easier and more direct.

Let me wrap up by answering the questions:

Questions

Is the design ok?

Sure. I mean, it’s mostly based on std::list, which was designed by experts, so it’s hard to go wrong.

Did I miss any bugs?

Yes. Because you have not implemented the special ops (violating the rule of 5), you have serious bugs. This class would likely crash the program, if you tried to copy or move it in any way. (You didn’t notice, because your tests did not try any copying or moving.)

Anything else?

Yes, you should look carefully at the functions in a list and figure out which ones are fundamental. That is, which ones are the basis for all other functions.

For lists, emplace() is a fundamental function. With just:

template <typename... Args>
auto emplace(const_iterator pos, Args&&... args) -> iterator;

you could write:

// All constructor overloads
list(size_type n);
list(size_type n, T const& value);
list(std::initializer_list<T> il);
template <std::input_iterator It>
list(It first, It last);
template <std::input_range R>
list(std::from_range_t, R&&);

auto insert(const_iterator pos, T const& value) -> iterator;
auto insert(const_iterator pos, T&& value) -> iterator;
auto insert(const_iterator pos, size_type n);
auto insert(const_iterator pos, std::initializer_list<T> il);
template <std::input_iterator It>
insert(const_iterator pos, It first, It last);

auto push_front(T const& value) -> void;
auto push_front(T&& value) -> void;

auto push_back(T const& value) -> void;
auto push_back(T&& value) -> void;

template <typename... Args>
auto emplace_front(Args&&... args) -> reference;

template <typename... Args>
auto emplace_back(Args&&... args) -> reference;

template <std::input_range R>
auto prepend_range(R&&) -> void;

template <std::input_range R>
auto append_range(R&&) -> void;

template <std::input_range R>
auto insert_range(const_iterator pos, R&&) -> iterator;

Let me say again: all of the functions above could be written with just emplace() and maybe a loop, and most would be one-liners.

If you also add erase(), another fundamental function, you pretty much have the entire interace of std::list.

Now, of course, you can write all the functions in that list with just emplace() and a loop… but for practical purposes, some of them should probably be customized. (For example, emplacing multiple items one at a time is silly; and handling failure in that case is difficult.)

Also, as I mentioned, it is possible to write iterator and const_iterator as a single class, and use a non-type bool template parameter to choose the const-ness. Doing that not only eliminates a bunch of code, it also removes the need for a lot of forward-declaring.

Other than all that, looks good!