Map (C++): различия между версиями
← Новая страница: «{{заголовок со строчной буквы}} {{Стандартная библиотека C++}} <code>map</code> — стандарт...» |
(нет различий)
|
Версия от 16:52, 25 января 2020
map
— стандартный шаблонный класс библиотеки языка программирования C++, предназначенный для реализации абстракции отображения в виде упорядоченного ассоциативного контейнера. Его объявление расположено в заголовочном файле <map>
библиотеки STL[1][2], а интерпретация позволяет провести аналогию со словарём или телефонной книгой[3].
Элементами класса map
являются пары из ключей и соответствующих им значений. Хранение элементов класса map
реализовано в упорядоченном виде на основании критерия сортировки, который применяется по значениям ключей. По умолчанию критерий сортировки задаётся оператором operator<
[4]. В отличие от контейнера set
класс map
предоставляет своему пользователю operator []
[1]. Для контроля за управлением памятью возможно подключать пользовательские версии распределителей памяти. Для практической реализации класса map
обычно используются деревья двоичного поиска[5].
Благодаря упорядоченной структуре контейнера map
поиск нужного элемента в нём может быть выполнен за логарифмическое время [6].
Примечания
- ↑ 1 2 Gregorie, 2018, map and multimap, p. 518.
- ↑ van Weert, Gregorie, 2016, Ordered Associative Containers, p. 71.
- ↑ 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.
- I. Horton, P. Van Weert. Beginning C++17. From Novice to Professional : [англ.]. — 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.
- P. Van Weert, M. Gregorie. C++ Standard Library Quick Reference : [англ.]. — Apress, 2016. — ISBN 978-1-4842-1875-4.