Страница 3 из 13
Все рассматриваемые ассоциативные контейнеры хранят последовательности своих элементов в отсортированном виде. Сортировка выполняется по ключу, причем для множеств и мультимножеств ключами выступают сами элементы (типа T), а в отображениях и мультиотображениях хранятся пары типа pair<Key, T>, первый компонент которых считается ключом (key), а второй – значением (value). По умолчанию порядок определяется операцией < для типа ключа Key, однако его можно явно указать в шаблоне контейнера в виде функционального объекта, реализующего бинарный предикат с параметрами типа Key и со свойствами операции сравнения «меньше». Мультимножества и мультиотображения, в отличие от множеств и отображений, позволяют хранить набор элементов с эквивалентными ключами (ключи считаются эквивалентными, если ни один из них не является меньшим, чем другой). Для отображения определена операция индексирования с дополнительными возможностями (см. п. 1.2.6). Вставка новых элементов в любой ассоциативный контейнер сохраняет его упорядоченность. И операция вставки, и операция удаления для ассоциативных контейнеров требует логарифмического времени, если для этих операций указывается параметр-ключ. За это же время выполняется и поиск элементов по ключу, для реализации которого в ассоциативных контейнерах предусмотрен целый набор функций-членов. Указанные свойства ассоциативных контейнеров делают их удобным механизмом для группировки и объединения наборов данных по ключу.
Поскольку контейнеры, перечисленные в таблицах 1 и 2, имеют много одинаковых функций-членов, все они далее рассматриваются совместно: в п. 1.2.2 перечисляются типы, связанные с контейнерами, и описываются варианты конструкторов, в п. 1.2.3 приводятся функции-члены, имеющиеся у всех контейнеров, в п. 1.2.4 – функции-члены последовательных контейнеров, в п. 1.2.5 – дополнительные функции-члены списков, в п. 1.2.6 – функции-члены ассоциативных контейнеров. В каждом пункте все функции-члены приводятся в алфавитном порядке их имен. Если некоторые функции-члены имеются не у всех рассматриваемых типов контейнеров, то это явно указывается; кроме того, специальным образом помечаются функции-члены, добавленные в стандарте C++11 (например, текст vector(C++11), string означает, что соответствующая функция-член доступна только для классов vector и string, причем для класса vector – только начиная со стандарта C++11). Если один из прежних вариантов функции-члена отсутствует в стандарте С++11, то он помечается текстом C++98.
Класс string имеет гораздо больше функций-членов, чем остальные контейнеры, однако в данном разделе приводятся только те из них, которые имеются также и у других последовательных контейнеров.
Если требуется одновременно упомянуть и множество, и мультимножество, то используется слово «(мульти)множество»; если требуется одновременно упомянуть и отображение, и мультиотображение, то используется слово «(мульти)отображение».
В последующих описаниях функций-членов некоторые переменные всегда связываются с данными фиксированного типа (этот тип определяется в самом контейнере – см. п. 1.2.2):
• n имеет тип size_type;
• k имеет тип key_type;
• x (а также x1, x2, …) имеет тип value_type;
• init_list имеет тип списка инициализации initializer_list<value_type> (элементы списка инициализации разделяются запятыми, сам список заключается в фигурные скобки);
• pos, hintpos, first и last (а также pos_lst, first_lst, last_lst) имеют тип итератора соответствующего контейнера (iterator).
Переменная other обозначает параметр, являющийся контейнером того же типа, что и контейнер, для которого вызывается функция-член. Переменные InIterFirst и InIterLast обозначают итераторы чтения, которые могут быть связаны с контейнером другого типа (при этом тип элементов контейнера должен совпадать с типом элементов контейнера, для которого вызывается функция-член).
Функции-члены begin, end, rbegin, rend, front, back, at, equal_range, find, lower_bound, upper_bound (а также data для векторов и operator[ ] для последовательных контейнеров) реализованы в двух вариантах: неконстантном и константном (например, iterator begin(…) и const_iterator begin(…) const); в дальнейшем это особо не оговаривается и константный вариант не приводится. В стандарте C++11 константные варианты функций-членов begin, end, rbegin, rend можно использовать с именами cbegin, cend, crbegin, crend соответственно.
1.2.2. Типы, определенные в контейнерах. Параметры конструкторов
Для доступа к указанным типам используется нотация ::, например vector<int>::iterator.
Типы итераторов, связанные с данным контейнером.
Типы ссылок на элементы данного контейнера.
Типы указателей на элементы данного контейнера.
Тип, используемый при указании размера контейнера.
Тип элементов контейнера (T для последовательных контейнеров, Key для (мульти)множеств, pair<const Key, T> для (мульти)отображений).
Тип Key (элементы-ключи для (мульти)множеств, ключи для (мульти)отображений).
Тип значений T для (мульти)отображений.
Тип функционального объекта, используемого при сравнении ключей типа key_type.
Тип функционального объекта, используемого при сравнении элементов типа value_type по ключу типа key_type.
Ниже приводятся варианты параметров для конструкторов контейнеров. Большинство вариантов может использоваться для всех видов рассматриваемых контейнеров; единственный особый вариант для последовательных контейнеров помечен соответствующим образом. Следует обратить внимание на вариант конструктора, появившийся в стандарте C++11 и использующий список инициализации.
Создает пустой контейнер. Для ассоциативных контейнеров можно дополнительно указать операцию сравнения comp (по умолчанию используется операция сравнения Compare(), взятая из шаблона).
Создает контейнер, содержащий элементы (типа value_type) из диапазона [InIterFirst, InIterLast). Для ассоциативных контейнеров можно дополнительно указать операцию сравнения comp (по умолчанию используется операция сравнения Compare(), взятая из шаблона). Для ассоциативных контейнеров вставляемые элементы не обязаны быть упорядоченными, однако если они упорядочены, то время их вставки ускоряется.