Quote:
|
Originally Posted by n0nsensical
I thought the STL vector was just an interface and each STL implementation of vector could theoretically be different. What I'm getting at is I don't see any reason why the elements of a vector couldn't be stored in contiguous memory, though actual implementations would find better ways. That wouldn't stop it from being resized because it could simply allocate a larger block of contiguous memory and copy the existing elements over to it. So are you talking about a spec or definition somewhere that says this or the de facto way of implementing it?
|
It's not just the interface, there are qualities that the interface must honour in order to be defacto STL containers. For instance, the [] operator for std::vector must execute in constant time, O(k). This can't be done with, say, a linked list implementation...
Having said that, after a modicum of research (asking someone who knows), I have discovered that std::vector need not be implemented using contiguous memory. This may not be true in the future since the STL container that
does implement contiguous memory, std::valarray, is in the process of being deprecated in favour of std::vector, since almost all implementations of it do exactly that (use contiguous memory).
In answer to
Pragma's reasoning, it is false. There's nothing about contiguous memory that makes it impossible to dynamically resize the container. Yes, it might require a lot of copies but there are no constraints to the execution time of insertion for std::vector, so that's okay (in terms of conformance).
This is beside the point. Because std::vector need not be implemented as contiguous memory, that might explain why "array" wasn't used as a name. However, I still feel that "vector" was a poor name in that it's not a vector in any sense of the word. At least the std::vector interface shares almost all of the qualities of an array. So much so that I say it is still a much better name than "vector"...