Topic: Is memory in a vector<T> contiguous?


Author: jpotter@falcon.lhup.edu (John Potter)
Date: 1999/12/08
Raw View
On 07 Dec 99 16:24:39 GMT, phalpern@newview.org (Pablo Halpern) wrote:

: I just looked it up, and you're right. An insert or erase at either end
: of a deque will invalidate iterators (but not references) into the
: deque. Any idea why this is true (especially for the end of the deque)?

Typically, deque is an array of pointers to arrays of T.  An iterator
must keep track of where in the array of pointers as well as where in
the array of T.  If the rightmost array of T is full and a push_back
is performed, it is possible to shift all of the pointers left and
add a new array of T to the right end.  It is also possible to allocate
a new array of pointers.  The references are still valid but the
iterators are now hopelessly lost.

John
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: phalpern@newview.org (Pablo Halpern)
Date: 1999/12/07
Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote:

>John Aldridge wrote:
>>
>> There is one.  It's called std::deque<>.
>
>It's not a perfect replacement; you can't reserve() space in a deque<>.
>A vector<> with an active reservation leaves some iterators or
>references valid under some circumstances where deque<> wouldn't. Not a
>big disadvantage, but there's probably some context where it matters.

I just looked it up, and you're right. An insert or erase at either end
of a deque will invalidate iterators (but not references) into the
deque. Any idea why this is true (especially for the end of the deque)?
Up until now I could not think of any reason to have both vector<> and
deque<> unless vector<> had an additional guarantee of being
continguous. I still favor adding that requirement, but I see that there
is at least one place where deque cannot be used as a drop-in
replacement for vector.

---------------------------------------------------------------
Pablo Halpern                              phalpern@newview.org
Check out my new book, The C++ Standard Library from Scratch at
http://www.halpernwightsoftware.com/stdlib-scratch
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: Paul Moore <gustav@morpheus.demon.co.uk>
Date: 1999/11/30
Raw View
I seem to recall seeing this here some time ago, but I can't find the
reference. Is it valid to assume that memory in a vector<T> is
allocated contiguously? In other words, is it OK, given

    vector<int> vi;

to pass &vi[0] to a function which expects a pointer to an array of
ints - ie an int*?

Without guarantees like this, I can see myself doing a *lot* of
copying of arrays between int[] and vector<int> (or whatever) - given
that legacy functions will be around for a *long* time yet.

Thanks for any comments,
Paul Moore.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]





Author: bs@research.att.com (Bjarne Stroustrup)
Date: 1999/11/30
Raw View

Paul Moore <gustav@morpheus.demon.co.uk> writes:

> I seem to recall seeing this here some time ago, but I can't find the
> reference. Is it valid to assume that memory in a vector<T> is
> allocated contiguously? In other words, is it OK, given
>
>     vector<int> vi;
>
> to pass &vi[0] to a function which expects a pointer to an array of
> ints - ie an int*?

Yes. The committee considered the issue and found that eventhough there was
no such guarantee in the standard, one had been intended. Consequently, it
was decided that unless some killer argument emerges (and naturally the
committee looked hard at the pros and cons without spotting such an argument
before voting) the guarantee will be part of the next revision.

Resolutions and clarifications of this sort are posted on a publically
accessible committee website.


> Without guarantees like this, I can see myself doing a *lot* of
> copying of arrays between int[] and vector<int> (or whatever) - given
> that legacy functions will be around for a *long* time yet.

Exactly. Far too long a time in many cases, but we can't ignore "legacies."

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


> Thanks for any comments,
> Paul Moore.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: 1999/11/30
Raw View
Paul Moore wrote:
>
> I seem to recall seeing this here some time ago, but I can't find the
> reference. Is it valid to assume that memory in a vector<T> is
> allocated contiguously? In other words, is it OK, given
>
>     vector<int> vi;
>
> to pass &vi[0] to a function which expects a pointer to an array of
> ints - ie an int*?
>
> Without guarantees like this, I can see myself doing a *lot* of
> copying of arrays between int[] and vector<int> (or whatever) - given
> that legacy functions will be around for a *long* time yet.

There is no such guarantee. Many people, including Stroustrup himself,
have said that contiguous allocation was intended. Most existing
implementations make contiguous allocations. It's been claimed that you
can't meet the complexity requirements with a non-contiguous
allocations, but it's quite possible to meet them by using fixed-size
multi-record blocks. It's been strongly suggested that the standard will
be changed in the future to require contiguous allocation, but that
hasn't been done yet. Unless it's treated as a defect fix, such a change
will have to wait till the next release of the standard, say in 2008 or
so.

In the meantime, if you want such a guarantee, consider using
std::valarray<>. Section 26.3.2.3 says "The expression &a[i+j] == &a[i]
+ j evaluates as true for all size_t i and size_t j such that i+j is
less than the length of the non-constant array a." Since, for
non-constant valarrays, operator[] must return at T&, and according to
26.1p1, T is not allowed to overload operator&(), that is a guarantee of
contiguous allocation. There's no comparable wording for std::vector<>
(or for a const valarray, for that matter!)

Unfortunately, there are number of inconvenient limitations on using
std::valarray<T>. See section 26.1p1 for the restrictions on T. In
addition, it lacks equivalents for insert() and erase(), and for any of
the other std::vector<> functions defined in terms of those two.

I like the idea of a container that doesn't require contiguous
allocation; only with such a container could you store more objects than
will fit in any single available contiguous block of memory. Whether
that container should be std::vector<> is another question.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: John Aldridge <jpsa@jjdash.demon.co.uk>
Date: 1999/12/01
Raw View
In article <384337CC.B59BEB1D@wizard.net>, James Kuyper Jr.
<kuyper@wizard.net> writes
>
>Paul Moore wrote:
>>
>> I seem to recall seeing this here some time ago, but I can't find the
>> reference. Is it valid to assume that memory in a vector<T> is
>> allocated contiguously?

>I like the idea of a container that doesn't require contiguous
>allocation; only with such a container could you store more objects than
>will fit in any single available contiguous block of memory. Whether
>that container should be std::vector<> is another question.

There is one.  It's called std::deque<>.
--
Cheers,
John


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]






Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: 1999/12/01
Raw View
John Aldridge wrote:
>
> In article <384337CC.B59BEB1D@wizard.net>, James Kuyper Jr.
> <kuyper@wizard.net> writes
> >
> >Paul Moore wrote:
> >>
> >> I seem to recall seeing this here some time ago, but I can't find the
> >> reference. Is it valid to assume that memory in a vector<T> is
> >> allocated contiguously?
>
> >I like the idea of a container that doesn't require contiguous
> >allocation; only with such a container could you store more objects than
> >will fit in any single available contiguous block of memory. Whether
> >that container should be std::vector<> is another question.
>
> There is one.  It's called std::deque<>.

It's not a perfect replacement; you can't reserve() space in a deque<>.
A vector<> with an active reservation leaves some iterators or
references valid under some circumstances where deque<> wouldn't. Not a
big disadvantage, but there's probably some context where it matters.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]