Is std::vector contiguous?

[Ravi]

Is a std::vector *guaranteed* to be contiguous in memory? Bjarne
Stroustrup says it takes constant time to access a vector element and
that implies contiguous storage but I just wanted to double-check. I
heard that ISO 14882 standard did not guarantee this. Has this changed?
Any pointers will be appreciated.
Thanks,
Ravi.

 

[Mike Smith]

Is a std::vector *guaranteed* to be contiguous in memory? Bjarne
Stroustrup says it takes constant time to access a vector element and
that implies contiguous storage

Not necessarily; it could mean that there is an array of pointers to
elements, and that the array is contiguous.

 

[Russell Hanneken]

Is a std::vector *guaranteed* to be contiguous in memory? Bjarne
Stroustrup says it takes constant time to access a vector element and
that implies contiguous storage but I just wanted to double-check. I
heard that ISO 14882 standard did not guarantee this. Has this changed?
Any pointers will be appreciated.

Karl Heinz Buchegger summarized the situation nicely in this post:

http://tinyurl.com/36adz

Quoting Karl:

The concensus is this:

* There is no guarantee
* This has probably been an oversight while comming up with the
standard
* The next version of the standard will guarantee this
* It is hard or impossible to fullfill the requirements of
std::vector if the data is not stored contigous
* There is no known version which does not store the data
contigous.

 

[Massimiliano Alberti]

* It is hard or impossible to fullfill the requirements of

std::vector if the data is not stored contigous

Why would it be impossible to fullfill the requirements by using a
trasparent array of pointers? (the external program doesn't see pointers...
The Vector class hide them)
I could conceive an implementation that stores POD directly in the vector
and class/structures in pointers.

--- bye

 

[Jonathan Turkanis]

Is a std::vector *guaranteed* to be contiguous in memory? Bjarne
Stroustrup says it takes constant time to access a vector element and
that implies contiguous storage but I just wanted to double-check. I
heard that ISO 14882 standard did not guarantee this. Has this changed?
Any pointers will be appreciated.

A vector's storage is guaranteed to be contiguous. From ISO 14882, 2nd
ed., 23.2.4 [lib.vector]:

"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()."

Jonathan

 

[Leor Zolman]

Is a std::vector *guaranteed* to be contiguous in memory? Bjarne
Stroustrup says it takes constant time to access a vector element and
that implies contiguous storage but I just wanted to double-check. I
heard that ISO 14882 standard did not guarantee this. Has this changed?
Any pointers will be appreciated.

A vector's storage is guaranteed to be contiguous. From ISO 14882, 2nd
ed., 23.2.4 [lib.vector]:

"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()."

Jonathan

Right, I believe it is whether or not it uses a "dynamic array" that isn't
(yet) nailed down in the standard. See Josuttis, the start of section 6.2.
-leor


Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

 

[Russell Hanneken]

A vector's storage is guaranteed to be contiguous. From ISO 14882, 2nd
ed., 23.2.4 [lib.vector]:

I guess my copy of the standard is out of date. So this was fixed in
Technical Corrigendum 1?

 

[Bjarne Stroustrup]

Yes. The 2003 "technical corrigendum" corects that. 23.2.4[1] says
"The elements of a vector are stored contiguously".

As Russell pointed out, this was always the intent and all
implementations always did it that way

-- Bjarne Stroustrup; http://www.research.att.com/~bs

 

[Mike Wahler]

Is a std::vector *guaranteed* to be contiguous in memory? Bjarne
Stroustrup says it takes constant time to access a vector element and
that implies contiguous storage but I just wanted to double-check. I
heard that ISO 14882 standard did not guarantee this. Has this changed?

I think this is mandated in TC1

-Mike