STL structures: "insert if not present" operation?

Question

I'm working on a program right now dealing with some exponential time algorithms. Because of this, a main loop of my program is being run many times, and I'm trying to optimize it as much as possible.

Profiling shows that a large portion of the time is spent in look-up and hash calculation for std::unordered_map.

I'm wondering:

1. Is there a way to cache the hash value of a key for std::unordered_map, and then provide it as an argument to insert later on?

2. Is there a way that I can do the following in a single operation: given an key and value {x,y}, check if key x is in the map, if it isn't, insert it and return {x,y}, otherwise return {x,z} for whatever z is already in the map.

I'm doing something like this right now, but it's inefficient, because I have to calculate the hash for the key and check if it's in the map. But if it isn't in the map, I do a completely separate insert operation. In theory, checking if it is present in the map should find where it would go in the map if inserted.

I'm open to trying other data structures, like std::map or something from Boost, if they would reduce the time for this operation.

Answer 1

You could just use the return value of std::unordered_map::insert() to achieve key existence checking + insertion with single hash calculation.

template<typename K, typename V>
std::pair<K, V> myinsert(std::unordered_map<K, V> &map, const std::pair<K, V> &kv)
{
    return *(map.insert(kv).first);
}