I don't understand std::tr1::unordered_map

Question

I need an associative container that makes me index a certain object through a string, but that also keeps the order of insertion, so I can look for a specific object by its name or just iterate on it and retrieve objects in the same order I inserted them.

I think this hybrid of linked list and hash map should do the job, but before I tried to use std::tr1::unordered_map thinking that it was working in that way I described, but it wasn't. So could someone explain me the meaning and behavior of unordered_map?

Answer 1

I think that an unordered_map and hash_map are more or less the same thing. The difference is that the STL doesn't officially have a hash_map (what you're using is probably a compiler specific thing), so unordered_map is the fix for that omission.

unordered_map is just that... unordered. You can't depend on it preserving any ordering on iteration.

Answer 2

@wesc: STL has std::map... so what's the difference with unordered_map? I don't think STL would implement twice the same thing and call it differently.

Answer 3

Boost documentation of unordered containers

The difference is in the method of how you generate the look up.

In the map/set containers the operator< is used to generate an ordered tree.

In the unordered containers, an operator( key ) => index is used.

See hashing for a description of how that works.

Answer 4

You sure that std::hash_map exists in all STL implementations? SGI STL implements it, however GNU g++ doesn't have it (it's located in the __gnu_cxx namespace) as of 4.3.1 anyway. As far as I know, hash_map has always been non-standard, and now tr1 is fixing that.

Answer 5

@wesc: I'm sure std::map is implemented by STL, while I'm sure std::hash_map is NOT in the STL (I think older version of Visual Studio put it in a namespace called stdext).

@cristopher: so, if I get it right, the difference is in the implementation (and thus performances), not in the way it behaves externally.

Answer 6

Sorry, read your last comment wrong. Yes, hash_map is not in STL, map is. But unordered_map and hash_map are the same from what I've been reading.

map -> log (n) insertion, retrieval, iteration is efficient (and ordered by key comparison)

hash_map/unordered_map -> constant time insertion and retrieval, iteration time is not guarantee to be efficient

Neither of these will work for you by themselves, since the map orders things based on the key content, and not the insertion sequence (unless your key contains info about the insertion sequence in it).

You'll have to do either what you described (list + hash_map), or create a key type that has the insertion sequence number plus an appropriate comparison function.

Answer 7

You need to index an associative container two ways:

• Insertion order
• String comparison

Try Boost.MultiIndex. I haven't used it this way but I think it's possible.

Answer 8

You've asked for the canonical reason why Boost::MultiIndex was made: list insertion order with fast lookup by key. Boost MultiIndex tutorial: list fast lookup