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]

Ravi wrote:

> 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.

--
Mike Smith

[Russell Hanneken]

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.

--
Russell Hanneken
rghan...@pobox.com
Remove the 'g' from my address to send me mail.

[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]

"Ravi" <rg...@cse.buffalo.edu> wrote in message
news:c2ag9f$j0t$1...@prometheus.acsu.buffalo.edu...

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]

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
le...@bdsoft.com
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]

Jonathan Turkanis wrote:
> 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]

Russell Hanneken <rghan...@pobox.com> wrote in message news:<4K32c.22875$aT1....@newsread1.news.pas.earthlink.net>...

> Ravi wrote:
> > 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.

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]

"Ravi" <rg...@cse.buffalo.edu> wrote in message
news:c2ag9f$j0t$1...@prometheus.acsu.buffalo.edu...

> 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