Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 134 ยท Collections

Sets

Learn Ruby's Set class - creating sets, adding and removing, fast membership tests, union, intersection, difference, subset checks, sets of objects and when to use a Set over an Array.

A set is a collection of unique values with no meaningful position. You can ask "is this in the set?" very quickly, add and remove members, and combine sets with the operations you know from school maths: union, intersection and difference. Whenever you find yourself calling uniq over and over, or writing array.include?(x) inside a loop, a set is probably the better tool.

Set has been part of the standard library for decades, and in Ruby 4.0 it is built into the core: you can write Set.new without any require. A set behaves like a hash that has only keys, so it has the same fast lookups and the same insertion-order behavior. This lesson covers creating sets, the operators, subset and superset tests, working with your own objects, and the cases where an array or a hash is still the better choice.

Creating a set

Ruby Making sets

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 gets), it gets the next line from this box.

Duplicates vanish as the set is built. Since Ruby 4.0 the inspect output looks like Set["red", "green", "blue"], the same text you would type to build it (older versions printed #<Set: {...}>). There is no set literal like [1, 2] or {a: 1}; use Set[1, 2, 3] as a short form of Set.new([1, 2, 3]), or call to_set on any enumerable.

Adding, removing and asking

Ruby add, delete and add?

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 gets), it gets the next line from this box.

add? is the key to the "seen before" idiom shown at the end: it returns nil when the item was already a member, so one call both tests and inserts. Compare that with the array version list.include?(x) followed by list << x, which scans the whole array each time.

Union, intersection, difference

Ruby Set algebra

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 gets), it gets the next line from this box.

  • a | b has everything that is in either set.
  • a & b has what is in both.
  • a - b has what is in a but not in b.
  • a ^ b has what is in exactly one of them.

The operators return new sets. merge and subtract change the set you call them on. disjoint? and intersect? answer yes/no questions without building a result.

Subsets and supersets

Ruby Comparing sets

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 gets), it gets the next line from this box.

The operators <, <=, > and >= mean "proper subset", "subset", "proper superset" and "superset". The spaceship operator <=> returns nil when neither set contains the other, which is the one case where sets cannot be ordered. A permission check such as "does this role cover everything the task requires?" is just required <= granted.

Iteration and order

A set is enumerable, so each, map, select, sort, sum, min and the rest work. Like a hash, a set remembers insertion order:

Ruby Iterating a set

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 gets), it gets the next line from this box.

Notice what each method returns. map, select, sort, group_by and partition come from Enumerable and return arrays (chain .to_set if you want a set again). Only the in-place methods such as delete_if, select! and reject! keep the receiver a set. There is no way to ask for "item number 2" with set[2], because position is not part of the idea. If you need indexes, you want an array.

Why a Set is fast

An array has to look at items one after another to answer include?. A set computes a hash of the value and jumps to the right spot. The answer takes about the same time for 10 or for 10 million members:

Ruby Array lookup versus set lookup

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 gets), it gets the next line from this box.

We print only the comparison, not the timings, because they differ from machine to machine. The set version is faster by a large factor here, and the gap widens as the data grows. Two pieces of advice follow. Build the set once and reuse it; converting an array to a set on every check wastes the gain. And for a handful of items the difference does not matter, so choose the clearer code.

Sets of your own objects

A set uses eql? and hash to decide whether two values are the same. For strings, symbols, numbers and arrays of those, that means "equal contents". For your own classes the default is identity, so two objects with the same data are different members until you say otherwise:

Ruby Custom objects need eql? and hash

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 gets), it gets the next line from this box.

The rule is the same as for hash keys: whenever a.eql?(b), then a.hash == b.hash must hold. Data objects and structs follow it automatically. See Equality and Identity for the full story. Never mutate an object in a way that changes its hash after it went into a set, or the set will no longer find it.

Freezing and errors

Ruby A frozen set rejects changes (fails on purpose)

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 gets), it gets the next line from this box.

The first line prints true, and then the script stops with main.rb:3:in 'Set#add': can't modify frozen Set: Set[:admin, :user] (FrozenError). Freezing a set is a good way to share a constant list of allowed values: ALLOWED = Set[:a, :b].freeze. Note that freeze is shallow, so members that are strings can still be changed unless they are frozen too.

Classic uses

Ruby Finding common and missing items

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 gets), it gets the next line from this box.

The graph example is the standard use of add?: it protects a traversal from running forever on a cycle (d points back to a).

Sets versus arrays versus hashes

Need Use
Ordered items, duplicates allowed, access by position Array
Fast "is it in there?", no duplicates, no values Set
A value attached to each key Hash
Unique items but result order matters to the reader uniq on an Array (or sort the set)

There is no SortedSet in modern Ruby. It was removed from the library in Ruby 3.0 because it depended on a gem that was not kept up. If you need members in sorted order, call set.sort when you read them (it returns an array), or keep an array sorted yourself.

In older code you will see require "set" at the top of the file. It still works in Ruby 4.0 and does no harm. A Gemfile entry is not needed because Set ships inside the language.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is Set[1, 2, 2, 3].size?

    A set stores each distinct value once, so the duplicate 2 collapses and the size is 3.
  2. 2. Which expression gives the members that are in set a but not in set b?

    • is difference. & is intersection, | is union, and ^ keeps items that appear in exactly one of the two sets.
  3. 3. What does seen.add?(x) return when x is already in the set?

    add? returns the set if the value was newly added and nil if it was already a member, which makes next unless seen.add?(x) a handy duplicate filter.
  4. 4. Two instances of your class have the same data, but Set[a, b].size is 2. What is missing?

    Sets decide sameness with eql? and hash. Without overriding them, objects are only equal to themselves.
  5. 5. Why is allowed.include?(x) usually faster on a Set than on an Array with many items?

    Array#include? checks items one by one, while a set jumps straight to the right slot using the hash, so lookup time does not grow with size.

Summary

  • Set holds unique values and is built into Ruby 4.0 core (Set.new, Set[...], to_set).
  • add, <<, delete, include? are the basics; add? returns nil for duplicates.
  • |, &, -, ^ give union, intersection, difference and symmetric difference as new sets.
  • subset?/<=, superset?/>=, disjoint? and intersect? compare sets.
  • Membership tests are fast because sets use hashing; objects must implement eql? and hash to behave as values.
  • Sets keep insertion order but have no indexes; there is no SortedSet, so sort when you read.

Next: Struct and Data