A set is a data structure which contains a "collection" of elements stored in no specific order, which can only store each value once. Unlike other collection data structures, typically sets are only added to and then used to test for Element within the set. The set data structure can be thought of as an implementation of a finite set. Sets usually define the following operations:

• Add: which adds an element to the set if it is not already present.
• Remove: which removes an element from the set if it is present.
• Contains: which checks if an element is present in the set.

Additionally, some set implementations may provide operations for the following:

• Union: which combines two sets to form a new set containing all elements from both sets.
• Intersection: which creates a new set containing only the elements that are present in both sets.
• Size: which returns the number of elements in the set.

Abstract Data Type

template <class T>
class Set {
    public:
        Set();
    
        // Add an element to the set
        void add(const T& element);
        
        // Remove an element from the set
        void remove(const T& element);
        
        // Check if the set contains an element
        bool contains(const T& element) const;
}

Implementation

Hash Table

A common implementation of a set is using a hash table, where each element is stored in an array based on the hash value of the element. This allows for average-case time complexity for the Add, Remove, and Contains operations at the cost of relatively high memory usage. Additionally, in the worst case (e.g., many collisions), these operations can degrade to .