База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

std::map — подредена карта с уникални ключове

std::map съхранява двойки ключ–стойност според реда на компаратора и допуска най-много един елемент за всеки еквивалентен ключ. Научете за търсене без промяна, вмъкване, изтриване и прехвърляне на възли, както и защо operator[] не проверява дали даден ключ присъства.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

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

std::map<Key, T, Compare> от <map> съхранява елементи std::pair<const Key, T> в реда на компаратора; по подразбиране използва std::less<Key>. Compare трябва да задава строго слабо подреждане. Ключовете са еквивалентни, ако !comp(a, b) && !comp(b, a), а не непременно ако a == b. Картата допуска само един такъв ключ; чрез итератор може да промените стойността, но не и ключа.

За да изберете варианта на std::map::insert за вмъкване на един елемент, създайте изрично елемент от типа value_type на картата: m.insert(value_type{key, value}). Този вариант връща двойка итератор-bool: ако вече има еквивалентен ключ, компонентът bool е false, а съхранената стойност не се заменя. Ако и key, и value могат неявно да се преобразуват към value_type, извикването m.insert({key, value}) може вместо това да избере варианта, който приема std::initializer_list<value_type>, връща void и се опитва да вмъкне два елемента. В примера с std::map<int, int> извикването с фигурни скоби избира варианта за един елемент. std::map::find връща итератор или std::map::end; end() сочи след последния елемент и не трябва да се дереферира. std::map::contains връща bool, а std::map::count връща 0 или 1. std::map::equal_range връща полуотворен диапазон [first, last) с нула или един елемент. Тези търсения не вмъкват елементи и имат сложност O(log n).

std::map::operator[] връща препратка към стойността; ако ключът липсва, операторът вмъква нов елемент с този ключ. С алокатора по подразбиране свързаната стойност се инициализира по стойност (например до 0 при int), което изисква T да може да се конструира по подразбиране. Потребителски алокатор може да промени начина на конструиране на елемента. Не използвайте [] само за проверка дали ключът присъства. std::map::erase(key) връща броя на изтритите елементи; erase(it) връща следващия итератор и изисква итератор, който може да се дереферира. std::map::size връща броя елементи за O(1). Обикновеното вмъкване и изтриване по ключ са с цена O(log n); изтриването чрез итератор е амортизирано O(1). Вмъкването не обезсилва итератори или препратки; изтриването обезсилва само тези към изтритите елементи.

std::map::extract отделя възел, без да копира или премества елемента му; липсващ ключ дава празен handle. Проверете empty() преди key(); отделеният ключ може да се промени преди повторното вмъкване на възела. std::map::merge прехвърля съвместими по тип възли, без да копира или премества елементите; конфликтните ключове остават в източника. Прехвърлянето на възли изисква еднакви алокатори. Примерът използва операции, налични в C++23; свързаният документ е развиващ се проект, а не окончателният стандарт C++23. Флагът на компилатора в хранилището не удостоверява продукционната среда.

Примери

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

Резултат

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници