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

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 2

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.