Doubly linked list: iterator/pointer arithmetic

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
struct element {

element *prev = NULL;
element *next = NULL;
T data = NULL;

int elem_ID = NULL;
char t_flag = NULL;
};

template
struct elem_iter {

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

element* target;

element* elem_iter::operator++(void) {

if (target->next->t_flag == 'e'){
return NULL;
}

target = target->next;
return target;
}
element* 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::operatortarget->elem_ID elem_ID);
}
bool elem_iter::operator>(elem_iter& rhs){

return (thi

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(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 
struct element {

    element *prev = NULL;  // Correct but why not have a constructor
    element *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 
struct element {

    element *prev = nullptr;
    element *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(move))
    {}
};

struct List

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

typedef elem_iter 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 const_iterator;

const_iterator begin()  const;
const_iterator end()    const;

Notice the ex

StackExchange Code Review Q#86593, answer score: 5