Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL map to STL vector

Reply
Thread Tools

STL map to STL vector

 
 
Seungbeom Kim
Guest
Posts: n/a
 
      01-15-2014
On 2014-01-15 08:50, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
>
> It isn't very descriptive. It's like saying a
> marble is not blue. Hash_map would be better.


A problem I see is that the name "unordered_map" strongly suggests
that a map should be ordered by default. While it's true that order
is an important property for std::map, a map in its purest sense
doesn't have to be ordered and it would have been no less sensible
to have std::map (unordered) and std:rdered_map instead. It's just
for a historical reason that an ordered map took the name "std::map".

The same goes for unordered_set: we all learned in elementary schools
that a set is just a collection of things like {apple, banana, orange},
which never has to be ordered. (Letting multiset carry the burden of
the prefix "multi-" makes sense because its behavior deviates from
that of a "normal set".)

And I don't think being unordered is the most important and essential
property for std::unordered_{map,set}. A negative description such as
"not xxx" or "un-xxx" usually isn't; std::unordered_{map,set} is not
what we get just by removing order from std::{map,set}. This makes
a big point that makes the names std::unordered_{map,set} lame.

> I think there was some history with that name,
> but think the name could still be changed to
> hash_map.


I don't believe it can happen. I don't like the choice, but I admit
it's made by the committee members who are in a better position to
make good decisions for the entire C++ community.

--
Seungbeom Kim
 
Reply With Quote
 
 
 
 
Tiib
Guest
Posts: n/a
 
      01-15-2014
On Wednesday, 15 January 2014 22:23:35 UTC+2, (E-Mail Removed) wrote:
> On Wednesday, January 15, 2014 11:32:44 AM UTC-6, Tiib wrote:
> > On Wednesday, 15 January 2014 18:50:53 UTC+2, (E-Mail Removed) wrote:
> > >
> > > It isn't very descriptive. It's like saying a
> > > marble is not blue. Hash_map would be better.

> >
> > Why? "Hash" sounds like Klingon/Orcish word
> > while every child understands "unordered". On
> > most cases the fact that unordered map is
> > built internally on hash table is as unimportant
> > as the fact that set is built upon red-black tree.

>
> I believe unordered_map has to have a hash function.
> It defaults to std::hash if you don't supply your own.


Yes. Also you can provide function to detect equality
of value of two keys and you can dynamically 'rehash'
and set load factor of hash table. For majority of use
cases those opportunities are unimportant. Majority
just need a map for searching mapping between two
values. They don't care about order of iteration.

> The Microsoft documentation on unordered_map says the
> sequence is "weakly ordered". That's a more accurate
> description than "unordered". But I don't like
> "weakly_ordered_map" for a name either. "Hash_map"
> is nice because it isn't so long.


The "order" we talk of here is iteration order that is
"unordered" since it is not related to order of keys
unlike with 'std::map'. The keys of 'std::unordered_map'
may be even not comparable with each other at all. As
long a functor to detect equality of two keys is available
it works fine.

> > > I think there was some history with that name,
> > > but think the name could still be changed to
> > > hash_map.

> >
> > When the requirements of standard are sufficiently
> > different than those of prior art then it is good idea
> > to rename.

>
> What different requirements?


Depends what 'hash_map' you are talking about. It was
very common extension provided by many library
implementations prior to standardising. Code that used
some particular implementation could continue to use
it without fear it changing or switch to standardised
'unordered_map' if there was budget for that switch.
 
Reply With Quote
 
 
 
 
Tiib
Guest
Posts: n/a
 
      01-15-2014
On Wednesday, 15 January 2014 22:35:01 UTC+2, (E-Mail Removed) wrote:
> On Wednesday, January 15, 2014 10:20:06 AM UTC-6, Tiib wrote:
> > Saving one integer value is questionable here. It is most
> > likely that removing it is inefficient like with C string.
> > C string is less efficient than 'std::string' on most of cases
> > precisely because of not storing the length anywhere.
> > So you need to show that you "pay", otherwise it might
> > be empty claim.

>
> Some containers you rarely/never need to know their size.


The C++ standard committee that wrote C++98 also thought
so. However in practice there was tons of newbies who wrote
things like 'if(x.size() == 0)' instead of 'if(x.empty())'. That is
terrible performance hit if a set counts its elements each time
someone detects its emptiness but the bug is so subtle and
common so the library implementers started to cache the size.
The committee then wizened up and standardised practice
that existed.
 
Reply With Quote
 
Seungbeom Kim
Guest
Posts: n/a
 
      01-16-2014
On 2014-01-15 09:32, Tiib wrote:
> On Wednesday, 15 January 2014 18:50:53 UTC+2, (E-Mail Removed) wrote:
>>
>> It isn't very descriptive. It's like saying a
>> marble is not blue. Hash_map would be better.

>
> Why? "Hash" sounds like Klingon/Orcish word
> while every child understands "unordered".


Maybe some children would understand "unordered" as the
status of their rooms with toys lying all around...

You need to understand hash containers and hash functions anyway
to be able to use std::unordered_map effectively, especially on
your own data type, so having "hash" in the name shouldn't be
too limiting, no matter how it sounds (especially to children).

> On most cases the fact that unordered map is
> built internally on hash table is as unimportant
> as the fact that set is built upon red-black tree.


I consider hashing is an important concept in std::unordered_map,
as I said above. I wouldn't go as far as red-black trees, but actually
I think I like the name "tree_map"; given the complexity requirements,
it's almost as if the standard is written with trees as the underlying
data structure in mind.

The balance in the names "tree_map" and "hash_map" is an added bonus.

--
Seungbeom Kim
 
Reply With Quote
 
woodbrian77@gmail.com
Guest
Posts: n/a
 
      01-16-2014
On Wednesday, January 15, 2014 6:11:37 PM UTC-6, Seungbeom Kim wrote:
> On 2014-01-15 09:32, �� Tiib wrote:
>
> > On Wednesday, 15 January 2014 18:50:53 UTC+2, (E-Mail Removed) wrote:

>
> >>

>
> >> It isn't very descriptive. It's like saying a

>
> >> marble is not blue. Hash_map would be better.

>
> >

>
> > Why? "Hash" sounds like Klingon/Orcish word

>
> > while every child understands "unordered".

>
> Maybe some children would understand "unordered" as the
> status of their rooms with toys lying all around...
>
> You need to understand hash containers and hash functions anyway
> to be able to use std::unordered_map effectively, especially on
> your own data type, so having "hash" in the name shouldn't be
> too limiting, no matter how it sounds (especially to children).
>


I've been trying to say something like that, but you beat
me to it so now I don't have to.

> > On most cases the fact that unordered map is
> > built internally on hash table is as unimportant
> > as the fact that set is built upon red-black tree.

>
> I consider hashing is an important concept in std::unordered_map,
> as I said above. I wouldn't go as far as red-black trees, but actually
> I think I like the name "tree_map"; given the complexity requirements,
> it's almost as if the standard is written with trees as the underlying
> data structure in mind.
>


That sounds interesting.

Brian
Ebenezer Enterprises
http://webEbenezer.net
 
Reply With Quote
 
woodbrian77@gmail.com
Guest
Posts: n/a
 
      01-16-2014
On Thursday, January 16, 2014 7:45:41 AM UTC-6, Juha Nieminen wrote:
>
> I don't think the standard demands the implementation to be a hash array
> (even though it demands a hash function to be provided.) The name would
> be misleading if the internal implementation happened to be something else.
>


Are there any implementations that do something else?

> Consistency would dictate std::map to be renamed to std:rdered_map,
> but backwards compatibility and grandfather clauses...
>


A new name could be introduced without forcing a renaming.
There would be two names for the same thing with one being
the hoped-to-be improved name.

 
Reply With Quote
 
Seungbeom Kim
Guest
Posts: n/a
 
      01-16-2014
On 2014-01-16 05:45, Juha Nieminen wrote:
>
> I don't think the standard demands the implementation to be a hash array
> (even though it demands a hash function to be provided.) The name would
> be misleading if the internal implementation happened to be something else.


I agree that standard names should not depend on implementation details,
but what would be so misleading in the name "hash_map" for something
that "by specification" requires and is organized by a hash function?

Besides, I'm curious to hear what data structures other than hash tables
exist that use a hash function and buckets but don't deserve the word
"hash" in the name.

--
Seungbeom Kim
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      01-16-2014
On 16.01.2014 22:36, Vir Campestris wrote:
> On 14/01/2014 21:14, Mr Flibble wrote:
>> Actually the benefit of doing 'reserve' diminishes as the number of
>> elements increases.


I don't see Mr Flibble's original article and I suspect that the context
may narrow down what's being discussed, but even as a general statement
that above is correct when just the word "relative" is added or understood.


> Do you have a source for that?


Instead of authority, try logic.

It is after all the greatest authority.

The C++ standard guarantees amortized linear time, O(n), for creating a
vector of n items, i.e. amortized constant time per item. The O(n) time
includes O(n) item moves or copies, plus O(log n) buffer allocations.
The latter contribution diminishes greatly, relative to the total, as n
increases.


> My understanding is that it will expand the vector - usually by doubling
> in size or some such - whenever it gets full.


Yes. This is what guarantees amortized linear time. It might be a
constant factor such as 1.6 instead of 2.0, but assuming a doubling and
starting at buffer size 1, then for n elements you get copy/move time
consumption 1 + 2 + 4 + 8 + ... N, where N is the highest power of 2
that is less than or equal to n, which sum equals 2*N - 1.


> This will require a copy
> of every single item (1). Worth avoiding if you can.


A copy or move. But I agree, it's worth avoiding, e.g. by doing a
reserve, as a matter of course. Still it is true that the relative
benefit of doing that /diminishes/ as Mr. Flibble, alias Leigh "Sausage"
Johnston, wrote (or intended to write, I added "relative").


Cheers & hth.,

- Alf

 
Reply With Quote
 
Tiib
Guest
Posts: n/a
 
      01-17-2014
On Thursday, 16 January 2014 02:11:37 UTC+2, Seungbeom Kim wrote:
> On 2014-01-15 09:32, �� Tiib wrote:
>
> > On Wednesday, 15 January 2014 18:50:53 UTC+2, (E-Mail Removed) wrote:
> >>
> >> It isn't very descriptive. It's like saying a
> >> marble is not blue. Hash_map would be better.

> >
> > Why? "Hash" sounds like Klingon/Orcish word
> > while every child understands "unordered".

>
> Maybe some children would understand "unordered" as the
> status of their rooms with toys lying all around...


Yes and most of the population considers strings as women
underwear. I meant children who consider writing software.
On 95% of cases it does not matter to user that it is internally
"splay_tree_multiset" or "hash_table_dictionary" or
"copy_on_write_string". "unordered" is better since it is adjective but
ideal would be to have just "multiset", "dictionary" or "string".

> You need to understand hash containers and hash functions anyway
> to be able to use std::unordered_map effectively, especially on
> your own data type, so having "hash" in the name shouldn't be
> too limiting, no matter how it sounds (especially to children).


All standard library containers have allocator parameter. Most
users of those containers are not too good in memory
management and incapable to develop efficient allocators
because they rarely need to. Same is with hashing. Most map
keys actually used are already hashable. On rare case when
compiler tells that it can't find 'hash<Key>' but it needs one the
people google a bit and write one rather quickly. IOW I don't
see that one must understand details of algorithm or container
overly deeply to use it effectively.

> > On most cases the fact that unordered map is
> > built internally on hash table is as unimportant
> > as the fact that set is built upon red-black tree.

>
> I consider hashing is an important concept in std::unordered_map,
> as I said above. I wouldn't go as far as red-black trees, but actually
> I think I like the name "tree_map"; given the complexity requirements,
> it's almost as if the standard is written with trees as the underlying
> data structure in mind.
>
> The balance in the names "tree_map" and "hash_map" is an added bonus.


I think it will be in the future that the types will be (possibly
automatically) configurable. There are some class libraries with heavily
configurable traits already but it is not too convenient to tinker there
(and diagnostics can be ridiculous) right now. That will likely improve
when concepts emerge.
 
Reply With Quote
 
woodbrian77@gmail.com
Guest
Posts: n/a
 
      01-17-2014
Please don't swear here, Leigh.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
const vector<A> vs vector<const A> vs const vector<const A> Javier C++ 2 09-04-2007 08:46 PM
Initializing vector<vector<int> > and other vector questions... pmatos C++ 6 04-26-2007 05:39 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
STL: Map of maps possible, but no multi-map of maps? Workarounds? Marcus C++ 2 12-09-2005 06:34 AM
how the vector is created, how to pass vector to webservices method apachesoap:Vector Rushikesh Joshi Perl Misc 0 07-10-2004 01:04 PM



Advertisments