CODEWITHSUNDEEP
c++algorithmperformancestltradeoff
xmllmx
xmllmx

Reputation: 42379

Is std::find suitable only for containers whose elements may be not sorted?

We can use std::find on std::set, but it may be slow because std::set has a member function std::set::find that is often faster than std::find.

Is std::find suitable only for containers whose elements may be not sorted, e.g. std::list?

Can std::find prevent the user from using it to find something on std::set?

Upvotes: 2

Views: 119

Answers (2)

Snehasish Sarkar
Snehasish Sarkar

Reputation: 134

Irrespective of the container, std::find() will always take O(n) for the worst case, since underneath it simply does linear iterative search, and compares the values pointed by the iterator.

So it is not capable of taking the benefit of whether elements in that container are sorted, or not.

And no, std::find does not prevent the user to find something on std::set.

Upvotes: 2

Edgar Rokjān
Edgar Rokjān

Reputation: 17483

Generally speaking you can use std::find with all the containers which provide you with input iterators. Here is the info about std::find with its iterator requirements.

The main question is effectiveness. The algorithm does not know anything about the inner representation of the container it works with. So std::find simply iterates over the elements of the particular container.There is no way to prevent it from dealing with containers like std::set. Moreover, it will be contradictory to the design of STL.

As a general rule you should prefer container methods to the algorithms with the same name.

Upvotes: 2

Related Questions