Does std::map support caching?

c++, dictionary, stl

Solution

It does a search through the whole map, there is no caching being done - or at least, the Standard does not mandate any and I would say no implementation does it, because all clients of such an implementation would have to pay for the possibly undesired overhead of updating the cached information after each insertion/removal.

The first approach is the idiomatic way to determine whether a key/value pair is contained in a map (just mind the fact that `operator ->` should be used instead of `operator .`, since what you get from `find()` is an iterator, and the assignment to `iter` should be outside the `if` condition):

auto iter = map.find(key);
if (iter != map.end()) {
    return iter->second;
}

Problem

For example: code1: ``` if((iter = map.find(key)) != map.end()) { return iter->second; } return 0; ``` code2: ``` if(map.count(key) > 0) { return map.at(key); } return 0; ``` code2 is much more simpler, but both `map.count()` and `map.at()` cost O(logn) time. Does `std::map` provide a feature that stores the last search item in cache and make searching same item faster, or does it just perform a second search in the whole map?

Original source