CODEWITHSUNDEEP
c++unordered-map
Rahul Iyer
Rahul Iyer

Reputation: 21025

How to optimise unordered_map lookup?

It seems that my program performance is bottlenecked by the following function:

inline bool isKeyInMap(const std::string key, std::unordered_map<std::string, MyClass>map)
{
    auto t = map.find(key);
    if (t == map.end()) return false;
    return true;
}

Is there a way to speed this up ?

EDIT: The code was part of a larger function. The passing by value was not on purpose - I wrote the above one to remove any code which had nothing to do with the bottle neck. I was trying to see if there is a faster way to do the following:

auto t = map.find(key);
if (t == map.end()) return false;
return true;

If I was as good a C++ programmer as the rest of you, I wouldn't be posting here in the first place. XD

Upvotes: 1

Views: 2658

Answers (4)

ravi
ravi

Reputation: 10733

There are two main things related to performance here.

1) You are asking to optimize search operation in unordered_map.

Unordered map is implemented as some sort of hash table. So, look-up in it is O(1) most of the times. That's the minimum cost so there's no further optimization possible in that.

2) You are passing map by value which results in copying of all map elements to some other value.

Only optimization you can do over here is pass map by const reference so as to avoid copying as well as changing contents of map.

Upvotes: 3

CinCout
CinCout

Reputation: 9619

Each time you pass by value, you end up copying everything into temporary variables. Pass by reference must do the trick:

inline bool isKeyInMap(const std::string& key, std::unordered_map<std::string, MyClass>& map) const
{
    auto t = map.find(key);
    if (t == map.end()) return false;
    return true;
}

Also, notice the const at the end of the method! Since you won't modify any member variable in this method, it's good to declare it const.

Upvotes: 0

Barry
Barry

Reputation: 303087

You're passing both the key and the map by value, and both of those copies are pretty expensive. Just changing the signature to:

inline bool isKeyInMap(const std::string& key, 
    const std::unordered_map<std::String, MyClass>& map);

should be dramatically faster.

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 477060

Pass the arguments by reference, not by value:

bool isKeyInMap(const std::string & key,
                const std::unordered_map<std::string, MyClass> & m)
{
    return m.find(key) != m.end();
}

Otherwise you end up copying everything every time you're making a query.

Upvotes: 7

Related Questions