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_htemplate <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;    }};#endiftypedef List<int> container;main.cpp:#include <iostream>#include <vector>#include <list>#include list.hint 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;}
Doubly linked list: iterator/pointer arithmetic
c++;linked list;iterator
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 Reviewstruct elementThis 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 ListLooks 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.SententialYour 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/507elem_iterIt 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.IdentifiersQuick 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;