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?

---

@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.

Classics

Answer 1

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.

Attaway

Answer 2

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

Cyan

Answer 3

You need to index an associative container two ways:

• Insertion order
• String comparison

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

Rempe

I know this is a super-old question, but as some answers give Boost Multi Index as the solution to the OP's needs, those are correct, but any recommendation of Boost multi Index IMO should also have links to Boost.Intrusive] (boost.org/doc/libs/1_50_0/doc/html/intrusive.html). More complicated to use, but often more efficient & flexible – Efferent

Yeah, I don't think Intrusive even existed in 2008. – Rempe

Answer 4

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.

Burtonburty

Answer 5

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.

Burtonburty

Answer 6

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.

Burtonburty

Answer 7

@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.

Classics

map is implemented with a balanced binary tree with its limitations and advantages. unordered_map is a hash table. – Brucite