Optimal way to look up std :: set
How should one look for std :: set when speed is a critical criterion for his / her project?
install: find ?
Complexity:
Logarithmic size.
std :: binary_search ?
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 :)).
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
.
It is not true what std::set
a random access iterator has. Even if it did, std::binary_search
it would be able to access at least several nodes as .find
it .find
only accesses the ancestors of the target node.