CODEWITHSUNDEEP
c++c++11stlfindcontainers
rwols
rwols

Reputation: 3078

Merits of std::find

Is there any advantage to using C++11's std::find over a container's find method?

Upvotes: 9

Views: 11087

Answers (1)

Andy Prowl
Andy Prowl

Reputation: 126442

In the case of std::vector (which does not have a find method) does std::find use some smart algorithm or the naive way of simply iterating over every element?

It cannot, because vectors are not sorted. There is no other way to find an element in an unsorted vector than a linear search with O(n) complexity.

On the other hand, sequence containers do not offer a find() member functions, so you could not possibly use that.

In the case of std::map it seems you need to pass along an std::pair, which is the value_type of an std::map. This does not seem very useful as usually you'd want to find for either a key or a mapped element.

Indeed, here you should use the find() member function, which guarantees a better complexity (O(log N)).

In general, when a container exposes a member function with the same name as a generic algorithm, this is because the member function does the same thing, but offers a better complexity guarantee.

What about other containers like std::list or std::set or std::unordered_set ?

Just like std::vector, std::list is not a sorted container - so the same conclusion applies.

For std::set and std::unordered_set, instead, you should use the find() member function, which guarantees a better complexity (O(log n) and average O(1), respectively).

Upvotes: 15

Related Questions