Doubly linked list: iterator/pointer arithmetic

Question

I'm using a doubly linked list container I've written as the working example. The textbook I'm using is from 2001, so feel free to point out where later versions of the C++ standard should be used instead.

Notes:

• List::iterator functionality mimics pointer arithmetic.
• Unlike most containers, list beginning is marked by a specific element which holds no data, to make reverse iteration easier: [begins][data][data][data][data][data][ends]
• De-referencing begin/end will deference the closest data element, so *begin = data@0 & *end = data@end-1.
• The List container plays more elegantly with basic loops (see main).

list.h:

#ifndef GUARD_List_h #define GUARD_List_h template <class T> struct element { element<T> *prev = NULL; element<T> *next = NULL; T data = NULL; int elem_ID = NULL; char t_flag = NULL; }; template <class T> struct elem_iter { elem_iter() { target = NULL; } elem_iter(element<T>* e) { target = e; } element<T>* target; element<T>* elem_iter::operator++(void) { if (target->next->t_flag == 'e'){ return NULL; } target = target->next; return target; } element<T>* elem_iter::operator--(void){ if (target->prev->t_flag == 'b'){ return NULL; } target = target->prev; return target; } T elem_iter::operator*(void){ if (target->t_flag == 'e'){ target = target->prev; return target->data; } else if (target->t_flag == 'b'){ target = target->next; return target->data; } return target->data; } bool elem_iter::operator!=(elem_iter& rhs){ return (rhs.target != this->target); } bool elem_iter::operator>=(elem_iter& rhs){ return (this->target->elem_ID >= rhs.target->elem_ID); } bool elem_iter::operator<=(elem_iter& rhs){ return (this->target->elem_ID <= rhs.target->elem_ID); } bool elem_iter::operator>(elem_iter& rhs){ return (this->target->elem_ID > rhs.target->elem_ID); } bool elem_iter::operator<(elem_iter& rhs){ return (this->target->elem_ID < rhs.target->elem_ID); } elem_iter elem_iter::operator+(int val){ for (int i = 0; i < val; i++){ this->target = this->target->next; } return *this; } elem_iter elem_iter::operator-(int val){ for (int i = 0; i < val; i++){ this->target = this->target->prev; } return *this; } }; template <typename T> class List { public: List::List(void) { element_count = 0; // create begin element<T>* b = new element <T>; b->t_flag = 'b'; begins = b; // create end element<T>* e = new element <T>; e->t_flag = 'e'; ends = e; // double link: begins & ends begins->next = ends; ends->prev = begins; element_count = 0; } typedef elem_iter<T> iterator; iterator begin(void) { iterator it(begins); return it; } iterator end(void) { iterator it(ends); return it; } void push_back(T val) { element<T>* elem = new element<T>; // create: new-elem elem->data = val; // set data elem->elem_ID = element_count++; // set ID elem->prev = ends->prev; // link: new-elem to last-data-elem ends->prev->next = elem; // link: last-data-elem to new-element elem->next = ends; // link: new-elem to List-end ends->prev = elem; // link: List-end to new-elem ends->elem_ID = element_count; // update: ends-ID when List grows } T at(size_t pos) { return get_element(pos)->data; } void del(size_t pos) { element<T>* elem = get_element(pos); // get: element for deletion elem->prev->next = elem->next; // rejoin: double link elem->next->prev = elem->prev; // rejoin: double link delete elem; ends->elem_ID = (element_count--); // update: when List shrinks } void clear(void) { element<T>* ep = begins->next; element<T>* ep_next = ep->next; while (ep->t_flag != 'e'){ delete ep; ep = ep_next; ep_next = ep->next; } begins->next = ends; ends->prev = begins; begins->data = NULL; ends->elem_ID = NULL; element_count = 0; } size_t size(void) const { return element_count; } bool empty(void) const { if (element_count == 0){ return true; } else { return false; } } private: element<T>* begins; // List begins element<T>* ends; // List ends size_t element_count; // List size element<T>* get_element(size_t pos) { if (empty()) { std::cerr << "No Element - Empty List"; throw; } if (pos < 0 || pos >= element_count){ std::cerr << "No Element - Out of Range"; throw; } iterator it; // Determine the more efficent iteration direction(forward or reverse) ? if ((element_count / 2) > pos) { it = begin(); for (size_t i = 0; i <= pos; i++){ it++; } } else { it = end(); for (size_t i = size() - pos; i > 0; i--){ it--; } } return it.target; } }; #endif typedef List<int> container; 

main.cpp:

#include <iostream> #include <vector> #include <list> #include "list.h" int main() { container ls; container::iterator begin = ls.begin(); container::iterator end = ls.end(); container::iterator iter = begin; std::cout << "Attempt to retrieve data from empty list: ls.at(3)" << std::endl; std::cout << "--------------------------------------------------" << std::endl; //std::cout << ls.at(3) << std::endl << std::endl; std::cout << "Test: growing list does not invalidate iter" << std::endl; std::cout << "-------------------------------------------" << std::endl; std::cout << "Empty list" << std::endl << std::endl; std::cout << "begin addr: " << &begin << " " << std::endl; std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl; std::cout << "end addr: " << &end << " " << std::endl; std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl; std::cout << std::endl << "Add data to list: 33 " << std::endl << std::endl; ls.push_back(33); std::cout << "begin addr: " << &begin << " " << std::endl; std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl; std::cout << "end addr: " << &end << " " << std::endl; std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl; std::cout << std::endl << "Add data to list: 33 " << std::endl << std::endl; ls.push_back(856); std::cout << "begin addr: " << &begin << " " << std::endl; std::cout << "begin t_flag: " << begin.target->t_flag << " " << std::endl; std::cout << "end addr: " << &end << " " << std::endl; std::cout << "end t_flag: " << end.target->t_flag << " " << std::endl << std::endl; std::cout << "clear() " << std::endl << std::endl; ls.clear(); std::cout << std::endl << std::endl; std::cout << "Add data to list: 0 1 2 3 4 5 6 7 8 9" << std::endl; std::cout << "-------------------------------------------------" << std::endl; for (int i = 0; i != 10; i++){ ls.push_back(i); } std::cout << std::endl << std::endl; std::cout << "data@ begin+4" << std::endl; std::cout << "-------------" << std::endl; std::cout << *(iter + 4) << std::endl; std::cout << std::endl << std::endl; std::cout << "data@ begin->end" << std::endl; std::cout << "----------------" << std::endl; iter = begin; while (iter++){ std::cout << *iter << " "; } std::cout << std::endl << std::endl << std::endl; std::cout << "data@ end->begin" << std::endl; std::cout << "----------------" << std::endl; iter = end; while (iter--){ std::cout << *iter << " "; } std::cout << std::endl << std::endl << std::endl; std::cout << "for/iter: begin->end" << std::endl; std::cout << "----------------" << std::endl; for (iter = begin; iter++;){ std::cout << *iter << " "; } std::cout << std::endl << std::endl << std::endl; std::cout << "iter arith: +4 +1 -1" << std::endl; std::cout << "--------------------" << std::endl; iter = ls.begin(); iter = iter + 4; std::cout << *iter << " "; std::cout << *(iter + 1) << " "; std::cout << *(iter - 1) << " "; std::cout << std::endl << std::endl << std::endl; std::cout << "data@: (0)(1)(2)(3)(4)(5)(6)(7)(8)(9)" << std::endl; std::cout << "-------------------------------------" << std::endl; for (int i = 0; i != 10; i++){ std::cout << ls.at(i) << " "; } ls.clear(); return 0; } 

Answer 1

Comment on notes:

List::iterator functionality mimics pointer arithmetic.

If you call it an iterator then it really should.

But you should be careful. There are actually several classes of iterator. The pointer implements the Random Access Iterator. An iterator for a doubly linked list usually only implements Reversible Iterator. The difference is that Random Access Iterator can do i += 10 in O(1) while the reversible iterator does not need this functionality.

Unlike most containers, list beginning is marked by a specific element which holds no data, to make reverse iteration easier: [begins][data][data][data][data][data][ends]

Actually using sentinels (A special marker in the list) is a very common way of implementing a doubly linked list (it makes the implementation much easier because you don't need to worry about the empty list and NULL).

But just because you have a sentinel value internally you do not need to expose that to the user of your class (that is not common). Usually begin() would return the first value after the sentinel.

De-referencing begin/end will deference the closest data element, so *begin = data@0 & *end = data@end-1.

That's a strange behavior. Also it makes swapping your container with other peoples containers bothersome (as you have a change in expected behavior). You should definitely conform to the expected behavior (unless you have a very specific use case that only your class is good for and you document it thoroughly).

The List container plays more elegantly with basic loops...see main.

We will see about that.

A.... no it does not.
Because it does not do what people expect. If you stray from expected behavior then you confuse the maintainer. It may look very neat to you. But to experienced programmers it looks like you fucked up. Then we have to go and dig into the implementation to verify that it actually works as expected (thus wasting time for the maintainer which is probably not you (but does have an axe and your address)).

The classic loop looks like this:

for(auto loop = con.begin(); loop != con.end(); ++loop) { std::cout << *loop << "\n"; } // With C++ 11 (or was it 14) it now looks like this: for(auto const& item : con) // this works with any object // that has begin() and end() // methods that return iterators. { std::cout << item << "\n"; } 

But even more often we use standard algorithms (they use iterators to perform actions on containers).

std::copy(con.begin(), con.end() std::ostream_iterator<int>(std::cout, "\n")); 

Code Review

struct element

This is am implmentation detail of your list.
So define the struct inside your List class (and make it private).

template <class T> struct element { element<T> *prev = NULL; // Correct but why not have a constructor element<T> *next = NULL; T data = NULL; // NOT correct. int elem_ID = NULL; // NOT correct. char t_flag = NULL; }; 

NULL is supposed to be used for pointers only. It marks a pointer that points at nothing. The last three elements in your object are not pointers and thus assigning NULL makes no sense. It compiles because in C++03 NULL was usually the integer zero. In this case the NULL is being converted back to zero and assigned to these values. You will not be able to tell the difference between NULL and zero. In C++11 the nullptr was introduced. This is not convertible back to zero and thus will generate a compiler error when used above.

Also your type T may not be constructable with a NULL pointer (or zero). So this will generate compilation errors.

I would have done:

template <class T> struct element { element<T> *prev = nullptr; element<T> *next = nullptr; T data; int elem_ID = 0; char t_flag = '\0'; element(T const& copy) : data(copy) {} // In C++11 we introduced the concept of moving data // rather than copying it (as in C++03). This is as // quick as copying and if the structure T is complicated // then much faster. If the object T does not know how to // move itself then it will use the copy above so it is // also backwards compatible with old code. element(T&& move) : data(std::forward<T>(move)) {} }; 

struct List

Looks good at first glance. You need a couple of interface changes to make it standards compliant.

typedef elem_iter<T> iterator; iterator begin(void); iterator end(void); 

One of the major important things in C++ (over C) is const correctness. It is very often that you see objects being passed around as const& (const references). This means you can read but not alter them. But it also means that your class must make available ways for your object to be read (via iterators). As a result I would also expect the following.

typedef elem_iter_const<T> const_iterator; const_iterator begin() const; const_iterator end() const; 

Notice the extra const on the end of the function name. This is an indication that this call will not modify the object so the compiler will allow this method to be called when the object is const (ie actually const or being accessed via a const reference).

The iterator returned from these calls should also be slightly different from normal iterators in that they can read from the container but will not allow modification of the container.

Third thing to note is the use of void. This is uncommon in C++ (it means the same but is rarely used (best to not use it but not going to make any difference if you do)). Note this is different from the C meaning of void as a parameter.

Sentential

Your use of sentenals is fine for simple types of T. But will not work for anything with a complex constructor. You should have a different object that does not have the T data load for your sentential.

Also most implementations only use a single sentential object. The pointers of the sentinel wrap around to point at itself. This way begin always points to the first element (or the sentinel if it is empty). While end always points at the sentinel. Then sentinel->next is the first element while sentinal->last is the last element (which could be itself if there are no elements).

If that was confusing I provide an example here.
https://codereview.stackexchange.com/a/28393/507

elem_iter

It looks good (I have not read in detail).
But it is a bit more complex than it needs to be. If you change your implementation to use a single sentinel then your iterator becomes much simpler.

Identifiers

Quick note on identifiers.

User defined types usually (and people could argue against this) have an initial uppercase letter. This makes it easy to identify user defined types over objects.

If I was going to do it here is where I would start:

Empty List

 ############# /-># sentenal #<-\ \--#Prev Next#--/ ############# 

One Element List

 #############<-------------------------\ # DATA # ############# | /--#Prev Next#----------># sentenal # | | #############<----------#Prev Next#--/ \------------------------->############# 

Description:

The sentinel is always there. You also need to make the list circular. That way the first element is next from the sentinel and the last is element prev from the sentinel.

When you construct the end() iterator use the sentinel as it is one past the end.

When you construct the begin iterator use the sentinel->next. Note if the list is empty the the circula nature makes it the same as the end() iterator.

Interface:

template<typename T> class LList { // Define the `Element` internally struct Element { /* STUFF */ }; // Just need one member (the end) // Because we are using a sentenal first and last are // one element away. So we can get to both ends by following // a single pointer. Element* sentenal; std::size_t size; // keep track of size locally public: // constructors/destructors. // Because we are a doing memory management we need to // implement the rule of 3. Since we can do move semantics // and it makes sense to extend this to the rule of 5. LList(); // default constructor LList(LList const& copy); // copy constructor LList(LList&& move); // move constructor ~LList(); // destructor LList& operator=(LList copy); // copy assignment (use copy and swap) LList& operator=(LList&& move); // move assignment (use swap) void swap(LList& rhs) noexcept; // swap (is no exception) but // useful in so many ways. void push_back(T const& value); // push back copy by value void push_back(T&& value); // push back move value into container. /* VERY Advanced but useful the new emplace back */ template<ARGS...> void emplace_back(ARGS args...); // Use T's constructor // Always want to test if a container is empty. // Some methods are only valid if empty is not true. bool empty() const; bool size() const; // Undefined behavior if empty() // Access front or back members. // But provide normal and const versions. T& front(); T const& front() const; T& back(); T const& back() const; // Define an internal iterator. // Use the `std::iterator` as a base for your iterator. struct Iterator: public std::iterator<std::bidirectional_iterator_tag, T> { /* STUFF */ }; // Need to define types that // are used by standard algorithms. typedef STUFF_WITH Iterator iterator; typedef STUFF_WITH Iterator const_iterator; // The iterator interface. iterator begin(); const_iterator begin() const; const_iterator cbegin() const; iterator end(); const_iterator end() const; const_iterator cend() const; // Deleting elements. void pop_front(); void pop_back(); void del(iterator iter); // Note delete via iterator }; 

We can simplify the iterator:

 struct Iterator: public std::iterator<std::bidirectional_iterator_tag, T> { Element* current; Iterator(Element* start) : current(start) {} // Increment/Decrement pre and post fix Iterator& operator++() {current = current->next;return *this;} Iterator& operator--() {current = current->prev;return *this;} Iterator operator++(int) {Iterator r(*this);this->operator++();return r;} // Note define in terms of prefix. Iterator operator--(int) {Iterator r(*this);this->operator--();return r;} // Note define in terms of prefix. // Test against other iterators. bool operator==(Iterator const& rhs) const {return current == rhs.current;} bool operator!=(Iterator const& rhs) const {return current != rhs.current;} }; // Have specific versions for normal iterator. // And another for a const version of the iterator. struct IteratorNorm: public Iterator { IteratorNorm(Element* st): Iterator(st) {} T& operator*() {return static_cast<DataElement*>(this->current)->data;} }; struct IteratorConst: public Iterator { IteratorConst(Element* st): Iterator(st) {} T const& operator*() const {return static_cast<DataElement*>(this->current)->data;} }; // Create the appropriate types need by algorithm typedef IteratorNorm iterator; typedef IteratorConst const_iterator; 

Answer 2

Here are some things that may help you improve your program. One thing you could do for yourself that would greatly improve your programming is to get a newer book. The C++ language has changed considerably since 2001, and there's not much reason to learn an obsolete version and bad habits.

Don't over-specify member functions

When you declare functions inline, as in your elem_iter structure, it is not necessary to repeat that each inline function is member of elem_iter. So instead of this:

T elem_iter::operator*(void){ 

write this:

T operator*(void){ 

Supply the missing postfix operators

There is a difference between iter++ and ++iter. Your code defines only the latter version, but attempts to use the former.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful. Once you do that, you'll see that you have been abusing NULL and using it as both an integer and a character value instead of just a pointer. For example, in List::clear() you have this:

begins->data = NULL; ends->elem_ID = NULL; 

However, data is defined as class T and elem_ID is defined as an int. Instead, assign 0 to elem_ID and don't do anything with data.

Improve your constructors

The List class has three data elements; begins, ends and element_count. The constructor should create and initialize those three things. A more modern style for your constructor might be this:

List() : begins(new element<T>), ends(new element<T>), element_count(0) { begins->t_flag = 'b'; ends->t_flag = 'e'; begins->next = begins->prev = ends; ends->prev = ends->next = begins; } 

Use constructors rather than = to initialize member data

Your code should use a constructor rather than = to initialize data in classes. For example, the constructor for element might be this:

element() : prev(nullptr), next(nullptr), data(), elem_ID(), t_flag(' ') {} 

This is important because it works for public or private data, while = only works for public data.

Write destructors for your classes

Any class that allocates memory must also free it when the object is deleted, but your classes are all missing destructors. To get you started, here's a simple destructor for the List class:

virtual ~List() { while (begins->next != begins) { begins->prev = begins->next; begins->next = begins->next->next; delete begins->prev; } delete begins; } 

Don't #include headers that aren't needed

This code includes <vector> and <list> but neither are actually used. Those lines should be deleted.

Use a consistent naming convention

Pick a naming convention and use it consistently. In this code, some of the classes are lowercase, such as elem_iter but List is capitalized. One common convention is the use uppercase for all classes and structures.

Keep class data and functions separated

The elem_iter class has a single data element target but it's hard to spot because it's hiding amid a number of functions. Better would be to gather all data items together and put them at either the beginning or the end of the class.

Prefer to keep data members private

It's generally bad practice to allow other code to reach inside objects and grab or alter data. For that reason, all of your structs should be classes and only some of the member functions should be public. Where you have closely related classes, you can declare them as friend to allow access to private members. For example, the code for your element might look like this:

template <class T> class List; template <class T> class elem_iter; template <class T> class element { public: element() : prev(nullptr), next(nullptr), data(), elem_ID(), t_flag(' ') {} friend List<T>; friend elem_iter<T>; private: element<T> *prev; element<T> *next; T data; int elem_ID; char t_flag; }; 

Notice that there are forward declarations for List and enum_iter.

Use const where practical

A number of places in the code should have the const keyword added. For example instead of this:

bool operator!=(elem_iter& rhs){ return (rhs.target != this->target); } 

write this:

bool operator!=(const elem_iter& rhs) const { return rhs.target != target; } 

In addition to const to indicate that the argument is not changed by the function, we also have a const at the end to indicate that the operator doesn't change the object. Also, this->target is redundant and return is not a function call and therefore does not need parentheses.

Use default argument values where sensible

The code currently has two different constructors for elem_iter:

elem_iter() { target = NULL; } elem_iter(element<T>* e) { target = e; } 

However, these could be written as a single constructor:

elem_iter(element<T>* e = nullptr) : target(e) {} 

Consider simplifying the interface

It's not clear to me that the elem_ID field is actually useful, so if I were writing this, I think I would omit it and all of the functions that rely on it. It's your choice of course, but often a simpler interface makes for an easier-to-use class.

Consider non-numeric objects

Right now, various places in the code limit class T to be numeric or at least something that can be initialized to 0. By some judicious rewriting, this artificial restriction can be eliminated. For instance, create a List of std::string and you will see where I mean.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.