Container Associative

Container associative STL (set, map, multiset, multimap) menyimpan elemen dalam urutan terurut berdasarkan key. Implementasi standar memakai Red-Black Tree — pohon biner seimbang dengan tinggi O(log n). Setiap operasi find, insert, dan erase berjalan dalam O(log n). Karena terurut, container ini mendukung operasi lower_bound dan upper_bound secara natif — sebuah keunggulan besar dibanding versi unordered. Pada Chapter ini kita akan membedah keempat container, memahami kapan memilih set vs map, dan kapan multiset/multimap dibutuhkan untuk duplikat key.

Empat Container Associative #

Keempatnya menjamin:

• find, insert, erase: O(log n).
• Iterasi terurut ascending menurut key (atau comparator custom).
• lower_bound(k) mengembalikan iterator ke elemen pertama >= k; upper_bound(k) ke elemen pertama > k.

Mekanisme: Red-Black Tree #

Red-Black Tree adalah pohon biner seimbang yang memenuhi lima invariant (root hitam, daun hitam, anak merah harus hitam, jalur dari root ke daun memiliki jumlah node hitam yang sama, dsb). Invariant ini menjamin tinggi pohon maksimum 2·log₂(n+1), sehingga setiap operasi turun dari root ke daun berjalan dalam O(log n).

Insert dan erase memicu rebalancing — rotasi dan recoloring sejumlah O(log n) node. Operasi tersebut tetap O(log n) namun memiliki konstanta yang lebih besar dibanding std::vector::push_back.

Kode: Empat Container Berdampingan #

#include <iostream>
#include <set>
#include <map>
#include <algorithm>

int main() {
    // 1) std::set — kumpulan unik terurut
    std::set<int> s = {5, 1, 3, 1, 4, 1, 2};
    std::cout << "set: ";
    for (int x : s) std::cout << x << ' ';
    std::cout << "(size=" << s.size() << ")\n";

    auto it = s.find(3);
    if (it != s.end()) std::cout << "find(3) = " << *it << '\n';
    s.insert(9);
    s.erase(1);
    std::cout << "set after insert(9), erase(1): ";
    for (int x : s) std::cout << x << ' ';
    std::cout << '\n';

    // lower_bound/upper_bound — manfaat utama ordered set
    auto lo = s.lower_bound(3);  // first >= 3
    auto hi = s.upper_bound(3);  // first > 3
    std::cout << "lower_bound(3) = " << *lo << '\n';
    std::cout << "upper_bound(3) = " << *hi << '\n';

    // 2) std::multiset — boleh duplikat
    std::multiset<int> ms = {3, 1, 4, 1, 5, 1, 3};
    std::cout << "multiset: ";
    for (int x : ms) std::cout << x << ' ';
    std::cout << "(count(1)=" << ms.count(1) << ")\n";

    // 3) std::map — key-value, key unik terurut
    std::map<std::string, int> m;
    m["alice"] = 90;
    m["bob"] = 75;
    m["carol"] = 88;
    m.insert({"alice", 999});  // tidak overwrite — key sudah ada
    std::cout << "map:\n";
    for (const auto& [k, v] : m) {
        std::cout << "  " << k << " -> " << v << '\n';
    }

    // 4) std::multimap — satu key boleh banyak value
    std::multimap<std::string, int> mm;
    mm.insert({"x", 1});
    mm.insert({"x", 2});
    mm.insert({"x", 3});
    mm.insert({"y", 10});
    std::cout << "multimap x range:\n";
    auto [b, e] = mm.equal_range("x");
    for (auto it2 = b; it2 != e; ++it2) {
        std::cout << "  " << it2->first << " -> " << it2->second << '\n';
    }

    return 0;
}

Output yang Dihasilkan:

set: 1 2 3 4 5 (size=5)
find(3) = 3
set after insert(9), erase(1): 2 3 4 5 9 
lower_bound(3) = 3
upper_bound(3) = 4
multiset: 1 1 1 3 3 4 5 (count(1)=3)
map:
  alice -> 90
  bob -> 75
  carol -> 88
multimap x range:
  x -> 1
  x -> 2
  x -> 3

Bedah Kode Baris-per-Baris #

1. std::set<int> s = {5, 1, 3, 1, 4, 1, 2};: initializer list dengan tujuh nilai, tetapi tiga 1 dianggap duplikat. Setelah insert, s berisi {1, 2, 3, 4, 5} (lima elemen unik terurut).
2. s.find(3): pencarian biner di pohon — O(log n). Mengembalikan iterator ke elemen bernilai 3, atau s.end() bila tidak ada.
3. s.insert(9); s.erase(1);: insert 9 dan hapus elemen bernilai 1. Keduanya O(log n). Setelah operasi: {2, 3, 4, 5, 9}.
4. s.lower_bound(3): iterator ke elemen pertama >= 3 — yaitu elemen 3 itu sendiri. Berguna untuk query “elemen terkecil yang tidak kurang dari x”.
5. s.upper_bound(3): iterator ke elemen pertama > 3 — yaitu 4. Kombinasi lower_bound dan upper_bound membentuk range elemen yang sama dengan key tertentu — penting untuk multiset.
6. std::multiset<int> ms = {3,1,4,1,5,1,3}: setiap nilai 1 dan 3 disimpan sebagai node terpisah. Iterasi menghasilkan {1,1,1,3,3,4,5} — terurut dengan duplikat.
7. ms.count(1): menghitung elemen bernilai 1. Kompleksitas O(log n + count) — setelah menemukan posisi 1, ia iterasi maju sampai value berubah.
8. m["alice"] = 90;: akses via operator[] — bila key belum ada, default-construct value (untuk int berarti 0) lalu assign. Bila key sudah ada, hanya assign. Karena itu operator[] pada map mutates container (mungkin insert) — gunakan m.at("alice") bila ingin throw saat key tidak ada.
9. m.insert({"alice", 999}): insert tidak menimpa bila key sudah ada. Map tetap menyimpan alice -> 90. Untuk overwrite paksa, gunakan m.insert_or_assign("alice", 999) (C++17) atau assignment langsung.
10. for (const auto& [k, v] : m): structured binding C++17 mengurai std::pair<const K, V> menjadi dua variabel. Map mengiterasi pasangan dalam urutan key ascending.
11. mm.equal_range("x"): mengembalikan pair iterator [first, second) yang membentang semua elemen dengan key "x". Untuk multimap, ini cara idiomatik iterasi semua value untuk satu key.

Operasi Penting: lower_bound dan upper_bound #

Karena container associative terurut, kedua operasi ini berjalan O(log n) — perbedaan utama dibanding versi unordered. Pola umum:

• “Elemen terkecil >= x” → s.lower_bound(x).
• “Elemen terkecil > x” → s.upper_bound(x).
• “Banyak elemen dalam [lo, hi)” → distance(s.lower_bound(lo), s.upper_bound(hi)).

Untuk DSA, kedua operasi ini krusial saat kita memakai std::set sebagai ordered symbol table — misalnya mencari penerus/predecessor di algoritma sweepline.

Kapan Memilih Container Associative #

Ringkasan #

• Empat container associative: set, map (key unik); multiset, multimap (key boleh duplikat).
• Implementasi standar memakai Red-Black Tree, kompleksitas O(log n) untuk find/insert/erase.
• Iterasi terurut ascending menurut key; lower_bound/upper_bound adalah keunggulan utama dibanding versi unordered.
• map::operator[] bersifat non-const (bisa insert); gunakan find/at pada const reference.
• multimap tidak mendukung operator[] — gunakan equal_range untuk mengakses range value.