C++ std::set & std::multiset: Self-Balancing Red-Black Search Trees

std::set is an associative container that stores unique elements in strictly sorted order. std::multiset allows duplicate elements while preserving sorting.

std::set with Range Queries (`lower_bound` & `upper_bound`)

#include <iostream>
#include <set>

int main() {
    std::set<int> scores = {45, 88, 12, 95, 60};

    // Automatic ascending sorted order: 12, 45, 60, 88, 95
    for (int s : scores) {
        std::cout << s << " ";
    }
    std::cout << "\n";

    // Fast logarithmic range search: Find first score >= 60
    auto it = scores.lower_bound(60);
    if (it != scores.end()) {
        std::cout << "First qualifying score >= 60: " << *it << "\n"; // 60
    }

    return 0;
}

Frequently Asked Questions (FAQ) - Student & Interview Review

Q1. What is the time complexity of insert, search, and delete in std::set?

Because std::set is implemented as a Red-Black Tree (Self-Balancing BST), all three operations execute in guaranteed O(log N) logarithmic time.

Q2. Can you modify an element in-place while it is stored in a std::set?

No! Elements in a std::set are const. Modifying an element directly would corrupt the Red-Black tree's sorted ordering invariant. You must erase the old element and insert the updated one.