Are std :: find and std :: map.find like O (logN)?

Question

Are std::find and std::map.find both O (logN)? If so, how does std::find implement a search on std::map in logarithmic time?

Is the std::find implementation specialized for the use of std::map ?

Answer 1

No, std::find is O (N), regardless of the container. He does not know the "container", there is no specialization for std::map . std::find uses only iterators that do not have information about the underlying container. According to cppreference.com , an implementation is equivalent to:

 template<class InputIt, class T> InputIt find(InputIt first, InputIt last, const T& value) { for (; first != last; ++first) { if (*first == value) { return first; } } return last; } 

According to the C ++ standard (emphasize mine):

25.2.5 Find [alg.find]

 template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value); ... 

• Returns: the first iterator i in the range [first,last) for which the following conditions are true: *i == value . ,, Returns last if no such iterator is found.

• Difficulty: the most recent is the first application of the corresponding predicate.