CKTIS / C++
std::map — uređena mapa jedinstvenih ključeva
std::map pohranjuje parove ključ–vrijednost prema redoslijedu komparatora i dopušta najviše jedan element za svaki ekvivalentni ključ. Upoznajte pretraživanje bez izmjena, umetanje, brisanje i prijenos čvorova te saznajte zašto operator[] ne provjerava postoji li ključ.
Verzija: 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> pohranjuje elemente std::pair<const Key, T> prema redoslijedu komparatora; zadano koristi std::less<Key>. Compare mora definirati strogi slabi poredak. Ključevi su ekvivalentni ako vrijedi !comp(a, b) && !comp(b, a), ne nužno ako je a == b. Mapa dopušta samo jedan takav ključ; iteratorom možete mijenjati vrijednost, ali ne i ključ.
Da biste odabrali preopterećenje funkcije std::map::insert za umetanje jednog elementa, izričito konstruirajte element tipa value_type te mape: m.insert(value_type{key, value}). To preopterećenje vraća par iterator-bool: ako ekvivalentni ključ već postoji, komponenta bool ima vrijednost false, a pohranjena se vrijednost ne prepisuje. Ako se i key i value mogu implicitno pretvoriti u value_type, poziv m.insert({key, value}) može umjesto toga odabrati preopterećenje koje prima std::initializer_list<value_type>, vraća void i pokušava umetnuti dva elementa. U primjeru s std::map<int, int> poziv s vitičastim zagradama odabire preopterećenje za jedan element. std::map::find vraća iterator ili std::map::end; end() označava poziciju iza posljednjeg elementa i ne smije se dereferencirati. std::map::contains vraća bool, a std::map::count vraća 0 ili 1. std::map::equal_range vraća poluotvoreni raspon [first, last) s nula ili jednim elementom. Te operacije pretraživanja ne umeću elemente i imaju složenost O(log n).
std::map::operator[] vraća referencu na vrijednost; ako ključ nedostaje, umeće novi element s tim ključem. Uz zadani alokator pridružena se vrijednost inicijalizira vrijednošću (primjerice na 0 za int), što zahtijeva da se T može konstruirati bez argumenata. Prilagođeni alokator može promijeniti način konstrukcije elementa. Nemojte koristiti [] samo za provjeru postoji li ključ. std::map::erase(key) vraća broj obrisanih elemenata; erase(it) vraća sljedeći iterator i zahtijeva dereferencibilan iterator. std::map::size vraća broj elemenata u O(1). Uobičajeno umetanje i brisanje po ključu imaju složenost O(log n); brisanje iteratorom amortizirano je O(1). Umetanje ne poništava iteratore ni reference; brisanje poništava samo one koji se odnose na obrisane elemente.
std::map::extract odvaja čvor bez kopiranja ili premještanja njegova elementa; za ključ koji ne postoji dobiva se prazan handle. Provjerite empty() prije key(); odvojeni ključ može se promijeniti prije ponovnog umetanja čvora. std::map::merge prenosi čvorove kompatibilnih tipova bez kopiranja ili premještanja elemenata; sukobljeni ključevi ostaju u izvoru. Prijenos čvorova zahtijeva jednake alokatore. Primjer koristi operacije dostupne u C++23; povezani dokument je nacrt koji se i dalje razvija, a ne konačni standard C++23. Zastavica prevoditelja repozitorija ne potvrđuje produkcijsko okruženje.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.