iterator end()

[nuderobmonkey]

I wonder me how iterator end() is implemented, since I had concern with code which was at the core like this:

#include <list>
#include <iostream>

int main()
{
    std::list<int> l { 1, 2, 3 };
    
    auto end = l.end();
    for(auto it=l.begin();  it!=end;  )
    {
        std::cerr << *it << '\n';
        
        it = l.erase(it); // points to its next element
        
        l.push_back(-1);
    }
}

Contrary to my expection, the execution don't stop, although iterator 'end' is set to the old end of the list. So what's going on there?

[Peter87]

push_back doesn't invalidate any iterators.
erase only invalidates the iterators referring the element that was removed.
The end iterator is not invalidated by these operations so it keeps referring to the end of the list.

[nuderobmonkey]

So could somone roughly explain how such an end() iterator is implemented? To what points the last element of such a list for its 'next'? Is it a nullptr?

[nuderobmonkey]

I tried to examining the behavior:

#include <list>
#include <iostream>

int main()
{
    std::list<int> l;
    
    std::cerr << static_cast<unsigned long long int>(l.end());
    
}

This doesn't work :(

#include <list>
#include <iostream>

int main()
{
    std::list<int> l;
    
    std::cerr << static_cast<unsigned long long int>( *l.end());
    
}

This returns 0

[JLBorges]

> So could somone roughly explain how such an end() iterator is implemented?

The typical implementation of a iterator holds a pointer to the node in the list; end can then be implemented by using a null pointer (note that the next of the last node in the list is a null pointer).

A simplified (non-SCARY) implementation could illustrate the general idea:

#include <iostream>
#include <initializer_list>
#include <string>

template < typename T > struct list {

    list() noexcept = default ;
    list( std::initializer_list<T> ilist ) { for( const T& v : ilist ) push_back(v) ; }

    ~list() { while( !empty() ) pop_back() ; }
    // etc.

    std::size_t size() const { return sz ; }
    bool empty() const { return size() == 0 ; }

    void push_back( const T& v ) {

         if( empty() ) first = last = new node{ v, nullptr, nullptr } ;
         else { last->next = new node{ v, last, nullptr } ; last = last->next ; }

         ++sz ;
    }

    void pop_back() { // invariant: !empty()

        if( size() == 1 ) { delete first ; first = last = nullptr ; }
        else { last = last->prev ; delete last->next ; last->next = nullptr ; }

        --sz ;
    }

    // etc.
    private: struct node ; public:
    struct iterator {

        // elided: type aliases to make it compatible with std::iterator_traits

        T& operator* () { return current->value ; }
        T* operator-> () { return &**this ; }

        iterator& operator++ () {  current = current->next ; return *this ; }
        iterator operator++ (int) { const auto temp = *this ; ++*this ; return temp ; }
        iterator& operator-- () {  current = current ? current->prev : lst.last ; return *this ; }
        iterator operator-- (int) { const auto temp = *this ; --*this ; return temp ; }

        bool operator== ( const iterator& that ) const { return current == that.current ; }
        bool operator!= ( const iterator& that ) const { return !( *this == that ) ; }

        private:
            node* current ;
            list& lst ;
            iterator( node* n, list& l ) : current(n), lst(l) {}
            friend list ;
    };

    iterator begin() { return { first, *this } ; }
    iterator end() { return { nullptr, *this } ; }

    // ...

    private:

        struct node { T value ; node* prev ; node* next ; };

        node* first = nullptr ;
        node* last = nullptr ;
        std::size_t sz = 0 ;
};

int main() {

    list<std::string> lst { "abcd", "efgh", "ijkl", "mnop", "qrst", "uvwx", "yz12" } ;
    for( const auto& str : lst ) std::cout << str << '\n' ;
}

http://coliru.stacked-crooked.com/a/324ee5f5f68790aa

[nuderobmonkey]

@JLBorges, thank you so much your for this great example, I'm always impressed by your extraordinary effort which you lay on your examples!