KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::map — een geordende map met unieke sleutels

std::map bewaart sleutel-waardeparen in de volgorde van de comparator, met hoogstens één element per equivalente sleutel. Leer zoeken zonder wijzigingen, invoegen, wissen en knooppunten overdragen, en waarom operator[] geen controle op aanwezigheid is.

Versie: 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> uit <map> bewaart elementen van het type std::pair<const Key, T> in de volgorde van de comparator; standaard wordt std::less<Key> gebruikt. Compare moet een strikte zwakke ordening definiëren. Sleutels zijn equivalent als !comp(a, b) && !comp(b, a), niet noodzakelijk als a == b. De map staat maar één zo’n sleutel toe; met een iterator kun je de waarde wijzigen, maar niet de sleutel.

Om de overload van std::map::insert voor één element te selecteren, construeer je expliciet een element van het value_type van de map: m.insert(value_type{key, value}). Deze overload geeft een iterator-bool-paar terug: als er al een equivalente sleutel bestaat, is de bool false en wordt de opgeslagen waarde niet overschreven. Als zowel key als value impliciet naar value_type kunnen worden geconverteerd, kan m.insert({key, value}) in plaats daarvan de overload voor std::initializer_list<value_type> selecteren. Die geeft void terug en probeert twee elementen in te voegen. In het voorbeeld met std::map<int, int> selecteert de aanroep met accolades de overload voor één element. std::map::find geeft een iterator of std::map::end terug; end() wijst voorbij het laatste element en mag niet worden gedereferentieerd. std::map::contains geeft bool terug en std::map::count 0 of 1. std::map::equal_range geeft een halfopen bereik [first, last) met nul of één element. Deze zoekacties voegen niets in en kosten O(log n).

std::map::operator[] geeft een verwijzing naar de waarde; als de sleutel ontbreekt, voegt de operator een nieuw element met die sleutel in. Met de standaardallocator ondergaat de bijbehorende waarde waarde-initialisatie (bijvoorbeeld tot 0 voor int); daarvoor moet T zonder argumenten geconstrueerd kunnen worden. Een aangepaste allocator kan wijzigen hoe het element wordt geconstrueerd. Gebruik [] niet alleen om aanwezigheid te controleren. std::map::erase(key) geeft het aantal verwijderde elementen terug; erase(it) geeft de volgende iterator terug en vereist een dereferentieerbare iterator. std::map::size geeft het aantal elementen in O(1). Gewoon invoegen en wissen op sleutel kosten O(log n); wissen met een iterator heeft een geamortiseerde tijdcomplexiteit van O(1). Invoegen invalideert geen iterators of verwijzingen; wissen invalideert alleen die naar verwijderde elementen.

std::map::extract maakt een knooppunt los zonder het element te kopiëren of te verplaatsen; bij een ontbrekende sleutel ontstaat een lege handle. Controleer empty() vóór key(); een losgemaakte sleutel kan worden gewijzigd voordat het knooppunt opnieuw wordt ingevoegd. std::map::merge draagt typecompatibele knooppunten over zonder elementen te kopiëren of te verplaatsen; conflicterende sleutels blijven in de bron. Voor overdracht moeten de allocators gelijk zijn. Het voorbeeld gebruikt bewerkingen die in C++23 beschikbaar zijn; het gekoppelde document is een evoluerend ontwerp, niet de definitieve C++23-standaard. De compileroptie van de repository bevestigt niets over de productieomgeving.

Voorbeelden

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

Resultaat

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

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen