Is std::list circular?

user_7101138 0
Viewed 439

Is the std::list a circular doubly-linked list? Using it I can the the following:

#include <list>
int main(){
    std::list<int> l = {10, 11, 12};
    std::list<int>::iterator it = l.end();
    it++;
    std::cout << *it << std::endl; // prints 10
}
c++
2 Answers

No it is not a circular doubly linked list.

The behaviour of your code is undefined (due to the increment of an iterator set to end()), that's all.

user_23808300

There are actually two levels to this question:

The language standard semantics answer

This answer has already been given by Bathsheba, which is basically that the prescribed behavior of an std::list<> does not include any circularities. When you increment the iterator past the end of the list, you enter the territory of undefined behavior, and all bets are off. Your program is allowed to print "You've been pwnd!" instead of the "10".

The implementation detail answer

The standard does not prescribe whether an std::list<> is circular or not. It only describes some observable behavior, and leaves some other behavior undefined. This allows the implementators of std::list<> some leeway to implement the list in the way they see fit.

Looking at the requirements of an std::list<>, we see that it

  • must support bidirectional iterators and

  • must provide an end() iterator in constant time.

Putting the two together, we see that decrementing the end() iterator is well defined on non-empty lists, and must yield an iterator to the last element of that list.

For the implementator, this means that

  • the list should be double linked (to support increment and decrement),

  • there must be a dummy iterator that end() can return, and

  • the dummy iterator must actually contain a pointer to the last element of the list.

It is possible to implement such a double linked list with either:

  • A pointer to the first element in the list's own object + a dummy iterator that only contains the pointer to the last element.

  • Two dummy iterators, one before the first element, and one after the last element. The iterator at the beginning would only provide a forward pointer, the iterator at the end would only provide a backward pointer.

  • Or just fuse the two dummy iterators together into a single object, using both the forward and backward pointers and making it only special in that it does not contain any data. This is the circular list approach.

The first two approaches introduce a lot of special handling of first elements, last elements and empty lists. That's not good. The third approach has no such special handling: The empty list simply links the dummy to itself on the forward and backward reference, and any list item addition/removal is just adding/removing an iterator between two already existing ones. This greatly simplifies the code.

As such, most implementators will opt for a circular implementation. It's the sane choice. The people who wrote the std::list<> you are using, seem to be of the sane kind. But there is no guarantee. They could replace their current implementation with a more complex one for no good reason at all, and ship that with the next release of their standard C++ library implementation. Your program might not print 10 anymore, or even print anything at all. It could also install a bitcoin miner instead. The C++ standard would not care: As long as the std::list<> provides the prescribed behavior, the implementation is free to do any bullshit it likes when you step across the line marked "undefined behavior".

user_24451840
Related