Re: Growable arrays?

[David Kastrup]

Mark H Weaver <address@hidden> writes:

> David Kastrup <address@hidden> writes:
>> Mark H Weaver <address@hidden> writes:
>>> C++, like Scheme, already supports fixed-size vectors in the core
>>> language, so it would be redundant to include them in a library.
>>
>> A vector with run-time determined size?  Which variant of C++ offers
>> that?
>
> Um, this is basic functionality that has been available in C since the
> beginning, e.g.: int *v = malloc (len * sizeof(int)).

That does not offer reflection of the length, so you are talking about a
different beast here.

> Admittedly, I've not written a single line of C++ in the last 15
> years, but as I recall C++ has the new[] operator that handles this
> nicely for arbitrary classes.

Still no reflection about the length.

>>> If C++ supported _only_ resizable vectors, such that there was no way
>>> to avoid the additional level of pointer indirection, and all derived
>>> data structures had to be built upon these doubly-indirected vectors,
>>> then I'd expect that the efficiency impact would be quite significant
>>> in both time and space.
>>
>> Reality check: C++ does not offer structs/classes containing vectors of
>> run-time determinable size.  You need to allocate a pointer for them.
>
> Yes, of course you need to allocate a block, and you need to do that
> for Scheme vectors as well.  However, a resizable vector object needs
> _two_ blocks: one block containing the elements, and another block
> containing the length and the pointer to the elements.  That means
> _two_ pointer lookups to access an element, as opposed to one for
> fixed-size vectors.

Reality check: this is _exactly_ what you need to do in C++ unless you
choose _not_ to store the length as part of the vector.  One lookup to
the block containing length and pointer to data, one lookup to get to
the data.

-- 
David Kastrup