Re: [Caml-list] Array.resize ?

[Eray Ozkural <erayo@cs.bilkent.edu.tr>]

On Friday 12 July 2002 01:30, Oleg wrote:
> Hi
>
> Is there an efficient way in O'Caml to append an element to an array ref?
>
> let append_elt r x = r := Array.append !r [| x |];;
>
> copies the contents of the whole array in its body, while e.g. C++ vector
> push_back in most cases won't (memory is reserved in chunks automatically,
> or it can be reserved manually)

Hi Oleg,

Here is some Data Structures 101 for you.

A vector is not an array. It is more like one of the "extensible array" types 
that are around since 1960's. The implementation of vector types use what we 
call an open table with amortized time for n consequent inserts being O(n) 
making a single insert O(1). (See the MIT Algorithms textbook for details) 
This also answers why memory alloc doesn't cost much when using vectors. 
Since the array is expanded or contracted by a factor of 2 in size you need 
only a logarithmic number of memory allocation calls.

A vector is not a special type in C++. You can implement one in ocaml just as 
well or better.

Cheers,

-- 
Eray Ozkural <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners