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.

Answer 1

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

Answer 2

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.