TITLE: STL vector and contiguousness requirement

(Newsgroups: comp.lang.c++.moderated,comp.std.c++, 6 May 98)


GARNER: peter.garner@toward.com (Peter Garner)

[snip]
> I have read books that state that
> vector is a CONTIGUOUS array.   I think a lot of
> people are under that (mis)impression.  According
> to "The STL Tutorial and Reference Guide" by
> Musser and Saini (ISBN 0-201-63398-1) in section
> 19.3.3 it states that "Vectors are containers that
> arrange elements of a given type in a strictly linear
> arrangement and allow fast random access to any
> element (i.e. any element can be accessed in
> constant time). "


JKANZE: jkanze@otelo.ibmmail.com

IMHO, this does not say that the elements of the vector must
be stored in contiguous memory locations.  My own dynamic
array class met these requirements, but did not store elements
contiguously.

Unless I've misunderstood something, linear, in this context,
means that for i < j, if v[ i ] exists and v[ j ] exists, all
intermediate elements also exist.  (A linked list is also linear.)

Access in constant time means just that, and says nothing concerning
the arrangement in memory.


GARNER:

> Of course this is just an author's
> opinion not the ISO Standard.  Of course this goes
> to show that others, (including myself) have made
> the assumption that vectors are contiguous and
> linear.


KANZE:

I presume that people make this assumption because of the name, and
not from anything in the description of the class.  And far too many
people just look at the implementation on their machine, and suppose
that it is universal.


GARNER:

> Frankly if the committee does not clarify
> this in a such a manner as to support the idea
> that vectors are contiguous it will necessitate
> the rewrite of a great deal of code of which I
> am aware.


KANZE:

The same could be say about modifying a variable twice without an
intervening sequence point.  When I first started using C, the same
could be said about dereferencing a null pointer.  (In the early '80s,
most Unix implementations mapped the address 0 to a block of memory
that contained zeros, and there was a lot of code which used the null
pointer and "" interchangeably.)

The fact that people write incorrect code that happens to work on
one particular implementation is not a valid motive for modifying the
standard.


GARNER:


> I SERIOUSLY doubt that ANYONE
> has written code that depends upon vectors
> being NON-CONTIGUOUS.


KANZE:

Of course not.  Since it is not guaranteed.  But I find it hard to
believe that any professional has written code that depended on vectors
being contiguous.  Such code certainly wouldn't get through any serious
code reveiw.


GARNER:

> For this reason
> I encourage all involved parties to consider
> clarifying the Standard so that it requires
> vectors to be implemented in a contiguous
> fashion.


KANZE:

And break my implementation:-)?

(Seriously, insofar as vector is the official alternative to C style
arrays, and there are no fixed length vectors which don't use dynamic
allocation, I would be extremely surprised if any implementation did
not use contiguous memory, since it results in additional run-time
overhead in operator[]. My solution, however, would be to define a
static
vector, whose length was a template argument, and which would guarantee
basically the same as what is guaranteed by C style arrays: contiguous
memory, no dynamic allocations within the vector, and the size
determined
by size()*sizeof( ElementType ).