input validation

[Steve Schveighoffer]

On Wed, 04 Mar 2009 13:55:10 -0800, Andrei Alexandrescu wrote:

> bearophile wrote:
>> Andrei Alexandrescu:
>>> Binary search is rather common.
>> 
>> Oh, yes, sorry, I meant among the ones you have listed there...
> 
> Of five, three are frequent (linear, binary, Boyer-Moore), one is a form
> of set intersection (find sorted in sorted), and the odd one is:
> 
> find(a, assumeSorted(b));
> 
> This is rare but has excellent best-case complexity (is it O(a.length /
> b.length)?) and is easy to add for completeness.
> 
>>> As an aside, your use of "index" suggests you return integrals out of
>>> the function. IMHO that's strongly unrecommended.
>> 
>> I don't want to use too much of your time (that it may be better spent
>> with your new child), but I don't understand what you mean. That
>> index() function is meant the index position of the item or
>> sub-sequence into the bigger array (or iterable), and it returns -1 if
>> not found. This is an usual design.
> 
> This is an extremely sloppy design. That it is usual doesn't make things
> any better!
> 
>> Some people think that such controls for -1 value aren't always done,
>> so to avoid that and some bugs, it's better to raise something like
>> IndexException when the needle isn't found.
> 
> Yah, this is the subject of a long rant but in short: returning int from
> find means that essentially that find is unusable with anything except
> random access structures. This in turn means you'd have to have
> different means, APIs, and user code to deal with e.g. lists, in spite
> of the fact that linear search is the same boring thing for all: look at
> the current thing, yes/no, move on to the next thing. IMHO ever since
> the STL has seen the light of day there is no excuse, not even sheer
> ignorance, to ever traffic in integers as a mean to access elements in
> containers, in any language that has even the most modest parameterized
> types capability.
> 
> Returning int from find is an insult. To add injury to it, have find
> also return an int for a list.
> 
> "Is this item in this list?"
> "Yeppers. It's the 538th element. Took me a hike to find it." "Well I
> wanted to do something with it." "Then go get it. I'm telling you, it'll
> take exactly 538 steps."

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?

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.

-Steve