10

Possible Duplicates:
Is it safe to assume that STL vector storage is always contiguous?
Are std::vector elements guaranteed to be contiguous?

Ideally, std::vector would be guaranteed to be contiguous. According to this post it seems like that is a bad assumption. I guess I really have two questions: 1) Is it really evil to assume that std::vector<> is contiguous? 2) If so, what alternatives exist?

10

The original C++ standard - C++98 - did not make such a guarantee. This was corrected later and the current C++ standard - C++03 - guarantees it. Moreover, I'm not aware of any implementation of C++ standard library that would store vector elements non-contiguously.

From the very pedantic point of view, the answer you linked was correct for its time, but no longer. It is obsolete now. You can safely rely one the fact that vector elements are stored contiguously.

7

std::vector is guaranteed to be contiguous. That person doesn't know what he's talking about. It uses an array internally, and if arrays aren't contiguous then I don't know what is.

7

The standard requires continuous storage 23.2.4 [lib.vector]/1:

A vector is a kind of sequence that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

5

std::vector offers guaranteed O(1) random access. It's hard to imagine how you'd implement that without contiguity (ETA: actually it's not, see the comments for a few reasonable approaches). I don't think it's evil to rely on that, but I'd question why you need to. What do you want to do that can't be done with iterators and operator[]?

5 accepted

There's been an interesting "exchange" on this between Andrew Koenig and Herb Sutter.

Koenig posted on his blog the following: Questions that make me cringe

and Sutter responded with this: Cringe not: Vectors are guaranteed to be contiguous

in which he says:

"It?s so important, in fact, that when it was discovered that the C++98 standard didn?t completely guarantee contiguity, the C++03 standard was amended to explicitly add the guarantee."

3

From cplusplus.com:

Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

While that site isn't the official spec, I've never seen a vector that was implemented any other way.

1

I believe the elements of a vector are guaranteed to be stored contiguously. http://www.cplusplus.com/reference/stl/vector/

Also answered here.

1

Vectors are guaranteed to be contiguous. See a later post on that exact same thread.

1

std::vector<> guarantees contiguous allocation. What may happen is, in the case of a reallocation, the array moves to another memory block, and all references are thus invalidated. This can be avoided with reserve().

0

The post is correct in that there is no known implementation where the data is not stored contiguously. However, if you need to seek alternatives then use Boost Array. It is essentially a safer array.

0

std::vector is guaranteed to be contiguous. But std::string is not.

-2

For what it's worth, there's been talk about adding a requirement that std::vector be contiguous to the standard, since this is such a common use case and there's no proper alternative within the standard library. For example how do you pass a managed buffer to ostream::write if it's not &vec[0]?

-3

According to the post you quoted, and everything I know about it, it's safe to assume contiguity. It isn't actually mandated, but everybody acts like it is, and implementors would have to go to extra work to make it non-contiguous.

For your second question, what sort of alternative would you look for? What is it that you need absolutely guaranteed contiguity for, and what are you going to use it for?