Generic List code with Iterator

Question

I was wondering if this implementation of generic list with iterator is correct. The code compiles and goes fine. What would you think shall I improve? (first time I post here, I'm scared). I'm also concerned about the const correctness of the code.

Class node

#ifndef LIST_H_
#define LIST_H_

template<typename K>
class Node {
public:
    Node();
    Node(const Node<K>& x);
    void setKey(const K& x);
    void setNext(Node<K> * const & x);
    void setPrev(Node<K> * const & x);
    Node<K>* getNext() const;
    Node<K>* getPrev() const;
    void insertNode(Node<K>* const & nil);
    void removeNode(Node<K>* const & nil);
    K getKey() const;
    K& getKeyRef();
private:
    K key;
    Node<K>* next;
    Node<K>* prev;
};

template<typename K>
inline Node<K>::Node() {
    this->setNext(this);
    this->setPrev(this);
}

template<typename K>
inline Node<K>::Node(const Node<K>& x) {
    this->setKey(x.getKey());
    this->setPrev(x.getPrev());
    this->setNext(x.getNext());
}

template<typename K>
inline void Node<K>::setKey(const K& x) {
    this->key = x;
}

template<typename K>
inline void Node<K>::setNext(Node<K> * const & x) {
    this->next = x;
}

template<typename K>
inline void Node<K>::setPrev(Node<K> * const & x) {
    this->prev = x;
}

template<typename K>
inline Node<K>* Node<K>::getNext() const {
    return this->next;
}

template<typename K>
inline Node<K>* Node<K>::getPrev() const {
    return this->prev;
}

template<typename K>
inline K Node<K>::getKey() const {
    return this->key;
}

template<typename K>
inline K& Node<K>::getKeyRef() {
    return this->key;
}

template<typename K>
inline void Node<K>::insertNode(Node<K>* const & nil) {
    this->setPrev(nil->getPrev());
    this->setNext(nil);
    nil->getPrev()->setNext(this);
    nil->setPrev(this);
}

template<typename K>
inline void Node<K>::removeNode(Node<K>* const & nil) {
    Node<K> *prev, *next;
    if(this != nil) {
        prev = this->getPrev();
        next = this->getNext();
        prev->setNext(next);
        next->setPrev(prev);
    }
}

#endif /* LIST_H_ */

Class list with nested iterator

#ifndef LIST_LIST_H_
#define LIST_LIST_H_

#include "list_node.h"
#include <iostream>

template<typename K>
class List {
public:

    class Iterator;

    List();
    List(const List<K>& x);
    ~List();
    void insert(const K& x);
    List<K>::Iterator begin();
    List<K>::Iterator end();
    List<K>::Iterator search(K k);
    void remove(List<K>::Iterator it);
    Node<K>* getSentinel() const;

    class Iterator {
    public:
        Iterator();
        Iterator(const List<K>& x);
        ~Iterator();
        Iterator(const Iterator& it);                   // Copy constructor
        List<K>::Iterator& operator=(const Iterator& it); // Assignment operator
        List<K>::Iterator& operator++();                   // Next element
        K& operator*();                    // Dereference
        bool operator==(const Iterator& o) const; // Comparison
        bool operator!=(const Iterator& o) const;
        void setCurrent(Node<K> * const & x);
        Node<K>* getCurr() const;
    private:
        Node<K> * curr;
    };

private:
    Node<K> *sentinel;
};

template<typename K>
inline List<K>::List() {
    this->sentinel = new Node<K>();
}

template<typename K>
inline List<K>::List(const List<K>& x) {
    Node<K>* curr = x.getSentinel()->getNext();
    while (curr != x.getSentinel()) {
        this->insert(curr->getKey());
        curr = curr->getNext();
    }
}

template<typename K>
inline List<K>::~List() {
    Node<K> *curr, *nil;
    nil = this->getSentinel();
    curr = nil->getNext();
    while(curr != nil) {
        curr->removeNode(nil);
        delete curr;
        curr = nil->getNext();
    }
}

template<typename K>
inline void List<K>::insert(const K& x) {
    Node<K>* node = new Node<K>();
    Node<K>* nil = this->getSentinel();
    node->setKey(x);
    node->insertNode(nil);
}

template<typename K>
Node<K>* List<K>::getSentinel() const {
    return this->sentinel;
}

template<typename K>
inline typename List<K>::Iterator List<K>::begin() {
    List<K>::Iterator it(*this);
    ++it;
    return it;
}

template<typename K>
inline typename List<K>::Iterator List<K>::end() {
    return List<K>::Iterator(*this);
}

template<typename K>
inline typename List<K>::Iterator List<K>::search(K k) {
    List<K>::Iterator it(*this);
    for (it = this->begin(); it != this->end(); ++it) {
        if (*it == k)
            return it;
    }
    return it;
}

template<typename K>
inline void List<K>::remove(List<K>::Iterator it) {
    Node<K>* curr = it.getCurr();
    curr->removeNode(this->getSentinel());
    delete curr;
}

template<typename K>
inline List<K>::Iterator::Iterator() {
    this->setCurrent(0);
}

template<typename K>
inline List<K>::Iterator::Iterator(const List<K>& x) {
    this->setCurrent(x.getSentinel());
}

template<typename K>
inline List<K>::Iterator::~Iterator() {
    ;
}

template<typename K>
inline List<K>::Iterator::Iterator(const Iterator& it) {
    this->setCurrent(it.getCurr());
}

template<typename K>
inline typename List<K>::Iterator& List<K>::Iterator::operator =(
        const Iterator& it) {
    if (this != &it) {
        this->setCurrent(it.getCurr());
    }
    return *this;
}

template<typename K>
inline typename List<K>::Iterator& List<K>::Iterator::operator ++() {
    this->setCurrent(this->getCurr()->getNext());
    return *this;
}

template<typename K>
inline K& List<K>::Iterator::operator *() {
    return this->getCurr()->getKeyRef();
}

template<typename K>
inline bool List<K>::Iterator::operator ==(const Iterator& o) const {
    return this->getCurr() == o.getCurr();
}

template<typename K>
inline bool List<K>::Iterator::operator!=(const Iterator& o) const {
    return !(*this == o);
}

template<typename K>
inline void List<K>::Iterator::setCurrent(Node<K>* const & x) {
    this->curr = x;
}

template<typename K>
inline Node<K>* List<K>::Iterator::getCurr() const {
    return this->curr;
}

#endif /* LIST_LIST_H_ */

Answer 1

Here are some things that may help you improve your code.

Use consistent naming

The include guard says #ifndef LIST_H but the actual include says #include "list_node.h". It's not technically an error, but I'd suggest that changing the include guard to #ifndef LIST_NODE_H_.

Fix the destructor

Right now there is a memory leak in the destructor. You need to add delete nil; as the last line.

Don't expose class internals

The getKeyRef() is a dangerous function because it essentially returns a handle to an internal data member of Node. In fact, because all of the private data members have functions which "leak" their internals, I'd suggest making Node a struct and then making it a private within the List class.

Avoid cluttering the code with this->

All of the instances of this-> are just visual noise and don't really add anything to the program. I'd recommend omitting all such instances.

Eliminate unneeded functions

The getSentinel() routine, it seems to me, is probably only useful within the List class, so I'd recommend eliminating the routine and simply using the sentinel member variable instead. Similarly, Iterator::setCurrent() and Iterator::getCurr() seem unnecessary. I'd also recommend omitting ~Iterator() since it literally does nothing.

Rethink variable names

The variables next and prev and key are good names because they suggest how they are used. However, nil and sentinel are not as good, in my view. In some languages nil is the equivalent to nullptr and it seems to me that instead of sentinel, a better name might be root. Also, I'd suggest that having root be a default-constructed Node instead of a pointer would simplify this class.

Consider a different constructor

The Node class could benefit from a constructor like this:

Node(const T& value, Node *prev_=nullptr, Node *next_=nullptr) : 
    key{value}, prev{prev_}, next{next_} 
{}

Simplify the insert code

Removing the functions from Node and making it a struct internal to List allows a much simplified insert routine. For example, here's how the Node might look:

template<typename T>
struct Node {
    Node(const T& value) :
        key{value}, prev{this}, next{this} 
    {}
    Node(const T& value, Node *p, Node *n) :
        key{value}, prev{p}, next{n} 
    {}
    T key;
    Node<T> *prev;
    Node<T> *next;
};

This allows the insert routine to be written like this:

template<typename K>
inline void List<K>::insert(const K& x) {
    auto tail = root.prev;
    root.prev = tail->next = new Node<K>(x, tail, &root);
}

This also assumes that the previous few changes have also been made.

Use nullptr rather than 0

Instead of this->setCurrent(0);, it would be better to use setCurrent(nullptr); or simply curr = nullptr;. While they result in the same thing, using nullptr makes the context and intent much more clear.

Consider implementing a bidirectional iterator

Since your List is a doubly-linked list, it should be relatively simple to provide a bidirectional iterator instead of just the forward iterator that is currently implemented.

Consider adding a construct that uses std::initializer_list

It would be nice to be able to instantiate a list like this:

List<std::string> mylist{"alpha", "beta", "gamma", "delta"};

This can be relatively easily added using the C++11 std::initializer_list.

Answer 2

Since Edward covered almost everything, I had to be extra picky about everything, e.g. going into -WeverythingPossible mode.

Bugs:

Node<K>* node = new Node<K>();

The line default constructs K, which is actually wrong. It should directly initialize underlying key with passed reference. As a result, if copying in setKey() will throw, the list will leak memory, e.g. the function doesn't have even basic exception guarantee. Exceptions problem apply to copy constructor as well, since it depends on insert() being correctly working.

Redundant code:

Inlining everything usually won't make a difference. It is a hint to the compiler, and mostly compilers ignore those hints.

Missing functionality:

• no operator* for const iterators.

• no reference in search(K k), it should be const K&. In fact, std::find() already does the job, so the function is redundant.

• No emplace

• No move constructor+assignment

• No exception specification.

• No post increment

• other not so important stuff

Coding style:

Usually binary operators, like !=, ==, etc, are implemented as free functions, friends if needed. The motivation is that if they want to extend the functionality, they can't provide foreign type as a left hand side argument, since member equality and other operators work only if they are on the left.

Iterators usualy have private constructor and the container usually is a friend of it (thats what I use). I believe the motivation is that iterator concept doesn't require that, though there is no serious reason for that.

Not enough metaprogramming. Real std::list doesn't try to compile copy constructor if the K is not copy constructible.

Some thoughts:

When writing C++ code, I don't feel like I'm enjoying a walk in a park, but rather feel like I'm in a midst of a battle which turns into bloodbath. It becomes very dangerous to let guard down. Also, always keep compiler warnings at very high, but not -Weverything, since it brings some very unnecessary stuff, like C++98 compatibility. The usual flags are like what @Edward said, -Wall -Wextra -pedantic -std=c++14, but if you have new compiler, it is possible to write -std=c++1z.

Answer 3

Consider using std::unique_ptr to avoid handling memory leakage issues. new and delete are error prone.