More on C++ vector
Vector is probably the most widely used container in C++, well, at least for me. Also as far as I remember in http://channel9.msdn.com/Events/BUILD/BUILD2011/TOOL-835T they mention something like that too.
Obviously vector is not the answer to all the questions, but most of the time vector works best or at least same as other containers.
So it is worth knowing how exactly it works. You should already know the complexity of insert and push_back, but knowing what really happens behind the curtains can also lead to various performace changes. Thus I will not be talking about WRONG place to use vector, but about where it could be used RIGHT but you can still have some performance improvements. So if you should really be using some other STL container instead of vector, these tips won’t help.
At first, it seems like it is a very simple data structure, but C++ has all kinds of hidden stuff and it is important to know them to use the language efficiently. Recently I’ve written about inserting objects to vector without a copy constructor, which has shown, that using vector without knowing this sneaky feature can lead to some performance degradation.
Using reserve with push_back
You might expect that push_back or new C++11 vector method emplace_back work in constant time. However it is not necessarily true as vector reallocation might take place during push_back if it runs out of reserved space.
If it was vector of objects, not pointers, this might take some time, because copy constructor would be called. To prevent this, there is a “hidden” method called reserve. I call it “hidden” because” I have never seen it being used in the code base I work. This method is simply never called, even if capacity could have been clearly determined beforehand.
In C++11 it might be solved with different approach – by enabling move constructor and move assignment operator. This will force elements to be moved instead of copied (well, at least on gcc version 4.6.1 it works for sure!).
However if you can even prevent moving your objects, why not to do so? Use reserve, it is already implemented and well documented, and you will not hurt anyone using it.
While this should not have significant difference in efficiency compared with accessing last element with operator, it is so much clearer to read code when it is used to access the last element. Also, if you do this
myVect[myVect.size() - 1]
you know you’re up to no good!
Foolproof yourself with const_iterator
Same as the reserve method, this one is also there! It is much like passing a const reference, it might save you from afternoon debugging.
Some Final Words
Do yourself a favor and don’t ignore the features STL provides you. Yeah, all the above would work just fine, but lets leave all the “Either way it works. Who cares?” and ignorance of inner workings for the java kids, shall we?