Dominique Devienne
We currently have a unordered_map< Uid, shared_ptr<Identity> >, where Identity already contains the Uid.
So I thought I could avoid the duplicated Uid by using an unordered_set< shared_ptr<Identity>, MyHash, MyPred > to hash/compare by the internal Uid, but unlike a Multi-Index hashed_index [1],unordered doesn't seem to provide:
"lookup operations accepting search keys different from the key_type of the index, which is a specially useful facility when key_type object are expensive to create."
Any reason why unordered cannot allow similar "compatible key" lookups?
There is no technical reason why Boost.Unordered couldn't provide the compatible key functionality. It just happens not to be a feature condidered in the standard, but if you convince the author to add it as an extension implementing it should be trivial.
What kind of overhead is there (memory use, runtime), if any, in using Multi-Index as opposed to unordered_set in this scenario?
No memory overhead, both data structures are equivalent in terms of their internal data structures (for the unique keys case). Speedwise both they should also perform approximately the same, my advice is that you do some profiling to make sure. As you say, Boost.MultiIndex is a heavier library and compile times will reflect that. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo