Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::map — uspořádaná mapa s jedinečnými klíči

std::map ukládá dvojice klíč–hodnota v pořadí komparátoru a pro každý ekvivalentní klíč obsahuje nejvýše jeden prvek. Seznamte se s vyhledáváním bez změny mapy, vkládáním, mazáním a přenosem uzlů i s tím, proč operator[] nekontroluje přítomnost klíče.

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

Syntaxe

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

std::map<Key, T, Compare> z <map> ukládá prvky std::pair<const Key, T> v pořadí komparátoru; ve výchozím nastavení používá std::less<Key>. Compare musí definovat striktní slabé uspořádání. Klíče jsou ekvivalentní, když platí !comp(a, b) && !comp(b, a), ne nutně když a == b. Mapa dovoluje jen jeden takový klíč; pomocí iterátoru lze měnit hodnotu, nikoli klíč.

Chcete-li vybrat přetížení std::map::insert pro vložení jednoho prvku, explicitně vytvořte prvek typu value_type dané mapy: m.insert(value_type{key, value}). Toto přetížení vrací dvojici iterátor-bool: pokud už existuje ekvivalentní klíč, složka bool má hodnotu false a uložená hodnota se nepřepíše. Pokud lze key i value implicitně převést na value_type, může volání m.insert({key, value}) místo toho vybrat přetížení, které přijímá std::initializer_list<value_type>, vrací void a pokusí se vložit dva prvky. V příkladu s std::map<int, int> volání se složenými závorkami vybírá přetížení pro jeden prvek. std::map::find vrací iterátor nebo std::map::end; end() označuje pozici za posledním prvkem a nesmí se dereferencovat. std::map::contains vrací bool, zatímco std::map::count vrací 0 nebo 1. std::map::equal_range vrací polootevřený rozsah [first, last) s nulou nebo jedním prvkem. Tato vyhledávání nic nevkládají a mají složitost O(log n).

std::map::operator[] vrací referenci na hodnotu; pokud klíč chybí, vloží nový prvek s tímto klíčem. Při použití výchozího alokátoru se přidružená hodnota inicializuje hodnotou (například na 0 u typu int), což vyžaduje, aby T bylo možné zkonstruovat bez argumentů. Vlastní alokátor může změnit způsob konstrukce prvku. Nepoužívejte [] jen ke kontrole přítomnosti. std::map::erase(key) vrací počet odstraněných prvků; erase(it) vrací následující iterátor a vyžaduje dereferencovatelný iterátor. std::map::size vrací počet prvků v O(1). Běžné vložení a mazání podle klíče mají složitost O(log n); mazání pomocí iterátoru má amortizovanou složitost O(1). Vložení nezneplatňuje iterátory ani reference; mazání zneplatňuje pouze ty k odstraněným prvkům.

std::map::extract oddělí uzel bez kopírování či přesunu jeho prvku; chybějící klíč vytvoří prázdný handle. Před key() zkontrolujte empty(); oddělený klíč lze před opětovným vložením uzlu změnit. std::map::merge přenáší typově kompatibilní uzly bez kopírování či přesunu prvků; konfliktní klíče zůstávají ve zdroji. Přenos uzlů vyžaduje stejné alokátory. Příklad používá operace dostupné v C++23; odkazovaný dokument je průběžně vyvíjený návrh, nikoli konečná norma C++23. Příznak kompilátoru v repozitáři nepotvrzuje produkční prostředí.

Pří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ýsledek

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ýsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje