13 Sets

The word “set” has more than 400 different definitions in the English language. Are you set to set the set set of sets on the set? That is to say: Are you ready to put the fixed group of mathematical collections on the TV?

The term’s meaning in Dart relates closely to the mathematical meaning. A set is a collection of elements where the order isn’t important and duplicate elements are ignored.

This contrasts with Dart lists, in which order is important and duplicates are allowed.

Because of their characteristics, sets can be faster than lists for certain operations, especially when dealing with large datasets. This makes them ideal for quickly checking whether an element exists in a collection. If you wanted to know whether a list of desserts contained donuts, you’d have to check each dessert to find out. Not so with sets. You ask a set if there are donuts, and the set tells you immediately: Yes, there’s one donut!

Creating a Set

You can create an empty set in Dart using the Set type annotation like so:

final Set<int> someSet = {};

The generic syntax with int in angle brackets tells Dart the set allows only integers. You could just as easily make the type String or bool or double, though.

The following form is shorter but identical in result:

final someSet = <int>{};

The curly braces are the same symbols used for sets in mathematics, which should help you remember them. Be sure to distinguish curly braces in this context from their use for defining scopes, though.

You can also use type inference with a set literal to let Dart determine the element types in the set.

final anotherSet = {1, 2, 3, 1};
print(anotherSet);

Because the set literal contains only integers, Dart can infer the type as Set<int>.

Additionally, you probably noticed there are two 1s there, but because sets ignore duplicates, anotherSet ends up with only one 1. Run that code to verify that anotherSet has only one 1:

{1, 2, 3}

Operations on a Set

In this section, you’ll see some general collection operations that apply to sets.

Checking the Contents

To see whether a set contains an item, use the contains method, which returns a bool.

Add the following to main and run the code:

final desserts = {'cake', 'pie', 'donut'};
print(desserts.contains('cake'));    // true
print(desserts.contains('cookies')); // false

Because desserts contains cake, the method returns true, whereas checking for cookies returns false.

Note

The contains method of the default Set implementation is quite fast. It has constant time complexity, which is written as O(1) in Big O notation. That means no matter how many elements the set contains, it will take the same amount of time to tell you whether a particular value exists in the set or not. There are minor exceptions to that rule, but it’s true in the average case. List also has a contains method. However, this method is much slower if the list contains many elements. The reason is that List.contains has to look at each element to check if the value is the same. This is known as linear time complexity and is written as O(n) in Big O notation, where n is the number of elements in the collection. Read Chapter 2, “Complexity”, in Data Structures & Algorithms in Dart to learn more about time complexity and Big O notation.

Adding Single Elements

Like growable lists, you can add and remove elements in a set. To add an element, use the add method:

final drinks = <String>{};
drinks.add('cola');
drinks.add('water');
drinks.add('cola');
print(drinks);

Run that to see the following set:

{cola, water}

You added cola twice, but only one cola shows up, as expected.

Removing Elements

You can also remove elements using the remove method.

Write the following line below the code you wrote previously:

drinks.remove('water');

Print drinks to reveal only a single element remains:

{cola}

Just like contains, the add and remove methods of the default Setimplementation are on average fast, constant-time operations.

Adding Multiple Elements

Use addAll to add elements from a list into a set:

drinks.addAll(['juice', 'coffee', 'milk']);

Print drinks again to show the new contents:

{cola, juice, coffee, milk}

Looping Over the Elements

Like lists, sets are also iterable collections, so you can iterate over the elements with a for-in loop.

Write the following to try that out:

for (final drink in drinks) {
  print("I'm drinking $drink.");
}

Run your code to produce the output below:

I'm drinking cola.
I'm drinking juice.
I'm drinking coffee.
I'm drinking milk.

Note

Although order isn’t an inherent characteristic of sets, the default implementation of Set in Dart uses LinkedHashSet, which does maintain the order in which the elements were added. Other optional implementations include HashSet, with unordered elements, and SplayTreeSet, with sorted elements.

Copying Sets

A set’s elements are mutable in the same way a list’s elements are. If you forget that, you might be surprised if you try to copy a set in the following way:

final beverages = drinks;
print(drinks);

beverages.remove('milk');
print(drinks);
print(beverages);

beverages points to the same object in memory as drinks does, so calling beverages.remove also removes the element from drinks.

Run the code above to see the result:

{cola, juice, coffee, milk}
{cola, juice, coffee}
{cola, juice, coffee}

The milk is gone from both drinks and beverages.

If you need to make a copy of a set, a convenient way to achieve this is by calling toSetlike so:

final liquids = drinks.toSet();
print(drinks);

liquids.remove('coffee');
print(drinks);
print(liquids);

This time, liquids is a different object in memory than drinks is.

Run that, and you’ll see that removing an element from liquids doesn’t affect the contents of drinks:

{cola, juice, coffee}
{cola, juice, coffee}
{cola, juice}

Note

The Set.toSet trick also works with List.toList when you need to copy a list. This only makes a shallow copy of the collection, though. That means the elements in the copy still point to the same objects in memory as the elements in the original collection; the elements aren’t recreated as new objects with the same values. If those elements are mutable, changing them will modify their values in both copies of the collection. If you need a deep copy, where even the elements are copied to new objects, you have to implement that behavior yourself.

Other Operations

Almost everything you learned about lists in Chapter 12, “Lists”, also applies to sets. Specifically, you can perform any of the following operations with sets:

• collection if
• collection for
• spread operators

The main thing you can do with lists that you can’t do with sets is access the elements by index.

Exercise

1. Create an empty set of type String and name it animals.
2. Add three animals to it.
3. Check if the set contains 'sheep'.
4. Remove one of the animals.

Set Relationships

Sometimes you have multiple datasets and want to know how they compare. Set A and Set B in the diagram below both contain integers, some of which are the same and others are different:

You’ve probably seen your share of Venn diagrams; if not in school, then at least as memes on the internet. They’re useful for showing the common elements between two sets.

In the diagram above, the numbers 1 and 4 occur in both sets. You can represent that with the following Venn diagram, where repeated members appear in the overlapping portion of both ovals:

Intersections

Finding the intersection of two sets in Dart tells you the common elements in them. The numbers 1 and 4 are the intersection of Set A and Set B:

Given the following two sets:

final setA = {8, 2, 3, 1, 4};
final setB = {1, 6, 5, 4};

Find the intersection like so:

final intersection = setA.intersection(setB);

Because both sets contain the numbers 1 and 4, that’s the answer you’re expecting. Print intersection to see:

{1, 4}

No disappointments there.

Unions

Combining two sets gives you the union. If there are any duplicates between the subsets, the union only includes them once:

Unions are as easy to find in Dart as intersections were.

Add the following line below what you wrote earlier:

final union = setA.union(setB);

Print union to see the results:

{8, 2, 3, 1, 4, 6, 5}

This union represents all the elements from both sets. Remember — sets do not need to be in order.

Difference

The difference is what one set contains that another does not. You can think of it as subtracting one set from another. In the image below, Set A is different than Set B because Set A includes the values 8, 2 and 3 whereas Set B doesn’t. Or an alternate way of stating that would be: Set A minus Set B equals the new set {8, 2, 3}:

Find the difference in Dart by writing the following:

final differenceA = setA.difference(setB);

Print differenceA to see the set below:

{8, 2, 3}

Of course, it’s also possible to find the difference going the other way:

Reverse your As and Bs to write the following:

final differenceB = setB.difference(setA);

Print differenceB to get the expected output:

{6, 5}

Exercise

Find the intersection and union of the following three sets:

final nullSafe = {'Swift', 'Dart', 'Kotlin'};
final pointy = {'Sword', 'Pencil', 'Dart'};
final dWords = {'Dart', 'Dragon', 'Double'};

Finding Duplicates

Because adding to and checking a set’s elements are fast operations, one application of this data structure is for finding duplicate elements in other collections.

In the sections below, you’ll first generate a list of random numbers and then use a set to check whether the list contains any duplicates.

Random Number Generation

Many applications require randomization, especially games. This makes your program more interesting and less predictable. Here are a few examples of where you would want to generate random values:

• Dealing a hand of cards.
• Rolling dice.
• Creating terrain and landscapes.
• Suggesting a secure password.

If the cards were always in the same order, your Solitaire game would get boring, wouldn’t it?

Generating a List of Random Integers

You can generate random values in Dart with the Random class from the dart:mathlibrary.

First, import the dart:math library at the top of your Dart file:

import 'dart:math';

Then, add the following code to main to generate a list of 10 random integers in the range 1-10:

// 1
final randomGenerator = Random();
final randomIntList = <int>[];

for (int i = 0; i < 10; i++) {
  // 2
  final randomInt = randomGenerator.nextInt(10) + 1;
  randomIntList.add(randomInt);
}

print(randomIntList);

Here’s what’s happening:

1. Random is a class that generates random values of types int, double and bool.
2. In this case, you want integers, so you call nextInt. This method generates a random integer between 0 and one less than the maximum value you give it — in this case, 10. Because you want a number between 1 and 10, not 0 and 9, you must add 1 to the random number.

Run the code above, and you’ll see a list of 10 integers. You have a better chance of getting struck by lightning than getting the same numbers as in the list below, but here’s what this chapter got:

[8, 3, 2, 3, 7, 7, 4, 5, 6, 2]

Notice there are some repeats in there. Those are what you want to find in the next step.

Finding Duplicate Integers in the List

Now, add the following code below what you wrote before:

// 1
final uniqueValues = <int>{};
final duplicates = <int>{};

for (int number in randomIntList) {
  // 2
  if (uniqueValues.contains(number)) {
    duplicates.add(number);
  }
  // 3
  uniqueValues.add(number);
}

print(duplicates);

This is how you would find the duplicate values in randomIntList:

1. Here, you initialize two empty sets: one to store every unique value in randomIntList, the other to store the duplicate values.
2. Add any duplicate you find to your duplicate list.
3. You could put this line in an else block, but sets ignore adding a duplicate, so it doesn’t matter.

Note

If you only wanted to find the unique values in randomIntList, you could call randomIntList.toSet(). Converting a list to a set removes all the duplicates.

Rerun your code to see something like the following:

[2, 4, 3, 7, 9, 5, 1, 10, 2, 9]
{2, 9}

The first line is the random list of 10 integers this chapter got. It’s different than the list generated earlier because Random gives new values every time it’s run. The second line shows the result of printing the duplicates set. In this instance of randomIntList, 2 and 9 are both duplicates.

Note

If you’re familiar with random number generation in other programming languages, you might wonder about the seed, a number used to initialize the internal algorithm that produces the pseudo-random values. For those who aren’t aware of it, computers don’t produce truly random numbers. Randomdoesn’t require a seed, though, and gives you different values every time you run the code. However, you can optionally provide a seed as an argument to the constructor if you like.

That wraps up your study of sets. You’ll learn about another important collection data structure called a map in the next chapter. But first, take some time to work on a few challenges.

Challenges

The following challenges will test your knowledge of sets. It’s best if you try to solve them yourself, but solutions are available with the supplementary materials for this book if you get stuck.

Challenge 1: A Unique Request

Write a function that takes a paragraph of text and returns a collection of unique String characters that the text contains.

Hint: Use String.fromCharCode to convert a code point back to a string.

Challenge 2: Symmetric Difference

Earlier in the chapter, you found the intersection and the union of the following sets:

final setA = {8, 2, 3, 1, 4};
final setB = {1, 6, 5, 4};

How would you find the set of all values that are unique to each set, meaning everything but the duplicates 1 and 4:

Key Points

• Sets store unordered collections of unique elements.
• Adding, removing and checking for a value’s existence in a set are all fast operations.
• The intersection of two sets is the shared values between them.
• A union of two sets is found by combining the values of both sets.
• The difference of two sets is found by subtracting one set from the other.
• One application of sets is for finding duplicate elements in other collections.