digitalmars.D.bugs - [Issue 10131] New: To remove duplicates and keep order
- d-bugmail puremagic.com (44/44) May 21 2013 http://d.puremagic.com/issues/show_bug.cgi?id=10131
http://d.puremagic.com/issues/show_bug.cgi?id=10131 Summary: To remove duplicates and keep order Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: bearophile_hugs eml.cc 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. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
May 21 2013