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 |
|
||||
const_pointer |
|
||||
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, специализация
|
Классы-члены
сравнивает объекты типа value_type (класс) |
Члены-функции
создаёт map (общедоступная функция-член) |
|
уничтожает map (общедоступная функция-член) |
|
| присваивает значения контейнеру (общедоступная функция-член) |
|
| возвращает связанный аллокатор (общедоступная функция-член) |
|
Доступ к элементам |
|
| доступ к заданному элементу с проверкой границ (общедоступная функция-член) |
|
| доступ к или вставка заданного элемента (общедоступная функция-член) |
|
Итераторы |
|
|
(C++11) | возвращает итератор к началу (общедоступная функция-член) |
|
(C++11) | возвращает итератор к концу (общедоступная функция-член) |
|
(C++11) | возвращает обратный итератор к началу (общедоступная функция-член) |
|
(C++11) | возвращает обратный итератор к концу (общедоступная функция-член) |
Ёмкость |
|
| проверяет, пуст ли контейнер (общедоступная функция-член) |
|
| возвращает количество элементов (общедоступная функция-член) |
|
| возвращает максимальное возможное число элементов (общедоступная функция-член) |
|
Модификаторы |
|
| очищает содержимое (общедоступная функция-член) |
|
| вставляет элементы или узлы(с C++17) (общедоступная функция-член) |
|
|
(C++23) | вставляет диапазон элементов (общедоступная функция-член) |
|
(C++17) | вставляет элемент или присваивает текущему элементу, если ключ уже существует (общедоступная функция-член) |
|
(C++11) | создаёт элемент на месте (общедоступная функция-член) |
|
(C++11) | создаёт элементы на месте с подсказкой (общедоступная функция-член) |
|
(C++17) | вставляет на месте, если ключ не существует, не делает ничего, если ключ существует (общедоступная функция-член) |
| удаляет элементы (общедоступная функция-член) |
|
| меняет содержимое (общедоступная функция-член) |
|
|
(C++17) | извлекает узлы из контейнера (общедоступная функция-член) |
|
(C++17) | соединяет узлы из другого контейнера (общедоступная функция-член) |
Поиск |
|
| возвращает количество элементов, соответствующих заданному ключу (общедоступная функция-член) |
|
| находит элемент с заданным ключом (общедоступная функция-член) |
|
|
(C++20) | проверяет, содержит ли контейнер элемент с заданным ключом (общедоступная функция-член) |
| возвращает диапазон элементов, соответствующих заданному ключу (общедоступная функция-член) |
|
| возвращает итератор на первый элемент, не меньший, чем заданный ключ (общедоступная функция-член) |
|
| возвращает итератор на первый элемент, больший, чем заданный ключ (общедоступная функция-член) |
|
Наблюдатели |
|
| возвращает функцию, сравнивающую ключи (общедоступная функция-член) |
|
возвращает функцию, сравнивающую ключи в объектах типа value_type (общедоступная функция-член) |
|
Внешние функции
|
(удалено в C++20)(удалено в C++20)(удалено в C++20)(удалено в C++20)(удалено в C++20)(C++20) | лексикографически сравнивает значения двух maps (шаблон функции) |
специализирует алгоритм std::swap (шаблон функции) |
|
|
(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 функция предоставлена |
См. также
|
(C++11) | набор пар ключ-значение, хэшируемых по ключам, ключи уникальны (шаблон класса) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/container/map