A set is a container that stores a collection of unique values. The elements or members of a set are not stored in any particular order and can not be accessed by position. Like the Bag ADT introduced in Chapter 2, the set is a nonlinear data structure. The Set ADT is a common container used in computer science for a variety of problems. The operations available for use with a set, which are explored in the next section, are the same as the operations performed on sets in mathematics.
While Python provides a set container as part of the language itself, other languages may make it available as part of the standard library. Still others, like the C language, does not provide a set type, even as part of its standard library. A set is another excellent example of an abstract data type that can be implemented using different data structures and organizing the data in a variety of ways with some being more efficient than others.
The Set ADT
The definition of the set abstract data type is provided here, followed by an implementation using a list. In later chapters, we will provide and evaluate alternate implementations for the Set ADT.
The Set ADT
A set is a container that stores a collection of unique values over a given comparable domain in which the stored values have no particular ordering.
Set()
Creates a new set initialized to the empty set.
length()
Returns the number of elements in the set, also known as the cardinality.
isEmpty()
Returns a Boolean value that indicates whether the set is empty.
contains(element)
Determines if the given value is an element of the set and returns the appropriate Boolean value.
add(element)
Modifies the set by adding the given value or element to the set if the element is not already a member. If the element is not unique, no action is taken and the operation is skipped.
remove(element)
Removes the given element from the set, which must be in the set.
clear()
Removes all elements from the set resulting in an empty set.
equals(setB)
Determines if the set is equal to another set and returns a Boolean value. For two sets, and , to be equal, both and must contain the same number of elements and all elements in must also be elements in . If both sets are empty, the sets are equal.
isSubsetOf(setB)
Determines if the set is a subset of another set and returns a Boolean value. For set to be a subset of , all elements in must also be elements in $B$.
union(setB)
Creates and returns a new set that is the union of this set and setB. The new set created from the union of two sets, and , contains all elements in $A$ plus those elements in that are not in . Neither set nor set is modified by this operation.
intersection(setB)
Creates and returns a new set that is the intersection of this set and setB. The intersection of sets and contains only those elements that are in both and . Neither set nor set is modified by this operation.
difference(setB)
Creates and returns a new set that is the difference of this set and setB. The set difference, , contains only those elements that are in but not in . Neither set nor set is modified by this operation.
iterator()
Returns an iterator that can be used to iterate over the collection of elements.
|
