Q:

vector vs list insert performance

I just watched a presentation by Herb Sutter (see min. 46 on http://channel9.msdn.com/Events/Build/2014/2-661 )  on various STL containters performance. It looks like std::vector is FASTER than a std::list even for insertion in the middle, which looks like a big NO-NO first... His explanation was that this is happening because of contiguous memory allocation in a std::vector, and because linear transversal seems to be super fast. I am now curious, did anyone observe a visible performance difference between the two in real code? I am not a professional programmer, I just tested a simple example on my laptop and it seems that indeed std::vector is inserting faster that a std::list. This seems a bit strange though... I would like to understand why the vector is faster in the STL implementation, 

A:

Since you did not provide a code example, I will provide some possible reasons.

std::list performs one dynamic memory allocation per insert, and dynamic memory allocation is an expensive operation. std::list also needs to take O(n/2) time to just find the middle element, because it has to follow the pointers instead of just doing one pointer addition.
std::vector will require shifting all the elements at the end of the list towards the right, which is probably similar or faster than the traversal time for std::list.  Moreover, std::vector will tend to double in size whenever it runs out of capacity, so it uses only O(log n) re-allocations, compared to O(n) allocations for std::list.

I think you might learn something interesting about the cost of copy vs cost of traversal if you start measuring with a larger size of each container. For example, 20 million elements.

Additionally, as  LightnessRacesinOrbit correctly pointed out, O(1) just means constant time, while O(n) means time proportional to the size of input, but these time bounds do not necessarily translate into practically measured time, especially for small sized inputs, because the O(1) time could be hiding a large constant. 
However, I believe that for this particular problem, the list traversal is probably the culprit, because it causes O(n) time for traversal in order to insert into the middle of the list.

