set find

[qjohnny2000]

Suppose that you are searching for an element in a set but you know
that it is between 2 iterators say iter1 and iter2.

Is there any version of find on a set that is log(n) but where you can
pass in the two iterators as bounds to the find to make it faster.

Basically it is like searching for a name in a telephone book but you
already know it is between page i and page j. You want to do a
binary search between page i and page j for the name. You don't want
to do the binary search on the whole phone book.

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Suppose that you are searching for an element in a set but you know
that it is between 2 iterators say iter1 and iter2.

Is there any version of find on a set that is log(n) but where you can
pass in the two iterators as bounds to the find to make it faster.

Basically it is like searching for a name in a telephone book but you
already know it is between page i and page j. You want to do a
binary search between page i and page j for the name. You don't want
to do the binary search on the whole phone book.

No, the find() of std::set does not accept any such parameters and the
iterators to a set are bidirectional, not random access so you can't
write one of your own. However considering that std::set's find is O(log
n) you have to have quite a large set to gain much from such a search.
If the set is huge and the interval is small you could used std::find
and it might be faster, but you'll never know until you try.