Inserting into a vector at the front

If you're looking for a computationally efficient way of inserting at the front, then you probably want to use a deque instead of a vector.

An old thread, but it showed up at a coworker's desk as the first search result for a Google query.

There is one alternative to using a deque that is worth considering:

std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
  foo.push_back(T());
std::reverse( foo.begin(), foo.end() );

You still use a vector which is significantly more engineered than deque for performance. Also, swaps (which is what reverse uses) are quite efficient. On the other hand, the complexity, while still linear, is increased by 50%.

As always, measure before you decide what to do.

The efficiency of obtaining the insertion point won't matter in the least - it will be dwarfed by the inefficiency of constantly shuffling the existing data up every time you do an insertion.

Use std::deque for this, that's what it was designed for.

If one of the critical needs of your program is to insert elements at the begining of a container: then you should use a std::deque and not a std::vector. std::vector is only good at inserting elements at the end.

Other containers have been introduced in C++11. I should start to find an updated graph with these new containers and insert it here.