Spec-Zone.ru › C++

std::map

Определено в заголовочном файле <map>
template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
(1)
namespace pmr {
    template<
        class Key,
        class T,
        class Compare = std::less<Key>
    > using map = std::map<Key, T, Compare,
                           std::pmr::polymorphic_allocator<std::pair<const Key, T>>>;
}
(2) (с C++17)

std::map — это упорядоченный ассоциативный контейнер, который содержит пары ключ-значение с уникальными ключами. Ключи сортируются с использованием функции сравнения Compare. Операции поиска, удаления и вставки имеют логарифмическую сложность. Обычно карты реализуются в виде красно-чёрных деревьев.

Итераторы std::map итерируются в порядке возрастания ключей, где возрастание определяется функцией сравнения, использованной при создании. То есть, если

  • m, итератор std::map
  • it_l и it_r, ссылающиеся на итераторы m, при этом it_l < it_r.

m.value_comp()(*it_l, *it_r) == true (от меньшего к большему, если используется стандартная функция сравнения).

Всюду, где стандартная библиотека использует требования Compare, уникальность определяется с помощью отношения эквивалентности. Грубо говоря, два объекта a и b считаются эквивалентными (не уникальными), если ни один не меньше другого: !comp(a, b) && !comp(b, a).

std::map соответствует требованиям Container, AllocatorAwareContainer, AssociativeContainer и ReversibleContainer.

Параметры шаблона

Типы членов

Тип члена Определение
key_type Key
mapped_type T
value_type std::pair<const Key, T>
size_type Целочисленный тип без знака (обычно std::size_t)
difference_type Целочисленный тип со знаком (обычно std::ptrdiff_t)
key_compare Compare
allocator_type Allocator
reference value_type&
const_reference const value_type&
pointer
Allocator::pointer (до C++11)
std::allocator_traits<Allocator>::pointer (с C++11)
const_pointer
Allocator::const_pointer (до C++11)
std::allocator_traits<Allocator>::const_pointer (с C++11)
iterator Двунаправленный итератор для value_type
const_iterator Двунаправленный итератор для const value_type
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator std::reverse_iterator<const_iterator>
node_type (с C++17) специализация узла-обработчика, представляющего узел контейнера
insert_return_type (с C++17) тип, описывающий результат вставки node_type, специализация

template<class Iter, class NodeType> struct /*unspecified*/ { Iter position; bool inserted; NodeType node; };
с параметрами шаблона iterator и node_type.

Классы-члены

value_compare
сравнивает объекты типа value_type
(класс)

Члены-функции

(конструктор)
создаёт map
(общедоступная функция-член)
(деструктор)
уничтожает map
(общедоступная функция-член)
operator=
присваивает значения контейнеру
(общедоступная функция-член)
get_allocator
возвращает связанный аллокатор
(общедоступная функция-член)
Доступ к элементам
at
доступ к заданному элементу с проверкой границ
(общедоступная функция-член)
operator[]
доступ к или вставка заданного элемента
(общедоступная функция-член)
Итераторы
begincbegin
(C++11)
возвращает итератор к началу
(общедоступная функция-член)
endcend
(C++11)
возвращает итератор к концу
(общедоступная функция-член)
rbegincrbegin
(C++11)
возвращает обратный итератор к началу
(общедоступная функция-член)
rendcrend
(C++11)
возвращает обратный итератор к концу
(общедоступная функция-член)
Ёмкость
empty
проверяет, пуст ли контейнер
(общедоступная функция-член)
size
возвращает количество элементов
(общедоступная функция-член)
max_size
возвращает максимальное возможное число элементов
(общедоступная функция-член)
Модификаторы
clear
очищает содержимое
(общедоступная функция-член)
insert
вставляет элементы или узлы(с C++17)
(общедоступная функция-член)
insert_range
(C++23)
вставляет диапазон элементов
(общедоступная функция-член)
insert_or_assign
(C++17)
вставляет элемент или присваивает текущему элементу, если ключ уже существует
(общедоступная функция-член)
emplace
(C++11)
создаёт элемент на месте
(общедоступная функция-член)
emplace_hint
(C++11)
создаёт элементы на месте с подсказкой
(общедоступная функция-член)
try_emplace
(C++17)
вставляет на месте, если ключ не существует, не делает ничего, если ключ существует
(общедоступная функция-член)
erase
удаляет элементы
(общедоступная функция-член)
swap
меняет содержимое
(общедоступная функция-член)
extract
(C++17)
извлекает узлы из контейнера
(общедоступная функция-член)
merge
(C++17)
соединяет узлы из другого контейнера
(общедоступная функция-член)
Поиск
count
возвращает количество элементов, соответствующих заданному ключу
(общедоступная функция-член)
find
находит элемент с заданным ключом
(общедоступная функция-член)
contains
(C++20)
проверяет, содержит ли контейнер элемент с заданным ключом
(общедоступная функция-член)
equal_range
возвращает диапазон элементов, соответствующих заданному ключу
(общедоступная функция-член)
lower_bound
возвращает итератор на первый элемент, не меньший, чем заданный ключ
(общедоступная функция-член)
upper_bound
возвращает итератор на первый элемент, больший, чем заданный ключ
(общедоступная функция-член)
Наблюдатели
key_comp
возвращает функцию, сравнивающую ключи
(общедоступная функция-член)
value_comp
возвращает функцию, сравнивающую ключи в объектах типа value_type
(общедоступная функция-член)

Внешние функции

operator==operator!=operator<operator<=operator>operator>=operator<=>
(удалено в C++20)(удалено в C++20)(удалено в C++20)(удалено в C++20)(удалено в C++20)(C++20)
лексикографически сравнивает значения двух maps
(шаблон функции)
std::swap(std::map)
специализирует алгоритм std::swap
(шаблон функции)
erase_if(std::map)
(C++20)
удаляет все элементы, удовлетворяющие определённым критериям
(шаблон функции)

Руководства по выводу типов

(с C++17)

Примечания

Макрокоманда проверки наличия функции Значение Стандарт Функция
__cpp_lib_containers_ranges 202202L (C++23) Создание и вставка диапазонов для контейнеров

Пример

#include <iostream>
#include <map>
#include <string>
#include <string_view>
 
void print_map(std::string_view comment, const std::map<std::string, int>& m)
{
    std::cout << comment;
    // Iterate using C++17 facilities
    for (const auto& [key, value] : m)
        std::cout << '[' << key << "] = " << value << "; ";
 
// C++11 alternative:
//  for (const auto& n : m)
//      std::cout << n.first << " = " << n.second << "; ";
//
// C++98 alternative:
//  for (std::map<std::string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
//      std::cout << it->first << " = " << it->second << "; ";
 
    std::cout << '\n';
}
 
int main()
{
    // Create a map of three (string, int) pairs
    std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
 
    print_map("1) Initial map: ", m);
 
    m["CPU"] = 25; // update an existing value
    m["SSD"] = 30; // insert a new value
    print_map("2) Updated map: ", m);
 
    // Using operator[] with non-existent key always performs an insert
    std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
    print_map("4) Updated map: ", m);
 
    m.erase("GPU");
    print_map("5) After erase: ", m);
 
    std::erase_if(m, [](const auto& pair){ return pair.second > 25; });
    print_map("6) After erase: ", m);
    std::cout << "7) m.size() = " << m.size() << '\n';
 
    m.clear();
    std::cout << std::boolalpha << "8) Map is empty: " << m.empty() << '\n';
}

Вывод:

1) Initial map: [CPU] = 10; [GPU] = 15; [RAM] = 20;
2) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;
3) m[UPS] = 0
4) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30; [UPS] = 0;
5) After erase: [CPU] = 25; [RAM] = 20; [SSD] = 30; [UPS] = 0;
6) After erase: [CPU] = 25; [RAM] = 20; [UPS] = 0;
7) m.size() = 3
8) Map is empty: true

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR Применено к Поведение, как опубликовано Правильное поведение
LWG 230 C++98 Key не должно было быть CopyConstructible
(ключ типа Key возможно не сможет быть сконструирован)
Key также должно быть
CopyConstructible
LWG 464 C++98 доступ к константной map по ключу был неудобен at функция предоставлена

См. также

unordered_map
(C++11)
набор пар ключ-значение, хэшируемых по ключам, ключи уникальны
(шаблон класса)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/map

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API