Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 61 ยท Collections

Sets

Learn Dart sets: unique elements, set literals vs maps, union, intersection and difference, how equality works, and LinkedHashSet, HashSet and SplayTreeSet.

A Set<E> is a collection of unique items. Adding something that is already in the set changes nothing. Sets answer two questions very quickly: "is this value in the collection?" and "which values appear in both of these collections?". If you have ever removed duplicates from a list or checked whether a user already has a permission, a set was the right tool.

The Dart code is read-only; TypeScript stand-ins let you run the matching ideas.

Creating sets

A set literal uses curly braces around values:

DART
void main() {
  var colors = {'red', 'green', 'blue'};   // Set<String>
  var empty = <String>{};                  // an empty set of strings
  Set<int> ids = {};                       // empty set, type from the variable

  print(colors);          // {red, green, blue}
  print(empty.isEmpty);   // true
  print(ids.runtimeType); // _Set<int> (printed name varies)
}

There is one trap. Both sets and maps use braces, and an empty {} with no type information is a map:

DART
void main() {
  var oops = {};            // Map<dynamic, dynamic>, not a set!
  var fine = <int>{};       // a set
  print(oops.runtimeType);  // a Map
  print(fine.runtimeType);  // a Set
}

A literal with elements and no colons, like {1, 2, 3}, is a set. One with key: value pairs is a map. For an empty set always write the type.

You can also build a set from another collection, which is the easiest way to remove duplicates:

DART
void main() {
  var tags = ['dart', 'flutter', 'dart', 'web', 'flutter'];
  var unique = tags.toSet();          // {dart, flutter, web}
  var again = Set.of(tags);           // same result
  var cleaned = tags.toSet().toList(); // back to a list without duplicates
  print(unique);
  print(again.length);   // 3
  print(cleaned);        // [dart, flutter, web]
}

Adding, removing and testing

DART
void main() {
  var seen = <int>{};

  print(seen.add(5));        // true: it was new
  print(seen.add(5));        // false: already there, nothing changes
  seen.addAll([6, 7, 7]);
  print(seen);               // {5, 6, 7}

  print(seen.contains(6));   // true
  print(seen.remove(6));     // true
  print(seen.remove(99));    // false: wasn't there
  print(seen.length);        // 2
  print(seen.containsAll([5, 7]));   // true
}

add returns a bool that tells you whether the item was new. That makes a handy duplicate detector: if (!seen.add(value)) { /* duplicate */ }. Looking something up with contains is very fast, much faster than contains on a long list, because a set finds the item through a hash code instead of scanning.

TypeScript Unique values and duplicate detection (TypeScript stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

Set operations

Sets support the classic operations from maths class. Each returns a new set and leaves the originals alone:

DART
void main() {
  var frontend = {'html', 'css', 'dart'};
  var backend = {'dart', 'sql', 'docker'};

  print(frontend.union(backend));         // {html, css, dart, sql, docker}
  print(frontend.intersection(backend));  // {dart}
  print(frontend.difference(backend));    // {html, css}
  print(backend.difference(frontend));    // {sql, docker}
}
flowchart LR
    subgraph A["frontend"]
        a1["html"]
        a2["css"]
    end
    subgraph B["both"]
        c1["dart"]
    end
    subgraph C["backend"]
        b1["sql"]
        b2["docker"]
    end
    A --- B --- C

Left to right: only in frontend, in both (the intersection), only in backend. The union is everything; the difference removes the overlap.

Other useful members: isSubsetOf does not exist in the core library, but containsAll does the same job (big.containsAll(small)), and lookup(value) returns the element stored in the set that equals the argument, or null. Because sets are Iterables, they also have map, where and the rest of the iterable methods.

How a set decides two items are the same

A set treats two values as duplicates when a == b is true and their hashCode values match. For numbers and strings that is value equality, so {'a', 'a'} holds one item. For your own classes, == defaults to identity: two objects are equal only if they are the very same object. So two separately created objects with the same fields count as different:

DART
class Point {
  final int x, y;
  Point(this.x, this.y);
}

void main() {
  var points = {Point(1, 2), Point(1, 2)};
  print(points.length);   // 2: different objects, default == is identity
}

To make a set (or a map key) treat equal-looking objects as one, override == and hashCode together. A later lesson, Operator Overloading, ==, hashCode and toString, shows how; records already compare by value, so {(1, 2), (1, 2)} has one element.

TypeScript Value equality versus identity (TypeScript stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or readFileSync(0)), it gets the next line from this box.

Which kind of set?

Set is an abstract interface, and the literal {...} gives you a LinkedHashSet, the default implementation. It remembers insertion order, so iterating gives items in the order they were first added. The dart:collection library offers other flavours:

Class Iteration order Lookup speed Notes
LinkedHashSet (the default) order of insertion fast (hash) what {...} creates
HashSet unspecified fast (hash) slightly lighter, order not guaranteed
SplayTreeSet sorted logarithmic needs Comparable items or a compare function
DART
import 'dart:collection';

void main() {
  var sorted = SplayTreeSet<int>()..addAll([5, 1, 4, 1, 3]);
  print(sorted);            // {1, 3, 4, 5}
  print(sorted.first);      // 1
  print(sorted.last);       // 5

  var byLength = SplayTreeSet<String>((a, b) => a.length.compareTo(b.length));
  byLength.addAll(['pear', 'fig', 'plum']);
  print(byLength);          // {fig, pear}  (plum has the same length as pear: duplicate)
}

The last line shows a subtle point: with a custom comparison, two items are "the same" when the function returns zero. If you need identity-based membership, use Set.identity(), which compares with identical instead of ==.

Constant sets

A const set is unmodifiable and must not contain duplicate elements, because the compiler can see them:

DART
const vowels = {'a', 'e', 'i', 'o', 'u'};
// const bad = {'a', 'a'};   // compile-time error: duplicate element

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the type of var x = {};?

    An empty pair of braces without type information is a map. Write <int>{} (or give the variable a Set type) to get an empty set.
  2. 2. What does seen.add(5) return when 5 is already in the set?

    Set.add returns a bool saying whether the item was new. It returns false for a duplicate and leaves the set unchanged.
  3. 3. Which call gives the items that are in both sets a and b?

    intersection returns a new set with the items present in both. union returns everything, and difference returns items only in the receiver.
  4. 4. Why does {Point(1, 2), Point(1, 2)} hold two items when Point does not override ==?

    Without an overridden == and hashCode, two objects are equal only if they are the same instance. Override both to compare by value.
  5. 5. Which set keeps its items sorted?

    SplayTreeSet from dart:collection keeps items in sorted order. LinkedHashSet keeps insertion order and HashSet makes no ordering promise.

Summary

  • A Set holds unique items; {1, 2, 3} is a set literal, but a bare {} is a map, so type empty sets (<int>{}).
  • add returns false for a duplicate; contains is fast because sets use hashing.
  • union, intersection and difference return new sets; toSet() removes duplicates from any iterable.
  • Membership uses == and hashCode, so your own classes need both overridden to compare by value.
  • The default set keeps insertion order; SplayTreeSet keeps items sorted; Set.identity() compares by identity.

Next, pair keys with values in Maps.