Re: Growable arrays?

[David Kastrup]

Daniel Hartwig <address@hidden> writes:

> On 11 June 2012 12:37, David Kastrup <address@hidden> 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.

Ah, too bad.  This needs to run under 1.8 as well.

> 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 :-)

Yes, but then it will actually be quite rare that the structure is
extended while it is read rather often.  It would probably do fine to
just do the extension lazily by exception, but then wrapping a catch
around every access is likely to be slower than checking the addition
list to be empty.

-- 
David Kastrup