Idiom #119 Deduplicate list
Remove duplicates from the list x.
Explain if the original order is preserved.
![Turning list [b,a,b,c] into [b,a,c]](https://storage.googleapis.com/programming-idioms-pictures/idiom/119/dedupe.png)
- Clojure
- C++
- C++
- C#
- D
- D
- Dart
- Elixir
- Erlang
- Go
- Go
- Go
- Go
- Go
- Groovy
- Haskell
- JS
- JS
- JS
- Java
- Java
- Java
- Java
- Java
- Kotlin
- Kotlin
- Lisp
- Lua
- Obj-C
- PHP
- Perl
- Python
- Python
- Python
- Python
- Python
- Ruby
- Rust
- Rust
- Scala
- Scheme
- Smalltalk
- Smalltalk
- VB
std::vector<std::string> x = {"one", "two", "two", "one", "three"};
std::unordered_set<std::string> t;
for (auto e : x)
t.insert(e);Original order is lost.
t contains the new list of unique objects.
t contains the new list of unique objects.
x = x.sort.uniq.array;uniq takes and output a range which could be infinite so it only looks for adjacent duplicates. That's why we sort x beforehand.
x = redBlackTree(x)[].array;Converts to a set then back to an array
slices.Sort(x)
x = slices.Compact(x)
Does not maintain order. Sorts the list. Type has to be comparable.
seen := make(map[T]bool)
j := 0
for _, v := range x {
if !seen[v] {
x[j] = v
j++
seen[v] = true
}
}
for i := j; i < len(x); i++ {
x[i] = nil
}
x = x[:j]Order is preserved.
Use this if T is a pointer type or reference type.
Discarded slots are set to nil, to avoid a memory leak.
This is O(n).
Use this if T is a pointer type or reference type.
Discarded slots are set to nil, to avoid a memory leak.
This is O(n).
y := make(map[T]struct{}, len(x))
for _, v := range x {
y[v] = struct{}{}
}
x2 := make([]T, 0, len(y))
for _, v := range x {
if _, ok := y[v]; ok {
x2 = append(x2, v)
delete(y, v)
}
}
x = x2Original order is preserved.
T is the type of the items.
Iterate twice, from list to map, then from map to list.
This is O(n).
T is the type of the items.
Iterate twice, from list to map, then from map to list.
This is O(n).
func deduplicate[S ~[]T, T comparable](x S) S {
seen := make(map[T]bool)
j := 0
for _, v := range x {
if !seen[v] {
x[j] = v
j++
seen[v] = true
}
}
var zero T
for i := j; i < len(x); i++ {
// Avoid memory leak
x[i] = zero
}
return x[:j]
}deduplicate is generic. Its type parameter T has a constraint: must be comparable with ==.
The order is preserved.
The order is preserved.
seen := make(map[T]bool)
j := 0
for _, v := range x {
if !seen[v] {
x[j] = v
j++
seen[v] = true
}
}
x = x[:j]The order is preserved.
Use this if T is not a pointer type or reference type.
This is O(n).
Use this if T is not a pointer type or reference type.
This is O(n).
final HashSet<T> seen = new HashSet<T>();
final Iterator<T> listIt = x.iterator();
while (listIt.hasNext()) {
final T curr = listIt.next();
if (seen.contains(curr)) {
listIt.remove();
} else {
seen.add(curr);
}
}Preserves the order of the items.
Upon first occurrence, store item in seen; all future occurrences of the item are removed from the list via the iterator listIt, removing the last-returned item.
Requires extra memory for the hash-set.
Note that the runtime cost is O(n^2).
Upon first occurrence, store item in seen; all future occurrences of the item are removed from the list via the iterator listIt, removing the last-returned item.
Requires extra memory for the hash-set.
Note that the runtime cost is O(n^2).
Set<T> uniques = new HashSet<>(x);
x.clear();
x.addAll(uniques);This uses the same List instance, emptied and then refilled.
Original ordering is not preserved.
Original ordering is not preserved.
(define (remove-duplicates l)
(cond ((null? l)
'())
((member (car l) (cdr l))
(remove-duplicates (cdr l)))
(else
(cons (car l) (remove-duplicates (cdr l))))))
(remove-duplicates x)