You could use a pair of:
- a map and
- a list of weak pointers to keys with a count of present items and deleted
items (you would compact the list whenever there are more deleted items
than present items)

Why the counts: removing items from the list on deletion is too slow.
Why the weak pointers: using keys directly could increase their lifetime
after they have been deleted from the map.
If you don't need deletion, just a list of keys is fine.

On Thu, Jul 14, 2016 at 2:44 PM, Christoph Höger <
christoph.hoeger@tu-berlin.de> wrote:

> Am 14.07.2016 um 20:35 schrieb Jesper Louis Andersen:
> > Hi,
> >
> > Could you give some small example of what you want or a more precise
> > definition? I can think of at least 3 ways to parse meaning out of
> > "gives keys in order of insertion", and I don't know which you might
> want.
>
> What I mean is that a map that is created by consecutive Map.add
> applications, yields the keys in the order of the add() applications, i.e.
>
> Map.keys (Map.add k_n v_n (Map.add k_(n-1) v_(n-1) (Map.add ... (Map.add
> k_1 v_1 Map.empty))))) =!= [k_1; ...; k_(n-1); k_n]
>
> it could also yield [k_n; k_(n-1); ... ;k_1], that does not matter that
> much.
>
>
>
>
>
> --
> Christoph Höger
>
> Technische Universität Berlin
> Fakultät IV - Elektrotechnik und Informatik
> Übersetzerbau und Programmiersprachen
>
> Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin
>
> Tel.: +49 (30) 314-24890
> E-Mail: christoph.hoeger@tu-berlin.de
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>