std::map w C++: klucze, wartości, wyszukiwanie i wstawianie

Wyszukiwanie po kluczu

vector świetnie się sprawdza, gdy indeksujesz po pozycji: element 0, element 1 i tak dalej. Często jednak nie masz pozycji; masz nazwę i chcesz rzecz, która jest do niej przypisana: nazwę użytkownika i jego wynik, słowo i liczbę jego wystąpień, kod kraju i jego stolicę. Przeszukiwanie wektora w poszukiwaniu dopasowania to O(n) i szybko robi się wolne.

std::map rozwiązuje ten problem. Przechowuje pary klucz-wartość, trzyma je posortowane według klucza i pozwala znaleźć wartość po kluczu w czasie O(log n). Aby go użyć, dołącz <map>:

#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> czytaj jako „mapa z kluczy string na wartości int”. Klucze są unikalne: przypisz dwa razy do tego samego klucza, a wygra druga wartość. Wewnętrznie map to zrównoważone drzewo poszukiwań binarnych, dlatego wszystko pozostaje posortowane, a wyszukiwanie jest logarytmiczne, a nie stałe.

Wstawianie elementów

Wpisy można dodawać na kilka sposobów, a różnice między nimi mają znaczenie. Najczęstszy to operator[], który tworzy klucz, jeśli nie istnieje, i zwraca referencję, do której możesz przypisać:

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

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

    inventory["apples"] = 12;     // utwórz + przypisz
    inventory["apples"] += 3;     // odczyt, zmiana, zapis: teraz 15

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

Jeśli chcesz wstawiania, które odmawia nadpisania istniejącego klucza, użyj insert albo emplace. Oba zwracają pair, którego .second to bool mówiący, czy wstawienie faktycznie nastąpiło:

#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 już istnieje
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, bez zmian
}

Używaj [], gdy chcesz, żeby „wygrywał ostatni zapis”, a insert/emplace, gdy istniejący klucz ma pozostać nietknięty.

Pułapka operator[]: wstawia przy odczycie

To najczęstszy błąd z map. operator[] nie jest czystym odczytem: jeśli klucza brakuje, po cichu wstawia go z wartością domyślną (0 dla int, "" dla string itd.) i zwraca do niej referencję. Samo sprawdzenie klucza przez [] zmienia więc mapę:

map<string, int> m;
if (m["maybe"] == 0) {   // BŁĄD: to właśnie utworzyło "maybe" -> 0
    // ...
}
cout << m.size();        // 1, a nie 0: klucz wstawiony przez przypadek

To uderza też przy const map, gdzie operator[] w ogóle się nie skompiluje, bo mógłby potrzebować wstawienia. Aby czytać bez wstawiania, użyj find, count/contains albo at (które rzuca wyjątek, zamiast wstawiać, gdy klucza nie ma):

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

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

    // find: zwraca iterator, == end(), jeśli klucza nie ma
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) albo count (każda wersja)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: rzuca std::out_of_range, gdy klucza brakuje, nigdy nie wstawia
    cout << "a = " << m.at("a") << "\n";
}

Praktyczna zasada: jeśli chcesz czytać, nigdy nie sięgaj po []. Używaj at, gdy klucz musi istnieć, a find/contains, gdy może go nie być.

Iteracja w kolejności posortowanej

Ponieważ map opiera się na drzewie, iteracja po nim odwiedza klucze w rosnącej kolejności posortowanej, zawsze i za darmo. Każdy element to pair<const Key, Value>, więc użyj structured binding, żeby czysto rozpakować klucz i wartość:

#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]++;   // brakujące klucze startują od 0, potem ++
    }

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

Zauważ, że klucz w wiązaniu jest const: przez auto& możesz w pętli zmienić wartość, ale nigdy nie zmienisz klucza w miejscu (to zepsułoby kolejność sortowania). Wynik wychodzi alfabetycznie (blue, sea, sky) bez żadnego sortowania, i właśnie dlatego wybiera się map zamiast tablicy mieszającej, gdy liczy się uporządkowane przechodzenie.

Idiom wordCount[w]++ to też kanoniczne zastosowanie wstawiania przy dostępie: tutaj chcesz, żeby brakujący klucz startował od 0, więc [] jest właściwym narzędziem.

Usuwanie elementów i rozmiar

Usuwaj po kluczu przez erase, które zwraca, ile elementów usunięto (0 albo 1 dla map). Możesz też usuwać przez iterator z find. Stan kontenera sprawdzisz przez size() i 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 (nie było go)

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

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

Jedna pułapka przy usuwaniu w pętli: m.erase(it) unieważnia iterator it, więc potem nie możesz zrobić ++it. Bezpieczny wzorzec od C++11 to it = m.erase(it), które zwraca iterator do następnego elementu. Do jednorazowego warunkowego usuwania w całej mapie czytelniejsze jest std::erase_if(m, predicate) (C++20).

Dalej: unordered_map

std::map daje posortowane klucze i przewidywalne operacje O(log n), ale za tę kolejność płacisz przy każdym wyszukiwaniu. Gdy kolejność kluczy cię nie obchodzi, a chcesz jak najszybszego wyszukiwania, unordered_map zamienia posortowane drzewo na tablicę mieszającą ze średnim dostępem O(1). Dalej zobaczysz, jak działa, kiedy jej średni czas stały wygrywa z logarytmem map i jakie pułapki haszowania (własne typy kluczy, kolizje w najgorszym przypadku) się z nią wiążą.