Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::map — uporządkowana mapa unikalnych kluczy

std::map przechowuje pary klucz–wartość w kolejności określonej przez komparator, z najwyżej jednym elementem dla każdego równoważnego klucza. Poznaj wyszukiwanie bez modyfikacji, wstawianie, usuwanie oraz przenoszenie węzłów.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

#include <map>
std::map<Key, T> m;
std::map<Key, T, Compare> ordered;

std::map<Key, T, Compare> z nagłówka <map> przechowuje elementy std::pair<const Key, T> w kolejności komparatora; domyślnie używa std::less<Key>. Compare musi definiować ścisły słaby porządek. Klucze są równoważne, gdy !comp(a, b) && !comp(b, a), niekoniecznie gdy a == b. Mapa dopuszcza tylko jeden taki klucz; iterator pozwala zmieniać wartość, ale nie klucz.

Aby wybrać przeciążenie std::map::insert wstawiające jeden element, przekaż jawnie utworzony element typu value_type mapy: m.insert(value_type{key, value}). To przeciążenie zwraca parę iterator–bool: jeśli równoważny klucz już istnieje, składowa bool ma wartość false, a zapisana wartość nie jest nadpisywana. Jeśli zarówno key, jak i value można niejawnie przekształcić na value_type, zapis m.insert({key, value}) może zamiast tego wybrać przeciążenie przyjmujące std::initializer_list<value_type>, które zwraca void i próbuje wstawić dwa elementy. W przykładzie z std::map<int, int> wywołanie z klamrami wybiera przeciążenie wstawiające jeden element. std::map::find zwraca iterator albo std::map::end; end() wskazuje za ostatni element i nie wolno go dereferencjonować. std::map::contains zwraca bool, a std::map::count zwraca 0 lub 1. std::map::equal_range zwraca półotwarty zakres [first, last) zawierający zero lub jeden element. Te operacje wyszukiwania nie wstawiają elementów i mają złożoność O(log n).

std::map::operator[] zwraca referencję do wartości; jeśli klucza brakuje, wstawia nowy element z tym kluczem. Przy domyślnym alokatorze wartość podlega inicjalizacji wartościowej (np. int otrzymuje 0), co wymaga, aby T można było skonstruować domyślnie. Własny alokator może zmienić sposób konstruowania elementu. Nie używaj [] tylko do sprawdzania obecności. std::map::erase(key) zwraca liczbę usuniętych elementów, a erase(it) zwraca następny iterator i wymaga iteratora dereferencjonowalnego. std::map::size zwraca liczbę elementów w O(1). Zwykłe wstawianie i usuwanie po kluczu kosztują O(log n); usuwanie przez iterator jest amortyzacyjnie O(1). Wstawianie nie unieważnia iteratorów ani referencji; usuwanie unieważnia tylko te do usuniętych elementów.

std::map::extract odłącza węzeł bez kopiowania ani przenoszenia jego elementu; brak klucza daje pusty uchwyt. Sprawdź empty() przed key(); odłączony klucz można zmienić i ponownie wstawić węzeł. std::map::merge przenosi pasujące typowo węzły bez kopiowania ani przenoszenia elementów; kolidujące klucze pozostają w źródle. Transfer węzłów wymaga równych alokatorów. Przykład używa operacji dostępnych w C++23; podlinkowany dokument jest rozwijanym szkicem, nie zamrożoną normą C++23. Flaga kompilatora repozytorium nie potwierdza środowiska produkcyjnego.

Przykłady

#include <iostream>
#include <map>
#include <utility>

int main() {
    std::map<int, int> m{{2, 20}};
    auto result = m.insert({2, 99});
    std::cout << std::boolalpha << "inserted=" << result.second << '\n';
    m[1] += 10;
    if (auto it = m.find(2); it != m.end()) {
        std::cout << "found=" << it->second << '\n';
    }
    auto [first, last] = m.equal_range(2);
    std::cout << "contains=" << m.contains(2)
              << " count=" << m.count(2)
              << " range=" << (first != last) << '\n';

    auto node = m.extract(1);
    if (!node.empty()) {
        node.key() = 3;
        m.insert(std::move(node));
    }
    std::map<int, int> source{{2, 200}, {4, 40}};
    m.merge(source);
    std::cout << "erased=" << m.erase(2)
              << " size=" << m.size()
              << " source=" << source.size() << '\n';
    for (const auto& [key, value] : m) {
        std::cout << key << ':' << value << '\n';
    }
}

Wynik

inserted=false
found=20
contains=true count=1 range=true
erased=1 size=2 source=1
3:10
4:40

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła