How do I update this old C++ doubly linked list code to C++11?

Question

I have the following code written in what would now be called C++98

It implements a doubly linked list, and I was considering updating it to C++11, but I had the following concerns:

it would seem that using std::unique_ptr makes sense, but there still needs to be other pointers "sharing" the unique_ptr. I.e if nxt is a unique_ptr, what do I do with prv and iterator::it?
it would seem that it should take an allocator as a template paraemter, but it will be an allocator of type T, not LLNode?
are there any traits, that need to be "registered"?
if move semantics are used, what methods should be defined e.g. operator=() && etc.?
what undefined behavior (if any) needs to be corrected?
what am i not concerned about that I should be?

An accepted answer would briefly discuss the concerns, and then reimplement in C++11 (admittedly, it's a lot of code, but most will be just cut and paste)

A good answer will briefly discuss the concerns, and then reimplement in C++11 the minimal amount to illustrate how to apply those concepts

using standard algorythms would make sense, using a standard container defeats the purpose

appropriate use of C++11 features is encouraged where it makes sense e.g. foreach as opposed to just using lambdas because it will work

This is not homework

The code:

template <class T>
class LinkedList
{
    class LLNode
    {
    public:
        LLNode() // For Sentinel (requires that T has a default constructor)
        {}  // set prv/nxt directly
        explicit LLNode(const T& x) : data(x) // For normal nodes
        {}  // set prv/nxt directly
        T& get_data() const
        {
            return const_cast<T&>(data);
        }
        LLNode * prv;
        LLNode * nxt;
    private:
        T data;
    };
public:
    class iterator
    {
    public:
        iterator(const LinkedList * p, LLNode * i)
                       : parent(const_cast<LinkedList *>(p)), it(i)
        {}
        iterator& operator ++() // pre
        {
            it = it->nxt;
            return *this;
        }
        iterator operator ++(int) // post
        {
            iterator ret=*this;
            it = it->nxt;
            return ret;
        }
        iterator& operator --() // pre
        {
            it = it->prv;
            return *this;
        }
        iterator operator --(int) //post
        {
            iterator ret=*this;
            it = it->prv;
            return ret;
        }
        T& operator *() const
        {
            return it->get_data();
        }
        T * operator ->() const
        {
            return &(it->get_data());
        }
        bool operator ==(const iterator& rhs) const
        {
            return it == rhs.it;
        }
        bool operator !=(const iterator& rhs) const
        {
            return it != rhs.it;
        }
        void erase()
        {
            parent->remove(it);
        }
        void insert_after(const T& x)
        {
            LLNode * add= new LLNode(x);
            parent->insert(it, add);
        }
        void insert_before(const T& x)
        {
            LLNode * add= new LLNode(x);
            parent->insert(it->prv, add);
        }
    private:
        LinkedList * parent;
        LLNode * it;
    };
    // Linked List class definition
    LinkedList()
    {
        init();
    }
    LinkedList(const LinkedList& rhs)
    {
        init();
        cp(rhs);
    }
    ~LinkedList()
    {
        rm();
    }
    LinkedList operator =(const LinkedList& rhs)
    {
        if (this != &rhs)
        {
            rm();
            cp(rhs);
        }
        return *this;
    }
    iterator begin() const
    {
        return iterator(this, sentinel.nxt);
    }
    iterator rbegin() const
    {
        return iterator(this, sentinel.prv);
    }
    iterator end() const
    {
        return iterator(this, const_cast<LLNode *>(&sentinel));
    }
    T& get_first() const  // illegal if is_empty() is true
    {
        return sentinel.nxt->get_data();
    }
    T& get_last() const // illegal if is_empty() is true
    {
        return sentinel.prv->get_data();
    }
    size_t size() const
    {
        return count;
    }
    bool is_empty() const
    {
        return count==0;
    }
    void insert_first(const T& x)
    {
        LLNode * add= new LLNode(x);
        insert(&sentinel, add);
    }
    void insert_last(const T& x)
    {
        LLNode * add= new LLNode(x);
        insert(sentinel.prv, add);
    }
    void erase_first() // illegal if is_empty() is true
    {
        remove(sentinel.nxt);
    }
    void erase_last() // illegal if is_empty() is true
    {
        remove(sentinel.prv);
    }
private:
    void insert(LLNode * before, LLNode * added)
    {
        LLNode * after=before->nxt;
        added->prv=before;
        added->nxt=after;
        before->nxt=added;
        after->prv=added;
        ++count;
    }
    void remove(LLNode * node) // illegal if is_empty() is true
    {
        node->prv->nxt=node->nxt;
        node->nxt->prv=node->prv;
        delete node;
        --count;
    }
    void cp(const LinkedList& rhs)
    {
        for (iterator i=rhs.begin(); i != rhs.end(); ++i)
        {
            insert_last(*i);
        }
    }
    void rm()
    {
        LLNode * run=sentinel.nxt;
        while (run != &sentinel)
        {
            LLNode * dead=run;
            run=run->nxt;
            delete dead;
        }
    }
    void init()
    {
        count=0;
        sentinel.nxt = sentinel.prv = &sentinel; // setup circular ref
    }
    LLNode sentinel;
    size_t count;
};

EDIT - C++11 attempt based on Mooing Duck's answer :

template <class T, class ALLOC=std::allocator<T> >
class LinkedList
{
        struct LLNode
        {
                LLNode * prv;
                LLNode * nxt;
                T& get_data() { return data; }
                T data;
        };
public:
        class iterator
        {
        public:
                using difference_type = ptrdiff_t;
                using value_type = T;
                using reference = T&;
                using pointer = T*;
                using iterator_category = std::bidirectional_iterator_tag;

                iterator(LinkedList * p, LLNode * i) : parent(p), it(i)
                {}
                iterator& operator ++() // pre
                {
                        it = it->nxt;
                        return *this;
                }
                iterator operator ++(int) // post
                {
                        iterator ret=*this;
                        it = it->nxt;
                        return ret;
                }
                iterator& operator --() // pre
                {
                        it = it->prv;
                        return *this;
                }
                iterator operator --(int) //post
                {
                        iterator ret=*this;
                        it = it->prv;
                        return ret;
                }
                const T& operator *() const
                {
                        return it->get_data();
                }
                T& operator *()
                {
                        return it->get_data();
                }
                const T * operator ->() const
                {
                        return &(it->get_data());
                }
                T * operator ->()
                {
                        return &(it->get_data());
                }
                bool operator ==(const iterator& rhs) const
                {
                        return it == rhs.it;
                }
                bool operator !=(const iterator& rhs) const
                {
                        return it != rhs.it;
                }
                void erase()
                {
                        parent->remove(it);
                }
                void insert_after(T& x)
                {
                        auto add=parent->alloc_node(x);
                        parent->insert(it->nxt, add);
                }
                void insert_before(T& x)
                {
                        auto add=parent->alloc_node(x);
                        parent->insert(it, add);
                }
        private:
                LinkedList * parent;
                LLNode * it;
        };
        class const_iterator
        {
        public:
                using difference_type = ptrdiff_t;
                using value_type = const T;
                using reference = const T&;
                using pointer = const T*;
                using iterator_category = std::bidirectional_iterator_tag;

                const_iterator(const LinkedList * p, const LLNode * i) : parent(p),
                        it(const_cast<LLNode *>(i))
                {}
                const_iterator(iterator& cvt) : parent(cvt.parent), it(cvt.it)
                {}
                const_iterator& operator ++() // pre
                {
                        it = it->nxt;
                        return *this;
                }
                const_iterator operator ++(int) // post
                {
                        const_iterator ret=*this;
                        it = it->nxt;
                        return ret;
                }
                const_iterator& operator --() // pre
                {
                        it = it->prv;
                        return *this;
                }
                const_iterator operator --(int) //post
                {
                        const_iterator ret=*this;
                        it = it->prv;
                        return ret;
                }
                const T& operator *() const
                {
                        return it->get_data();
                }
                const T * operator ->() const
                {
                        return &(it->get_data());
                }
                bool operator ==(const const_iterator& rhs) const
                {
                        return it == rhs.it;
                }
                bool operator !=(const const_iterator& rhs) const
                {
                        return it != rhs.it;
                }
        private:
                const LinkedList * parent;
                LLNode * it;
        };

        using my_alloc=typename
             std::allocator_traits<ALLOC>::template rebind_alloc<LLNode>;

        using my_traits=typename
             std::allocator_traits<ALLOC>::template rebind_traits<LLNode>;

        // Linked List class definition
        LinkedList(const ALLOC& alloc = ALLOC() ) : mem(alloc)
        {
                init();
        }
        LinkedList(const LinkedList& rhs) : mem(rhs.mem)
        {
                init();
                cp(rhs);
        }
        LinkedList(LinkedList&& rhs) : mem(rhs.mem) // Move
        {
                init();
                shallow_cp(rhs);

        }
        ~LinkedList()
        {
                rm();
        }
        LinkedList operator =(const LinkedList& rhs)
        {
                if (this != &rhs)
                {
                        rm();
                        cp(rhs);
                }
                return *this;
        }
        LinkedList operator =(LinkedList&& rhs) // Move
        {
                if (this != &rhs)
                {
                        rm();
                        shallow_cp(rhs);
                }
                return *this;
        }
        const_iterator begin() const
        {
                return const_iterator(this, sentinel.nxt);
        }
        iterator begin()
        {
                return iterator(this, sentinel.nxt);
        }
        const_iterator rbegin() const
        {
                return const_iterator(this, sentinel.prv);
        }
        iterator rbegin()
        {
                return iterator(this, sentinel.prv);
        }
        const_iterator end() const
        {
                return const_iterator(this, &sentinel);
        }
        iterator end()
        {
                return iterator(this, &sentinel);
        }
        T& front()  // illegal if is_empty() is true
        {
                return sentinel.nxt->get_data();
        }
        T& back() // illegal if is_empty() is true
        {
                return sentinel.prv->get_data();
        }
        size_t size() const
        {
                return count;
        }
        bool is_empty() const
        {
                return count==0;
        }
        void insert_first(const T& x)
        {
                LLNode * add=alloc_node(x);
                insert(&sentinel->nxt, add);
        }
        void insert_last(const T& x)
        {
                LLNode * add=alloc_node(x);
                insert(&sentinel, add);
        }
        void erase_first() // illegal if is_empty() is true
        {
                remove(sentinel.nxt);
        }
        void erase_last() // illegal if is_empty() is true
        {
                remove(sentinel.prv);
        }
private:
        LLNode * alloc_node(const T& x)
        {
                auto ret = my_traits::allocate(mem,1);
                my_traits::construct(mem, &(ret->data), x);
                return ret;
        }
        void unalloc_node(LLNode * dead)
        {
                my_traits::deallocate(mem, dead, 1);
        }
        void insert(LLNode * after, LLNode * added)
        {
                LLNode * before=after->prv;
                added->prv=before;
                added->nxt=after;
                before->nxt=added;
                after->prv=added;
                ++count;
        }
        void remove(LLNode * node) // illegal if is_empty() is true
        {
                node->prv->nxt=node->nxt;
                node->nxt->prv=node->prv;
                unalloc_node(node);
                --count;
        }
        void cp(const LinkedList& rhs)
        {
                mem = rhs.mem;
                for (const_iterator i=rhs.begin(); i != rhs.end(); ++i)
                {
                        insert_last(*i);
                }
        }
        void shallow_cp(LinkedList& rhs)
        {
                if (rhs.count)
                {
                        count=rhs.count;
                        sentinel=rhs.sentinel; // shallow copy

                        // fix the links to the old sentinel

                        sentinel.nxt.prv=&sentinel;
                        sentinel.prv.nxt=&sentinel;
                        rhs.init();
                }
        }

        void rm()
        {
                LLNode * run=sentinel.nxt;
                while (run != &sentinel)
                {
                        LLNode * dead=run;
                        run=run->nxt;
                        unalloc_node(dead);
                }
        }
        void init()
        {
                count=0;
                sentinel.nxt = sentinel.prv = &sentinel; // setup circular ref
        }
        LLNode sentinel;
        size_t count;
        my_alloc mem;
};

Is anything missing/wrong?

*"This is not homework"* -- Sure looks like it. Not for you, but for us. — Benjamin Lindley, Jan 23 '14 at 01:33
@Yuushi then how does that explain the use of allocators or unique_ptr — Glenn Teitelbaum, Jan 23 '14 at 01:36
I suggest you try to update the code to c++ 11 by yourself, and then ask for advice. — dieram3, Jan 23 '14 at 01:36
@dieram3 If I posted it using allocator and unique_ptr everyplace, how would that help, I listed concerns, applying them to the code is trivial, if a partial code snippet can answer great — Glenn Teitelbaum, Jan 23 '14 at 01:41
programmers are `lazy`. The `task` you have described sounds a lot like... well a task, and requires one to actually `read your code` to try to `understand your logic` and finally come up with a c++11 design of that code. Please do as @dieram3 suggested and actually show some progress before posting code here for help. — smac89, Jan 23 '14 at 01:56

score 2 · Accepted Answer · edited May 23 '17 at 12:03

it would seem that using std::unique_ptr makes sense, but there still needs to be other pointers "sharing" the unique_ptr. I.e if nxt is a unique_ptr, what do I do with prv and iterator::it?

Don't. (1) It makes various internal algorithms trickier to perform without accidentally deleting a node, and (2) unique_ptr stores the deleter, in your case that's either (A) a copy of the iterator, or (B) a pointer to the iterator. Either one is a waste of space. The container should store the allocator, and the container should handle deletions.

it would seem that it should take an allocator as a template paraemter, but it will be an allocator of type T, not LLNode?

Containers take an allocator of type T, though all of them use a rebound type internally. The standard is that allocators to containers take type T, and that way every std::vector<T, allocator<?>> matches every other. Also, outsiders should not be able to access LLNode. You'd probably store a given_allocator<LLNode> internally though. That's why we have rebinding.

are there any traits, that need to be "registered"?

For containers, no. There are interfaces to match, but those are relatively obvious.

Yes, your iterators are supposed to register traits, but that's easily done by merely adding five typedefs at the front.

typedef ptrdiff_t difference_type; //usually ptrdif_t
typedef T value_type; //usually T
typedef T& reference; //usually T&
typedef T* pointer; //usually T*
typedef std::bidirectional_iterator_tag iterator_category;

if move semantics are used, what methods should be defined e.g. operator=() && etc.?

Obviously the container should be move constructable and move assignable if it makes sense, which it does 99.99% of the time. Even std::array has move operators. Also decide which member functions should support move-only-T (insert range via iterators, but not insert range + count), and which member functions support any T (emplace one).

what undefined behavior (if any) needs to be corrected?

It would appear that your insert(iterator, data) inserts the data after the iterator, when the standard is to insert before the iterator. Your way makes it impossible to add data to the beginning, and makes it possible to add data after the after-the-end.
Your iterators have but do not need remove and insert functions. I wouldn't have mentioned it, but in this case they require the iterators to be twice as big as needed. I'd offer a tentative suggestion to remove them, but only tentative. That's a small penalty, and potentially a useful feature.
Your operator = deallocates everything and then reallocates. It might be handy to simply copy element by element skipping that when possible. Trickier to code though.
You're missing a constructor that constructs from a pair of iterators.
Your iterators allow mutating of data from const containers. THIS ONE IS BIG
get_first and get_last are normally called front and back.

what am i not concerned about that I should be?

The big one that everyone overlooks is exception safety. Your code is exception safe, but that appears to be because your code is amazingly simple, and you skipped all of the "hard" parts :P

For more information review these:
Writing your own STL Container
How to implement an STL-style iterator and avoid common pitfalls?

Edit for your C++11 followup:

missing:

template LLNode(U&& x) //or, one T&& and one const T&
LinkedList(std::initializer_list x)
T& LLNode::get_data() const //important, your code doesn't even compile
T* iterator::operator->() const //important
const_iterator cbegin() const
const_iterator cend() const
const T& front() const //important
const T& back() const //important
template void assign(iter, iter);
void assign(std::initializer_list);
void swap(const X&);

Incorrect:

insert_* should probably take a U&& and use std::forward<U>(x). Variadic templates would be better.
no iterator pair constructor.
memory leak in alloc_node, and you should be constructing a LLNode, you have uninitialized prv/nxt.
unalloc_node never destroys, only deallocates, leading to a memory leak

Missing but pretty unimportant

typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
reverse_iterator rbegin(); //optional
const_reverse_iterator rbegin() const;
const_reverse_iterator crbegin() const;
reverse_iterator rend(); //optional
const_reverse_iterator rend() const;
const_reverse_iterator crend() const;

Optional:

not sure why my_alloc and my_traits and they're identical.
inherit privately from the allocator. It's a little wierd, but commonly saves you 8 bytes.

@GlennTeitelbaum: You got most of them. I added another batch of suggestions. And SO is not the correct forum for doing this. — Mooing Duck, Jan 24 '14 at 06:02

How do I update this old C++ doubly linked list code to C++11?

1 Answers1

Edit for your C++11 followup: