[Haskell-cafe] Advice needed on best way to simulate an STL vector

[Cale Gibbard]

Well, you could use something like C++ does for implementing STL
vectors in terms of arrays -- iirc, it generally doubles the allocated
size each time applying an operation to the vector would make it
exceed its capacity (the current allocation size), and keeps track of
the actual number of elements stored separately. It's important to do
allocation which is proportional to the existing capacity, or repeated
insertion will become quadratic time rather than linear. So
essentially, some data structure like

data Vector a = Vector { store :: Array Int a, end :: Int }

would be a sufficient minimal way to start. When the store needs to be
increased, you simply create a new array with twice as many elements,
copy the initial elements in from the old array which is then thrown
away, and only update end to the position of the actual last element.
This is analogous to what C++ implementations of the vector class do.

What will bite you is if you try to generalise from indices of type
Int to instances of Ix -- the Ix operations assume that there are
lower and upper bounds on indices. The upper bound of course quickly
becomes a problem. You could however use Enum, which has toEnum and
fromEnum, which are sufficient to use with the implementation in terms
of Ints. It could also be claimed that Int isn't always the best
initial type to use, and indeed I'd still feel safer with Integer
somehow, but then, fromEnum and toEnum use Int, and if you have more
than 2 billion elements in your vector at the same time, maybe you
should be looking at your algorithm more carefully and/or doing your
own low level memory allocation via FFI. :)

 - Cale

On 19/04/06, Brian Hulley <brianh at metamilk.com> wrote:
> Hi -
> In C++, STL provides a vector class which behaves as an array except you can
> insert/delete elements from it. I'm wondering what is the best Haskell data
> structure to use to simulate this, either mutable or immutable.
>
> I've looked at the Array interface, but although there is the // operation
> to replace some elements, there does not appear to be a simple way to
> delete/insert elements.
>
> Ideally I'd like functions like:
>
> -- Insert new elements starting at the specified index, moving the others up
> to make room
> insert:: Array i e -> i -> [e] -> Array i e
>
> -- Delete a range of elements, moving later elements back down
> delete:: Array i e -> i -> i -> Array e
>
> -- Append a new element to the end of an array
> push_back :: Array i e -> e -> Array i e
>
> Is there an efficient way of implementing these operations in Haskell, based
> on arrays, or should I be using some other data structure altogether eg a
> list?
>
> Also, for large arrays, am I right in thinking that it is still more
> efficient to use immutable arrays rather than mutable arrays (because it is
> easier for gc to always just deal with immutable values)?
>
> Thanks, Brian.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>