"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