Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::map — usporiadaná mapa s jedinečnými kľúčmi

std::map ukladá dvojice kľúč–hodnota v poradí komparátora a pre každý ekvivalentný kľúč obsahuje najviac jeden prvok. Zoznámte sa s vyhľadávaním bez zmeny mapy, vkladaním, mazaním a prenosom uzlov a s tým, prečo operator[] nekontroluje prítomnosť kľúča.

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

Syntax

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

std::map<Key, T, Compare> z <map> ukladá prvky std::pair<const Key, T> v poradí komparátora; predvolene používa std::less<Key>. Compare musí definovať striktné slabé usporiadanie. Kľúče sú ekvivalentné, keď platí !comp(a, b) && !comp(b, a), nie nevyhnutne keď a == b. Mapa povoľuje iba jeden taký kľúč; pomocou iterátora možno meniť hodnotu, nie kľúč.

Ak chcete vybrať preťaženie std::map::insert na vloženie jedného prvku, explicitne vytvorte prvok typu value_type danej mapy: m.insert(value_type{key, value}). Toto preťaženie vracia dvojicu iterátor-bool: ak už existuje ekvivalentný kľúč, zložka bool má hodnotu false a uložená hodnota sa neprepíše. Ak sa key aj value dajú implicitne konvertovať na value_type, volanie m.insert({key, value}) môže namiesto toho vybrať preťaženie, ktoré prijíma std::initializer_list<value_type>, vracia void a pokúsi sa vložiť dva prvky. V príklade s std::map<int, int> volanie so zloženými zátvorkami vyberie preťaženie pre jeden prvok. std::map::find vracia iterátor alebo std::map::end; end() označuje pozíciu za posledným prvkom a nesmie sa dereferencovať. std::map::contains vracia bool, zatiaľ čo std::map::count vracia 0 alebo 1. std::map::equal_range vracia polootvorený rozsah [first, last) s nulou alebo jedným prvkom. Tieto vyhľadávania nič nevkladajú a majú zložitosť O(log n).

std::map::operator[] vracia referenciu na hodnotu; ak kľúč chýba, vloží nový prvok s týmto kľúčom. Pri použití predvoleného alokátora sa priradená hodnota inicializuje hodnotou (napríklad na 0 pri type int), čo vyžaduje, aby sa T dalo skonštruovať bez argumentov. Vlastný alokátor môže zmeniť spôsob konštrukcie prvku. Nepoužívajte [] iba na kontrolu prítomnosti. std::map::erase(key) vracia počet odstránených prvkov; erase(it) vracia nasledujúci iterátor a vyžaduje dereferencovateľný iterátor. std::map::size vracia počet prvkov v O(1). Bežné vloženie a mazanie podľa kľúča majú zložitosť O(log n); mazanie pomocou iterátora má amortizovanú zložitosť O(1). Vloženie nezneplatňuje iterátory ani referencie; mazanie zneplatňuje iba tie k odstráneným prvkom.

std::map::extract oddelí uzol bez kopírovania či presunu jeho prvku; chýbajúci kľúč vytvorí prázdny handle. Pred key() skontrolujte empty(); oddelený kľúč možno pred opätovným vložením uzla zmeniť. std::map::merge prenáša typovo kompatibilné uzly bez kopírovania či presunu prvkov; konfliktné kľúče zostávajú v zdroji. Prenos uzlov vyžaduje rovnaké alokátory. Príklad používa operácie dostupné v C++23; odkazovaný dokument je priebežne vyvíjaný návrh, nie konečná norma C++23. Príznak kompilátora v repozitári nepotvrdzuje produkčné prostredie.

Príklady

#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';
    }
}

Výsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje