On 22/11/2013 04:32 PM, Warp wrote:
> Orchid Win7 v1<voi### [at] devnull>  wrote:
>> So there is literally only one possible implementation for vector?
>
> Not really. For example, the standard doesn't make guarantees about
> when exactly reallocation happens when you keep adding elements to
> the vector, or how much the capacity is increased each time it happens.
> That's up to the implementation. (The only thing that the standard
> guarantees is that adding new elements at the end of the vector is
> amortized-constant-time.)
>
> It also doesn't give promises about where the allocated memory will be.
> (For example, it would be perfectly possible for a std::vector
> implementation to use a "short vector optimization", which would be
> similar to the concept of "short string optimization". All this would
> be completely transparent to the outside.)
>
> The only thing it does guarantee is that the memory allocated by
> std::vector will be contiguous (like with 'new[]'), and a pointer
> to one of its elements will work the same as a pointer to an element
> in a raw array.
>
> (Note that if you add a new element to a std::vector, any existing
> iterators and pointers to it are invalidated. This is because if
> reallocation happens, they will end up pointing to freed memory,
> and thus using them after that is a no-no.)

That makes sense, I guess...

(One helpful commenter pointed out that std::vector<bool> is allowed to 
behave differently, though.)

I did enjoy the guy who claimed that because you're guaranteed O(1) 
access time, it must be a continuous array. O RLY? Because I'm pretty 
sure I can come up with an O(1) implementation that isn't contiguous...

Post a reply to this message