Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori