 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Stephen Howe
Guest
|
 Posted: Thu Apr 07, 2005 7:17 am Post subject: TR1 and unordered_map |
 |
|
Hi
Consider std::map
Looking carefully at the whole interface, there is absolutely no reason why
it has to be implemented by Red-Black or AVL trees. AFAIK, any other data
structure will do providing the complexity requirements of the standard for
std::map are met. In that sense, it is future proof, in that if someone
determined some new data structure that met the complexity requirements,
std::map could be implemented in terms of that.
And because of the clean interface, std::map could be std::ordered_map.
Well and good.
Now consider TR1 as mentioned here:
[url]www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf[/url]
It is not future proof. If another data structure is found that meets the
complexity requirement for tr1::unordered_map, it then has meet the
additional baggage requirements of X::hasher, X::local_iterator,
X::const_local_iterator (see Table 21).
None of this is to do with "unorderedness". It is all to do with "hashness".
Unlike std::map, this containers underlying data structure is "poking
through". An alternative underlying data structure is not as far-fetched as
it sounds. Skip Lists by Pugh are relatively recent.
So I am very unhappy at choice of name.
So either
(i) clean the interface so that it is devoid of hash related concepts and
leave headers/containers with names "unordered_map"
(ii) change the names so that headers/containers have names of "hashmap" or
"hash_map" (because the interface _does_ poke through, it is not clean).
(i) IMO, is not really possible without damaging the usability of the
container.
Programmers should be able to supply their own hash function and do the
other things that Matt Austern envisions.
So that leaves (ii).
Stephen Howe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Seungbeom Kim
Guest
|
| Posted: Thu Apr 07, 2005 11:46 am Post subject: Re: TR1 and unordered_map |
|
|
Stephen Howe wrote:
| Quote: | Now consider TR1 as mentioned here:
[url]www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf[/url]
It is not future proof. If another data structure is found that meets the
complexity requirement for tr1::unordered_map, it then has meet the
additional baggage requirements of X::hasher, X::local_iterator,
X::const_local_iterator (see Table 21).
None of this is to do with "unorderedness". It is all to do with "hashness".
Unlike std::map, this containers underlying data structure is "poking
through". An alternative underlying data structure is not as far-fetched as
it sounds. Skip Lists by Pugh are relatively recent.
So I am very unhappy at choice of name.
|
So am I.
But have you read N1456
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html>?
Arguments from N1456:
(1) The names hash_* are already in use (whether or not in std: .
(2) The names unordered_* reveals the most important property of
unorderedness.
(1) is not convincing. The std namespace was meant to be reserved by the
standard library, so the committee's effort to choose the best names
should not be hindered by vendors who violated the rules. And you have
argued against (2).
However, the names hash_* have been considered and rejected, to my
disappointment (and of many others, possibly).
By the way, this topic fits better in <news:comp.std.c++>.
--
Seungbeom Kim
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Beman Dawes
Guest
|
| Posted: Thu Apr 07, 2005 2:56 pm Post subject: Re: TR1 and unordered_map |
|
|
Seungbeom Kim wrote:
| Quote: | ...
Arguments from N1456:
(1) The names hash_* are already in use (whether or not in std:.
(2) The names unordered_* reveals the most important property of
unorderedness.
(1) is not convincing. The std namespace was meant to be reserved by
the
standard library, so the committee's effort to choose the best names
should not be hindered by vendors who violated the rules.
|
You are missing the point somewhat. It isn't vendors who would be
damaged by the hash_* names. Rather, users who have existing code would
be damaged. The LWG wasn't particularly concerned with protecting the
two or three vendors affected. They were concerned with protecting user
code, which was believed to be widespread.
--Beman
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Pete Becker
Guest
|
| Posted: Thu Apr 07, 2005 2:58 pm Post subject: Re: TR1 and unordered_map |
|
|
Stephen Howe wrote:
| Quote: |
Now consider TR1 as mentioned here:
[url]www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf[/url]
It is not future proof. If another data structure is found that meets the
complexity requirement for tr1::unordered_map, it then has meet the
additional baggage requirements of X::hasher, X::local_iterator,
X::const_local_iterator (see Table 21).
None of this is to do with "unorderedness". It is all to do with "hashness".
|
Yup. But that's what people think they want. I've always felt that hash
tables require far too much customization to be standardized.
| Quote: | (ii) change the names so that headers/containers have names of "hashmap" or
"hash_map" (because the interface _does_ poke through, it is not clean).
|
Can't be done. Too many conflicting uses of those names or similar ones.
You really don't want to restart that battle. <g>
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Thu Apr 07, 2005 3:03 pm Post subject: Re: TR1 and unordered_map |
|
|
In article <d32r6h$pd3$1 (AT) news (DOT) Stanford.EDU>,
Seungbeom Kim <musiphil (AT) bawi (DOT) org> wrote:
| Quote: | Stephen Howe wrote:
Now consider TR1 as mentioned here:
[url]www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf[/url]
It is not future proof. If another data structure is found that meets the
complexity requirement for tr1::unordered_map, it then has meet the
additional baggage requirements of X::hasher, X::local_iterator,
X::const_local_iterator (see Table 21).
None of this is to do with "unorderedness". It is all to do with "hashness".
Unlike std::map, this containers underlying data structure is "poking
through". An alternative underlying data structure is not as far-fetched as
it sounds. Skip Lists by Pugh are relatively recent.
So I am very unhappy at choice of name.
So am I.
But have you read N1456
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html>?
Arguments from N1456:
(1) The names hash_* are already in use (whether or not in std:.
(2) The names unordered_* reveals the most important property of
unorderedness.
(1) is not convincing. The std namespace was meant to be reserved by the
standard library, so the committee's effort to choose the best names
should not be hindered by vendors who violated the rules. And you have
argued against (2).
However, the names hash_* have been considered and rejected, to my
disappointment (and of many others, possibly).
By the way, this topic fits better in <news:comp.std.c++>.
|
Considered and rejected is a very diplomatic way of putting it.
I was there, as a vendor, and shipping hash_* containers. This event
(standardizing hash containers, and the conflicts that would arise) was
a clearly foreseeable and foreseen event by all vendors many years ago:
http://groups-beta.google.com/group/codewarrior.mac/browse_thread/thread/
3989139a6a8e2129/c68ac77d4f556206?q=insubject:MSL+insubject:C%2B%2B+insub
ject:Tip+insubject:9&rnum=1#c68ac77d4f556206
http://groups-beta.google.com/group/codewarrior.mac/browse_thread/thread/
f14f8965c5aa7f32/00aa67a61aafbaa9?q=insubject:MSL+insubject:C%2B%2B+insub
ject:Tip+insubject:10&rnum=1#00aa67a61aafbaa9
Starting in 2000 I took Metrowerks customers through the process of
removing extension containers such as hash_* from namespace std. It was
a multi-year effort, involving transition releases where the containers
were available in both namespace std and in namespace Metrowerks. But I
knew it was worth doing so that when it came time to standardize hash
containers, things would go smoothly. My customers were most forgiving
of my initial mistake of putting these extensions into namespace std.
Some other vendors (gcc I believe) had similar strategies. One vendor
did not. One vendor refused to put their customers through any such
transition, was the driving force behind all of the options considered
in N1456, and now that vendor's customers are looking at probable
std::unordered_* containers instead of std::hash_* containers. Contrast
N1326 with N1456 and the effects of this flash-point issue are clear.
The committee has only decided on std::tr1::unordered_*. The committee
has specifically made no decision concerning std::unordered_*. TR1 is
an experiment, not a standard. It exists so that we can fix problems
before standardization. If there are any components of TR1 that are not
working well for you, please let us know. Please let your vendor know.
You may have to say it loudly, and several times. You may have to
gather consensus.
-Howard
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Seungbeom Kim
Guest
|
| Posted: Fri Apr 08, 2005 7:44 am Post subject: Re: TR1 and unordered_map |
|
|
Beman Dawes wrote:
| Quote: | Seungbeom Kim wrote:
...
Arguments from N1456:
(1) The names hash_* are already in use (whether or not in std:.
(2) The names unordered_* reveals the most important property of
unorderedness.
(1) is not convincing. The std namespace was meant to be reserved by the
standard library, so the committee's effort to choose the best names
should not be hindered by vendors who violated the rules.
You are missing the point somewhat. It isn't vendors who would be
damaged by the hash_* names. Rather, users who have existing code would
be damaged. The LWG wasn't particularly concerned with protecting the
two or three vendors affected. They were concerned with protecting user
code, which was believed to be widespread.
|
Which user code?
Are we allowed to put user code into namespace std?
--
Seungbeom Kim
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
P.J. Plauger
Guest
|
| Posted: Fri Apr 08, 2005 11:23 pm Post subject: Re: TR1 and unordered_map |
|
|
"Seungbeom Kim" <musiphil (AT) bawi (DOT) org> wrote
| Quote: | Beman Dawes wrote:
Seungbeom Kim wrote:
...
Arguments from N1456:
(1) The names hash_* are already in use (whether or not in std:.
(2) The names unordered_* reveals the most important property of
unorderedness.
(1) is not convincing. The std namespace was meant to be reserved by the
standard library, so the committee's effort to choose the best names
should not be hindered by vendors who violated the rules.
You are missing the point somewhat. It isn't vendors who would be
damaged by the hash_* names. Rather, users who have existing code would
be damaged. The LWG wasn't particularly concerned with protecting the
two or three vendors affected. They were concerned with protecting user
code, which was believed to be widespread.
Which user code?
Are we allowed to put user code into namespace std?
|
No, but user code can refer to code that's in namespace std.
In fact, it rather expects to when accessing library
components.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ian McCulloch
Guest
|
| Posted: Sat Apr 09, 2005 10:04 am Post subject: Re: TR1 and unordered_map |
|
|
Beman Dawes wrote:
| Quote: |
Seungbeom Kim wrote:
...
Arguments from N1456:
(1) The names hash_* are already in use (whether or not in std:.
(2) The names unordered_* reveals the most important property of
unorderedness.
(1) is not convincing. The std namespace was meant to be reserved by
the
standard library, so the committee's effort to choose the best names
should not be hindered by vendors who violated the rules.
You are missing the point somewhat. It isn't vendors who would be
damaged by the hash_* names. Rather, users who have existing code would
be damaged. The LWG wasn't particularly concerned with protecting the
two or three vendors affected. They were concerned with protecting user
code, which was believed to be widespread.
|
If you (or the LWG) are going to argue that such code is widespread, then I
think it is fair that you name exactly which compilers you are referring
to, and the reasons why such code is believed to be widespread.
Cheers,
Ian
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Boaz Kelmer
Guest
|
| Posted: Tue Apr 12, 2005 6:50 am Post subject: Re: TR1 and unordered_map |
|
|
| Quote: | Howard Hinnant <hinnant (AT) metrowerks (DOT) com> writes:
Seungbeom Kim <musiphil (AT) bawi (DOT) org> wrote:
Stephen Howe wrote:
Now consider TR1 as mentioned here:
[url]www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf[/url]
[...]
So I am very unhappy at choice of name.
So am I.
[...]
However, the names hash_* have been considered and rejected, to my
disappointment (and of many others, possibly).
Considered and rejected is a very diplomatic way of putting it.
I was there, as a vendor, and shipping hash_* containers. This event
(standardizing hash containers, and the conflicts that would arise) was
a clearly foreseeable and foreseen event by all vendors many years ago:
[...]
The committee has only decided on std::tr1::unordered_*. The committee
has specifically made no decision concerning std::unordered_*. TR1 is
an experiment, not a standard. It exists so that we can fix problems
before standardization. If there are any components of TR1 that are not
working well for you, please let us know. Please let your vendor know.
You may have to say it loudly, and several times. You may have to
gather consensus.
|
Names are important. Standard names are even more important.
The unordered_map/set name is far from ideal. hash_map/set
is much better. The fact that some vendors already chose to
use it only reinforces this claim.
I have always thought that the existing names map/set are
also wrong. An abstract (or mathematical) set has no notion
of order, but these classes do. Bette call them ordered_map/set.
So my vote (as if I had one) is:
hash_map/set for the hash containers
ordered_map/set for the ordered containers.
-- Boaz
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Beman Dawes
Guest
|
| Posted: Wed Apr 20, 2005 9:41 am Post subject: Re: TR1 and unordered_map |
|
|
"Ian McCulloch" <ianmcc (AT) physik (DOT) rwth-aachen.de> wrote
| Quote: | You are missing the point somewhat. It isn't vendors who would be
damaged by the hash_* names. Rather, users who have existing code would
be damaged. The LWG wasn't particularly concerned with protecting the
two or three vendors affected. They were concerned with protecting user
code, which was believed to be widespread.
If you (or the LWG) are going to argue that such code is widespread, then
I
think it is fair that you name exactly which compilers you are referring
to, and the reasons why such code is believed to be widespread.
|
GCC, Metrowerks, Microsoft, and those are just the first three I looked at.
The namespace and degree of difference from the TR1 interface varies, but
there is at least some problem for users of all of those. And I consider the
use "widespread" simply because I see it all the time in code from multiple
sources, including my own.
--Beman
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
