O'Reilly logo

Beginning Algorithms by James Ross, Simon Harris

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 12. Sets

Sets are collections that hold only distinct values; a set guarantees that an item will not be added more than once. They are particularly useful in scientific applications but often provide a more sensible structure than lists for holding data when duplicate values are not needed. More often than not when a list is used, a set is probably what is intended.

This chapter discusses the following topics:

  • The basic operations of a set

  • A set implementation designed for small amounts of data, the list set

  • Another implementation that efficiently manages large amounts of unordered data, the hash set

  • A third type of set that has predictable iteration order, the tree set

Understanding Sets

Think of a set as an unordered pool of data containing no duplicates. This differs from a list, which, like an array, maintains the order of insertion and allows duplicates. Figure 12-1 depicts the set of letters A through K. Notice that there is no explicit ordering of the values.

Sets typically support the operations shown in Table 12-1.

A set is a pool of distinct, unordered values.

Figure 12.1. A set is a pool of distinct, unordered values.

Table 12.1. Set Operations

Operation

Description

add

Adds a value to the set. If added, the size of the set is increased by one and returns true; otherwise, returns false if the value already existed.

delete

Deletes a value from the set. If deleted, the size of the set is decreased by one and returns true; otherwise, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required