On Thursday 17 October 2002 11:05 pm, Eray Ozkural wrote:
> 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.

This is exactly what I meant when I wrote "memory is reserved in chunks 
automatically ... " above.  

(BTW might I suggest you save the condescending tone for somewhere else?)

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

Which is why I asked for it.

Oleg

P.S. You keep replying to messages that are over THREE months old and 
probably long since lost their relevance: e.g. my question has been answered 
(see RES by Markus Mottl)
-------------------
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