input validation

[Andrei Alexandrescu]

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