4
\$\begingroup\$

Based on the previous question, I have utilized most of the answers.

  • The code is now fully compatible with the STL by implementing forward iterators to store and retrieve values.
  • Using raw pointers instead of smart pointers

The code is working as expected. I would like to know if my implementation is correct and how I can improve it further.

#include <iostream>
#include <iterator>
#include <algorithm>

template<typename T>
class List
{
    struct Node
    {
        Node* next;
        T     value;
    };


public:
    // in order to make this class a fully compatible with the STL
    // we need to implement iteration like in STL
    class const_iterator : public std::iterator<std::forward_iterator_tag, T, std::size_t, T const*, T const&>
    // Random access and bidirectional movement are not efficient in a single linked list,
    // so we choose a simple forward iterator that can store and retrieve values
    {
    public:
        // Traits(copy n paste) from STL containers
        typedef std::forward_iterator_tag   iterator_category;
        typedef T                           value_type;
        typedef ptrdiff_t                   difference_type;
        typedef T const*                    pointer;
        typedef T const&                    reference;

        const_iterator(Node* current_node = nullptr)
            : m_current_position(current_node)
        {}

        // operators
        reference operator*()
        {
            return m_current_position->value;
        }

        pointer operator ->()
        {
            return std::pointer_traits<pointer>::pointer_to(**this);
        }

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

        const_iterator operator++(int) 
        {
            auto previous = *this;
            ++*this;
            return previous;
        }

        bool operator ==(const_iterator const& rhs)
        {
            return m_current_position == rhs.m_current_position;
        }

        bool operator !=(const_iterator const& rhs)
        {
            return !(*this == rhs);
        }

    private:
        Node* m_current_position;
    };

    // repeat for non-constant iterator
    class iterator : public std::iterator<std::forward_iterator_tag, T, std::size_t, T*, T&>
    {
    public:
        typedef std::forward_iterator_tag   iterator_category;
        typedef T                           value_type;
        typedef ptrdiff_t                   difference_type;
        typedef T*                           pointer;
        typedef T&                          reference;

        iterator(Node* current_node = nullptr)
            : m_current_position(current_node)
        {}

        reference operator*()
        {
            return m_current_position->value;
        }

        pointer operator ->()
        {
            return std::pointer_traits<pointer>::pointer_to(**this);
        }

        iterator& operator++()
        {
            m_current_position = m_current_position->next;
            return *this;
        }

        iterator operator++(int)
        {
            auto previous = *this;
            ++*this;
            return previous;
        }

        bool operator ==(iterator const& rhs)
        {
            return m_current_position == rhs.m_current_position;
        }

        bool operator !=(iterator const& rhs)
        {
            return !(*this == rhs);
        }

        Node* m_current_position;
    };


public:
    List();
    List(List<T> const& rhs);
    ~List();

    iterator begin();
    iterator end();

    const_iterator cbegin() const;
    const_iterator cend() const;

    void push_front(T const& value);
    void push_back(T const& value);

    iterator erase(iterator it);

    void clear();
    void pop_front();

    size_t size() const;
    bool empty() const;

    List& operator =(List<T> const& rhs);

private:
    Node*       m_head;
    Node*       m_tail;
    std::size_t m_size;
};

template <typename T>
List<T>::List()
    : m_head(nullptr), m_tail(nullptr), m_size()
{
}

template <typename T>
List<T>::List(List<T> const& rhs)
    : list()
{
    *this = rhs;
}

template <typename T>
List<T>::~List()
{
    clear();
}
template <typename T>
typename List<T>::iterator List<T>::begin()
{
    return iterator(m_head);
}

template <typename T>
typename List<T>::iterator List<T>::end()
{
    return iterator(nullptr);
}

template <typename T>
typename List<T>::const_iterator List<T>::cbegin() const
{
    return const_iterator(m_head);
}

template <typename T>
typename List<T>::const_iterator List<T>::cend() const
{
    return const_iterator(nullptr);
}

template <typename T>
void List<T>::push_front(T const& value)
{
    auto node = new Node;

    node->next = m_head;
    node->value = value;

    m_head = node;

    if (m_tail == nullptr)
    {
        m_tail = node;
    }

    m_size++;
}

template <typename T>
void List<T>::push_back(T const& value)
{
    if (m_tail != nullptr)
    {
        auto at = iterator(m_tail);

        auto node = new Node;

        node->next = at.m_current_position->next;
        node->value = value;

        at.m_current_position->next = node;

        m_size++;

        if (node->next == nullptr)
        {
            m_tail = node;
        }
    }
    else
    {
        push_front(value);
    }
}

template <typename T>
typename List<T>::iterator List<T>::erase(typename List<T>::iterator it)
{
    auto temp = it.m_current_position->next;
    it.m_current_position->next = temp->next;
    m_size--;

    if (it.m_current_position->next == nullptr)
    {
        m_tail = it.m_current_position;
    }

    delete temp;

    return iterator(it.m_current_position->next);
}

template <typename T>
void List<T>::clear()
{
    while (!empty())
    {
        pop_front();
    }
}

template <typename T>
void List<T>::pop_front()
{
    auto temp = m_head;

    m_head = temp->next;

    if (m_head == nullptr)
        m_tail = nullptr;

    m_size--;

    delete temp;
}

template <typename T>
std::size_t List<T>::size() const
{
    return m_size;
}

template <typename T>
bool List<T>::empty() const
{
    return m_size == 0;
}

template <typename T>
List<T>& List<T>::operator =(List<T> const& rhs)
{
    clear();

    for (auto it = rhs.cbegin(); it != rhs.cend(); ++it)
    {
        push_back(*it);
    }

    return *this;
}

template <typename T>
void print(List<T> const& list)
{
    for (auto it = list.cbegin(); it != list.cend(); ++it)
        std::cout << *it << " ";

    std::cout << std::endl;
}

int main()
{
    List<int> list;

    // testing push_back and push_front
    list.push_back(3);
    list.push_back(4);
    list.push_front(2);
    list.push_front(1);

    // testing assign contructors
    List<int> list2;
    list2 = list;

    // testing for-range
    for (const auto& i : list)
        std::cout << i << ' ';

    std::cout << "\n\n list size: " << list.size() << "\n\n";

    // testing iterators
    List<int>::iterator it;
    it = list.begin();
    list.erase(++it);
    print(list);

    it = list.begin();
    *it = 10;
    print(list);

    std::cout << "\n\n list size: " << list.size() << "\n\n";

    // testing clear
    list.clear();

    if (list.empty())
        std::cout << "list is empty and its size: " << list.size() << std::endl;

    // testing STL
    std::fill(list2.begin(), list2.end(), 100);
    std::copy(list2.begin(), list2.end(), std::ostream_iterator<int>(std::cout, " "));
}
\$\endgroup\$

3 Answers 3

Reset to default
2
\$\begingroup\$

  1. While the base-class thinks your difference_type is a size_t, your derived class uses ptrdiff_t. That's a bug.

  2. You could cut your iterator-code in half by templating:

    template<class U = T>
struct iterator : std::iterator<std::forward_iterator_tag, U>
{
    // ...
};
using const_iterator = iterator<const T>;

  3. You are missing const_iterator begin() const and const_iterator end() const.

  4. You know what I'm missing? A way to convert from iterator to const_iterator.

  5. Consider allowing construction and assignment from a std::initializer_list<T>.

  6. Consider allowing emplacing / inserting after an iterator.

  7. You should add move-initialization for performance.

  8. I'm missing a swap(List&) member-function. Adding that allows you to use the copy-and-swap idiom for efficient assignment, offering the strong instead of the basic exception-safety-guarantee.

    Anyway, currently your assignment-operator is broken under self-assignment.

  9. push_back is too complicated, and leaks if assignment of T can throw.
    Also, you don't have the moving variant, nor the emplacing one: 

    void push_back(T&& t) { emplace_back(std::move(t)); }
void push_back(const T& t) { emplace_back(t); }

template<class T, class... U>
void List<T>::emplace_back(U&&... u) {
    if(!m_tail)
        return emplace_front(std::forward<U>(u)...);
    m_tail->next = new Node{nullptr, T(std::forward<U>(u)...)};
    m_tail = m_tail->next;
    ++m_size;
}

  10. The same is true for push_front:

    void push_front(T&& t) { emplace_front(std::move(t)); }
void push_front(const T& t) { emplace_front(t); }

template<class T, class... U>
void List<T>::emplace_front(U&&... u) {
    m_head = new Node{m_head, T(std::forward<U>(u)...)};
    ++m_size;
    if(!m_tail)
        m_tail = m_head;
}

Generally, look at std::forward_list for additional inspiration.

As an aside, I really meant it that making tail a Node** would simplify things.

\$\endgroup\$
3
  • \$\begingroup\$ i have implemented every thing you mentions except copy-swap idiom. i dont know how to copy rest of list by this idiom. and for Node** tail i did it but i dont see any simplification in code. \$\endgroup\$ Commented Nov 1, 2015 at 16:39
  • \$\begingroup\$ Copy-swap-idiom for assignment is simple (like everything once one understand it ;-)): Take the argument by value (it will either be moved or copied there, caller decides), and just call swap in the method. \$\endgroup\$ Commented Nov 1, 2015 at 16:45
  • \$\begingroup\$ And making tail a Node** means it can always point to the proper pointer to change for inserting a new Node, it is never nullptr. \$\endgroup\$ Commented Nov 1, 2015 at 16:48
2
\$\begingroup\$

push_back() simplification

Your push_back() function seems overly complicated. This part:

if (m_tail != nullptr)
{
    auto at = iterator(m_tail);

    auto node = new Node;

    node->next = at.m_current_position->next;
    node->value = value;

    at.m_current_position->next = node;

    m_size++;

    if (node->next == nullptr)
    {
        m_tail = node;
    }
}

could just be:

if (m_tail != nullptr)
{
    auto node = new Node;

    node->value  = value;
    node->next   = NULL;
    m_tail->next = node;
    m_tail       = node;
    m_size++;
}

erase() looks wrong

Your erase function looks like it is erasing the node following the iterator instead of at the iterator. In particular it has these problems:

  1. Erases the wrong node.
  2. Will crash if iterator is at the end of the list.
  3. If the head is ever erased (which is currently not possible due to #1), m_head is not updated.
\$\endgroup\$
5
  • \$\begingroup\$ thanks for your time to review this code, yes erase is deleting the node after. i had iterator invalidated if i deleted current node. probably i should add assert to insure that not delete last node. \$\endgroup\$ Commented Oct 31, 2015 at 9:52
  • \$\begingroup\$ You might want to look into aggregate-initialization. \$\endgroup\$ Commented Oct 31, 2015 at 13:47
  • \$\begingroup\$ As-is, your replacement for push_back leaks. \$\endgroup\$ Commented Oct 31, 2015 at 21:33
  • \$\begingroup\$ @Deduplicator How does it leak? \$\endgroup\$ Commented Oct 31, 2015 at 22:33
  • \$\begingroup\$ Assume that assignment of value throws. \$\endgroup\$ Commented Oct 31, 2015 at 22:34
1
\$\begingroup\$

When exceptions fly, you leak memory

When removing the smart pointers, you introduced subtle bugs. If, after you allocated a Node, an exception happens for instance in T::operator= - the Node object will leak in List::push_*. This should not happen and did not happen in your previous implementation or std::list.

This is exactly why I disagree with the previous recommendation to remove the smart pointers. It is difficult to get these things right in corner cases.

Edit/clarification: Of course it is possible to also get it right with raw pointers. But it is much harder to get right than by using std::unique_ptr, which has zero runtime cost and can simply things.

Further

  1. Try to provide a perfect forwarding interface, including emplace_*.

  2. You miss the header for ptrdiff_t ()

  3. There is a typo here:

    template <typename T>
List<T>::List(List<T> const& rhs)
    : list() <--- ???

  4. You shoud return something from main.

\$\endgroup\$
6
  • \$\begingroup\$ @Deduplicator: a missing return is most certainly a compiler warning and therefore should be avoided. \$\endgroup\$ Commented Nov 1, 2015 at 11:44
  • \$\begingroup\$ Sorry, I read to fast when I looked at your initial revision, but you clarified that. The point about main still stands though, return 0; is implicit in C++ for that function. \$\endgroup\$ Commented Nov 1, 2015 at 13:56
  • \$\begingroup\$ i have run this code in VC14 with _CrtDumpMemoryLeaks() there is no leak. which memory leak detector do you use? \$\endgroup\$ Commented Nov 1, 2015 at 15:19
  • \$\begingroup\$ @MORTAL, have you used a T that throws an exception during T::operator=? \$\endgroup\$ Commented Nov 1, 2015 at 15:27
  • 1
    \$\begingroup\$ @MORTAL See en.wikipedia.org/wiki/Exception_safety: For every function you look at each expression, and determine which guarantee it offers, and how they are combined. The guideline is "A function should always support the strictest guarantee that it can support without penalizing users who don't need it. " stroustrup.com/except.pdf \$\endgroup\$ Commented Nov 1, 2015 at 17:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.