Why does std::map have a find member function?

  • A+
Category:Languages

A colleague and I were discussing the relative merits of member vs. non-member functions. A question arose: why does std::map have a find member function.

My answer was that although you can use std::find on maps, you must search for the key-value pair, or use find_if and e.g. a lambda. However, this is linear and map.find offers a search by key in better than linear time. I ended with the assertion that if it could have been a non-member, then it would have been! (Although, std::string suggests that I might have been somewhat hasty in my generalization).

My colleague pointed out that it would be possible to implement find the same way as a non-member function using map.lower_bound.

Is there a rationale for map.find having been made a member?

 


A big objection to implementing std::find searching for a key on std::map as a non-member function is that doing so would prevent you from implementing the current version of std::find, which searches for a key-value pair.

Being an associative container, std::map contains key-value pairs. Non-member std::find is defined for all containers as a function that searches for an item in the container, which must be a key-value pair for std::map; using std::find to look up an item by its key would be inconsistent.

Obviously, one could implement std::find_by_key function applicable only to maps, but such function would always have a specialization based on the type of map. This provides no improvement in the API design over adding a member-function.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: