Beginning Algorithms

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.

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, ...