Steve Schveighoffer wrote:
BTW, what happens if you pass a sorted list into find? Intuitively,
you'd assume you can pass as assumeSorted? But you can't really do
anything but linear search?
It's up to the designer of the API. Passing a sorted forward range into
sort will cut the average search time in half, which does not improve
complexity.
Then what if you pass a tree structure into find? It's sorted, but not
exactly random access...
I think find should return an iterator/pointer fine, but I don't think
there's a find template that can be used on all possible container
types. Probably the best solution I think is to implement find inside
the container itself, and have the global find function advance a range
to the point of the element (or return an empty range if not found), with
"quick" searches reserved for sorted random-access ranges. Note that stl
works this way.
Yah, that's right. The coolness of the technique comes mostly when the
structure that can help searching is not obvious at the type system
level (e.g. "is sorted") or is present in the needle, not the haystack
(Boyer-Moore). I believe this approach is superior to STL's.
I still think it's cool to have find operate on a variety of haystacks
and needles. That way users don't need to fiddle with details of
changing call syntax etc.
Andrei
