473,320 Members | 1,940 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Is std::vector contiguous?

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.
Jul 22 '05 #1
8 2364
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

Jul 22 '05 #2
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
rg********@pobox.com
Remove the 'g' from my address to send me mail.
Jul 22 '05 #3
> * 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
Jul 22 '05 #4

"Ravi" <rg**@cse.buffalo.edu> wrote in message
news:c2**********@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? 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
Jul 22 '05 #5
On Fri, 5 Mar 2004 15:57:14 -0700, "Jonathan Turkanis"
<te******@kangaroologic.com> wrote:

"Ravi" <rg**@cse.buffalo.edu> wrote in message
news:c2**********@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?
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
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
Jul 22 '05 #6
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
rg********@pobox.com
Remove the 'g' from my address to send me mail.
Jul 22 '05 #7
Russell Hanneken <rg********@pobox.com> wrote in message news:<4K*******************@newsread1.news.pas.ear 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
Jul 22 '05 #8

"Ravi" <rg**@cse.buffalo.edu> wrote in message
news:c2**********@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
Jul 22 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: Newsgroup - Ann | last post by:
Hi: I saw the following codes from the FAQ about the contiguous storage of vector. I am just wondering how does the implementation of the <vector> guarantee the contiguous? What if a vector v...
6
by: isaacyho | last post by:
Is there a fast way to crop a vector? I have a vector of size n, and want to reduce it to some subregion (x,y ). Seems like you shouldn't have to recopy all of those elements into a new vector,...
1
by: Alex Vinokur | last post by:
Testsuites "Comparative Performance Measurement. Reading file into string" at http://groups.google.com/group/perfo/msg/8273f4d1a05cfbd1 http://groups.google.com/group/sources/msg/27a9b6f91239c909...
8
by: Ross A. Finlayson | last post by:
I'm trying to write some C code, but I want to use C++'s std::vector. Indeed, if the code is compiled as C++, I want the container to actually be std::vector, in this case of a collection of value...
6
by: slyi | last post by:
Is it ok to assume that the following assertion is valid for all implementations of std::vector?: std::vector<T> v(10); T* p = &v; for (size_t n=0; n < v.size(); n++) assert( p+n == &v ); ...
4
by: mathieu | last post by:
Hello, I am looking at the API of std::vector but I cannot find a way to specify explicitely the size of my std::vector. I would like to avoid vector::resize since it first initializes the...
4
by: Bobrick | last post by:
Hi. I'm in the process of making a GUI for a function someone else wrote, and i've come across a type i'm unfamiliar with, namely "std::vector<unsigned char>". I need to get the contents of this...
3
by: n.torrey.pines | last post by:
I'd like to be able to view two contiguous elements of a vector as a pair. Assuming I'm not accessing the last element, of course, and the element type is not bool, when is it safe to do so,...
3
by: MacApp | last post by:
I read in http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69 they proposed: My question is: does the above implies the: (Type *) &v<char>==(Type *)(&v<char> + n*sizeof (Type));...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.