220 41426 article Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: gogu Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: std::map augmentation Date: Wed, 6 Feb 2019 18:44:00 -0800 (PST) Approved: news@gmane.org Message-ID: Reply-To: std-proposals@isocpp.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_125_1716863266.1549507440797" Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="28792"; mail-complaints-to="usenet@blaine.gmane.org" To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBC727OO73AFRB4NW53RAKGQEMDJKPTA@isocpp.org Thu Feb 07 03:44:07 2019 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yb1-f197.google.com ([209.85.219.197]) by blaine.gmane.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.89) (envelope-from ) id 1grZfY-0007HK-V6 for gclcip-std-proposals@m.gmane.org; Thu, 07 Feb 2019 03:44:05 +0100 Original-Received: by mail-yb1-f197.google.com with SMTP id t3sf4816506ybo.15 for ; Wed, 06 Feb 2019 18:44:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:subject:mime-version:x-original-sender :reply-to:precedence:mailing-list:list-id:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=Iy/UkTCcVw7iX43r9HVdxXMe2yxLs8LrUGbpsubbYZw=; b=2T7DX4yVU9rlQ09iDNxdj80rzzgr9wbRsp3yrRK0mrMn3r84c+l8bxfh0xBi0TZaLZ DIg/QELh+onSZpEwkSEVpvmUPww278euc1ejXdjpYSjFAHEb1sVNQr3sO/OxLGE/khTL 7stHkzSTkLapV/LZd5zzfWZhxzA4O14lj6z3NFcOKcK0XvJDI3I/zmCSwyhHm4zue8bq yhZrf6Cbf0UYmDjEjx3JJzYHg22HScS7vFYPfjFEF/Fy9tFsCf7oQX1i8KwkepK2Zvp9 T5klrVbhFdGMQaNQ21i25ECopeSevZZaSP3A1vmuZgYC9avxq7qMf7/7uKJ5lk9Pq6NX qRsg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=Iy/UkTCcVw7iX43r9HVdxXMe2yxLs8LrUGbpsubbYZw=; b=X/hCs/qyjdDKVd8DuLXzdLYr5d0wXp0jQl6nVHc6T+ZeQnIkfSCYwI0+xbrsumYk7J 6CsD7r0WKlI2xoYW9UjQZnElpMp12IQEQNLXdzftfJj7U8VX6dgWjGydgzRUSQpmK3Jt 4u0oUiYRWcVmJ7zsnGafttVnaaLN0Scx4tvR65+WDM8tX9fKDIOEMMycUgom3fcsyZgf lx//bO3h2c3yXrQf4SbYI3EWNABU18ySqCUt09I6q3WS2n0De5eVG0GS7J8uwoP3oa8s 88djNuwAtSLW2fdj2jnGxI4hlV8AQCglVvc72oYxsBeEFqCnVurnQJk/pPFgdTipGtmy TRoQ== X-Gm-Message-State: AHQUAuZa281Kk4uyC5S2SghLinkvpVsIOYwcXapn+/euBT4G9L1fbI1x RONf/TOS2Zq2S6rw+2Cedx15KA== X-Google-Smtp-Source: AHgI3IYvTBG9D4vHVmazSii0A8vn2r9LeSaO/vjkuU0eW7TjY+yD7cre54StjDNz/Rxyu8gAwH3q+Q== X-Received: by 2002:a5b:98b:: with SMTP id c11mr5788970ybq.90.1549507443622; Wed, 06 Feb 2019 18:44:03 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a25:c042:: with SMTP id c63ls287390ybf.4.gmail; Wed, 06 Feb 2019 18:44:01 -0800 (PST) X-Received: by 2002:a25:ab82:: with SMTP id v2mr138950ybi.3.1549507441627; Wed, 06 Feb 2019 18:44:01 -0800 (PST) X-Original-Sender: valeriu.smerica@my.fmi.unibuc.ro Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:41426 Archived-At: ------=_Part_125_1716863266.1549507440797 Content-Type: multipart/alternative; boundary="----=_Part_126_477192966.1549507440797" ------=_Part_126_477192966.1549507440797 Content-Type: text/plain; charset="UTF-8" Make std::map an order statistic tree. Add another template parameter to std::map before the allocator type that will decide wether or not std::map will be an order statistic tree. Memory will not be wasted. A second node type will be defined in the implementation that also contains the size of the subtree rooted at the node. https://en.wikipedia.org/wiki/Order_statistic_tree The std::map should have two other functions, called select and rank that behave as the wikipedia article says. These should be disabled using std::enable_if_t/concepts on the parameter that decides if the map is an order statistic tree or not. Updating the size of the subtree of a node could be done inside of the already defined functions using if constexpr inside the function. The body of the compile-time if would update that size for each node on the path down to the insertion point. What do you guys think? -- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/ce18cc74-9116-4da6-b320-fe2b4715b1d6%40isocpp.org. ------=_Part_126_477192966.1549507440797 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Make std::map an order statistic tree. Add another te= mplate parameter to std::map before the allocator type that will decide wet= her or not std::map will be an order statistic tree. Memory will not be was= ted. A second node type will be defined in the implementation that also con= tains the size of the subtree rooted at the node.

https:= //en.wikipedia.org/wiki/Order_statistic_tree

The s= td::map should have two other functions, called select and rank that behave= as the wikipedia article says. These should be disabled using std::enable_= if_t/concepts on the parameter that decides if the map is an order statisti= c tree or not. Updating the size of the subtree of a node could be done ins= ide of the already defined functions using if constexpr inside the function= .. The body of the compile-time if would update that size for each node on t= he path down to the insertion point.

What do y= ou guys think?

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/ce18cc74-9116-4da6-b320-fe2b4715b1d6= %40isocpp.org.
------=_Part_126_477192966.1549507440797-- ------=_Part_125_1716863266.1549507440797-- .