c++ - Time complexity of find() in std::map?

Question

How efficient is the find() function on the std::map class? Does it iterate through all the elements looking for the key such that it's O(n), or is it in a balanced tree, or does it use a hash function or what?

Answer 1

Log(n) It is based on a red black tree.

Edit: n is of course the number of members in the map.