Is std::vector contiguous?

Discussion in 'C++' started by Ravi, Mar 5, 2004.

  1. Ravi

    Ravi Guest

    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.
     
    Ravi, Mar 5, 2004
    #1
    1. Advertising

  2. Ravi

    Mike Smith Guest

    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
     
    Mike Smith, Mar 5, 2004
    #2
    1. Advertising

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

    Remove the 'g' from my address to send me mail.
     
    Russell Hanneken, Mar 5, 2004
    #3
  4. > * 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
     
    Massimiliano Alberti, Mar 5, 2004
    #4
  5. "Ravi" <> wrote in message
    news:c2ag9f$j0t$...
    > 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
     
    Jonathan Turkanis, Mar 5, 2004
    #5
  6. Ravi

    Leor Zolman Guest

    On Fri, 5 Mar 2004 15:57:14 -0700, "Jonathan Turkanis"
    <> wrote:

    >
    >"Ravi" <> wrote in message
    >news:c2ag9f$j0t$...
    >> 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

    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
     
    Leor Zolman, Mar 5, 2004
    #6
  7. 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

    Remove the 'g' from my address to send me mail.
     
    Russell Hanneken, Mar 5, 2004
    #7
  8. Russell Hanneken <> wrote in message news:<4K32c.22875$>...
    > 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
     
    Bjarne Stroustrup, Mar 5, 2004
    #8
  9. Ravi

    Mike Wahler Guest

    "Ravi" <> wrote in message
    news:c2ag9f$j0t$...
    > 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
     
    Mike Wahler, Mar 6, 2004
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Newsgroup - Ann
    Replies:
    0
    Views:
    415
    Newsgroup - Ann
    Aug 15, 2003
  2. Anonymous
    Replies:
    20
    Views:
    4,427
    Pete Becker
    Mar 30, 2005
  3. Jason Heyes
    Replies:
    8
    Views:
    767
    Andrew Koenig
    Jan 15, 2006
  4. Replies:
    3
    Views:
    404
    James Kanze
    Dec 21, 2007
  5. Rune Allnor
    Replies:
    4
    Views:
    992
    Rune Allnor
    Dec 11, 2008
Loading...

Share This Page