What is the fastest way to check if value is exists in std::map?-CodePudding

What is the fastest way to check if value is exists in the std::map<int, int>? Should I use unordered map? In this task I can't use any libraries instead of std.

Now, I am not know any ways to do this without checking all values.

CodePudding user response：

The fastest way is to not do it. Don't look for values in maps, look for keys in maps.

If you need to search for a value, use another data structure (or a separate map).

The only way to search for a value in a map is linearly (O(N)), but due to caching overhead in iterating over the map data structure, it's going to be even slower than iterating over e.g. a vector.

CodePudding user response：

Unless you have very big data sets (over 100'000 or so) access times into maps should not bother you, since it's gonna be really minuscule in either cases, because you just have int as a key already. To check whether value exist in a map or not you should just use iterators or maybe std::find_if. Doesn't really matter what way you choose it's gonna be linear (O(n)) anyway.

// both examples assume you using c   17 standart
// simple cycle variant
bool is_value_exists(auto const &map, int val) {
  for (auto const &[key, value] : map) {
    if (value == val) return true;
  }
  return false;
}
// find if version
#include <algorithm>
bool is_value_exists2(auto const &map, int val) {
  return std::find_if(
    map.begin(), 
    map.end(),
    [val](auto const &kv) { return kv.second == val; }
  ) != map.end();
}

CodePudding user response：

Regarding the values, a map is not really different from a list or a vector. So exhaustive (linear) search is the fastest way.

CodePudding user response：

Whenever you are entering key-value pair into the std::map instance, also add its pointer to the iterator of that element in an std::vector<iterator_...> variable.

myVec[value]=myMap.find(key); // at time of inserting a new key

This way, you can just use the value as a key(index) in the vector and directly access the map content using that pointer after comparing to nullptr.

Biggest downside is the extra book-keeping required when you remove keys from the map. If the removing operation is frequent enough, you may also use a map in place of it because if the expected value-range is too big (like all of 32bits), it is not memory-efficient.

You can also use the map-iteration-search as a backing-store of a direct-mapped cache (which works the fastest for integer keys(values here)). All cache-hits would be served at the cost of just a bitwise & operation with some value like 8191, 4095, etc (O(1)). All cache-misses would still require a full iteration of the map elements that is slow (O(N)).

So, if the cache-hit ratio is close to 100%, it can approach O(1), otherwise it will be O(N) that is slow.

CodePudding user response：

You can find and element using the find method. Maps are usually implemented by red-black trees, which has a logarithmic search complexity.

If you need to search by a value, then you could create a reverse map, a map which has the values of the initial map as keys and the corresponding keys are the values. You can search for the value by key in the second map, which will yield the key. However, rebuilding the invert map takes resources both in time and storage, so you should only do it if you are going to search multiple times.

CodePudding user response：

To see if any object exists in a map or unordered_map, just say:

auto itor = map.find(key);
if (itor != map.end()) {
    // exists
} else {
    // does not exist.
}

std::unordered_map is typically implemented as a hash table. Hence it has O(1) lookup performance in the average and best cases. And O(N) in the worst case - such as when all the items hash to the same bucket.

std::map is is typically implemented as a red-black tree (a specialized binary tree that can self-balance). It's best, average, and worse case for lookup is O(lg N).

You typically want to use std::unordered_map. Use std::map for when you want to enumerate over items in the collection in sorted order.

You can look up the complexity of most methods on the std:: containers at cplusplus.com or cppreference.com.

https://cplusplus.com/reference/map/map/find/ https://cplusplus.com/reference/unordered_map/unordered_map/find/