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. Gregorie, 2018, map and multimap, p. 518.
  2. Van Weert, Gregorie, 2016, Ordered Associative Containers, p. 71.
  3. Goodrich, Tamassia, Mount, 2011, The STL map Class, p. 372.
  4. Литвиненко, 2005, Контейнеры Map, Multimap, с. 198.
  5. Horton, Van Weert, 2018, Maps, p. 730.
  6. Литвиненко, 2005, Контейнеры Map, Multimap, с. 195.
  7. Class template std:map www.cplusplus.com
  8. Goodrich, Tamassia, Mount, 2011, The STL map Class, p. 372, 373.
  9. 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). — 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.