How to remove duplicate elements in a list while preserving order?

Question

I just saw a short video from Seth Ladd on Collections.

A Set has only unique elements (are not ordered), but sometimes i need an ordered list and i want to remove all duplicates (the 2nd occurrence of an element e.g. String should be removed from the list)

original input to a list: A, B, C, B, D, A should result in A, B, C, D. I need to keep the order. A result like B, A, D, C would not help me.

Answer 1

Justin Fagnani already gave a good answer. Here is another one:

Iterable distinct(Iterable i) {
  var map = new LinkedHashMap();
  i.forEach((x) { map[x] = true; });
  return map.keys;  // map.keys.toList() would free the map for GC.
}

Answer 2

Use toSet and then toList

  var ids2 = ["A", "B", "C", "B", "D", "A"];
  var result = ids2.toSet().toList();

[A, B, C, D]

Answer 3

It's fairly easy to implement on your own:

Iterable distinct(Iterable i) {
  var set = new Set();
  return i.where((e) {
    var isNew = !set.contains(e);
    set.add(e);
    return isNew;
  });

It'd be even nicer if Set.add() returned a bool that indicated whether the set was modified:

Iterable distinct(Iterable i) {
  var set = new Set();
  return i.where((e) => set.add(e));
}

You can file feature request bugs of course.

Edit: As Florian points out, the above solution only works if the returned Iterable is only used once. Subsequent uses will return Iterators with no elements, because even element has been seen already on the first use.

To solve this we need to keep a visited set for every Iterator created from the returned Iterable, not just one for the Iterable. We can do that by creating Iterable and Iterator subclasses like with WhereIterable/WhereIterator:

Iterable distinct(Iterable i) => new DistinctIterable(i);

class DistinctIterable<E> extends Iterable<E> {
  final Iterable<E> _iterable;

  DistinctIterable(this._iterable);

  Iterator<E> get iterator {
    return new DistinctIterator<E>(_iterable.iterator);
  }
}

class DistinctIterator<E> extends Iterator<E> {
  final Iterator<E> _iterator;
  final Set<E> _visited = new Set<E>();

  DistinctIterator(this._iterator);

  bool moveNext() {
    while (_iterator.moveNext()) {
      if (!_visited.contains(_iterator.current)) {
        _visited.add(_iterator.current);
        return true;
      }
    }
    return false;
  }

  E get current => _iterator.current;
}

Yes, this is much longer, but it'll work correctly with many-use finite Iterables and one-use infinite Iterables. The infinite iterable use case could easily have problems with memory, which is an argument for not including it in the core lib and forcing developers to make some decisions about what exactly they need.