map (C++)
map — стандартный шаблонный класс библиотеки языка программирования C++, предназначенный для реализации абстракции отображения в виде упорядоченного ассоциативного контейнера. Его объявление расположено в заголовочном файле <map> библиотеки STL[1][2]. В контексте доступа к своим элементам класс map рассматривается как ассоциативный массив, в котором роль индексов играют значения ключей[3], что позволяет провести аналогию со словарём или телефонной книгой[4].
Описание
Элементами класса map являются пары из ключей и соответствующих им значений. Хранение элементов класса map реализовано в упорядоченном виде на основании критерия сортировки, который применяется по значениям ключей. По умолчанию критерий сортировки задаётся оператором operator< [5]. В отличие от контейнера set класс map предоставляет своему пользователю operator [][1]. Для контроля за управлением памятью возможно подключать пользовательские версии распределителей памяти. Для практической реализации класса map обычно используются деревья двоичного поиска[6].
Благодаря упорядоченной структуре контейнера map операции поиска или внесения нужного элемента могут быть выполнены за логарифмическое время [7].
Примечания
- ↑ 1 2 Gregorie, 2018, map and multimap, p. 518.
- ↑ Van Weert, Gregorie, 2016, Ordered Associative Containers, p. 71.
- ↑ Литвиненко, 2005, Контейнеры Map, Multimap, с. 198.
- ↑ Horton, Van Weert, 2018, Maps, p. 730.
- ↑ Литвиненко, 2005, Контейнеры Map, Multimap, с. 195.
- ↑ Class template std:map
- ↑ Posch, Galowicz, 2018, Knowing the new insertion hint semantics of std::map:insert, p. 524.
Источники
- Литвиненко, Н. А. Технология программирования на С++ : Начальный курс. — СПб. : «БХВ-Петербург», 2005. — 288 с. — ББК 32.973.26-018.1я73. — УДК 681.3.068Ь800.92С++(075.8)(G). — ISBN 5-94157-655-2.
- Gregorie, M. Professional C++ : [англ.]. — 4th. — John Wiley & Sons, 2018. — ISBN 978-1-119-42130-6.
- 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.