CODEWITHSUNDEEP
c++algorithmc++11stlset
gsamaras
gsamaras

Reputation: 73444

Optimal way to search a std::set

How should one search a std::set, when speed is the critical criterion for his/her project?

set:find?

Complexity:

Logarithmic in size.

std::binary_search?

Complexity:

On average, logarithmic in the distance between first and last: Performs approximately log2(N)+2 element comparisons (where N is this distance). On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

Just a binary search implemented by him/her (like this one)? Or the STL's one is good enough?

Is there a way to answer this theoretically? Or we have to test ourselves? If someone has, it would be nice if (s)he would share this information with us (if no, we are not lazy :) ).

Upvotes: 3

Views: 763

Answers (2)

Alexander Gessler
Alexander Gessler

Reputation: 46677

The iterator type provided by std::set is a bidirectional_iterator, a category which does not require random access to elements, but only element-wise movements in both directions. All random_access_iterator's are bidirectional_iterators, but not vice versa.

Using std::binary_search on a std::set can therefore yield O(n) runtime as per the remarks you quoted, while std::set::find has guaranteed O(logn).

So to search a set, use set::find.

Upvotes: 4

David Eisenstat
David Eisenstat

Reputation: 65506

It's unlikely that std::set has a random access iterator. Even if it did, std::binary_search would access at least as many nodes as .find, since .find accesses only the ancestors of the target node.

Upvotes: 1

Related Questions