Re: Growable arrays?

[Daniel Hartwig <mandyke@gmail.com>]

On 11 June 2012 12:37, David Kastrup <dak@gnu.org> wrote:
> What is a vlist?

vlist is a data type introduced around guile 2.0.  You will find it
documented in the Guile Reference under Compound Data Types.

They are growable and provide vector-like access performances and
memory locality.

>>> Now it would be possible when the type lattice gets extended to store
>>> the new entries in a hashtable and go from there.
>>
>> Why not use a hash for everything?  Unless your initial lattice is
>> very large there would be relatively small loss in performance.
>
> About double the memory impact (vector->1 cell, hash table->1 cell per
> hash bucket+1 additional cons cell per element) and much slower copying.
> And quite slower access.
>

With these concerns your only options are really vlist or implementing
growable vector.

>>>  Or put them into a
>>> list, and reallocate on first access beyond the existing element.  That
>>> seems rather contorted.
>>
>> You mean “put them into a /vector/”?
>
> No, since a vector can't be grown.  This would basically switch the data
> structure between "write" and "read" mode, where "write mode" grows the
> list of additions, and "read mode" accesses the vector.  Switching from
> write to read entails creating a newly allocated vector and copying the
> new additions from the list as well as the old vector into it.

I see, that is rather contorted :-)