CKTIS / C++
std::map — urejena mapa z enoličnimi ključi
std::map shranjuje pare ključ–vrednost po vrstnem redu primerjalnika in vsebuje največ en element za vsak ekvivalenten ključ. Spoznajte iskanje brez spreminjanja, vstavljanje, brisanje in prenos vozlišč ter zakaj operator[] ne preverja prisotnosti ključa.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <map>
std::map<Key, T> m;
std::map<Key, T, Compare> ordered;std::map<Key, T, Compare> iz <map> shranjuje elemente std::pair<const Key, T> po vrstnem redu primerjalnika; privzeto uporablja std::less<Key>. Compare mora določati strogo šibko urejenost. Ključi so ekvivalentni, kadar velja !comp(a, b) && !comp(b, a), ne nujno kadar velja a == b. Mapa dovoljuje le en tak ključ; z iteratorjem lahko spremenite vrednost, ne pa ključa.
Če želite izbrati preobremenitev std::map::insert za vstavljanje enega elementa, izrecno ustvarite element tipa value_type te mape: m.insert(value_type{key, value}). Ta preobremenitev vrne par iterator-bool: če ekvivalenten ključ že obstaja, je vrednost bool enaka false, shranjena vrednost pa se ne prepiše. Če je mogoče tako key kot value implicitno pretvoriti v value_type, lahko klic m.insert({key, value}) namesto tega izbere preobremenitev, ki sprejme std::initializer_list<value_type>, vrne void in poskusi vstaviti dva elementa. V primeru z std::map<int, int> klic z zavitimi oklepaji izbere preobremenitev za en element. std::map::find vrne iterator ali std::map::end; end() kaže za zadnji element in ga ne smete dereferencirati. std::map::contains vrne bool, std::map::count pa 0 ali 1. std::map::equal_range vrne polodprto območje [first, last) z nič ali enim elementom. Ta iskanja ne vstavljajo elementov in imajo zahtevnost O(log n).
std::map::operator[] vrne sklic na vrednost; če ključa ni, vstavi nov element s tem ključem. Pri privzetem alokatorju se pripadajoča vrednost inicializira z vrednostjo (na primer na 0 pri tipu int), zato mora biti T mogoče privzeto konstruirati. Alokator po meri lahko spremeni način konstrukcije elementa. [] ne uporabljajte zgolj za preverjanje prisotnosti. std::map::erase(key) vrne število odstranjenih elementov; erase(it) vrne naslednji iterator in zahteva dereferencirljiv iterator. std::map::size vrne število elementov v O(1). Običajno vstavljanje in brisanje po ključu imata zahtevnost O(log n); brisanje z iteratorjem je amortizirano O(1). Vstavljanje ne razveljavi iteratorjev ali sklicev; brisanje razveljavi samo tiste za odstranjene elemente.
std::map::extract odklopi vozlišče, ne da bi njegov element kopiral ali premaknil; manjkajoči ključ ustvari prazen ročaj. Pred key() preverite empty(); odklopljeni ključ lahko spremenite pred ponovnim vstavljanjem vozlišča. std::map::merge prenese združljiva vozlišča brez kopiranja ali premikanja elementov; nasprotujoči si ključi ostanejo v viru. Prenos vozlišč zahteva enake alokatorje. Primer uporablja operacije, ki so na voljo v C++23; povezani dokument je razvijajoči se osnutek, ne dokončni standard C++23. Zastavica prevajalnika v repozitoriju ne potrjuje produkcijskega okolja.
Primeri
#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';
}
}
Rezultat
inserted=false found=20 contains=true count=1 range=true erased=1 size=2 source=1 3:10 4:40
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.