Optimal way to look up std :: set
How should one look for std :: set when speed is a critical criterion for his / her project?
Complexity:
Logarithmic size.
Complexity:
On average, logarithmically over the distance between first and last: Performs an approximate comparison of log2 (N) +2 elements (where N is the distance). On non-random access iterators, the iterators, on average, produce additional linear complexity in N.
Just a binary search implemented by it (like this one )? Or is STL alone good enough?
Is there a way to answer this in theory? Or do we need to test ourselves? If someone has it, it would be nice if they pass this information on to us (if not, we are not lazy :)).
source to share
The type of iterator provided std::set
is bidirectional_iterator
, a category that does not require random access to elements, but only an element that moves in both directions. All random_access_iterator
are bidirectional_iterator
s, but not vice versa.
Using std::binary_search
on std::set
can, therefore, give O(n)
the lead time according to the remarks you cited, while std::set::find
guaranteed O(logn)
.
To find a set
, useset::find
.
source to share