From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id C9EF47EF5E for ; Thu, 14 Jul 2016 21:10:55 +0200 (CEST) IronPort-PHdr: 9a23:QyHGTBGQ5qu1NPYWHdBkKp1GYnF86YWxBRYc798ds5kLTJ75rsywAkXT6L1XgUPTWs2DsrQf2rKQ7/qrADVRqb+681k6OKRWUBEEjchE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i760zceF13FOBZvIaytQ8iJ3pzxi7r5osSCKyxzxxOFKYtoKxu3qQiD/uI3uqBFbpgL9x3Sv3FTcP5Xz247bXianhL7+9vitMU7q3cYjck87NZNWrnWeKExTLoQTGh3cjN92Mq+nhnZTBCT4WMcZUWInRdSS1zO7Av7RYv2qiu8tu1w1ySAFdHrCLo5QzCj6eFnRUm7pj0AMmsW+WvNi8F0xJlQoB+7qgY3l4HdapuUOf44ZajdcMkXX0JOW89QU2pKBYbqPNhHNPYIIesN99q1nFAJtxbrWVih Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=gabriel.scherer@gmail.com; spf=Pass smtp.mailfrom=gabriel.scherer@gmail.com; spf=None smtp.helo=postmaster@mail-it0-f46.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.214.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.214.46 as permitted sender) identity=mailfrom; client-ip=209.85.214.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-it0-f46.google.com) identity=helo; client-ip=209.85.214.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-it0-f46.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CBAABt4odXhi7WVdFchBR8BqcuhX6GNoZ/IoV3AoEsBzsRAQEBAQEBAQERAQEBCAsLCSEvgjIEA4IkAQQBEhEdARsSCwEDAQsGBQQHGh0CAiIBEQEFAQoSBhMSEIdzAQMPCA6lDoExPjGLO4FqgloFhQkKGScDClKDPQEBAQEBAQEBAgEBAQEBAQEYAgYQhhqETYQQXYJUgloFhlQMkj+BXYQ1gnuFTII5jHiCa4tvEh6BDw8lgjqBcyAyhiqBRAEBAQ X-IPAS-Result: A0CBAABt4odXhi7WVdFchBR8BqcuhX6GNoZ/IoV3AoEsBzsRAQEBAQEBAQERAQEBCAsLCSEvgjIEA4IkAQQBEhEdARsSCwEDAQsGBQQHGh0CAiIBEQEFAQoSBhMSEIdzAQMPCA6lDoExPjGLO4FqgloFhQkKGScDClKDPQEBAQEBAQEBAgEBAQEBAQEYAgYQhhqETYQQXYJUgloFhlQMkj+BXYQ1gnuFTII5jHiCa4tvEh6BDw8lgjqBcyAyhiqBRAEBAQ X-IronPort-AV: E=Sophos;i="5.28,364,1464645600"; d="scan'208,217";a="226739530" Received: from mail-it0-f46.google.com ([209.85.214.46]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 14 Jul 2016 21:10:54 +0200 Received: by mail-it0-f46.google.com with SMTP id u186so661711ita.0 for ; Thu, 14 Jul 2016 12:10:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=iFszr2aZea/Jos8iP47HfQueBPgTINAjVutk7OEraw8=; b=gouvJiienQNAjCL9sl5ZdFxA5VnNq/Gn0dYUV5ZLcKPpRQaVkSooEKpbeh0H+oRIN+ YmY99Xz0WY/d+qMMHoUM6FtmIqiq1+HwBXZldCtWJ+nmQnb+NmPloXfTI5dvofiqyG6u fibotTtnvPW5qgvRmeODP7imZdqmHkWhSJyX7EmizQSKMRVI1UZOCMwAe7RTJzz27Si/ tDJTONkaU+ndT0Yh0B4oDRwZVFk735wrp7QiWzRD4zr/Z1v0solodzQAKyvnPXAzOWYn Bblo7XFea/u9ify0pkS98brlM856PVs4ya3/AEqZdrg0mFR7XrwixfMLgxFixeBz4j6U iTVw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=iFszr2aZea/Jos8iP47HfQueBPgTINAjVutk7OEraw8=; b=UbKP7M47mImRdc6u3zQxQDac9YPD1YqGIjfq2Rg7jAVGSnpb/6pZVFfSGXc7R0zOD5 nqnb3Pl9zK9E8MRsvNVnNjvTnb2LHJe7JDqmbqPfzABNt+FFSoRDhioxjO0VIvZe3Ue1 DxK9AiTr8Uy+H6jExgcEQgZgp3Gp5LEQKUO+E9elwZUT+dm2mguREJpfhdFR65mHNQ0H 19Qal4dZZeJww1GgfhjGTkx3y9lCaLYsqnzLspWU+wjvazOW/gRdrvbvdH5Jd3qaQxlR 6JbXNmK5A/FltAlJH5qVZmQ730NBamr3OoQxbz8CeUJPX3sBaKKJ2ikEJGhXRbkyxxK5 KrLQ== X-Gm-Message-State: ALyK8tIE8eJPAsxqOGYUebYFRTe/I08REbR3WB0W+t8lOxsg7i9AOUr+DbqtrhvrTsbSzNvR1KSBnHffue3eyQ== X-Received: by 10.36.55.133 with SMTP id r127mr2377421itr.15.1468523453456; Thu, 14 Jul 2016 12:10:53 -0700 (PDT) MIME-Version: 1.0 Received: by 10.79.68.130 with HTTP; Thu, 14 Jul 2016 12:10:13 -0700 (PDT) In-Reply-To: References: <2a4393e2-eea1-1876-f29a-188ed992e5b4@tu-berlin.de> From: Gabriel Scherer Date: Thu, 14 Jul 2016 15:10:13 -0400 Message-ID: To: =?UTF-8?Q?Christoph_H=C3=B6ger?= Cc: caml users Content-Type: multipart/alternative; boundary=001a114066e6c9de6105379d425a Subject: Re: [Caml-list] Map that maintains insertion-order on keys --001a114066e6c9de6105379d425a Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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=C3=B6ger < 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))))) =3D!=3D [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=C3=B6ger > > Technische Universit=C3=A4t Berlin > Fakult=C3=A4t IV - Elektrotechnik und Informatik > =C3=9Cbersetzerbau 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 > --001a114066e6c9de6105379d425a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
You could use a pair of:
- a map and
- a list of we= ak pointers to keys with a count of present items and deleted items (you wo= uld compact the list whenever there are more deleted items than present ite= ms)

Why the counts: removing items from the list on deletion is too = slow.
Why the weak pointers: using keys directly could increase their li= fetime 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= =C3=B6ger <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 whi= ch 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.<= br>
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))))) =3D!=3D [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=C3=B6ger

Technische Universit=C3=A4t Berlin
Fakult=C3=A4t IV - Elektrotechnik und Informatik
=C3=9Cbersetzerbau und Programmiersprachen

Sekr. TEL12-2, Ernst-Reuter-Platz 7, 10587 Berlin

Tel.: = +49 (30) 314-24890
E-Mail: christoph.hoeger@t= u-berlin.de

--
Caml-list mailing list.=C2=A0 Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocam= l_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

--001a114066e6c9de6105379d425a--