Issue 10131 - To remove duplicates and keep order
Summary: To remove duplicates and keep order
Status: NEW
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P4 enhancement
Assignee: RazvanN
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2013-05-21 16:59 UTC by bearophile_hugs
Modified: 2024-12-01 16:17 UTC (History)
2 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description bearophile_hugs 2013-05-21 16:59:50 UTC
I suggest to add to Phobos a function with semantics similar to this one, that sometimes I find useful:


T[] noDupes(T)(in T[] s) {
    import std.algorithm: canFind;
    T[] result;
    foreach (T c; s)
        if (!result.canFind(c))
            result ~= c;
    return result;
}

void main() {
    import std.string: squeeze;
    assert("AAAA".noDupes == "A");
    assert("AAAA".squeeze == "A");
    assert("ABAC".noDupes == "ABC");
    assert("ABAC".squeeze == "ABAC");
}


Notes:
- It's related to std.string.squeeze and std.algorithm.uniq, but they need the items to be sorted to remove all the duplicates, while the function discussed here doesn't change the order of the items.
- The implementation shown here is slow, O(n^2), because it's meant to just show the semantics clearly. If the items are hashable it's possible to create a O(n) implementation, storing the items in a hash. If the items are comparable it's possible to write a O(n ln n) version that creates an array of sorted pointers and then performs binary searches on it. The O(n^2) version is a fallback if the items are not hashable nor comparable. The three versions are meant to be three parts of the same general function.
Comment 1 Seb 2017-10-10 13:15:12 UTC
PR https://github.com/dlang/phobos/pull/5774
Comment 2 dlangBugzillaToGithub 2024-12-01 16:17:38 UTC
THIS ISSUE HAS BEEN MOVED TO GITHUB

https://github.com/dlang/phobos/issues/9976

DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB