Logo

Programming-Idioms

  • C++
  • Java

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] 
import java.util.HashSet;
import java.util.ArrayList;
x = new ArrayList<T>(new HashSet<T>(x));

This creates a new ArrayList object.
Original ordering is not preserved.
import java.util.ArrayList;
import java.util.LinkedHashSet;
x = new ArrayList<>(new LinkedHashSet<>(x));
import java.util.HashSet;
import java.util.Iterator;
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).
import java.util.HashSet;
import java.util.List;
import java.util.Set;
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.
import java.util.Iterator;
import java.util.List;
Iterator<T> g;
T t;
int i, n;
for (i = 0, n = x.size(); i < n; ++i) {
    t = x.get(i);
    g = x.listIterator(i + 1);
    while (g.hasNext())
        if (g.next().equals(t)) {
            g.remove();
            --n;
        }
}
#include <string>
#include <unordered_set>
#include <vector>
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.
#include <algorithm>
#include <vector>
std::sort(x.begin(), x.end());
auto last = std::unique(x.begin(), x.end());
x.erase(last, x.end());

List x must be a STL container like a std::vector.
(distinct x)
New implementation...
< > ⌨
programming-idioms.org 
x = new ArrayList<T>(new HashSet<T>(x));
x = new ArrayList<>(new LinkedHashSet<>(x));
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);
  }
}
Set<T> uniques = new HashSet<>(x);
x.clear();
x.addAll(uniques);
Iterator<T> g;
T t;
int i, n;
for (i = 0, n = x.size(); i < n; ++i) {
    t = x.get(i);
    g = x.listIterator(i + 1);
    while (g.hasNext())
        if (g.next().equals(t)) {
            g.remove();
            --n;
        }
}
std::vector<std::string> x = {"one", "two", "two", "one", "three"};
std::unordered_set<std::string> t;
for (auto e : x)
    t.insert(e);
std::sort(x.begin(), x.end());
auto last = std::unique(x.begin(), x.end());
x.erase(last, x.end());
(distinct x)
var uniques = x.Distinct().ToList();
x = redBlackTree(x)[].array;
x = x.sort.uniq.array;
x = x.toSet().toList();
Enum.uniq(x)
S = lists:usort(X)
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]
}
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]
seen := make(map[T]bool)
j := 0
for _, v := range x {
	if !seen[v] {
		x[j] = v
		j++
		seen[v] = true
	}
}
x = x[:j]
slices.Sort(x)
x = slices.Compact(x)

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 = x2
x.unique()
nub x
const seen = new Set();
x = x.filter( v => {
  if(seen.has(v))
    return false;
  seen.add(v);
  return true;
});
x = Array.from(new Set(x));
x = [...new Set(x)];
x = x.toSet().toList()
x = x.distinct()
(remove-duplicates x)
local seen = {}
for index,item in ipairs(x) do
	if seen[item] then
		table.remove(x, index)
	else
		seen[item] = true
	end
end
[NSSet setWithArray:x].allObjects
$x = array_unique($x);
var
  x: TList;
begin
  for i:= x.count-1 downto 0 do
    if x.indexOf(x.items[i]) <> -1 then
      x.delete(i);
end;
@x = uniq(@x);
def dedup(x):
  y = []
  for i in x:
    if not i in y:
      y.append(i)
  return y
x = list({*x})
a, b, n = 0, 0, len(x)
t = None
while a != n:
    t, b = x[a], a + 1
    while b != n:
        if x[b] == t:
            del x[b]
            n = n - 1
        else: b = b + 1
    a = a + 1
x = list(set(x))
x = list(OrderedDict(zip(x, x)))
x.uniq!
let dedup: Vec<_> = x.iter().unique().collect();
x.sort();
x.dedup();
x = x.distinct
(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)
x intersection: x asSet.
x asSet.
x = x.Distinct.ToList