STL map to STL vector

[Mike Copeland]

Is it possible to simply (single statement) move the data from one
container type (the TeamMap, below) to a different type of container
(the TeamVector, below)? My data resides in the map object, but since I
have to occasionally display the data in different orders (e.g.
teamName, teamTypeCode), I must copy the data to a vector and sort it
before producing my listings.
I know that I can copy the individual objects from the map to the
vector one-at-a-time, but I'm hoping that there's a technique that will
do it simply and quickly. Any thoughts? TIA


typedef map<char, int> ShirtStats;
struct TeamData
{
bool isAdded; // Added to container data
bool isValidTeam; // really is a team
char teamTypeCode; // Team type Code
int teamMembers1; // Count of Team Members-1
int teamMembers2; // Count of Team Members-2
int genderCounts[NMAXEVT][2]; // counts of Gender by Event
int shirtTotalMatrix[5][8];
string teamCode; // Team's Code (strTId)
string teamName; // Team's Name
ShirtStats shirtStats;
} extern teamWork;
typedef map<string, TeamData> TeamMap;
TeamMap::iterator tIter;
ShirtStats::iterator ssIter;
TeamMap teamMap;
typedef vector<TeamData> TeamVector;
typedef TeamVector::iterator TeamIter;
TeamVector teamVect;
TeamIter tvIter;

---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com

[Luca Risolia]

Mike Copeland wrote:

> Is it possible to simply (single statement) move the data from one
> container type (the TeamMap, below) to a different type of container
> (the TeamVector, below)?

std::for_each(std::make_move_iterator(std::begin(TeamMap)),
std::make_move_iterator(std::end(TeamMap)),
[](decltype(TeamMap)::value_type&& v) {
TeamVector.push_back(std::move(v.second));
});

[Ian Collins]

Mike Copeland wrote:
> Is it possible to simply (single statement) move the data from one
> container type (the TeamMap, below) to a different type of container
> (the TeamVector, below)? My data resides in the map object, but since I
> have to occasionally display the data in different orders (e.g.
> teamName, teamTypeCode), I must copy the data to a vector and sort it
> before producing my listings.
> I know that I can copy the individual objects from the map to the
> vector one-at-a-time, but I'm hoping that there's a technique that will
> do it simply and quickly. Any thoughts? TIA

Construct the vector using the map's beginning and end:

TeamVector t( teamMap.begin(), teamMap.end() );

--
Ian Collins

[woodb...@gmail.com]

On Monday, January 13, 2014 6:06:47 PM UTC-6, Mike Copeland wrote:
> Is it possible to simply (single statement) move the data from one
> container type (the TeamMap, below) to a different type of container
>
> (the TeamVector, below)? My data resides in the map object, but since I
> have to occasionally display the data in different orders (e.g.
> teamName, teamTypeCode), I must copy the data to a vector and sort it
> before producing my listings.
> I know that I can copy the individual objects from the map to the
> vector one-at-a-time, but I'm hoping that there's a technique that will
> do it simply and quickly. Any thoughts? TIA
>

How about

http://www.boost.org/doc/libs/1_55_0/libs/multi_index/doc/index.html


That would help you avoid the copying.

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Ike Naar]

That won't work because the value type of the map is not the same as the
value type of the vector.

[Ike Naar]

From Mike's description (snipped) it looks like he wants to copy the
data, not move it.

[Ian Collins]

Whoops, you're right. I was thinking of std::set, not map.

--
Ian Collins

[Alf P. Steinbach]

The following little class comes in handy then:


[code]
template< class Iter, class Referent, class Remap_func >
struct Remap_iter
: Iter
{
typedef Iter Base;

Referent& operator* ()
{ return Remap_func()( Base::operator*() ); }

Referent const& operator* () const
{ return Remap_func()( Base::operator*() ); }

Remap_iter( Iter const& it )
: Base( it )
{}
};
[code]


It doesn't cover all the cases but one can just add to it. Good enough
for Mike's code with Visual C++. That is,


[code]
struct Map_to_vec
{
TeamData& operator()( TeamMap::value_type& v )
{ return v.second; }
};

int main()
{
typedef Remap_iter< TeamMap::iterator, TeamData, Map_to_vec > Vec_iter;

TeamMap m;
TeamVector v( Vec_iter( m.begin() ), Vec_iter( m.end() ) );
}
[/code]


compiles nicely.

Disclaimer: haven't tested it with any data!


Cheers & hth.,

- Alf

[Juha Nieminen]

Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
> The following little class comes in handy then:

Or instead you could do the sensible thing and use a 1-liner:

for(auto& element: theMap) theVector.push_back(element.second);

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Alf P. Steinbach]

On 14.01.2014 10:49, Juha Nieminen wrote:
> Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
>> The following little class comes in handy then:
>
> Or instead you could do the sensible thing and use a 1-liner:
>
> for(auto& element: theMap) theVector.push_back(element.second);

I'm not sure it's always so sensible as a /general/ solution, which I
somewhat unthinkingly aimed at.

In particular, if you want to declare `theVector` as `const`, which is
usually a good idea since one can then be sure at a glance that it won't
change, then the above approach needs a lambda or named function:

vector<TeamData> theVector( [&]() -> vector<TeamData>
{
vector<TeamData> result;
for(auto& element: m) theVector.push_back(element.second);
return result;
}() );

Like, ouch. I think the "iterator conversion" approach stands a much
better chance of reducing that to something more simple &
straightforward, something without case-specific code. Perhaps even
something readable...

However, I agree that the loop is probably the best advice to Mike, the OP.

Dang, I didn't think of that.


Cheers,

- Alf

[Seungbeom Kim]

(Assuming you want to move the contents)

Given the following declarations:
> struct TeamData;
> typedef std::map<std::string, TeamData> TeamMap; TeamMap teamMap;
> typedef std::vector<TeamData> TeamVector; TeamVector teamVect;

It should read like this:

std::for_each(std::make_move_iterator(std::begin(teamMap)),
std::make_move_iterator(std::end(teamMap)),
[&](decltype(teamMap)::value_type&& v) {
teamVect.push_back(std::move(v.second));
});

By the way, I think it can be made simpler like this:

std::for_each(std::begin(teamMap),
std::end(teamMap),
[&](decltype(teamMap)::value_type& v) {
teamVect.push_back(std::move(v.second));
});

A function that takes an lvalue parameter and moves things out of it
is dangerous in general, but this is a lambda function used specifically
for moving the contents out of an existing container, so it is okay.
And whether you take an lvalue parameter or an rvalue parameter,
it becomes an lvalue inside the function and you need std::move anyway.

--
Seungbeom Kim

[Vir Campestris]

On 14/01/2014 00:06, Mike Copeland wrote:
> Is it possible to simply (single statement) move the data from one
> container type (the TeamMap, below) to a different type of container
> (the TeamVector, below)?

Having read all the solutions, and having a nagging feeling there's
something you can do with bind... I'll add merely one thing I'm sure of.

If the map is of any reasonable size it's probably worth doing a
reserve(...) first.

Andy

[Mr Flibble]

Actually the benefit of doing 'reserve' diminishes as the number of
elements increases.

/Flibble

[woodb...@gmail.com]

On Tuesday, January 14, 2014 3:14:09 PM UTC-6, Mr Flibble wrote:

>
> Actually the benefit of doing 'reserve' diminishes as the number of
> elements increases.

Maps may be the worst standard container.
I also avoid std::list.


Brian
Ebenezer Enterprises - So far G-d has helped us.
http://webEbenezer.net

[Jorgen Grahn]

On Tue, 2014-01-14, woodb...@gmail.com wrote:
> On Tuesday, January 14, 2014 3:14:09 PM UTC-6, Mr Flibble wrote:
>
>>
>> Actually the benefit of doing 'reserve' diminishes as the number of
>> elements increases.
>
> Maps may be the worst standard container.

Why? I find it invaluable -- it gives you the type->type mapping most
modern languages have. (Of course, unordered_map does most of the
same things, and for the few cases where it matters, slightly faster.)

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[woodb...@gmail.com]

On Tuesday, January 14, 2014 4:36:46 PM UTC-6, Jorgen Grahn wrote:
> On Tue, 2014-01-14, woodb...@gmail.com wrote:

> > Maps may be the worst standard container.
>
> Why? I find it invaluable -- it gives you the type->type mapping most
> modern languages have. (Of course, unordered_map does most of the
> same things, and for the few cases where it matters, slightly faster.)
>

I think the pair based interface is flawed and there should
instead be a container like Boost.intrusive.rbtree in the
standard. It wouldn't have to be intrusive, but it
wouldn't be pair based. Then you're able to work with one
type rather than two types. No more "first' and "second".
Multi_index doesn't use pair in its interface either.

I don't know if what Leigh wrote is correct, but if it is
that would be another strike against maps.

Maps keep track of the number of elements in them. The
boost intrusive library gives you the option to not
have to pay for keeping track of the elements like that.

I think unordered_map is a lame name.

Brian
Ebenezer Enterprises - Heavenly code.
http://webEbenezer.net

[blaz.b...@gmail.com]

std::transform(team_map.begin(), team_map.end(), std::back_inserter(team_vec),
[](decltype(team_map)::value_type e) { return e.second; });

One liner is indeed much clearer :)

[Juha Nieminen]

Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
> In particular, if you want to declare `theVector` as `const`

I suppose you could build a non-const vector and then construct the
const one using "const std::vector<whatever> v(std::move(tmp));"
and if std::vector has been properly implemented the extra copying
will be elided, but yeah, it's kind of a hack (and is not possible
eg. in a class initialization list.)

Which brings up the interesting question of why there isn't a simple
and easy solution in the standard library for this.

[Juha Nieminen]

woodb...@gmail.com wrote:
> I think the pair based interface is flawed and there should
> instead be a container like Boost.intrusive.rbtree in the
> standard. It wouldn't have to be intrusive, but it
> wouldn't be pair based. Then you're able to work with one
> type rather than two types. No more "first' and "second".
> Multi_index doesn't use pair in its interface either.

It almost sounds like you are talking about std::set.

For most situations where you would use std::map, you can use std::set
instead, but to get the same functionality you have to design your
element type appropriately. std::map simply saves you the trouble
and gives you a handy shortcut when you need a type->type relational
data container.

> I think unordered_map is a lame name.

It's descriptive. What else do you want?

[Öö Tiib]

On Wednesday, 15 January 2014 05:38:02 UTC+2, woodb...@gmail.com wrote:
> On Tuesday, January 14, 2014 4:36:46 PM UTC-6, Jorgen Grahn wrote:
> > On Tue, 2014-01-14, woodb...@gmail.com wrote:
>
> > > Maps may be the worst standard container.
> >
> > Why? I find it invaluable -- it gives you the type->type mapping most
> > modern languages have. (Of course, unordered_map does most of the
> > same things, and for the few cases where it matters, slightly faster.)
> >
>
> I think the pair based interface is flawed and there should
> instead be a container like Boost.intrusive.rbtree in the
> standard.

That tree is not map. Map consists of relations of value
of some type to other value of (possibly some other) type.
Such relations or "mappings" are the point of map. You
can use tree of mappings as map but then you need to
describe what is mapping.

> It wouldn't have to be intrusive, but it
> wouldn't be pair based. Then you're able to work with one
> type rather than two types. No more "first' and "second".
> Multi_index doesn't use pair in its interface either.

Pair is a way to represent a mapping. There may be
endless other ways but notice that you propose none.

If you need a set with specific iteration order or search
criteria then you indeed can use 'boost::intrusive::set' or
'boost::intrusive::multiset'. If you need a set with
several iteration orders or search criteria then you
can use 'boost::multi_index_container'. Those are not
maps. Do not use 'map', 'multimap' or 'unordered_map'
indeed if you just need 'set'.

> I don't know if what Leigh wrote is correct, but if it is
> that would be another strike against maps.

Yes, it is correct about most implementations of vector.
Those reserve automatically double bigger buffer when
vector runs out of space. So benefit is log N and so
the difference diminishes when N grows. If you want
a map implementation based on vector then take
'boost::flat_' (multi)map/set'.

> Maps keep track of the number of elements in them. The
> boost intrusive library gives you the option to not
> have to pay for keeping track of the elements like that.

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.

> I think unordered_map is a lame name.

There is 'typedef' if you need better describing alias for type.
Therefore "is a lame name" is not that convincing argument.

[woodb...@gmail.com]

On Wednesday, January 15, 2014 10:01:54 AM UTC-6, Juha Nieminen wrote:
> woodb...@gmail.com wrote:
>
> > I think the pair based interface is flawed and there should
>
> > instead be a container like Boost.intrusive.rbtree in the
>
> > standard. It wouldn't have to be intrusive, but it
>
> > wouldn't be pair based. Then you're able to work with one
>
> > type rather than two types. No more "first' and "second".
>
> > Multi_index doesn't use pair in its interface either.
>
>
>
> It almost sounds like you are talking about std::set.
>
> For most situations where you would use std::map, you can use std::set
> instead, but to get the same functionality you have to design your
> element type appropriately. std::map simply saves you the trouble
> and gives you a handy shortcut when you need a type->type relational
> data container.
>

I believe std::set has some const assumption that makes it
difficult to use as an alternative.

>
> > I think unordered_map is a lame name.
>
> It's descriptive. What else do you want?
>

It isn't very descriptive. It's like saying a
marble is not blue. Hash_map would be better.
I think there was some history with that name,
but think the name could still be changed to
hash_map.

Brian
Ebenezer Enterprises
http://webEbenezer.net

[Öö Tiib]

On Wednesday, 15 January 2014 18:50:53 UTC+2, woodb...@gmail.com wrote:
> On Wednesday, January 15, 2014 10:01:54 AM UTC-6, Juha Nieminen wrote:
> > woodb...@gmail.com wrote:
> > > I think unordered_map is a lame name.
> >
> > It's descriptive. What else do you want?
> >
>
> 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 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. Same was with 'boost::scoped_ptr' that
became 'std::unique_ptr'.

[Mr Flibble]

On 15/01/2014 03:38, woodb...@gmail.com wrote:
>
> I don't know if what Leigh wrote is correct, but if it is
> that would be another strike against maps.

what I said about 'reserve' applied to vectors not maps; map doesn't
have a 'reserve'.

/Flibble

[woodb...@gmail.com]

On Wednesday, January 15, 2014 11:32:44 AM UTC-6, Öö Tiib wrote:
> On Wednesday, 15 January 2014 18:50:53 UTC+2, woodb...@gmail.com 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.
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.

>
> > 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?

[woodb...@gmail.com]

On Wednesday, January 15, 2014 11:40:13 AM UTC-6, Mr Flibble wrote:
>
>
> what I said about 'reserve' applied to vectors not maps; map doesn't
> have a 'reserve'.
>

Oops. Thanks. I vaguely remember hearing discussion
about adding reserve functions to some other containers,
but I don't know if anything came of that.

[woodb...@gmail.com]

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.

[Seungbeom Kim]

On 2014-01-15 08:50, woodb...@gmail.com 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::ordered_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

[Öö Tiib]

On Wednesday, 15 January 2014 22:23:35 UTC+2, woodb...@gmail.com wrote:
> On Wednesday, January 15, 2014 11:32:44 AM UTC-6, Öö Tiib wrote:
> > On Wednesday, 15 January 2014 18:50:53 UTC+2, woodb...@gmail.com 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.

[Öö Tiib]

On Wednesday, 15 January 2014 22:35:01 UTC+2, woodb...@gmail.com 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.

[Seungbeom Kim]

On 2014-01-15 09:32, �� Tiib wrote:
> On Wednesday, 15 January 2014 18:50:53 UTC+2, woodb...@gmail.com 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

[woodb...@gmail.com]

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, woodb...@gmail.com 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.

[Juha Nieminen]

woodb...@gmail.com wrote:
> I believe std::set has some const assumption that makes it
> difficult to use as an alternative.

Fair enough.

>> > I think unordered_map is a lame name.
>>
>> It's descriptive. What else do you want?
>>
>
> It isn't very descriptive. It's like saying a
> marble is not blue. Hash_map would be better.

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.

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

[woodb...@gmail.com]

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::ordered_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.

[Seungbeom Kim]

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

[Vir Campestris]

On 14/01/2014 21:14, Mr Flibble wrote:
> Actually the benefit of doing 'reserve' diminishes as the number of
> elements increases.

Do you have a source for that?

My understanding is that it will expand the vector - usually by doubling
in size or some such - whenever it gets full. This will require a copy
of every single item (1). Worth avoiding if you can.

Andy
--
(1) Even if it's a move in the new C++11 world it won't be zero cost.

[Alf P. Steinbach]

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

[Mr Flibble]

On 16/01/2014 22:06, Alf P. Steinbach wrote:
> 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").

You are a fucking nutter mate.

/Flibble.

[Juha Nieminen]

Seungbeom Kim <musi...@bawi.org> 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?

Does the standard require for std::unordered_map to use the provided
hash function for something?

[Öö Tiib]

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, woodb...@gmail.com 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.

[Robert Wessel]

On Fri, 17 Jan 2014 11:38:20 +0000 (UTC), Juha Nieminen
<nos...@thanks.invalid> wrote:

>Seungbeom Kim <musi...@bawi.org> 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?
>
>Does the standard require for std::unordered_map to use the provided
>hash function for something?

While I can see being able to search for a pair so long a key_equal is
provided, I'm not sure how you could manage the complexity guarantees
if you ignored hash_function. The problem is when hash_function
preprocesses the key in some way before hashing it (for example, you
might lowercase a string, so that the hash is not case sensitive).

[Vir Campestris]

On 17/01/2014 14:28, Robert Wessel wrote:
> While I can see being able to search for a pair so long a key_equal is
> provided, I'm not sure how you could manage the complexity guarantees
> if you ignored hash_function. The problem is when hash_function
> preprocesses the key in some way before hashing it (for example, you
> might lowercase a string, so that the hash is not case sensitive).

That doesn't matter, it's what the key_equal does that counts.

You'll still be able to store objects if your hash just returns zero -
it's for efficiency only that you want to minimise hash clashes.

Andy

[Robert Wessel]

Which is why I said: "While I can see being able to search for a pair

[woodb...@gmail.com]

Please don't swear here, Leigh.

[woodb...@gmail.com]

On Friday, January 17, 2014 3:53:13 PM UTC-6, Vir Campestris wrote:
>
> That doesn't matter, it's what the key_equal does that counts.
>
> You'll still be able to store objects if your hash just returns zero -
> it's for efficiency only that you want to minimise hash clashes.
>

I'd consider that to be an efficiency bug.

[woodb...@gmail.com]

On Wednesday, January 15, 2014 4:52:38 PM UTC-6, Öö Tiib wrote:
>
> 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.

It seems there were some sadists on the committee --
"What is is right."

Oh well, we have alternatives beyond committee's ideas.
For example, if you are working on on line services,
you may have a lot of freedom in terms of what libraries
you use in the back end of your service.


Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Seungbeom Kim]

On 2014-01-17 03:38, Juha Nieminen wrote:
> Seungbeom Kim <musi...@bawi.org> wrote:
>>
>> 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?
>
> Does the standard require for std::unordered_map to use the provided
> hash function for something?

Almost. Yes practically. 23.2.5[unord.req]/9:
"Keys with the same hash code appear in the same bucket."

Technically, an unordered associative container may avoid using the
hash function without violating that requirement if it chooses to use
a single bucket (even as it creates more buckets to lower the "nominal"
load factor), but it was never meant to be used that way, and it would
be a terrible QoI issue.

Anyway, my point was that the standard requires in the interface
specification the existence of something called a "hash function" and
that the word "hash" doesn't just refer to an implementation detail.

--
Seungbeom Kim