Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Is std::vector contiguous?

Reply
Thread Tools

Is std::vector contiguous?

 
 
Ravi
Guest
Posts: n/a
 
      03-05-2004
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.
 
Reply With Quote
 
 
 
 
Mike Smith
Guest
Posts: n/a
 
      03-05-2004
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

 
Reply With Quote
 
 
 
 
Russell Hanneken
Guest
Posts: n/a
 
      03-05-2004
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.


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
http://www.velocityreviews.com/forums/(E-Mail Removed)
Remove the 'g' from my address to send me mail.
 
Reply With Quote
 
Massimiliano Alberti
Guest
Posts: n/a
 
      03-05-2004
> * 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


 
Reply With Quote
 
Jonathan Turkanis
Guest
Posts: n/a
 
      03-05-2004

"Ravi" <(E-Mail Removed)> wrote in message
news:c2ag9f$j0t$(E-Mail Removed)...
> 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


 
Reply With Quote
 
Leor Zolman
Guest
Posts: n/a
 
      03-05-2004
On Fri, 5 Mar 2004 15:57:14 -0700, "Jonathan Turkanis"
<(E-Mail Removed)> wrote:

>
>"Ravi" <(E-Mail Removed)> wrote in message
>news:c2ag9f$j0t$(E-Mail Removed).. .
>> 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 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
 
Reply With Quote
 
Russell Hanneken
Guest
Posts: n/a
 
      03-05-2004
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?

--
Russell Hanneken
(E-Mail Removed)
Remove the 'g' from my address to send me mail.
 
Reply With Quote
 
Bjarne Stroustrup
Guest
Posts: n/a
 
      03-05-2004
Russell Hanneken <(E-Mail Removed)> wrote in message news:<4K32c.22875$(E-Mail Removed) thlink.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
 
Reply With Quote
 
Mike Wahler
Guest
Posts: n/a
 
      03-06-2004

"Ravi" <(E-Mail Removed)> wrote in message
news:c2ag9f$j0t$(E-Mail Removed)...
> 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


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments