Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is it safe to use std::list as a circular list?

So incrementing or decrementing the end() iterator is defined in the standard? On linux, the begin() is implemented as end()++.

#include <list>
#include <iostream>

int main()
{
  std::list<int> numbers;
  for (int i = 0; i < 10; i++)
    numbers.push_back(i);

  auto it = numbers.begin();
  int count = 3;
  while (count)
  {
    std::cout << *it++;
    if (it == numbers.end())
    {
      ++it; // is this ok ???
      --count;
      std::cout << '\n';
    }
  }
}

So the output always the same on every platform?

Output:

0123456789
0123456789
0123456789
like image 854
Industrial-antidepressant Avatar asked Oct 20 '12 19:10

Industrial-antidepressant


People also ask

Should I use std::list?

Consider using std::list if: You need to store many items but the number is unknown. You need to insert or remove new elements from any position in the sequence. You do not need efficient access to random elements.

Is std::list Circular?

@cmaster-reinstatemonica -- from the perspective of the language definition, std::list is not a circular list. Its list of requirements does not include anything that makes it circular.

Is std::list linked?

The std::list is implemented as a doubly-linked list.

How do you make a linked list circular in C++?

We can declare a node in a circular linked list as any other node as shown below: struct Node { int data; struct Node *next; }; In order to implement the circular linked list, we maintain an external pointer “last” that points to the last node in the circular linked list.


2 Answers

Incrementing the iterator returned from end() of any of the standard C++ library containers results in undefined behavior. Due to an implementation detail common to most implementations of std::list<T> it may work to increment list.end() but there is no guarantee that it does.

like image 188
Dietmar Kühl Avatar answered Oct 13 '22 00:10

Dietmar Kühl


No, this is not ok. The std::list iterator is a BidirectionalIterator, which is a refinement of ForwardIterator. The precondition for both ++i and i++ for a ForwardIterator states:

i is dereferenceable

which does not hold for end() as it points past the last item of the list.

like image 26
Thomas Avatar answered Oct 13 '22 00:10

Thomas