Sets In C++

In C++, std::set and std::unordered_set are associative containers that store unique elements, meaning no duplicate values are allowed. They are particularly useful when you need to keep a collection of items where order doesn't matter, but uniqueness does. Let's dive into the details of these two containers.

1. std::set

Characteristics:

• Ordered: Elements are automatically sorted according to their values using a comparison function (by default, std::less<T>).

• Unique Elements: Does not allow duplicate elements.

• Balanced Binary Tree (typically Red-Black Tree): The underlying data structure is usually a Red-Black Tree, which allows for ordered traversal.

• Complexity:

  • Insertion, Deletion, Search: O(log n)

Creating a Set

std::set<int> s; // Creates an empty set of integers
std::set<int> s = {3, 1, 2}; // Creates and initializes a set with {1, 2, 3}

Basic Operations

• Insertion:

    std::set<int> s;
    s.insert(3); // s = {3}
    s.insert(1); // s = {1, 3}
    s.insert(2); // s = {1, 2, 3}
  

  The insertion operation returns a pair:

  • pair<iterator, bool>, where the iterator points to the inserted element (or to the equivalent element already in the set), and the bool is true if the insertion was successful, false otherwise.

• Accessing Elements: Direct access by index is not allowed, but you can use iterators:

    std::set<int> s = {1, 2, 3};
    for (auto it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " "; // Output: 1 2 3
    }
  

• Search:

    std::set<int> s = {1, 2, 3};
    auto it = s.find(2); // it points to the element 2
    if (it != s.end()) {
        std::cout << "Found: " << *it; // Output: Found: 2
    }
  

• Deletion:

    std::set<int> s = {1, 2, 3};
    s.erase(2); // s = {1, 3}
  

Other Useful Functions

• size(): Returns the number of elements in the set.

    std::set<int> s = {1, 2, 3};
    std::cout << s.size(); // Output: 3
  

• clear(): Removes all elements from the set.

    std::set<int> s = {1, 2, 3};
    s.clear(); // s is now empty
  

• count(): Returns 1 if the element is found, otherwise 0 (useful for checking existence).

    std::set<int> s = {1, 2, 3};
    if (s.count(2)) {
        std::cout << "2 is in the set"; // Output: 2 is in the set
    }
  

• lower_bound() and upper_bound():

  • lower_bound(x): Returns an iterator to the first element that is not less than x.

  • upper_bound(x): Returns an iterator to the first element that is greater than x.

    std::set<int> s = {1, 2, 3};
    auto it = s.lower_bound(2); // it points to 2
    auto it2 = s.upper_bound(2); // it2 points to 3

• swap(): Exchanges the contents of two sets.

    std::set<int> s1 = {1, 2};
    std::set<int> s2 = {3, 4};
    s1.swap(s2); // s1 = {3, 4}, s2 = {1, 2}
  

2. std::unordered_set

Characteristics:

• Unordered: Elements are not stored in any particular order.

• Unique Elements: Does not allow duplicate elements.

• Hash Table: The underlying data structure is a hash table, which allows for faster average time complexity for operations.

• Complexity:

  • Insertion, Deletion, Search: O(1) on average (O(n) in the worst case due to collisions)

Creating an Unordered Set

std::unordered_set<int> us; // Creates an empty unordered set of integers
std::unordered_set<int> us = {3, 1, 2}; // Creates and initializes an unordered set

Basic Operations

• Insertion:

    std::unordered_set<int> us;
    us.insert(3); // us = {3}
    us.insert(1); // us = {1, 3}
    us.insert(2); // us = {1, 2, 3}
  

• Accessing Elements: Direct access by index is not allowed, but you can use iterators (order is not guaranteed):

    std::unordered_set<int> us = {1, 2, 3};
    for (auto it = us.begin(); it != us.end(); ++it) {
        std::cout << *it << " "; // Output order is not guaranteed
    }
  

• Search:

    std::unordered_set<int> us = {1, 2, 3};
    auto it = us.find(2); // it points to the element 2
    if (it != us.end()) {
        std::cout << "Found: " << *it; // Output: Found: 2
    }
  

• Deletion:

    std::unordered_set<int> us = {1, 2, 3};
    us.erase(2); // us = {1, 3}
  

Other Useful Functions

• size(): Returns the number of elements in the unordered set.

    std::unordered_set<int> us = {1, 2, 3};
    std::cout << us.size(); // Output: 3
  

• clear(): Removes all elements from the unordered set.

    std::unordered_set<int> us = {1, 2, 3};
    us.clear(); // us is now empty
  

• count(): Returns 1 if the element is found, otherwise 0 (useful for checking existence).

    std::unordered_set<int> us = {1, 2, 3};
    if (us.count(2)) {
        std::cout << "2 is in the unordered set"; // Output: 2 is in the unordered set
    }
  

• swap(): Exchanges the contents of two unordered sets.

    std::unordered_set<int> us1 = {1, 2};
    std::unordered_set<int> us2 = {3, 4};
    us1.swap(us2); // us1 = {3, 4}, us2 = {1, 2}
  

Comparison: std::set vs std::unordered_set

• Ordering: std::set maintains the elements in a sorted order, while std::unordered_set does not.

• Performance: std::unordered_set is generally faster (O(1) average time complexity) for insertions, deletions, and lookups compared to std::set (O(log n)).

• Memory Usage: std::unordered_set generally uses more memory due to the underlying hash table.

Conclusion

Understanding the nuances of std::set and std::unordered_set can help you choose the right container for the problem at hand. Use std::set when you need ordered elements and efficient traversal in sorted order. Opt for std::unordered_set when you need faster average time complexity for insertions and lookups and don't require ordering. Both containers offer powerful capabilities for managing collections of unique elements in competitive programming and general software development.