std::map C++: Key, Value, Pencarian, dan Penyisipan

Mencari Sesuatu Berdasarkan Key

vector sangat bagus saat kamu mengakses berdasarkan posisi: elemen 0, elemen 1, dan seterusnya. Namun sering kali kamu tidak punya posisi; kamu punya sebuah nama dan ingin mendapat hal yang terkait dengannya: username dan skornya, sebuah kata dan jumlahnya, kode negara dan ibu kotanya. Menelusuri vector untuk mencari yang cocok itu O(n) dan cepat jadi lambat.

std::map menyelesaikan masalah ini. Ia menyimpan pasangan key-value, menjaganya tetap terurut berdasarkan key, dan membuatmu bisa mencari value berdasarkan key-nya dalam waktu O(log n). Sertakan <map> untuk memakainya:

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> dibaca sebagai "map dari key string ke value int." Key bersifat unik: isi key yang sama dua kali dan value kedualah yang menang. Secara internal map adalah balanced binary search tree, itulah sebabnya semuanya tetap terurut dan pencariannya logaritmik, bukan konstan.

Menyisipkan Elemen

Ada beberapa cara memasukkan entri, dan perbedaannya penting. Yang paling umum adalah operator[], yang membuat key-nya kalau belum ada dan mengembalikan referensi yang bisa kamu isi:

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // create + assign
    inventory["apples"] += 3;     // read-modify-write, now 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Kalau kamu ingin penyisipan yang menolak menimpa key yang sudah ada, pakai insert atau emplace. Keduanya mengembalikan pair yang .second-nya berupa bool yang memberi tahu apakah penyisipan benar-benar terjadi:

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada already exists
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, unchanged
}

Pakai [] saat "penulisan terakhir yang menang" memang yang kamu inginkan, dan insert/emplace saat key yang sudah ada sebaiknya dibiarkan.

Jebakan operator[]: Ia Menyisipkan Saat Membaca

Inilah bug map yang paling umum. operator[] bukan sekadar membaca: kalau key-nya tidak ada, ia diam-diam menyisipkannya dengan value default (0 untuk int, "" untuk string, dan seterusnya) lalu mengembalikan referensi ke value itu. Jadi hanya mengecek sebuah key dengan [] sudah mengubah map-nya:

map<string, int> m;
if (m["maybe"] == 0) {   // BUG: this just created "maybe" -> 0
    // ...
}
cout << m.size();        // 1, not 0 - you inserted a key by accident

Ini juga menjebakmu pada const map, tempat operator[] bahkan tidak bisa dikompilasi karena mungkin perlu menyisipkan. Untuk membaca tanpa menyisipkan, pakai find, count/contains, atau at (yang melempar exception alih-alih menyisipkan saat key-nya tidak ada):

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: returns an iterator, == end() if absent
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) or count (any version)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: throws std::out_of_range if missing - never inserts
    cout << "a = " << m.at("a") << "\n";
}

Patokannya: kalau kamu ingin membaca, jangan pernah memakai []. Pakai at saat key-nya pasti ada, dan find/contains saat key-nya mungkin tidak ada.

Penelusuran dalam Urutan Terurut

Karena map didukung tree, menelusurinya mengunjungi key dalam urutan naik yang terurut, selalu, tanpa biaya tambahan. Setiap elemen adalah pair<const Key, Value>, jadi pakai structured binding untuk membongkar key dan value-nya dengan rapi:

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // missing keys start at 0, then ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Perhatikan bahwa key di binding itu bersifat const: kamu bisa mengubah value lewat loop dengan auto&, tetapi tidak pernah bisa mengubah key di tempat (itu akan merusak urutannya). Output-nya keluar secara alfabetis (blue, sea, sky) tanpa langkah sorting apa pun, dan persis karena itulah orang memilih map daripada hash table saat penelusuran terurut itu penting.

Idiom wordCount[w]++ itu juga merupakan pemakaian kanonis dari perilaku menyisipkan saat diakses: di sini kamu memang ingin key yang tidak ada dimulai dari 0, jadi [] adalah alat yang tepat.

Menghapus Elemen dan Ukuran

Hapus berdasarkan key dengan erase, yang mengembalikan jumlah elemen yang dihapus (0 atau 1 untuk map). Kamu juga bisa menghapus lewat iterator dari find. Cek keadaan container dengan size() dan empty():

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (wasn't there)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Satu jebakan saat menghapus di dalam loop: m.erase(it) membuat iterator it tidak valid, jadi kamu tidak bisa melakukan ++it sesudahnya. Pola yang aman sejak C++11 adalah it = m.erase(it), yang mengembalikan iterator ke elemen berikutnya. Untuk penghapusan bersyarat sekali jalan di seluruh map, std::erase_if(m, predicate) (C++20) lebih rapi.

Berikutnya: unordered_map

std::map memberimu key yang terurut dan operasi O(log n) yang bisa ditebak, tetapi kamu membayar urutan itu di setiap pencarian. Kalau kamu tidak peduli urutan key dan hanya ingin pencarian secepat mungkin, unordered_map menukar tree yang terurut dengan hash table: akses rata-rata O(1). Berikutnya kita akan melihat cara kerjanya, kapan rata-rata waktu konstannya mengalahkan logaritma milik map, dan jebakan hashing (tipe key buatan sendiri, collision terburuk) yang menyertainya.