On 04/21/2014 09:22 PM, Taylor Hillegeist wrote:
> Question though? why doesn't canFind() work on statically
> allocated arrays?
That's an issue all of face from time to time. (Happened to me again
last week. :) )
The reason is, algorithms like canFind work with input ranges and
fixed-length arrays are not input ranges because they cannot support
popFront(), which would reduce their length.
The solution is to use a full slice of the array by appending [] to it:
if (stuff[].canFind(2)) { // <-- note []
It works because now canFind() operates on a temporary slice (aka
dynamic array).
Getting back to your original question, std.algorithm.find and canFind()
are O(N) algorithms, which is too slow if you already have a sorted range.
When you indeed have a sorted range, you can pass it through
assumeSorted() to create a SortedRange object so that you can take
advantage of O(log N) algorithms like trisect() and friends (one of
those friends is contains()):
import std.range;
void main()
{
auto arr = [ 1, 2, 3, 3, 4, 5 ];
auto result = arr.assumeSorted.trisect(3);
assert(result[0].equal([ 1, 2 ]));
assert(result[1].equal([ 3, 3 ]));
assert(result[2].equal([ 4, 5 ]));
}
The search in that program is O(log N).
Ali
