Map (C++)

Шаблон:Заголовок со строчной буквы Шаблон:Стандартная библиотека C++ map — стандартный шаблонный класс библиотеки языка программирования C++, предназначенный для реализации абстракции отображения в виде упорядоченного ассоциативного контейнера. Его объявление расположено в пространстве имён std заголовочного файла <map> библиотеки STLШаблон:SfnШаблон:SfnШаблон:Sfn. В контексте доступа к своим элементам класс map рассматривается как ассоциативный массив, в котором роль индексов играют значения ключейШаблон:Sfn, что позволяет провести аналогию со словарём или телефонной книгойШаблон:Sfn.

Описание

Элементами класса map являются пары из ключей и соответствующих им значений. Хранение элементов класса map реализовано в упорядоченном виде на основании критерия сортировки, который применяется по значениям ключей. По умолчанию критерий сортировки задаётся оператором operator< Шаблон:Sfn. В отличие от контейнера set класс map предоставляет своему пользователю operator []Шаблон:Sfn. Для контроля за управлением памятью возможно подключать пользовательские версии распределителей памяти. Для практической реализации класса map обычно используются деревья двоичного поиска.

Базовая функциональность

Стандартные методы класса map дают возможность пользователю осуществлять операции поиска, вставки и обхода контейнера унифицированным образом. Для многих из них предусмотрено взаимодействие со штатными итераторами библиотеки STLШаблон:Sfn.

Благодаря упорядоченной структуре контейнера map операции поиска или внесения нужного элемента могут быть выполнены за логарифмическое время $O(logn)$Шаблон:Sfn.

Название	Функции
size()	Возвращает количество элементов в контейнере
empty()	Возвращает true если контейнер пуст
find(k)	Возвращает итератор, указывающий на значение, соответствующее значению ключа k. Если такого значения в контейнере нет, то возвращается итератор end
operator[k]	Возвращает ссылку на значение, соответствующее ключу k. Если такого ключа не существует, то он создаётся.
insert(pair(k,v))	Вставляет в контейнер пару (k,v), возвращая адрес его позиции
erase(k)	Удаляет из контейнера элемент с ключом k
erase(p)	Удаляет из контейнера элемент, на который указывает итератор p
begin()	Возвращает итератор на начало контейнера
end()	Возвращает итератор на конец контейнера

Источники

• Шаблон:Публикация
• Шаблон:Публикация
• Шаблон:Публикация
• Шаблон:Публикация
• Шаблон:Публикация
• Шаблон:Публикация