On 29 May 2014 22:24, Pete Bartlett wrote:

I realise now that in my case, where the hash calculation is expensive relative to node insertion cost, it is worthwhile doing a sort of memoization technique: If my original key type is K and hash is h, I can change the key type to pair where the keys are now (k,h(k)) and then give the unordered_map an adapted hash that simply returns pair.second. I now only pay the hash calculation cost when first inserting into the submaps. As you point out below, this is only safe for non-random hashes but works for me.

Certainly, I was talking about the fully general case. You can add extra requirements in your own code.

...

...

- some more intrusive change?

...

Maybe. Could write a function that inserts from another container, rather than using >iterators. It is now possible to tell if the same hash function type was used, but it isn't >possible to tell that they're equal (eg. when using a randomized hash function, the hash >values might not be the same for two different instances). It might be possible to create a >type trait to detect if the hash function has an equality operator - and assume they're not >equal if it doesn't.

Having said the above, I fancy a crack at this just for my own education. I'll let you know if I get anywhere.

To be honest, the code's more complicated than it really should be. Although this case might not be too bad. The implementation of insert_range in unique.hpp code is pretty weird - it deals with some edge cases that you don't need to think about, so you could base insertion on something like this (untested): template <class InputIt> void simpler_insert_range(InputIt i, InputIt j) { node_constructor a(this->node_alloc()); for (; i != j; ++i) { insert_range_impl2(a, this->get_key(*i), i, j); } } Hopefully the implementation of insert_range in equivalent.hpp is easier to deal with.