> std::vector implements one of the simplest data structures in computer science.
It may "implement" one of the simplest DS, but this particular implementation is anything but trivial to use. You can get a pointer to an element in it, and keep using the vector, and the pointer will point to the correct element... until you push_back() one too many element, it resizes, and then suddenly your pointer is invalid.
But if you reserve() the right amount of space, you can keep it valid! If you are very careful. But then you don't want to call reserve() too often because it may actually turn your O(N) algorithm into O(N^2)! (Basically, calling reserve() N times on O(N) length vector takes O(N^2) time, while doing push_back() N times is guaranteed to be O(N).)
Sure, std::vector is useful, and I use it all the time, but it is anything but simple. It's C++ after all. :)
You have the similar problems if you build your own resizeable arrays in C, unless you resort to an extra level of indirection (e.g. an array of pointers, or pointers to array chunks).
std::vector has a series of gotchas, but any generic resizeable array which has similar performance will have similar gotchas; std::vector wasn't made that way just for giggles.
dmpk2k is right: the requirements on iterator validity are the obvious consequences of using a reallocatable array. Replace a std::vector with malloc-ed memory and call realloc every so often, and you'll find your pointers to elements in the array don't stay valid. It's not a gratuitous problem; you'd run into it no matter how you implement your grow able array.
Interestingly, keeping track of indexes into the array avoids the issue completely.
boost::stable_vector[0] isn't a bad middle ground between a linked list and a vector if you just want iterator stability and better exception safety (for types that throw when moved or copied)
It may "implement" one of the simplest DS, but this particular implementation is anything but trivial to use. You can get a pointer to an element in it, and keep using the vector, and the pointer will point to the correct element... until you push_back() one too many element, it resizes, and then suddenly your pointer is invalid.
But if you reserve() the right amount of space, you can keep it valid! If you are very careful. But then you don't want to call reserve() too often because it may actually turn your O(N) algorithm into O(N^2)! (Basically, calling reserve() N times on O(N) length vector takes O(N^2) time, while doing push_back() N times is guaranteed to be O(N).)
Sure, std::vector is useful, and I use it all the time, but it is anything but simple. It's C++ after all. :)