linked list implementation attempt

Question

The following is my attempt at writing a linked list that attempts to emulate the behavior of std::list. Any feedback would be appreciated.

#pragma once

#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <stdexcept>
#include <utility>

//a list is composed of links that contain pointers to previous
//and successive links
template<typename T>
struct Link {
    T val;
    Link<T>* prev;
    Link<T>* succ;

    void swap(Link* other)
    {
        using std::swap;
        swap(val, other->val);
        std::swap(prev, other->prev);
        std::swap(succ, other->succ);
    }

    Link(const T& v = T{}, Link<T>* p = nullptr, Link<T>* s = nullptr)
        :val{ v }, prev{ p }, succ{ s } {
    }
};

template<typename T>
void hook(Link<T>* a, Link<T>* b)
{
    a->succ = b;
    b->prev = a;
}

template<typename T>
struct List_iterator {
private:
    //mutable so we can increment a const_iterator
    mutable Link<T>* curr;
public:
    //List is a friend so that it can access curr without curr being public
    template<typename T>
    friend class List;

    explicit List_iterator(Link<T>* link) :curr{ link } {}

    T& operator*() { return curr->val; }
    const T& operator*() const { return curr->val; }

    Link<T>* operator->() { return curr; }
    Link<T>* const operator->() const { return curr; }

    //increment and decrement operators are overloaded so that
    //pre- and post- increments and decrements are possible

    List_iterator& operator++() 
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        curr = curr->succ; return *this;
    }

    List_iterator operator++(int)
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        auto temp = *this;
        operator++();
        return temp;
    }

    const List_iterator& operator++() const
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        curr = curr->succ; return *this;
    }

    const List_iterator operator++(int) const
    {
        if (!curr) throw std::runtime_error("Cannot increment null iterator\n");
        auto temp = *this;
        operator++();
        return temp;
    }

    List_iterator& operator--() 
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        curr = curr->prev; return *this;
    }

    List_iterator operator--(int)
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        auto temp = *this;
        operator--();
        return temp;
    }

    const List_iterator& operator--() const
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        curr = curr->prev; return *this;
    }

    const List_iterator operator--(int) const
    {
        if (!curr) throw std::runtime_error("Cannot decrement null iterator\n");
        auto temp = *this;
        operator--();
        return temp;
    }

    //had to define an advance b/c std::advance wouldn't work
    //even after adding an iterator tag
    void advance(std::size_t n) const;

    bool operator==(const List_iterator& other) const  { return curr == other.curr; }
    bool operator!=(const List_iterator& other) const  { return curr != other.curr; }

    explicit operator bool() const { return curr; }
};

template<typename T>
void List_iterator<T>::advance(std::size_t n) const
{
    while (n--) operator++(); 
}

template<typename T>
class List;

template<typename T>
void merge(List<T>& sub_a, List<T>& sub_b, List<T>& list);

template<typename T>
void sort_helper(List<T>& list);

template<typename T>
class List {
    Link<T>* first;
    Link<T>* last;
    std::size_t sz;

    void cleanup();
    List_iterator<T> insert_first_element(Link<T>* new_link);
    void insert_back_unchecked(Link<T>* new_link);
    void insert_front_unchecked(Link<T>* new_link);
    List_iterator<T> insert_unchecked(const List_iterator<T> pos, Link<T>* new_link);
public:
    using size_type = std::size_t;
    using iterator = List_iterator<T>;
    using const_iterator = const List_iterator<T>;

    //all ctors must call default ctor first so conditions 
    //are set for insertion and deletion functions
    List() : first{ new Link<T>{} }, last{ first }, sz{ 0 } {}

    List(std::initializer_list<T>lst)
        :List(lst.begin(), lst.end()) {}

    //Initialize list w/ values in range [f, l)
    template<typename In>
    List(In f, In l);

    List(const List& other)
        :List(other.begin(), other.end()) {}
    List& operator=(const List& other);

    List(List&& other) noexcept;
    List& operator=(List&& other) noexcept;

    ~List() { cleanup(); }

    bool empty() const noexcept { return sz == 0; }

    void clear() noexcept
    {
        if (sz == 0) return;
        List temp;
        swap(temp);
    }

    void swap(List& other) noexcept
    {
        std::swap(first, other.first);
        std::swap(last, other.last);
        std::swap(sz, other.sz);
    }

    size_type size() const noexcept { return sz; }
    iterator begin() noexcept { return iterator(first); }
    iterator end() noexcept { return iterator(last); }
    const_iterator begin() const noexcept { return const_iterator(first); }
    const_iterator end() const noexcept { return const_iterator(last); }
    const_iterator cbegin() const noexcept { return const_iterator(first); }
    const_iterator cend() const noexcept { return const_iterator(last); }
    iterator insert(const_iterator p, const T& v);
    iterator erase(iterator p);
    T& front() { return first->val; }
    T& back() { return last->prev->val; }
    const T& front() const { return first->val; }
    const T& back() const { return last->prev->val; }
    void push_back(const T& v);
    void push_front(const T& v);

    template<typename... U>
    iterator emplace(const_iterator pos, U&&... args);

    template<typename... U>
    void emplace_back(U&&... args);

    template<typename... U>
    void emplace_front(U&&... args);
    void resize(size_type new_size, T val = T{});
    //transfer elements from one list to another
    void splice(const_iterator pos, List& other);
    void splice(const_iterator pos, List&& other) { splice(pos, other); }
    void reverse() noexcept;
    //remove consecutive duplicate elements
    void unique();

    bool operator==(const List& other);
    bool operator!=(const List& other) { return !(*this == other); }

    void remove(const T& value);

    template<typename Pred>
    void remove_if(Pred pred);

    //uses a merge sort
    void sort() { sort_helper(*this); }
};

template<typename T>
template<typename In>
List<T>::List(In f, In l)
    :List()
{
    while (f != l) { push_back(*f++); }
}

template<typename T>
typename List<T> & List<T>::operator=(const List & other)
{
    List<T> temp{ other };
    swap(temp);
    return *this;
}

template<typename T>
List<T>::List(List && other) noexcept
    :first{ other.first }, last{ other.last }, sz{ other.sz }
{
    other.first = other.last = nullptr;
    other.sz = 0;
}

template<typename T>
typename List<T> & List<T>::operator=(List && other) noexcept
{
    swap(other);
    return *this;
}

template<typename T>
void List<T>::cleanup()
{
    Link<T>* link;
    while (first)
    {
        link = first;
        first = first->succ;
        delete link;
    }
}

template<typename T>
typename List<T>::iterator List<T>::insert_first_element(Link<T>* new_link)
{
    first = new_link;
    hook(new_link, last);
    ++sz;
    return iterator(first);
}

template<typename T>
void List<T>::insert_back_unchecked(Link<T>* new_link)
{
    hook(last->prev, new_link);
    hook(new_link, last);
    ++sz;
}

template<typename T>
void List<T>::insert_front_unchecked(Link<T>* new_link)
{
    hook(new_link, first);
    first = new_link;
    ++sz;
}

template<typename T>
List_iterator<T> List<T>::insert_unchecked(const_iterator pos, Link<T>* new_link)
{
    if (pos == begin()) insert_front_unchecked(new_link);
    else {
        hook(pos.curr->prev, new_link);
        hook(new_link, pos.curr);
        ++sz;
    }
    return iterator(new_link);
}

template<typename T>
void sort_helper(List<T> & list)
{
    if (list.size() < 2) return;

    auto iter_split = list.begin();
    iter_split.advance(list.size() / 2);
    List<T> a{ list.begin(), iter_split };
    List<T> b{ iter_split, list.end() };
    sort_helper(a);
    sort_helper(b);
    merge(a, b, list);
}

//inserts a Link with value v before p
//undefined behaviour if an invalid iterator is specified
template<typename T>
inline typename List<T>::iterator List<T>::insert(const_iterator p, const T & v)
{
    Link<T>* new_link = new Link<T>{ v };
    if (empty()) { return insert_first_element(new_link); }
    else return insert_unchecked(p, new_link);
}

template<typename T>
typename List<T>::iterator List<T>::erase(iterator p)
{
    if (empty() || p == end()) return end();

    auto ret_val = p.curr->succ;
    if (p.curr->prev) hook(p.curr->prev, ret_val);
    else {
        first = ret_val;
        first->prev = nullptr;
    }

    delete p.curr;
    --sz;
    return iterator(ret_val);
}

template<typename T>
inline void List<T>::push_back(const T & v)
{
    Link<T>* new_link = new Link<T>{ v };
    if (empty()) insert_first_element(new_link);
    else insert_back_unchecked(new_link);
}

template<typename T>
inline void List<T>::push_front(const T & v)
{
    Link<T>* new_link = new Link<T>{ v };
    if (empty()) insert_first_element(new_link);
    else insert_front_unchecked(new_link);
}

template<typename T>
void List<T>::resize(size_type new_size, T val)
{
    //store old sz b/c erase will decrement sz so the loop will execute less times than it should
    const auto old_sz = sz;
    for (auto i = new_size; i < old_sz; ++i) erase(--end());
    for (auto i = sz; i < new_size; ++i) push_back(val);
}

template<typename T>
void List<T>::splice(const_iterator pos, List & other)
{
    if (other.sz == 0) return;
    if (pos.curr->prev) hook(pos.curr->prev, other.first);
    else first = other.first;
    hook(other.last->prev, pos.curr);
    other.first = other.last = nullptr;
    sz += other.sz;
    other.sz = 0;
}

template<typename T>
void List<T>::reverse() noexcept
{
    using std::swap;
    auto b = begin();
    auto e = end();
    while (b != e && b != --e) { swap(*b++, *e); }
}

template<typename T>
void List<T>::unique()
{
    auto iter = end();
    while (iter != begin())
    {
        if (*iter == iter.curr->prev->val) {
            iter = iterator(erase(iter).curr->prev);
        }
        else --iter;
    }
}

template<typename T>
bool List<T>::operator==(const List & other)
{
    if (sz != other.sz) return false;
    auto m_begin = begin();
    auto o_begin = other.begin();
    while (m_begin != end())
    {
        if (*m_begin++ != *o_begin++) return false;
    }
    return true;
}

template<typename T>
void List<T>::remove(const T& value)
{
    auto iter = begin();
    while (iter != end())
    {
        if (*iter == value) iter = erase(iter);
        else ++iter;
    }
}

template<typename T>
void merge(List<T> & a, List<T> & b, List<T> & list)
{
    auto a_iter = a.begin();
    auto b_iter = b.begin();
    auto list_iter = list.begin();
    while (a_iter != a.end() && b_iter != b.end())
    {
        if (*a_iter <= *b_iter)
        {
            *list_iter = *a_iter;
            ++a_iter;
        }
        else
        {
            *list_iter = *b_iter;
            ++b_iter;
        }
        ++list_iter;
    }
    while (a_iter != a.end()) { *list_iter++ = *a_iter++; }
    while (b_iter != b.end()) { *list_iter++ = *b_iter++; }
}

template<typename T>
template<typename ...U>
inline typename List<T>::iterator List<T>::emplace(const_iterator pos, U && ...args)
{
    Link<T>* new_link = new Link<T>{ T( std::forward<U>(args)... ), pos.curr->prev, pos.curr };
    if (empty()) { return insert_first_element(new_link); }
    else return insert_unchecked(pos, new_link);
}

template<typename T>
template<typename ...U>
inline void List<T>::emplace_back(U && ...args)
{
    Link<T>* new_link = new Link<T>{ T( std::forward<U>(args)...) };
    if (empty()) insert_first_element(new_link);
    else insert_back_unchecked(new_link);
}

template<typename T>
template<typename ...U>
inline void List<T>::emplace_front(U && ...args)
{
    Link<T>* new_link = new Link<T>{ T(std::forward<U>(args)...) };
    if (empty()) insert_first_element(new_link);
    else insert_front_unchecked(new_link);
}

template<typename T>
template<typename Pred>
void List<T>::remove_if(Pred pred)
{
    auto iter = begin();
    while (iter != end())
    {
        if (pred(*iter)) iter = erase(iter);
        else ++iter;
    }
}

nwp · Accepted Answer · 2018-05-12 10:28:06Z

~~Some of your member functions should not exist.~~ You don't want n algorithms and m containers to result in n*m implementations, because that number becomes rather big. Also people tend to forget to add all algorithms to their containers, especially when new ones appear. Instead you are supposed to implement algorithms and containers separately to only need n+m implementations. This ~~applies~~ does not apply to unique, remove and remove_if ~~that have a non-member std function std::unique, std::remove and std::remove_if~~ because the member functions are more efficient than the free standing functions. Also std::remove only moves elements while std::list::remove actually erases them.
Unfortunately it doesn't apply to sort because std::sort requires random access iterators which you don't have.
Your sort implementation seems to make a lot of copies. If you can't find a clever efficient way you can just create a std::vector<T*> and std::sort that and then apply the positioning to your list.
I would expect a linked list to work with move-only types such as std::unique_ptr<int>, but it doesn't because you copy Ts in various functions.
I am getting compilation errors with both gcc and clang. It looks like you only tested with VS's compiler which tends to be a bit lenient.
Avoid cleanup functions. That is what the destructor is for. Also you already have clear.
Your List_iterator does bad things when const. For example you can do
```
const List<int> l{1, 2, 3};
auto it = l.begin();
*it = 42;
```
That last line should not compile, but it does. Blame the mutable that should not be there. Unfortunately you need to write 2 classes to get this right in C++, typically List_iterator and Const_list_iterator.
Looking at the list of things required to make a bidirectional iterator it seems like you are missing some, for example everything around std::iterator_traits which also explains
```
//had to define an advance b/c std::advance wouldn't work
//even after adding an iterator tag
```
It is a bit annoying to do all those things from the linked documentation, especially when you realize that you need to follow more links because it says "The type It satisfies ForwardIterator" which has yet another list of requirements and that one links to more requirements. On the upside once you did all of it the standard algorithms work with your iterator and you can delete a bit of code. Also algorithms from other libraries like boost tend to work when you have standard iterators.
You can initialize members in the class declaration, for example
```
template<class T>
class List {
    Link<T>* first{nullptr};
    Link<T>* last{nullptr};
    std::size_t sz = 0;
}
```
If your constructor initializes members the class initialization is treated as not existing (so no loss in performance for double-initializing), but if you forget or leave it out you get sane defaults.
I would like to see Link and sort_helper in the private part of List for encapsulation. If you let users access those types they will use them which I think is not intended.

Thanks for the feedback. In terms of your first point, I'm a bit confused because I only defined member functions that were also in std::list. Also, the non-member std versions of these functions don't actually affect the size of the container, they simply shift elements. I would appreciate some clarification. And thanks for the iterator help. After a bit of extra googling I realized I needed more than just the iterator tag for std functions like std::advance to work. — Equilibrium
– Equilibrium, Commented May 11, 2018 at 22:06
Also, I made sort_helper a non-member because it didn't need access to private members inside the list. Would there be a way to keep it as a non-member while shielding it from users? — Equilibrium
– Equilibrium, Commented May 11, 2018 at 22:12
@Equilibrium You would normally not try to shield your class from internal implementation details and just make sort_helper a private member. You could alternatively make it a private member of some other (otherwise empty) class and make List a friend, but I would not consider the resulting confusion worth the added safety. I don't know why std::list::remove and the other mentioned functions exist. My guess is historic reasons. I don't see a technical reason why they should exist. — nwp
– nwp, Commented May 11, 2018 at 22:51
@Equilibrium I got some insight into why std::list::remove exists. While confusing it makes sense from a performance point of view to have a special member function and not use the erase-remove idiom. So the first point, while generally true, does not apply to the mentioned functions. — nwp
– nwp, Commented May 12, 2018 at 10:23

JDługosz · Accepted Answer · 2018-05-10 23:33:52Z

#pragma once is OK with me. Some people might flag it for review; I note that if it is for publication to unknown users, you should add (properly-made) guards too.

Link<T>* prev;
Link<T>* succ;

One of those should be a unique_ptr. I just saw a presentation from a conference video that remarked that a major standard library implementation had a memory leak (in vector I think) in case an exception was thrown during construction or assignment, sometimes. So don’t revert to old-style primitive code just because you are writing a collection!

List() : first{ new Link<T>{} }, last{ first }, sz{ 0 } {}

and here is where this will protect you from this very bug. You are not deleting the node in the case where your constructor throws an exception. In general, other things in your member-init list can throw, not just the function body!

So always have owning semantics on resources, even if you don’t rely on that for normal usage.

Link<T>* new_link = new Link<T>{ T( std::forward<U>(args)...) };

That is, you can write

auto new_link = make_unique<T>{ T( std::forward<U>(args)...) };
    ⋮
put_it_where_it_belongs (new_link.release());

and you are protected against memory leaks when the Link constructor (and its payload’s constructor contained within) throws, and for any exceptions that occur up to when you discharge responsibility for keeping it.

You put a lot of work into writing the iterator from scratch. Use Boost.Iterator to do most of the work for you, instead. This can be a façade around the pointer type, and you change only the category (to bidirectional) and write simple next and prev functions, and how to unbox the data from the node. All the various members and variations will be done for you automatically.

void swap(Link* other)

Swapping a Link with a Link* is strange. You should make that parameter a Link& instead. And mark it as noexcept if T has a no-throw swap.

    if (!curr) throw std::runtime_error("Cannot increment null iterator\n");

This identical line is present in many of the functions. Take a look via Compiler Explorer or your debug asm window: the throw generates a lot of code. Contrast that to the main path you want inlined, which is a simple deref and assignment.

So, make a separate raise_error member, and make it not-inline. Call that from the inlined functions. Also can use compiler-specific features to mark the test as expected vs unexpected. (Microsoft's distribution of the GSL includes a GSL_LIKELY macro for cross-platform)

All and all, it looks like good code, well-written. You know about current features and style, and you seem to have made a through catalog of all the members and features, not just the basics.

Just get rid of naked news, to do better than the common implementations!

Thanks for the response. I never considered using unique_ptr for this, so I'll definitely modify the links to use them. I also really need to get into Boost, it seems like it would have simplified this project a lot. — Equilibrium
– Equilibrium, Commented May 11, 2018 at 22:09

Stack Exchange Network

linked list implementation attempt

2 Answers 2

You must log in to answer this question.

Hot Network Questions

linked list implementation attempt

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions