input validation

[Christopher Wright]

Andrei Alexandrescu wrote:
> 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.

How does this work? find in a sorted linked list has the same expected 
runtime as in an unsorted one -- on average, 0.5 * length. Assuming that 
comparisons and iterating are equally expensive, that is. If you assume 
that comparison is more expensive, you can do better, though cheaper 
comparisons don't benefit you at all.