Memilih Struktur Data

Memilih struktur data yang tepat adalah keputusan paling berpengaruh terhadap performa solusi. Banyak pemula mengganti std::vector dengan std::list tanpa alasan, lalu heran saat kode justru melambat. Sebaliknya, memakai std::map untuk pencarian sementara std::unordered_map lebih cepat adalah jebakan klasik. Pada Chapter ini kita akan membangun tabel keputusan berdasarkan operasi yang dominan di soal, lalu membahas kasus umum dengan kode pembanding.

Kerangka: Operasi Apa yang Dominan? #

Aturan #

Sebelum memilih struktur data, tanyakan: operasi mana yang paling sering dilakukan? Berikut daftar operasi dan struktur data yang cocok:

Operasi Dominan	Struktur Data Terbaik	Catatan
Akses acak indeks	`std::vector` / `std::array`	O(1)
Insert/delete di ujung	`std::vector`	O(1) amortized
Insert/delete di depan	`std::deque`	O(1)
Insert/delete di tengah	`std::list` (jarang) / skip list	O(1) bila iterator; O(n) cari
Pencarian key exact	`std::unordered_map` / `std::unordered_set`	O(1) rata-rata
Pencarian dengan urut	`std::map` / `std::set` (BST)	O(log n), traversal terurut
Range query statis	Prefix sum / sparse table	O(1) setelah precompute
Range query dinamis	Segment tree / Fenwick tree	O(log n) update + query
Max/min dinamis	Priority queue / heap	O(log n) push/pop, O(1) top
Insert + max/min	Heap	O(log n) insert, O(1) max/min
Substring search	Suffix array / KMP / Z	O(n) preprocessing

Mekanisme: Hitung Operasi #

Untuk n = 10⁵ operasi:

std::vector::push_back O(1) amortized → total 10⁵ × 1 = 10⁵ ops. Aman.
std::vector::insert(begin, ...) O(n) → total 10⁵ × 10⁵ = 10¹⁰ ops. TLE.
std::set::insert O(log n) → total 10⁵ × 17 = 1,7 × 10⁶ ops. Aman.
std::unordered_set::insert O(1) rata-rata → total 10⁵ ops. Aman dan lebih cepat dari std::set.

Pembanding: Vector vs List #

Aturan #

Banyak literatur lama menyatakan linked list lebih cepat untuk insert/delete di tengah. Realitas pada hardware modern: cache locality membuat std::vector jauh lebih cepat dalam hampir semua kasus kecuali benar-benar banyak insert/delete di tengah dengan iterator sudah ada.

Kode: Benchmark Vector vs List #

cpp
#include <iostream>
#include <vector>
#include <list>
#include <chrono>
#include <random>

int main() {
    const int N = 100000;
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(1, 1'000'000);

    // Skenario: insert 100k elemen ke depan
    auto t1 = std::chrono::high_resolution_clock::now();
    std::vector<int> v;
    for (int i = 0; i < N; ++i) {
        v.push_back(dist(rng));
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << "vector push_back: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms\n";

    // Iterasi semua elemen
    long long sum_v = 0;
    t1 = std::chrono::high_resolution_clock::now();
    for (int x : v) sum_v += x;
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "vector iteration: "
              << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()
              << " us, sum=" << sum_v << '\n';

    // List
    t1 = std::chrono::high_resolution_clock::now();
    std::list<int> l;
    for (int i = 0; i < N; ++i) {
        l.push_back(dist(rng));
    }
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "list push_back: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms\n";

    long long sum_l = 0;
    t1 = std::chrono::high_resolution_clock::now();
    for (int x : l) sum_l += x;
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "list iteration: "
              << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count()
              << " us, sum=" << sum_l << '\n';
    return 0;
}

Output yang Dihasilkan (sample, bervariasi per mesin):

text
vector push_back: 0 ms
vector iteration: 32 us, sum=49970910913
list push_back: 2 ms
list iteration: 277 us, sum=50073456928

Baris v.push_back(dist(rng));: vector menyimpan elemen berurutan dalam memori. push_back amortized O(1).
Baris for (int x : v) sum_v += x;: iterasi sequential — sangat cepat karena cache locality (CPU prefetching blok memori berurutan).
Baris l.push_back(dist(rng));: linked list mengalokasikan node terpisah di heap. Setiap push_back adalah alokasi new — mahal.
Baris for (int x : l) sum_l += x;: iterasi linked list mengikuti pointer next — cache miss setiap kali, jauh lebih lambat.
Hasil pengamatan: vector ~3× lebih cepat untuk push_back dan ~8× lebih cepat untuk iterasi. Pola ini konsisten pada hardware modern.

Pembanding: unordered_map vs map #

Aturan #

std::map (BST merah-hitam) menjamin O(log n) untuk semua operasi. std::unordered_map (hash table) menjanjikan O(1) rata-rata tetapi O(n) terburuk. Untuk soal kompetisi dengan data random, unordered_map biasanya lebih cepat.

Kode: Benchmark unordered_map vs map #

cpp
#include <iostream>
#include <unordered_map>
#include <map>
#include <chrono>
#include <random>

int main() {
    const int N = 1000000;
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(1, N * 10);

    // unordered_map insert
    auto t1 = std::chrono::high_resolution_clock::now();
    std::unordered_map<int,int> um;
    for (int i = 0; i < N; ++i) {
        um[dist(rng)] = i;
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    std::cout << "unordered_map insert " << N << ": "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms, size=" << um.size() << '\n';

    // map insert
    t1 = std::chrono::high_resolution_clock::now();
    std::map<int,int> m;
    for (int i = 0; i < N; ++i) {
        m[dist(rng)] = i;
    }
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "map insert " << N << ": "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms, size=" << m.size() << '\n';

    // Lookup benchmark
    int found_um = 0;
    t1 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        if (um.count(dist(rng))) found_um++;
    }
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "unordered_map lookup: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms, found=" << found_um << '\n';

    int found_m = 0;
    t1 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        if (m.count(dist(rng))) found_m++;
    }
    t2 = std::chrono::high_resolution_clock::now();
    std::cout << "map lookup: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
              << " ms, found=" << found_m << '\n';
    return 0;
}

Output yang Dihasilkan (sample, bervariasi per mesin):

text
unordered_map insert 1000000: 191 ms, size=951688
map insert 1000000: 587 ms, size=951308
unordered_map lookup: 72 ms, found=95114
map lookup: 642 ms, found=95236

Baris std::unordered_map<int,int> um;: hash table. Lookup rata-rata O(1) asumsi hash bagus.
Baris std::map<int,int> m;: BST merah-hitam. Lookup selalu O(log n).
Hasil unordered_map insert 191 ms vs map insert 587 ms: unordered_map ~3× lebih cepat. Konstanta BST (pointer chasing) mahal.
Hasil unordered_map lookup 72 ms vs map lookup 642 ms: unordered_map ~9× lebih cepat untuk lookup.
Catatan: size=951688 vs 951308 berbeda karena RNG state dipakai bersama (dist(rng) menghasilkan nilai berbeda untuk run kedua).

Tabel Keputusan Lengkap #

Berdasarkan Operasi #

Operasi Utama	Struktur Data	Kompleksitas
Akses indeks O(1)	`vector`, `array`	O(1)
Push/pop back O(1)	`vector`	O(1) amortized
Push/pop depan O(1)	`deque`	O(1)
Insert/delete di posisi iterator	`list` (jarang)	O(1)
Search exact key	`unordered_set/map`	O(1) rata-rata
Search terurut (lower_bound)	`set/map`	O(log n)
Range sum statis	Prefix sum	O(1) query
Range sum dinamis	BIT	O(log n)
Range max/min statis	Sparse table	O(1) query
Range max/min dinamis	Segment tree	O(log n)
Max/min dinamis	Heap (priority_queue)	O(log n) insert, O(1) top
K-th terkecil dinamis	Order statistic tree	O(log n)
Path finding	BFS/DFS + adjacency list	O(V + E)
Shortest path	Dijkstra (heap)	O((V+E) log V)
MST	Kruskal (sort + DSU)	O(E log E)
SCC	Tarjan / Kosaraju	O(V + E)

Berdasarkan Tipe Soal #

Tipe Soal	Struktur Data Kanonik
Counting sort (small range)	Array of counters
Two sum (sorted)	Two pointers
Longest increasing subseq	`vector` + `lower_bound` (patience sorting)
Count inversions	BIT + coordinate compression
Maximum sliding window	Monotonic deque
Frequency table	`unordered_map`
Sorted frequency	`map` atau `multiset`
Disjoint sets	DSU
Path / SCC	Adjacency list + BFS/DFS

Ringkasan #

Pertanyaan pertama: operasi apa yang paling sering? Pilih struktur data yang menjamin kompleksitas terbaik untuk operasi tersebut.
std::vector adalah default terbaik — cache locality membuatnya cepat untuk hampir semua use case kecuali insert/delete di tengah.
std::unordered_map umumnya lebih cepat dari std::map untuk lookup, tetapi rawan collision hash di test case adversarial. Gunakan custom hash bila perlu.
Range query: statis (prefix sum, sparse table) untuk array tidak berubah, dinamis (BIT, segment tree) untuk array yang diupdate.
Selalu benchmark bila ragu — asumsi O(·) tidak selalu mencerminkan kecepatan nyata.