Comment #0 by bearophile_hugs — 2013-05-21T16:59:50Z
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.