Core Concepts of the Set Container

The std::set container in C++ is an associative container designed to store unique elements. Its defining characteristics include automatic sorting upon insertion and strict uniqueness of values. Unlike sequence containers, data access and insertion in a set are handled via specific member functions rather than direct indexing or push_back. Internally, sets are typically implemented using a balanced binary search tree, such as a Red-Black Tree, which ensures logarithmic time complexity for insertion, deletion, and lookup operations.

Initialization and Data Insertion

To define a set, you must include the <set> header. Initialization can be done using the default constructor, an initializer list, or via copy construction.

#include <set>
#include <iostream>

// Default constructor
std::set<int> primarySet;

// Initialization with values
std::set<int> secondarySet = {5, 1, 9, 3};

// Copy construction
std::set<int> tertiarySet(secondarySet);

Since sets are ordered, the values in secondarySet will automatically be arranged as 1, 3, 5, 9.

Insertion is performed using the insert() method. Because sets prohibit duplicate values, attempting to insert an existing value will result in no modification.

void insert_demo() {
    std::set<int> numbers = {10, 20};
    // Insert a new unique element
    numbers.insert(15);
    // Attempt to insert a duplicate (fails silently)
    auto result = numbers.insert(10);
    
    if (result.second == false) {
        std::cout << "Insertion failed: element already exists." << std::endl;
    }
}

Modifying Elements: Erasure and Clearing

The set container provides several methods to remove elements.

• clear(): Removes all elements from the container.
• erase(pos): Removes the element at the specific iterator position.
• erase(beg, end): Removes elemants within the renge [beg, end).
• erase(value): Removes all elements matching the specific value (in a set, this is at most one).

void erase_demo() {
    std::set<int> dataset = {10, 20, 30, 40, 50};
    
    // Erase by value
    dataset.erase(30);
    
    // Erase by iterator (first element)
    if (!dataset.empty()) {
        dataset.erase(dataset.begin());
    }
    
    // Erase a range (remove everything except the last one)
    dataset.erase(dataset.begin(), --dataset.end());
    
    dataset.clear();
}

Capacity and Swapping

Basic operations for managing container state include checking size, emptiness, and swapping contents with another set.

void capacity_demo() {
    std::set<char> setA = {'a', 'b', 'c'};
    std::set<char> setB = {'x', 'y', 'z', 'w'};
    
    if (!setA.empty()) {
        std::cout << "SetA size: " << setA.size() << std::endl;
    }
    
    setA.swap(setB);
    
    std::cout << "After swap, SetA size: " << setA.size() << std::endl;
}

Searching and Counting

To locate elements, use the find() and count() methods.

• find(key): Returns an iterator to the element if found; otherwise, returns end().
• count(key): Returns the number of elements matching the key. For sets, this is always 0 or 1.

void search_demo() {
    std::set<int> identifiers = {100, 200, 300};
    
    auto it = identifiers.find(200);
    if (it != identifiers.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    int exists = identifiers.count(400); // Returns 0
}

Container Variants: Set vs. Multiset vs. Unordered_Set

Choosing the right container depends on the requirements for ordering and uniqueness.

While set and multiset maintain sort order, unordered_set provides faster average lookups (O(1)) by using a hash table, at the cost of ordering. multiset differs from set by allowing duplicate keys; consequently, its insert method always succeeds and returns an iterator, rather than a pair containing a boolean success flag.

// Multiset allows duplicates
std::multiset<int> multiSet;
multiSet.insert(10);
multiSet.insert(10); // Valid
std::cout << "Count of 10: " << multiSet.count(10) << std::endl;

Utilizing Pairs

The std::pair structure is useful for grouping two related values. It is often used to store heterogeneous data. The insert method of a standard set returns a pair where the first element is an iterator to the element, and the second is a boolean indicating success.

#include <utility>

void pair_demo() {
    // Construction methods
    std::pair<std::string, int> record1("Alice", 30);
    auto record2 = std::make_pair("Bob", 25);
    
    // Accessing members
    std::cout << record1.first << ": " << record1.second << std::endl;
    
    // Receiving insert result
    std::set<int> numSet;
    std::pair<std::set<int>::iterator, bool> outcome = numSet.insert(5);
    
    if (outcome.second) {
        std::cout << "Insertion successful." << std::endl;
    }
}

Custom Sorting Rules

Sets default to ascending order. To change this, you must provide a custom comparator (functor) at the time of instantiation. This comparator must be defined before the set is declared.

Sorting Built-in Types

To sort integers in descending order, define a struct that overloads the operator().

struct DescendingSort {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

void custom_sort_demo() {
    // Standard ascending sort
    std::set<int> ascendingSet = {10, 5, 20};
    
    // Descending sort using functor
    std::set<int, DescendingSort> descendingSet = {10, 5, 20};
    
    for (const auto& val : descendingSet) {
        std::cout << val << " "; // Outputs: 20 10 5
    }
}

Sorting Custom Data Types

When storing custom objects (e.g., a class), the compiler does not know how to sort them inherently. You must provide a comparator that specifies the sorting logic based on member variables.

class Employee {
public:
    std::string name;
    int id;
    
    Employee(std::string n, int i) : name(n), id(i) {}
};

// Comparator sorting by Employee ID
struct CompareEmployee {
    bool operator()(const Employee& emp1, const Employee& emp2) const {
        return emp1.id < emp2.id;
    }
};

void custom_object_demo() {
    std::set<Employee, CompareEmployee> workforce;
    
    workforce.insert(Employee("John Doe", 101));
    workforce.insert(Employee("Jane Smith", 105));
    workforce.insert(Employee("Bob Johnson", 103));
    
    for (const auto& emp : workforce) {
        std::cout << "ID: " << emp.id << ", Name: " << emp.name << std::endl;
    }
    // Output order will be 101, 103, 105
}