• via Digitalmars-d-bugs (32/32) Dec 21 2016 https://issues.dlang.org/show_bug.cgi?id=16998

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=16998

          Issue ID: 16998
           Summary: Provide a uniq & group range methods that doesn't rely
                    on sortedness
           Product: D
           Version: D2
          Hardware: x86_64
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: greeenify gmail.com

Sorting is in O(n log n) and requires a random access range (=allocation!)
However plain iteration can be done in O(n) and groups can be created with a
simple hashmap and e.g. the simplest implementation of uniq is sth. like this:

auto uniq(R)(R r)
{
    import std.algorithm.iteration : each;
    bool[dchar] d;
    r.each!(key => d[key] = true);
    return d.byKey;
}

unittest
{
    import std.algorithm.iteration : walkLength;
    assert("cbbba"d.uniq.walkLength == 3);
}

The idea is that for the common use case (unsorted ranges), these non-lazy
range functions allocate less and should perform faster.

--