Does std::map support caching?

Question

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?

Answer 1

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;
}