Balanced Trees for Free: std::set and std::map

Self-balancing trees

Real libraries use self-balancing BSTs (like red-black trees) that rotate nodes to keep the height O(log n) always. In C++ you get one for free: std::set and std::map.

#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;

int main() {
    set<int> s = {50, 30, 70, 20, 40};
    s.insert(60);
    s.erase(30);
    cout << "sorted:";
    for (int x : s) cout << ' ' << x;
    cout << endl;
    cout << "smallest " << *s.begin() << ", largest " << *s.rbegin() << endl;
    cout << "first >= 45: " << *s.lower_bound(45) << endl;

    map<string, int> marks;
    marks["Ravi"] = 78;
    marks["Asha"] = 91;
    marks["Meera"] = 85;
    for (auto& [name, m] : marks) cout << name << " " << m << endl;   // sorted by name
    return 0;
}

Output

sorted: 20 40 50 60 70
smallest 20, largest 70
first >= 45: 50
Asha 91
Meera 85
Ravi 78

Remember: Need things kept sorted, or “the next bigger value”? Use set/map. Only need fast lookups? unordered_ versions are faster.