Topic: Allow searching in set and unordered_set with
Author: Shachar Shemesh <shachar@lingnu.com>
Date: Sat, 24 May 2014 10:33:28 +0300
Raw View
This is a multi-part message in MIME format.
--------------050501080702090307030100
Content-Type: text/plain; charset=UTF-8
Today, the "find" method of std::set and std::unordered_set gets just
one type of argument, the Key template type for the container.
Sometimes, the container contains a compound type with only some of its
members participating in calculating the key equality. In those cases,
it makes sense to search, not based on the complete type, but based on
only those parts of the type that are used to calculate the equality.
For example, in fakeroot-ng[1], there is an unordered_map of what is,
essentially, a struct, containing information the program keeps track of
other processes in the system. These include the process' uid, gid etc.
When an event arrives from any of those processes, a lookup is performed
where the PID is the key, and the struct is found.
This setup is extremely inconvenient. It means that I have one of three
options, none optimal:
1. Pass the pid explicitly to any function that also needs a pointer to
the struct.
2. Store the pid also in the struct.
3. Instead of passing a pointer to the struct, pass an iterator to the
unordered_map
1 makes the interface for the functions awkward. 2 means I store a
duplicate of the same piece of information. 3 is unacceptable because
the iterator might be invalidated by another thread, while the pointer
is valid so long as that particular entry is alive.
Ideally, what I'd like to do is store the struct in an unordered_set,
where I can search it based solely based on pid. I can still do this
today by creating an empty struct, but that is even more wasteful than
option 2 above.
I fully realize that in order to implement that regarding
std::unordered_set, we'd also need to make sure that the hash
calculation does not take into account anything other than the parts of
the Key type that are used to calculate the key. The template arguments
order makes it difficult to do in a backward compatible way. Had Hash
and KeyEqual been reversed, we could have demanded that KeyEqual have a
typedef of the core key type, and have Hash use only that for
calculating the hash. As things stand, that cannot be done.
Still, I think even requiring anyone who wants to make use of that
option to provide a non-default Hash and KeyEqual would put things in a
better place than it is today, without breaking backward compatibility.
As always, input is welcome
Shachar
--
---
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/.
--------------050501080702090307030100
Content-Type: text/html; charset=UTF-8
<html style="direction: ltr;">
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<style type="text/css">body p { margin-bottom: 0.2cm; margin-top: 0pt; } </style>
</head>
<body style="direction: ltr;"
bidimailui-detected-decoding-type="UTF-8" bgcolor="#FFFFFF"
text="#000000">
Today, the "find" method of std::set and std::unordered_set gets
just one type of argument, the Key template type for the container.
Sometimes, the container contains a compound type with only some of
its members participating in calculating the key equality. In those
cases, it makes sense to search, not based on the complete type, but
based on only those parts of the type that are used to calculate the
equality.<br>
<br>
For example, in fakeroot-ng[1], there is an unordered_map of what
is, essentially, a struct, containing information the program keeps
track of other processes in the system. These include the process'
uid, gid etc. When an event arrives from any of those processes, a
lookup is performed where the PID is the key, and the struct is
found.<br>
<br>
This setup is extremely inconvenient. It means that I have one of
three options, none optimal:<br>
<ol>
<li>Pass the pid explicitly to any function that also needs a
pointer to the struct.</li>
<li>Store the pid also in the struct.</li>
<li>Instead of passing a pointer to the struct, pass an iterator
to the unordered_map</li>
</ol>
<p>1 makes the interface for the functions awkward. 2 means I store
a duplicate of the same piece of information. 3 is unacceptable
because the iterator might be invalidated by another thread, while
the pointer is valid so long as that particular entry is alive.<br>
</p>
<p>Ideally, what I'd like to do is store the struct in an
unordered_set, where I can search it based solely based on pid. I
can still do this today by creating an empty struct, but that is
even more wasteful than option 2 above.<br>
</p>
<p>I fully realize that in order to implement that regarding
std::unordered_set, we'd also need to make sure that the hash
calculation does not take into account anything other than the
parts of the Key type that are used to calculate the key. The
template arguments order makes it difficult to do in a backward
compatible way. Had Hash and KeyEqual been reversed, we could have
demanded that KeyEqual have a typedef of the core key type, and
have Hash use only that for calculating the hash. As things stand,
that cannot be done.<br>
</p>
<p>Still, I think even requiring anyone who wants to make use of
that option to provide a non-default Hash and KeyEqual would put
things in a better place than it is today, without breaking
backward compatibility.<br>
</p>
<p>As always, input is welcome<br>
Shachar<br>
</p>
</body>
</html>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:std-proposals+unsubscribe@isocpp.org">std-proposals+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href="mailto:std-proposals@isocpp.org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href="http://groups.google.com/a/isocpp.org/group/std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/</a>.<br />
--------------050501080702090307030100--
.
Author: Jim Porter <jvp4846@g.rit.edu>
Date: Sat, 24 May 2014 00:49:52 -0700 (PDT)
Raw View
------=_Part_923_28757173.1400917792329
Content-Type: text/plain; charset=UTF-8
On Saturday, May 24, 2014 2:33:37 AM UTC-5, Shachar Shemesh wrote:
>
> Today, the "find" method of std::set and std::unordered_set gets just one
> type of argument, the Key template type for the container. Sometimes, the
> container contains a compound type with only some of its members
> participating in calculating the key equality. In those cases, it makes
> sense to search, not based on the complete type, but based on only those
> parts of the type that are used to calculate the equality.
>
This is something I've been hoping for as well. The following threads may
be of interest to you:
https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/rURBQ6eM7wU
https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/mRu7rIrDAEw
- Jim
--
---
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/.
------=_Part_923_28757173.1400917792329
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Saturday, May 24, 2014 2:33:37 AM UTC-5, Shachar Shemes=
h wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0=
..8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
=20
=20
=20
=20
<div>
Today, the "find" method of std::set and std::unordered_set gets
just one type of argument, the Key template type for the container.
Sometimes, the container contains a compound type with only some of
its members participating in calculating the key equality. In those
cases, it makes sense to search, not based on the complete type, but
based on only those parts of the type that are used to calculate the
equality.<br></div></blockquote><div><br>This is something I've been ho=
ping for as well. The following threads may be of interest to you:<br><br>h=
ttps://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/rURBQ6eM7=
wU<br>https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/mR=
u7rIrDAEw<br><br>- Jim<br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />
------=_Part_923_28757173.1400917792329--
.