Topic: Lookup in unordered_map and unordered_set by hash
Author: Olaf van der Spek <olafvdspek@gmail.com>
Date: Sat, 10 Nov 2012 04:45:16 -0800 (PST)
Raw View
------=_Part_117_12172452.1352551516104
Content-Type: text/plain; charset=ISO-8859-1
Op vrijdag 9 november 2012 20:11:02 UTC+1 schreef DeadMG het volgende:
> As for std::equal_to<T>, you're right that it's problematic. I thought
> that Stephan's proposal to make them polymorphic was accepted, in which
> case it would work.
>
Didn't know about that proposal, in that case I assume it's a non-issue.
> But if it doesn't work, then we will have to specify operator== directly
> rather than std::equal_to, then.
>
As in removing the template parameter KeyEqual?
BTW, if you use maps (a lot), a function like my find_ptr might be handy:
template <class T, class U>
const typename T::value_type::second_type* find_ptr(const T& c, U v)
{
typename T::const_iterator i = c.find(v);
return i == c.end() ? NULL : &i->second;
} It simplifies the majority of use cases of find.
http://code.google.com/p/xbt/source/browse/trunk/xbt/misc/xbt/find_ptr.h
--
------=_Part_117_12172452.1352551516104
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Op vrijdag 9 november 2012 20:11:02 UTC+1 schreef DeadMG het volgende:<br><=
blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;bord=
er-left: 1px #ccc solid;padding-left: 1ex;"><div>As for std::equal_to<T&=
gt;, you're right that it's problematic. I thought that Stephan's proposal =
to make them polymorphic was accepted, in which case it would work. </div><=
/blockquote><div><br></div><div>Didn't know about that proposal, in that ca=
se I assume it's a non-issue.</div><div> </div><blockquote class=3D"gm=
ail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc soli=
d;padding-left: 1ex;"><div>But if it doesn't work, then we will have to spe=
cify operator=3D=3D directly rather than std::equal_to, then.</div></blockq=
uote><br>As in removing the template parameter KeyEqual?<br><div><br></div>=
<div>BTW, if you use maps (a lot), a function like my find_ptr might be han=
dy:</div><div><br></div><div><table id=3D"src_table_0" style=3D"border-coll=
apse: collapse; color: rgb(0, 0, 0); font-family: Monaco, 'DejaVu Sans Mono=
', 'Bitstream Vera Sans Mono', 'Lucida Console', monospace; font-size: 12px=
; white-space: pre;"><tbody><tr id=3D"sl_svn2368_10"><td class=3D"source" s=
tyle=3D"padding-left: 4px; white-space: pre-wrap; vertical-align: top;"><sp=
an class=3D"kwd" style=3D"color: rgb(0, 0, 136);">template</span><span clas=
s=3D"pln"> </span><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">&l=
t;</span><span class=3D"kwd" style=3D"color: rgb(0, 0, 136);">class</span><=
span class=3D"pln"> T</span><span class=3D"pun" style=3D"color: rgb(102, 10=
2, 0);">,</span><span class=3D"pln"> </span><span class=3D"kwd" style=3D"co=
lor: rgb(0, 0, 136);">class</span><span class=3D"pln"> U</span><span class=
=3D"pun" style=3D"color: rgb(102, 102, 0);">></span><span class=3D"pln">=
<br></span></td></tr><tr id=3D"sl_svn2368_11"><td class=3D"source" style=3D=
"padding-left: 4px; white-space: pre-wrap; vertical-align: top;"><span clas=
s=3D"kwd" style=3D"color: rgb(0, 0, 136);">const</span><span class=3D"pln">=
</span><span class=3D"kwd" style=3D"color: rgb(0, 0, 136);">typename</span=
><span class=3D"pln"> T</span><span class=3D"pun" style=3D"color: rgb(102, =
102, 0);">::</span><span class=3D"pln">value_type</span><span class=3D"pun"=
style=3D"color: rgb(102, 102, 0);">::</span><span class=3D"pln">second_typ=
e</span><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">*</span><spa=
n class=3D"pln"> find_ptr</span><span class=3D"pun" style=3D"color: rgb(102=
, 102, 0);">(</span><span class=3D"kwd" style=3D"color: rgb(0, 0, 136);">co=
nst</span><span class=3D"pln"> T</span><span class=3D"pun" style=3D"color: =
rgb(102, 102, 0);">&</span><span class=3D"pln"> c</span><span class=3D"=
pun" style=3D"color: rgb(102, 102, 0);">,</span><span class=3D"pln"> U v</s=
pan><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">)</span><span cl=
ass=3D"pln"><br></span></td></tr><tr id=3D"sl_svn2368_12"><td class=3D"sour=
ce" style=3D"padding-left: 4px; white-space: pre-wrap; vertical-align: top;=
"><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">{</span><span clas=
s=3D"pln"><br></span></td></tr><tr id=3D"sl_svn2368_13"><td class=3D"source=
" style=3D"padding-left: 4px; white-space: pre-wrap; vertical-align: top;">=
<span class=3D"pln"> </span><span class=3D"kwd" =
style=3D"color: rgb(0, 0, 136);">typename</span><span class=3D"pln"> T</spa=
n><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">::</span><span cla=
ss=3D"pln">const_iterator i </span><span class=3D"pun" style=3D"color: rgb(=
102, 102, 0);">=3D</span><span class=3D"pln"> c</span><span class=3D"pun" s=
tyle=3D"color: rgb(102, 102, 0);">.</span><span class=3D"pln">find</span><s=
pan class=3D"pun" style=3D"color: rgb(102, 102, 0);">(</span><span class=3D=
"pln">v</span><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">);</sp=
an><span class=3D"pln"><br></span></td></tr><tr id=3D"sl_svn2368_14"><td cl=
ass=3D"source" style=3D"padding-left: 4px; white-space: pre-wrap; vertical-=
align: top;"><span class=3D"pln"> </span><span c=
lass=3D"kwd" style=3D"color: rgb(0, 0, 136);">return</span><span class=3D"p=
ln"> i </span><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">=3D=3D=
</span><span class=3D"pln"> c</span><span class=3D"pun" style=3D"color: rgb=
(102, 102, 0);">.</span><span class=3D"kwd" style=3D"color: rgb(0, 0, 136);=
">end</span><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">()</span=
><span class=3D"pln"> </span><span class=3D"pun" style=3D"color: rgb(102, 1=
02, 0);">?</span><span class=3D"pln"> NULL </span><span class=3D"pun" style=
=3D"color: rgb(102, 102, 0);">:</span><span class=3D"pln"> </span><span cla=
ss=3D"pun" style=3D"color: rgb(102, 102, 0);">&</span><span class=3D"pl=
n">i</span><span class=3D"pun" style=3D"color: rgb(102, 102, 0);">-></sp=
an><span class=3D"pln">second</span><span class=3D"pun" style=3D"color: rgb=
(102, 102, 0);">;</span><span class=3D"pln"><br></span></td></tr><tr id=3D"=
sl_svn2368_15"><td class=3D"source" style=3D"padding-left: 4px; vertical-al=
ign: top;"><span class=3D"pun"><font color=3D"#666600"><span style=3D"white=
-space: pre-wrap;">}
It simplifies the majority of use cases of find.
http://code.google.com/p/xbt/source/browse/trunk/xbt/misc/xbt/find_ptr.h<br=
></span></font></span></td></tr></tbody></table></div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_117_12172452.1352551516104--
.
Author: DeadMG <wolfeinstein@gmail.com>
Date: Tue, 13 Nov 2012 09:03:58 -0800 (PST)
Raw View
------=_Part_533_12353427.1352826238296
Content-Type: text/plain; charset=ISO-8859-1
No- the equality parameter would still be used for all K-K comparisons,
just not K-T comparisons. I'll add an equality comparator functor to the
argument list, I think.
>
>
--
------=_Part_533_12353427.1352826238296
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
No- the equality parameter would still be used for all K-K comparisons, jus=
t not K-T comparisons. I'll add an equality comparator functor to the argum=
ent list, I think.<blockquote class=3D"gmail_quote" style=3D"margin: 0;marg=
in-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"></blockquote=
>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_533_12353427.1352826238296--
.
Author: DeadMG <wolfeinstein@gmail.com>
Date: Tue, 13 Nov 2012 15:38:30 -0800 (PST)
Raw View
------=_Part_270_30307953.1352849910665
Content-Type: multipart/alternative;
boundary="----=_Part_271_29499315.1352849910665"
------=_Part_271_29499315.1352849910665
Content-Type: text/plain; charset=ISO-8859-1
A quick sample proposal is up at http://codepuppy.co.uk/HashProposal.aspx.
Unstyled version attached.
--
------=_Part_271_29499315.1352849910665
Content-Type: text/html; charset=ISO-8859-1
A quick sample proposal is up at http://codepuppy.co.uk/HashProposal.aspx. Unstyled version attached.<div><br></div><div><br></div>
<p></p>
-- <br />
<br />
<br />
<br />
------=_Part_271_29499315.1352849910665--
------=_Part_270_30307953.1352849910665
Content-Type: text/html; charset=UTF-8; name=hashprop.html
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment; filename=hashprop.html
X-Attachment-Id: 3079ffb6-652e-4767-8267-e4e158dc8647
=EF=BB=BF
<!DOCTYPE html>
<html lang=3D"en">
<body">
=20
<h1>Extensions to unordered containers</h1>
<p>The rationale for this proposal is a simple pair of use cases, and exten=
ds the Standard unordered_map and unordered_set to permit them. The first i=
s the use of alternative types as key. For example, currently, it is=20
impossible to look up by a type other than the key type. This sounds re=
asonable but is actually fairly limiting. Consider
</p>
<div class=3D"well"><code>
int main() {<br />
std::unordered_set<std::unique_ptr<T>> =
set;<br />
}</code></div>
<p>Whilst it's possible to insert into the set, there is no means to erase =
or test for membership, as that would involve constructing two unique_ptr t=
o the same resource. However, there is no implementation reason to=20
prevent lookup by an arbitrary key type, T, as long as hash(t) =3D=3D h=
ash(k) for any key k in the map, if t =3D=3D k.
</p>
<p>Secondly, it is impossible to override the hash or equivalence function =
for a given lookup. This can be used for localized optimizations- especiall=
y caching. For example,</p>
<div class=3D"well"><code>
int main() {<br />
std::unordered_map<std::string, int> map;<br =
/>
std::string value;<br />
std::size_t hash_cache;<br />
bool dirty;<br />
// later<br />
map.find(value, [&](std::string& val) {<br />
if (!dirty) return hash_cac=
he; else return std::hash<std::string>()(val);<br />
});<br />
}<br />
</code></div>
<p>These two interface limitations are overcome by presenting new functions=
.. Whilst insertion cannot be further generalized, erasure and lookup both c=
an be.</p>
<div class=3D"well"><code>
template<typename T, typename Hash =3D std::hash<T>, typename Eq =
=3D std::equal_to<T>><br />
iterator find(T t, Hash h =3D Hash(), Eq e =3D Eq());<br />
template<typename T, typename Hash =3D std::hash<T>, typename Eq =
=3D std::equal_to<T>><br />
const_iterator find(T t, Hash h =3D Hash(), Eq e =3D Eq()) const;
</code></div>
<p>In this case, h(t) gives the hash value of t, and e(t, k) returns whethe=
r or not t is equal to k, for some key k. Also proposed are similar variant=
s for erase(), and operator[] for unordered_map. The operator=20
can't take the additional function object arguments, so the hash and eq=
uality argument stored as part of the container will be used. Given these f=
unctions, it's quite possible to implement both of the use cases=20
described above.
</p>
=20
</body>
</html>=E2=80=8B
------=_Part_270_30307953.1352849910665--
.