Re: [Boost-users] [unordered] Merging unordered maps

Subject: Re: [Boost-users] [unordered] Merging unordered maps
From: Daniel James (dnljms_at_[hidden])
Date: 2014-05-29 19:06:32

On 29 May 2014 22:24, Pete Bartlett <pete_at_[hidden]> 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<K,size_t> 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.