www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 16998] New: Provide a uniq & group range methods that doesn't


          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;

    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.

Dec 21 2016