map (C++) (map (C++))
map — стандартный шаблонный класс библиотеки языка программирования C++, предназначенный для реализации абстракции отображения в виде упорядоченного ассоциативного контейнера. Его объявление расположено в пространстве имён std заголовочного файла <map> библиотеки STL[1][2][3]. В контексте доступа к своим элементам класс map рассматривается как ассоциативный массив, в котором роль индексов играют значения ключей[4], что позволяет провести аналогию со словарём или телефонной книгой[5].
Описание
[править | править код]Элементами класса map являются пары из ключей и соответствующих им значений. Хранение элементов класса map реализовано в упорядоченном виде на основании критерия сортировки, который применяется по значениям ключей. По умолчанию критерий сортировки задаётся оператором operator< [6]. В отличие от контейнера set класс map предоставляет своему пользователю operator [][1]. Для контроля за управлением памятью возможно подключать пользовательские версии распределителей памяти. Для практической реализации класса map обычно используются деревья двоичного поиска[7].
Базовая функциональность
[править | править код]Стандартные методы класса map дают возможность пользователю осуществлять операции поиска, вставки и обхода контейнера унифицированным образом. Для многих из них предусмотрено взаимодействие со штатными итераторами библиотеки STL[8].
Благодаря упорядоченной структуре контейнера map операции поиска или внесения нужного элемента могут быть выполнены за логарифмическое время [9].
| Название | Функции |
|---|---|
size() |
Возвращает количество элементов в контейнере |
empty() |
Возвращает true если контейнер пуст
|
find(k) |
Возвращает итератор, указывающий на значение, соответствующее значению ключа k. Если такого значения в контейнере нет, то возвращается итератор end
|
operator[k] |
Возвращает ссылку на значение, соответствующее ключу k. Если такого ключа не существует, то он создаётся.
|
insert(pair(k,v)) |
Вставляет в контейнер пару (k,v), возвращая адрес его позиции
|
erase(k) |
Удаляет из контейнера элемент с ключом k
|
erase(p) |
Удаляет из контейнера элемент, на который указывает итератор p
|
begin() |
Возвращает итератор на начало контейнера |
end() |
Возвращает итератор на конец контейнера |
Примечания
[править | править код]- ↑ 1 2 Gregorie, 2018, map and multimap, p. 518.
- ↑ Van Weert, Gregorie, 2016, Ordered Associative Containers, p. 71.
- ↑ Goodrich, Tamassia, Mount, 2011, The STL map Class, p. 372.
- ↑ Литвиненко, 2005, Контейнеры Map, Multimap, с. 198.
- ↑ Horton, Van Weert, 2018, Maps, p. 730.
- ↑ Литвиненко, 2005, Контейнеры Map, Multimap, с. 195.
- ↑ Class template std:map Архивная копия от 30 января 2020 на Wayback Machine www.cplusplus.com
- ↑ Goodrich, Tamassia, Mount, 2011, The STL map Class, p. 372, 373.
- ↑ Posch, Galowicz, 2018, Knowing the new insertion hint semantics of std::map:insert, p. 524.
Источники
[править | править код]- Литвиненко, Н. А. Технология программирования на C++ : Начальный курс. — СПб. : «БХВ-Петербург», 2005. — 288 с. — ББК 32.973.26-018.1я73. — УДК 681.3.068Ь800.92C++(075.8)(G). — ISBN 5-94157-655-2.
- Gregorie, M. Professional C++ : [англ.]. — 4th. — John Wiley & Sons, 2018. — ISBN 978-1-119-42130-6.
- Goodrich, M. T. Data Structures and Algorithms in C++ : [англ.] / M. T. Goodrich, R. Tamassia, D. M. Mount. — 2nd. — John Wiley & Sons, 2011. — ISBN 978-0-470-38327-8.
- Horton,, I. Beginning C++17. From Novice to Professional : [англ.] / I. Horton,, P. Van Weert. — 5th. — Apress, 2018. — ISBN 978-1-4842-3365-8. — doi:10.1007/978-1-4842-3366-5.
- Posch, M. Expert C++ Programming : Leveraging the power of modern C++ to build scalable modular applications : [англ.] / M. Posch, J. Galowicz. — 2nd. — Packt Publishing, 2018. — ISBN 978-1-78883-139-0.
- Van Weert, P. C++ Standard Library Quick Reference : [англ.] / P. Van Weert, M. Gregorie. — Apress, 2016. — ISBN 978-1-4842-1875-4.