"in" everywhere

Steven Schveighoffer schveiguy at yahoo.com
Thu Oct 7 07:22:28 PDT 2010


On Thu, 07 Oct 2010 10:09:17 -0400, Daniel Gibson <metalcaedes at gmail.com>  
wrote:

> Steven Schveighoffer schrieb:
>> On Thu, 07 Oct 2010 07:54:14 -0400, atommixz <atommixz at gmail.com> wrote:
>>
>>> It would be nice if it were possible to use the "in" expression  
>>> wherever
>>> possible. Now it is only implemented for associative. arrays. (Weird).
>>> Examples of how this could be used:
>>> - Find string in string
>>> - Search for a character in a string
>>> - Search for an item in the array, array of characters, array of  
>>> strings,
>>> tuples, enum, structure
>>> - what else?
>>  This has been suggested before.  The problem is that 'in' is generally  
>> considered to be a fast operation (< O(n)) so linear search is out.
>>  -Steve
>
> Is it?
> I wouldn't expect it to be < O(n) on a regular array, but it'd still be  
> convenient to have instead of iterating over the array and comparing the  
> contents yourself.

The problem is with generic code.  Generic code that accepts some type  
that defines the "in" operator.  What can that generic code expect for  
performance when using "in"?  As a general rule, generic programming must  
always assume the worst case, and if we have no rules for 'in', the worst  
case is linear.  Which means generic code may not use 'in' when it would  
be a fast operation.  Same thing with indexing.  Try sorting a 'random  
access' range which uses a linear search on opIndex, and see what the  
performance is.

In addition, arr.find(x) seems pretty simple to me.

-Steve


More information about the Digitalmars-d mailing list