accessing std::list in the middle

Question

I have a dummy question. I always read that C++ std::list container has constant time for inserting elements at the beginning, at the end and in the middle: Which is the correct way to insert an element directly in the middle of a std::list? Is maybe this one?

  std::list<int> l;
  l.push_back(10);
  l.push_back(20);
  l.push_back(30);
  l.push_back(40);
  l.push_back(50);
  l.push_back(60);
  l.insert( l.end()- l.begin() /2 ); //? is this 
  // inserting directly in the middle?

When we say 'inserting in the middle' do we really mean that we save linear time to go from the beginning of the list to the desired point ( traversing one by one through all linked elements in between)?

Answer 1

Here, "the middle" means an arbitrary point in the list, as long as you already have an iterator referring to that point. Given that, insertion is just a matter of modifying a few pointers around the insertion point.

If you don't already have an iterator for the insertion point, and it isn't somewhere simple like the beginning or the end, then it will take linear time to walk through the list to find it.

Answer 2

You can do the iterator maths generically like this:

 std::list<int>::iterator it = l.begin();
 std::advance(it, std::distance(l.begin(), l.end())/2);
 l.insert(it, value);

This will work for any iterator type (except OutputIterator or InputIterator)

Of course it is way more efficient to say

 std::advance(it, l.size()/2);
 l.insert(it, value);

Unfortunately, l.insert(l.begin + (l.size()/2), value) won't work because list iterators aren't random access, therefore don't have operator+ defined (to prevent performance surprises!). Keep in mind that std::advance() might be a costly operation depending on iterator type (it will be slow for reverse iterators implemented on a forward-only container, e.g.).

Answer 3

When we say 'inserting in the middle' do we really mean that we save linear time to go from the beginning of the list to the desired point ( traversing one by one through all linked elements in between)?

Yes.
Basically, It means the list needs to just change pointers to insert a new element and not navigate the entire list or copy the contents etc.Hence the insertion is constant time, because there is no need of traversing the list or copying the containers etc.

Answer 4

Inserting in the "middle" of a list means inserting somewhere other than the beginning or end. But doing an insertion requires an iterator to the insertion point. Once you have such an iterator, the insertion time is constant, but getting such an iterator in the first place is a separate issue.

Answer 5

No, when we say "inserting in the middle" we do not mean "finding the insertion point according to whatever criteria that takes traversing of the whole or indefinite part of the list".