Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is std::list circular?

Tags:

c++

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
}
like image 969
michalt38 Avatar asked May 11 '20 15:05

michalt38


People also ask

What is a circular linked list?

What is a Circular Linked List? A circular linked list is a linked list where all nodes are connected to form a circle. Generally, the last node of the linked list has a NULL in the address field, but a circular linked list has the address of the head node in the address field of the last node.

Why do we use circular list in operating system?

It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list. 4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

What are the advantages of circular list in Java?

We can maintain a pointer to the last inserted node and front can always be obtained as next of last. 3) Circular lists are useful in applications to repeatedly go around the list.

How to insert elements at different positions of a circular list?

We can insert elements at 3 different positions of a circular linked list: Suppose we have a circular linked list with elements 1, 2, and 3. Let's add a node with value 6 at different positions of the circular linked list we made above. The first step is to create a new node. 1. Insertion at the Beginning


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.

like image 138
Bathsheba Avatar answered Oct 07 '22 07:10

Bathsheba


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".

like image 35
cmaster - reinstate monica Avatar answered Oct 07 '22 07:10

cmaster - reinstate monica