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_ */

• Phrancis: Welcome to Code Review! Hope you get some great answers.
• Rafael Lerm: Who owns the nodes? The way the code is now, when the list gets destroyed, then all the contents will be leaked.
• user8469759: Good point... I'll fix that.
• user8469759: @RafaelLerm, I've implemented a destructor.

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.

• Incomputable: "a default-constructed Node" - Then Key would need to be default constructible as well. And also copyable if one wants to be able copy the List.
• user8469759: I'll wait some more suggestion from you then before starting to apply them.
• Edward: I've updated my answer to be more complete.
• Incomputable: @Edward, I'm sorry if I'm being too picky.
• Incomputable: @user8469759, if you want to get review on new code, then it would be better to post a follow up question. If not, you can post a selfie answer, but it should be full blown review. Changing code (even adding code), is discouraged after receiving answers.

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.

• Edward: I absolutely agree that turning up the warnings helps to avoid writing faulty code. My default compiler settings for clang and gcc are -Wall -Wextra -pedantic -std=c++14.
• user8469759: @Incomputable, is Node<K> *nil equal to Node<K> * const& nil? I thought they were different.
• Incomputable: @user8469759, the effect is the same. What you meant by Node<K> * const&? Reference to a const pointer pointing to non const object? Then true, otherwise not. Also, passing built in types as const references don't make much sense, since they are very cheap to copy. There are also implementation details about references, but I will leave them to discover in the future.
• user8469759: @Incomputable, I meant exactly that I pass a pointer and I want to be able to change the value of the pointed variable, but not the value of the pointer. Like if a points to b that stores c I want to be able to change the c value but not the b value (because that's actually what I need to do).
• Incomputable: @user8469759, I see what you mean now. Just didn't see it used anywhere before (usually people would just pass it as plain reference, or use constructor for that or let list do that). Its just that I'm used to plain structs to do that kind of stuff. You're correct.

Answer 3

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

• user8469759: Hi, I've never used std::unique_ptr, in a nutshell what would be the benefit in my code?