add support for heterogeneous insert

[the5avage]

This pull request adds support for heterogeneous. This is useful for the same reasons as heterogeneous lookup. You can for example insert words from a string into a set of strings, without unnecessary memory allocations (see example).

In addition to the requirements for heterogeneous lookup the "key" type has to be constructible from the "key_equal" type. I strongly recommend using an explicit constructor otherwise you always live in danger of silent copys.

The changes required for this to work are very minor, because most of the code is already generic.

Right now it's only implemented for robin_set and not tested throughoutly, because i want to know what you think about it before i waste my time.

example.cpp.txt

[Tessil]

Hi,

Thank you for your contribution.

Currently you're implementing the insert with the heterogeneous key only for robin_set, how do you plan to do it for robin_map? The current insert method of the map takes a std::pair<Key, T>, would you create a similar method to accept a heterogeneous key in the first element of the pair and then create a real std::pair<Key, T> if needed? Or do you plan to change try_emplace to accept a heterogeneous key (but then we will have a weird mismatch between the API of the set and the map where one accept heterogeneous keys for the insert method but the other only for the try_emplace method).

[the5avage]

Because i had a real use-case for the set, i didn't think about the map honestly. Let's say we want to modify my previous example and count how often each distinct word occurs in the string. We can use a map<string, int> and either insert 0 or increment the int. This would work perfectly fine with your first suggestion (create real pair if needed).

One could object that this is not optimal, because when we create pair<Key, T> from pair<KeyEqual, T> we have to move/copy T, which might be expensive. For this map it is not an issue, because it's using open addressing. If moving T is expensive you have a much bigger problem anyway, because T might get moved on rehash (even insertion of other elements in case of robin hash).
Only in case a consistent API with other maps is needed, one might think about passing KeyEqual and T as separate arguments (with & and && overloads). I think this is a bit too speculative and could still be added later if necessary.

I'll implement insert taking a std::pair<KeyEqual, T> when i find some time in the next days...

[Tessil]

Closing, as out-of-date. Don't hesitate to reopen if it's a feature that is still needed.