220 3645 article Path: news.gmane.org!not-for-mail From: jgottman6@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: N3573: Why heterogenous extensions to unordered containers will not work Date: Mon, 8 Apr 2013 17:36:46 -0700 (PDT) Lines: 162 Approved: news@gmane.org Message-ID: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_5167_18593397.1365467806728" X-Trace: ger.gmane.org 1365467807 804 80.91.229.3 (9 Apr 2013 00:36:47 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 9 Apr 2013 00:36:47 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBD7LHGWIQEPRBH6FRWFQKGQESXYZA6Q@isocpp.org Tue Apr 09 02:36:51 2013 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-ve0-f198.google.com ([209.85.128.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UPMYK-0006f6-PG for gclcip-std-proposals@m.gmane.org; Tue, 09 Apr 2013 02:36:49 +0200 Original-Received: by mail-ve0-f198.google.com with SMTP id ox1sf10616365veb.9 for ; Mon, 08 Apr 2013 17:36:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:x-beenthere:x-received:date:from:to:message-id:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:x-google-group-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe:content-type; bh=iOEqPYRkESO4E8qfWkkQZXQs42BinIvJCVisUfyAQoY=; b=vfDDoy4CkusklfZ36NRqOjHhMF+PgOlDsvgQWXgcaw/iatGon8LRMsrn6pyR6cOabN LIkReLAE84JdUIvDFfIxL1MlbHnW1JiaEbhIJiDa/7Xrjg64jlECor8A6Sxm9gkattsv 2Sw3iiXxBbFiBt6zAPQPe3tpcyP9Ti9dyuT64OOfcPLUoK97JAkNlEoim95EM27TaR6x ed0PQ+ncfFhDmQnf/J6sRMPIkAME9s7vPfPybHAC0eW099/XwmZR5suKITEGKjK5Cx5R /Y4HEd16muVqClN/12sKcX9w9GthURB2DmEmufKpKErc6bbm0QmotcIcIuxkH7sfnXf0 qnIA== X-Received: by 10.224.157.1 with SMTP id z1mr7007354qaw.8.1365467807873; Mon, 08 Apr 2013 17:36:47 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.49.106.163 with SMTP id gv3ls3380223qeb.88.gmail; Mon, 08 Apr 2013 17:36:47 -0700 (PDT) X-Received: by 10.49.95.134 with SMTP id dk6mr1938565qeb.10.1365467806960; Mon, 08 Apr 2013 17:36:46 -0700 (PDT) X-Original-Sender: jgottman6@gmail.com 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:3645 Archived-At: ------=_Part_5167_18593397.1365467806728 Content-Type: text/plain; charset=ISO-8859-1 N3573 suggests allowing lookup into unordered sets and maps by alternative keys, as long as operator== can compare both types and the hashes of the two types are compatible. The use case given is std::unordered_map map; map.find("foo"); // We don't have to construct string("foo") to do the find. While this would be useful, there is too much chance of two types being equality-comparable but having incompatible hashes. For example, under gcc 8.0, std::hash(-1L) == 18446744073709551615 and std::hash(-1.0) == 11078049357879903929 Thus, if N3573 were accepted, this code would fail: std:unordered_set s; s.insert(-1L); // Internally converts -1L to -1.0 and hashes that assert(s.find(-1L) != s.end()); // fails. find calls hash(-1L) and gets the wrong bucket Note that under C++11 rules this code succeeds, because find also converts its parameter to double before hashing. Joe Gottman -- --- 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. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en. ------=_Part_5167_18593397.1365467806728 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable N3573 suggests allowing lookup into unordered sets and maps by alternative = keys, as long as operator=3D=3D can compare both types and the hashes of th= e two types are compatible.  The use case given is

 std= ::unordered_map<std::string, int> ma= p;<= span style=3D"color: #000;" class=3D"styled-by-prettify">
 map.find("foo"); // We don't have to construct string("foo") to do the find.=


While this would be useful, there is too= much chance of two types being equality-comparable but having incompatible= hashes.  For example, under gcc 8.0,
std::hash<long>(-1L) =3D=3D 18446744073709551615
<= /div>and
= std::hash<double>= (-1.0) =3D=3D 11078049357879903929


Thus, if N357= 3 were accepted, this code  would fail:

<= code class=3D"prettyprint">
std:unordered_set<double> s;
s.insert(-<= /span>1L); // Internally converts -1L to -1.0 a= nd hashes that
as= sert(s.find(-1L) !=3D s.end()); // fails. find calls hash<long>(-1L) = and gets the wrong bucket


Note that under C++11 = rules this code succeeds, because find also converts its parameter to doubl= e before hashing.

Joe Gottman

--
 
---
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-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-pro= posals/?hl=3Den.
 
 
------=_Part_5167_18593397.1365467806728-- .