Текст книги "Введение в стандартную библиотеку шаблонов C++. Описание, примеры использования, учебные задачи"

Удаляет все элементы контейнера и копирует в него все элементы контейнера other (тип контейнера other должен совпадать с типом преобразуемого контейнера). Возвращает полученный контейнер. В стандарте С++11 добавлен вариант операции =, обеспечивающий перемещение элементов контейнера other, если контейнер other является ссылкой на r-значение (r-value reference), а также вариант со списком инициализации init_list (см. описание последнего варианта конструктора в п. 1.2.2).

Возвращает итератор, указывающий на первый элемент контейнера.

Удаляет все элементы контейнера.

Возвращает true, если контейнер пуст, и false в противном случае.

Возвращает итератор, указывающий на позицию за последним элементом контейнера.

Возвращает максимально возможный размер контейнера.

Возвращает обратный итератор, связанный с последним элементом контейнера.

Возвращает обратный итератор, связанный с позицией перед первым элементом контейнера.

Возвращает текущий размер контейнера.

Меняет местами содержимое данного контейнера и контейнера other того же типа.

Удаляет все элементы контейнера и копирует в него новые данные (n копий значения x или элементы из диапазона [InIterFirst, InIterLast)). В стандарте C++11 добавлен вариант с параметром init_list – списком инициализации. Данная функция расширяет возможности, предоставляемые операцией копирования =.

Возвращает ссылку на элемент с индексом n (0 <= n < size()). Выход за границы не контролируется. Для типа string в случае n == size() возвращается символ с кодом 0.

Возвращает ссылку на элемент с индексом n (0 <= n < size()). Выход за границы приводит к возбуждению исключения out_of_range.

Возвращает ссылку на последний элемент контейнера. Для пустого контейнера поведение не определено.

Возвращает текущую емкость контейнера.

Возвращает указатель на внутренний массив, содержащий элементы вектора или символы строки. Для строк реализован только в константном варианте и возвращает константный указатель.

Вставляет в позицию pos контейнера новый элемент, создавая этот элемент «на месте» и используя при его конструировании параметры arg1, arg2, … . Позволяет избежать дополнительных операций копирования или перемещения, выполняемых при использовании функции-члена insert. Возвращает итератор, указывающий на вставленный элемент.

Добавляет в конец контейнера новый элемент, создавая этот элемент «на месте» и используя при его конструировании параметры arg1, arg2, … . Позволяет избежать дополнительных операций копирования или перемещения, выполняемых при использовании функции-члена push_back.

Добавляет в начало контейнера новый элемент, создавая этот элемент «на месте» и используя при его конструировании параметры arg1, arg2, … . Позволяет избежать дополнительных операций копирования или перемещения, выполняемых при использовании функции-члена push_front.

Удаляет элемент на позиции pos или все элементы в диапазоне [first, last) и возвращает итератор, указывающий на элемент, следующий за последним удаленным элементом (или итератор end(), если были удалены конечные элементы контейнера).

Возвращает ссылку на первый элемент контейнера. Для пустого контейнера поведение не определено.

Вставляет в контейнер новые данные, начиная с позиции pos (соответственно одно или n значений x, элементы из диапазона [InIterFirst, InIterLast) или элементы из списка инициализации init_list). Первый вариант функции-члена возвращает итератор, указывающий на вставленный элемент. Два последних варианта, добавленных в стандарт С++11 вместо третьего варианта, возвращают итератор, указывающий на первый вставленный элемент, или исходное значение pos, если диапазон или список инциализации являются пустыми.

Удаляет последний элемент. Для пустого контейнера поведение не определено.

Удаляет первый элемент. Для пустого контейнера поведение не определено.

Добавляет x в конец контейнера.

Добавляет x в начало контейнера.

Резервирует емкость размером не менее n.

Изменяет размер контейнера, делая его равным n. Если n > size(), то в конец контейнера добавляется требуемое число копий x. Если n < size(), то удаляется требуемое количество конечных элементов контейнера. В стандарте С++11 вариант с одним параметром оптимизирован таким образом, чтобы избежать создания ненужных копий объектов T.

Позволяет уменьшить размер памяти, выделенной для хранения элементов контейнера, однако не гарантирует, что память действительно будет уменьшена.

Все дополнительные функции-члены класса list, кроме splice, представляют собой специальные реализации соответствующих алгоритмов, которые необходимо использовать вместо стандартных алгоритмов при обработке списков.

Выполняет операцию слияния текущего списка и списка lst того же типа (оба списка должны быть предварительно отсортированы). При слиянии элементы сравниваются с помощью операции < или предиката comp, если он явно указан (и эта же операция или предикат должны быть ранее использованы для сортировки списков). Слияние является устойчивым, т. е. относительный порядок следования элементов исходных списков не нарушается. Если «одинаковые» элементы присутствуют как в текущем списке, так и в списке lst, то элемент из lst помещается после элемента, уже присутствующего в текущем списке. В результате слияния список lst становится пустым. В стандарте С++11 добавлены варианты с параметром lst, являющимся ссылкой на r-значение (r-value reference).

Удаляет из списка, соответственно, все вхождения элемента x или все элементы, для которых предикат pred возвращает значение true.

Изменяет порядок элементов списка на обратный.

Выполняет сортировку списка, используя операцию < или предикат comp, если он явно указан. Сортировка является устойчивой, т. е. относительный порядок элементов с одинаковыми ключами сортировки не изменяется.

Перемещает элементы из списка lst в текущий список (элементы размещаются, начиная с позиции pos). Перемещаются, соответственно, все элементы списка lst, элемент списка lst, расположенный на позиции pos_lst, и элементы списка lst из диапазона [first_lst, last_lst) (если текущий список совпадает со списком lst, то итератор pos не должен входить в диапазон [first_lst, last_lst)). В стандарте С++11 добавлены варианты с параметром lst, являющимся ссылкой на r-значение (r-value reference).

Удаляет соседние «одинаковые» элементы списка, оставляя первый из набора «одинаковых» элементов. Для сравнения элементов используется операция == или предикат pred, если он явно указан.

Возвращает ссылку на значение, связанное с ключом k. Если ключ k отсутствует в контейнере, то в контейнер добавляется пара с ключом k и значением по умолчанию T(), и операция [ ] возвращает ссылку на это значение. Фактически данная операция возвращает следующее выражение: insert(make_pair(k, T())).first->second. В стандарте С++11 добавлен вариант с параметром k, являющимся ссылкой на r-значение (r-value reference).

Возвращает ссылку на значение, связанное с ключом k. Если ключ k отсутствует в контейнере, то возбуждается исключение out_of_range.

Возвращает число ключей со значением k. Для множества и отображения это либо 0, либо 1; для мультимножества и мультиотображения возвращаемое значение может быть больше 1.

Вставляет в контейнер новый элемент, создавая этот элемент «на месте» и используя при его конструировании параметры arg1, arg2, … . Позволяет избежать дополнительных операций копирования или перемещения, выполняемых при использовании функции-члена insert. Если элемент с указанным ключом уже имеется в контейнере, то в случае множества и отображения попытка вставки игнорируется. Возвращает итератор, указывающий на вставленный элемент, а также (в варианте для множества и отображения) логическое значение, определяющее, была ли произведена вставка. Если вставка не была произведена из-за того, что в контейнере (множестве или отображении) уже существует элемент с таким же ключом, то возвращается позиция уже имеющегося элемента с этим ключом.

Вставляет в контейнер новый элемент, создавая этот элемент «на месте» и используя при его конструировании параметры arg1, arg2, … . Позволяет избежать дополнительных операций копирования или перемещения, выполняемых при использовании функции-члена insert. Параметр hintpos является «подсказкой» для позиции вставки: элемент x вставляется максимально близко перед позицией hintpos. Возвращает итератор, указывающий на вставленный элемент (если элемент с указанным ключом уже имеется в контейнере, то в случае множества и отображения попытка вставки игнорируется и возвращается позиция уже имеющегося элемента с этим ключом).

Возвращает результат вызова функций lower_bound и upper_bound в виде пары итераторов: make_pair(lower_bound(k), upper_bound(k)).

Удаляет элемент (элементы) с ключом k, элемент в позиции pos или все элементы в диапазоне [first, last). В первом случае возвращает количество удаленных элементов (для множества и отображения это либо 0, либо 1). Два последних варианта, добавленных в стандарт С++11 вместо двух предыдущих вариантов, возвращают итератор, указывающий на элемент, следующий за последним удаленным элементом (или итератор end(), если были удалены конечные элементы контейнера).

Ищет ключ k и возвращает итератор, указывающий на соответствующий элемент контейнера, или end(), если ключ не найден. В случае мультимножества и мультиотображения итератор может указывать на любой из элементов с ключом k.

Вставляет в контейнер новые данные. Если данные с указанным ключом уже имеются в контейнере, то в случае множества и отображения попытка вставки игнорируется. Во всех вариантах, кроме двух последних, функция возвращает позицию вставленного элемента, а также (в первом варианте, имеющемся только у множества и отображения) логическое значение, определяющее, была ли произведена вставка. Если вставка не была произведена из-за того, что в контейнере (множестве или отображении) уже существует элемент с таким же ключом, то возвращается позиция уже имеющегося элемента с этим ключом. Параметр hintpos является «подсказкой» для позиции вставки: элемент x вставляется максимально близко к позиции hintpos (в стандарте C++11 уточняется, что вставка выполняется перед позицией hintpos). Вариант с параметрами InIterFirst, InIterLast обеспечивает вставку всех элементов из диапазона [InIterFirst, InIterLast); эти элементы не обязаны быть упорядоченными по ключу, однако если они упорядочены, то время их вставки уменьшается. Вариант с параметром init_list (списком инициализации) вставляет в контейнер все элементы из указанного списка; этот вариант добавлен в стандарте C++11.

Возвращает функциональный объект, обеспечивающий сравнение ключей.

Если в множестве или отображении присутствует элемент с ключом k, то возвращается его позиция (в случае мультимножества или мультиотображения возвращается позиция первого элемента с ключом k); если такого элемента нет, то возвращается позиция, куда будет вставлен такой элемент.

Если в множестве или отображении присутствует элемент с ключом k, то возвращается позиция элемента, следующего за ним (в случае мультимножества и мультиотображения возвращается позиция элемента, следующего за последним элементом с ключом k); если элемента с ключом k нет, то возвращается позиция, куда будет вставлен такой элемент.

Возвращает функциональный объект, обеспечивающий сравнение элементов контейнера по их ключам. В случае (мульти)множества совпадает с объектом key_compare, в случае (мульти)отображения выполняет сравнение пар pair<const Key, T> по их первому компоненту Key.

Функция-член insert реализована во всех последовательных контейнерах в трех вариантах (в стандарте С++11 добавлен еще один вариант). Первый параметр во всех вариантах – итератор pos, определяющий позицию вставки. Новые данные вставляются, начиная с указанной позиции pos; все прежние элементы, начиная с позиции pos и далее, смещаются вправо (по направлению к концу контейнера). Варианты различаются параметрами, определяющими, что именно вставляется: это либо (1) один параметр x типа T (вставляется единственное значение x), либо (2) параметры n и x (вставляются n значений x), либо (3) два итератора чтения InIterFirst и InIterLast (вставляются все элементы из диапазона [InIterFirst, InIterLast)), либо (4, в стандарте C++11) список инициализации init_list. До появления стандарта C++11 только вариант (1) функции insert возвращал значение, этим значением являлся итератор, указывающий на вставленный элемент. В стандарте С++11 варианты (3) и (4) также возвращают значение – итератор, указывающий на первый вставленный элемент, или исходное значение pos, если диапазон или список инциализации являются пустыми. Параметр-итератор pos и возвращаемый итератор всегда прямые (обычные) итераторы; обратные итераторы в качестве pos использовать нельзя.

Имеются дополнительные функции-члены, связанные со вставкой: это push_back(x) – вставка одного элемента в конец контейнера (реализована для всех последовательных контейнеров) и push_front(x) – вставка одного элемента в начало контейнера (реализована для дека и списка). Эти функции не возвращают значения.

Функция-член erase реализована во всех последовательных контейнерах в двух вариантах: (1) с параметром-итератором pos, определяющим позицию удаляемого элемента, и с двумя параметрами-итераторами first и last, определяющими диапазон [first, last) удаляемых элементов. В обоих вариантах возвращается итератор, который указывает на элемент, расположенный за удаленным элементом (или удаленным диапазоном).

Имеются дополнительные функции-члены, связанные с удалением: это pop_back() – удаление последнего элемента из контейнера (реализована для всех последовательных контейнеров; поддержка для строк string добавлена в стандарте C++11), pop_front() – удаление первого элемента из контейнера (реализована для дека и списка), clear() – удаление всех элементов из контейнера (реализована для всех контейнеров). Эти функции не возвращают значения.

Альтернативой функциям insert и erase для списков list являются три варианта функции-члена splice, позволяющие перемещать отдельные элементы или их диапазоны между различными списками или между различными позициями одного списка. Все варианты функции splice начинаются с параметров pos (итератора, определяющего место вставки) и lst (списка-источника вставляемых данных). Если других параметров нет, то список-источник lst целиком вставляется в позицию pos списка-приемника; если имеется один дополнительный параметр-итератор pos_lst, то из списка-источника в список-приемник перемещается единственный элемент, связанный с итератором pos_lst; если имеются два дополнительных параметра first_lst и last_lst, то перемещается диапазон элементов [first_lst, last_lst). Все перемещаемые элементы удаляются из списка-источника.

При выполнении вставки и удаления важно знать, когда в результате выполнения этих действий итераторы и ссылки становятся недействительными (одновременно со ссылками становятся недействительными и указатели).

Вектор

Вставка:

• если в результате вставки выполняется перераспределение памяти (увеличивается емкость), то становятся недействительными все итераторы и ссылки;

• если перераспределения памяти не производится, то итераторы и ссылки до позиции вставки остаются корректными, а прочие – недействительными.

Удаление:

• все итераторы и ссылки до позиции удаления остаются корректными, а прочие – недействительными.

Дек

Вставка:

• все итераторы делаются недействительными;

• ссылки делаются недействительными при вставке в середину дека и остаются корректными при вставке в начало или конец дека.

Удаление:

• все итераторы делаются недействительными;

• ссылки на оставшиеся элементы делаются недействительными при удалении элементов из середины дека и остаются корректными при удалении начальных или конечных элементов дека.

Список

Вставка:

• все итераторы и ссылки остаются корректными.

Удаление:

• все итераторы и ссылки на оставшиеся элементы списка остаются корректными.

В данном пункте, как и в пунктах 1.2.2–1.2.7, посвященных основным видам контейнеров, при описании конструкторов и функций-членов контейнеров не указывается дополнительный тип Alloc, который обычно устанавливается по умолчанию. Все рассматриваемые в данном пункте контейнеры определены в пространстве имен std.

Начнем с описания контейнеров-адаптеров: стека (stack), очереди (queue) и очереди с приоритетом (priority_queue).

Особенностью контейнеров-адаптеров является то, что они основаны на одном из «настоящих» контейнеров, который хранится в качестве внутреннего контейнера (underlying container) с именем c – защищенного члена контейнера-адаптера. Для очереди с приоритетом используется еще один защищенный член – функциональный объект comp, используемый для сравнения элементов.

Реализация функций-членов контейнеров-адаптеров сводится к вызову соответствующих функций-членов «внутреннего» контейнера c. При этом набор средств, доступных для контейнеров-адаптеров, существенно сокращен по сравнению со средствами внутреннего контейнера. В частности, с контейнерами-адаптерами не связываются итераторы, что не позволяет их использовать совместно со стандартными алгоритмами.

В таблице 3 приводится описание шаблонов контейнеров-адаптеров.

Таблица 3

Контейнеры-адаптеры

Для всех контейнеров-адаптеров можно использовать конструктор без параметров и конструктор копии с параметром other того же типа, что и создаваемый адаптер; в стандарте С++11 добавлен конструктор перемещения, в котором параметр other является ссылкой на r-значение.

Кроме того, для стека и очереди можно использовать конструктор с явно указанным контейнером cont типа const Container& (в стандарте C++11 добавлен вариант с типом Container&&), содержимое которого копируется (или, соответственно, перемещается) во внутренний контейнер c адаптера.

Для очереди с приоритетом предусмотрены также конструкторы со следующими параметрами (в квадратных скобках, как обычно, указаны необязательные параметры):

Здесь параметр comp имеет тип const Compare& и определяет операцию сравнения для очереди с приоритетом, параметр cont имеет тип const Container& или Container&& (C++11) и определяет начальное содержимое, которое копируется или, соответственно, перемещается во внутренний контейнер c адаптера. При наличии параметров-итераторов чтения first и last после первоначального заполнения внутреннего контейнера с помощью параметра cont (или, по умолчанию, создания пустого внутреннего контейнера) для него вызывается функция-член c.insert(c.end(), first, last). На завершающем этапе формирования очереди с приоритетом с использованием данных вариантов конструктора для ее внутреннего контейнера вызывается алгоритм make_heap(c.begin(), c.end(), comp).

Для всех контейнеров-адаптеров определена операция =, обеспечивающая копирование (а в стандарте C++11 и перемещение) элементов из одного адаптера в другой того же типа.

Кроме того, для всех контейнеров-адаптеров (как и для всех других контейнеров) определены функции-члены bool empty() const и size_type size() const (выполнение которых сводится к вызову одноименных функций-членов внутренних контейнеров: c.empty() и c.size()), а также функция-член void swap(other), обеспечивающая обмен содержимым между двумя адаптерами одинакового типа (для этого выполняется вызов алгоритма swap(c, other.c), а в случае очереди с приоритетом дополнительно вызывается алгоритм swap(comp, other.comp)).

Для доступа к элементам контейнеров-адаптеров предусмотрены следующие функции-члены:

• стек: reference top() – доступ к верхнему элементу стека (возвращает c.back());

• очередь: reference front() – доступ к начальному элементу очереди (возвращает c.front()) и reference back() – доступ к конечному элементу очереди (возвращает c.back());

• очередь с приоритетом: reference front() – доступ к наибольшему элементу очереди (возвращает c.front()).

Контейнеры-адаптеры реализуют ограниченный набор действий. Стек позволяет добавлять новый элемент в вершину, получать значение верхнего элемента и удалять верхний элемент. Очередь позволяет добавлять новый элемент в конец, получать значение начального и конечного элемента и удалять начальный элемент. Очередь с приоритетом позволяет добавлять новый элемент, получать значение наибольшего элемента и удалять наибольший элемент.

Во всех контейнерах-адаптерах используются одинаковые имена для функций-членов, связанных с добавлением и удалением элементов. Эти функции-члены описаны в таблице 4.

Таблица 4

Вставка и удаление для контейнеров-адаптеров

Теперь кратко опишем те новые виды контейнеров, которые появились в стандарте C++11.

Контейнер array является контейнерным аналогом массива фиксированного размера. Его шаблон имеет вид: array<T, N>, где T – это тип элементов, а N – число, задающее размер контейнера. Данный контейнер определен в заголовочном файле <array>. Помимо конструктора без параметров контейнер array можно инициализировать с помощью списка инициализации. Все, кроме одной, функции-члены контейнера array аналогичны по своему назначению одноименным функциям-членам контейнера vector (можно сказать, что array – это контейнер vector без возможности вставки и удаления элементов). Перечислим эти функции-члены:

• функции, описанные в п. 1.2.3: begin и его константный вариант cbegin, empty, end и его константный вариант cend, max_size, rbegin и его константный вариант crbegin, rend и его константный вариант crend, size, swap;

• функции, описанные в п. 1.2.4: operator[], at, back, data, front.

Единственная функция-член, имеющаяся в контейнере array и при этом отсутствующая в контейнере vector, – это функция void fill(value), позволяющая заполнить существующий контейнер array одинаковыми значениями value.

Контейнер forward_list является контейнерной реализацией односвязного списка (в отличие от контейнера list, реализующего двусвязный список). Данный контейнер требует меньше памяти для хранения своих элементов, но при этом обладает и более ограниченным по сравнению со списком list набором возможностей. Его шаблон имеет вид: forward_list<T>, где T – тип элементов списка. Контейнер определен в заголовочном файле <forward_list>. Контейнер forward_list имеет те же варианты конструктора и операции =, что и контейнер list.

Перечислим функции-члены, которые имеются у обеих реализаций списков – как list, так и forward_list – и выполняются аналогичным образом:

• функции, описанные в п. 1.2.3: begin и его константный вариант cbegin, clear, empty, end и его константный вариант cend, max_size, swap;

• функции, описанные в п. 1.2.4: assign, emplace_front, front, pop_front, push_front, resize;

• функции, описанные в п. 1.2.5: merge, remove, remove_if, reverse, sort, unique.

Обратите внимание на то, что у списка forward_list отсутствуют средства быстрого доступа к его конечному элементу, а также обратные итераторы и функция-член size.

Функции-члены, связанные со вставкой и удалением элементов списка forward_list, отличаются от аналогичных функций списка list тем, что в качестве параметра pos указывается не позиция вставляемого или удаляемого элемента, а позиция, предшествующая позиции вставляемого или удаляемого элемента (что обусловлено односвязностью списка forward_list). По этой причине все функции-члены, связанные со вставкой и удалением, снабжены в классе forward_list суффиксом «after»: insert_after, emplace_after, erase_after, splice_after. Назначение этих функций и смысл их параметров те же, что и для аналогичных функций-членов контейнера list без суффикса _after: insert, emplace, erase (см. п. 1.2.4) и splice (см. п. 1.3.5). Исключение составляет параметр pos, указывающий, как было отмечено выше, позицию, предшествующую позиции вставляемого или удаляемого элемента, а также параметр first для функции erase_after(first, last) и параметры pos_lst и first_lst для функций splice_after(pos, lst, pos_lst) и splice_after(pos, lst, first_lst, last_lst):

• функция erase_after(first, last) удаляет элементы в диапазоне (first, last) (элемент first не удаляется, в чем состоит отличие от реализации функции-члена erase(first, last) в других последовательных контейнерах – см. п. 1.2.4);

• функция splice_after(pos, lst, pos_lst) перемещает из списка lst (типа forward_list) в текущий список элемент, следующий за элементом в позиции pos_lst (и помещает его в позицию, следующую за позицией pos), а функция splice_after(pos, lst, first_lst, last_lst) перемещает в позицию, следующую за позицией pos, элементы списка lst, расположенные в диапазоне (first_lst, last_lst) (элемент first_lst в диапазон не включается). Это отличается от поведения функций-членов splice контейнера list с аналогичным набором параметров (см. п. 1.2.5).

Контейнер forward_list содержит также функции-члены before_begin и cbefore_begin, которые возвращают обычный и константный итератор, указывающий на позицию, предшествующую первому элементу контейнера. Эти итераторы позволяют использовать функции insert_after, emplace_after, splice_after и erase_after для вставки новых данных в начало контейнера forward_list и удаления начальной части его элементов.

Неупорядоченные ассоциативные контейнеры unordered_set, unordered_multiset, unordered_map и unordered_multimap обеспечивают ту же функциональность, что и стандартные упорядоченные ассоциативные контейнеры set, multiset, map и multimap (см. п. 1.2.1, 1.2.2, 1.2.6), однако для поиска по ключу в них используются хеш-функции (hash functions), генерирующие хеш-коды ключей, а также функции, сравнивающие ключи на равенство. Все элементы, ключи которых возвращают одинаковый хеш-код, помещаются в одну ячейку (bucket) неупорядоченного ассоциативного контейнера (число ячеек для контейнера может либо устанавливаться по умолчанию, либо указываться в его шаблоне). При поиске элемента по ключу вначале вычисляется хеш-код ключа, определяющий ячейку, которая может содержать элемент с данным ключом. Если эта ячейка содержит несколько элементов, то элемент с нужным ключом ищется в ней обычным перебором. Высокая скорость в подобном механизме поиска обеспечивается за счет того, что для каждого ключа можно быстро определить его хеш-код, позволяющий сразу обратиться к нужной ячейке, которая, как правило, содержит небольшое число элементов.

Таким образом, поиск по ключу в неупорядоченных ассоциативных контейнерах выполняется с помощью двух видов операций сравнения на равенство, определяемых в шаблоне контейнера: это операция сравнения хеш-кодов, вычисленных хеш-функцией, и операция сравнения на равенство самих ключей (выполняемая при переборе элементов в пределах одной ячейки). Это отличает неупорядоченные контейнеры от упорядоченных, в которых ключи сравниваются тем или иным вариантом операции <.

Неупорядоченные ассоциативные контейнеры содержат практически все средства, имеющиеся у упорядоченных контейнеров (см. п. 1.2.2 и 1.2.6); отсутствуют лишь функции для работы с обратными итераторами, а также функции lower_bound и upper_bound (хотя функция-член equal_range имеется). Кроме того, вместо функций key_comp и value_comp у неупорядоченных контейнеров предусмотрены функции-члены hash_function (возвращает хеш-функцию), и key_eq (возвращает функцию для сравнения ключей на равенство). Разумеется, при переборе элементов неупорядоченных ассоциативных контейнеров не гарантируется, что они будут располагаться по возрастанию ключей.

Неупорядоченные контейнеры включают также следующие функции-члены для работы с ячейками:

• max_bucket_count() возвращает максимальное количество ячеек, которое можно выделить для данного контейнера;

• bucket_count() возвращает количество ячеек, выделенных для данного контейнера;

• bucket(key) возвращает индекс ячейки, содержащей элементы с ключом key;

• bucket_size(n) возвращает размер ячейки с указанным индексом n;

• begin(n), end(n) и cbegin(n), cend(n) возвращают итераторы для перебора всех элементов, входящих в ячейку с индексом n.

Наконец, еще одна группа функций-членов предназначена для оптимизации размещения данных в неупорядоченных контейнерах:

• load_factor() возвращает среднее число элементов к ячейке (число типа float, равное size()/bucket_count());

• max_load_factor позволяет определить (функция без параметров, возвращающая результат типа float) и изменить (void-функция с параметром типа float) максимальное среднее число элементов в ячейке; контейнер автоматически увеличивает количество ячеек, если значение load_factor() превысит указанное максимальное значение;

• rehash(count) позволяет явно изменить количество ячеек; в результате новое значение bucket_count() будет больше или равно count, а также больше size()/max_load_factor();

• reserve(n) настраивает контейнер таким образом, чтобы его размер можно было увеличивать до n элементов без автоматического увеличения количества ячеек.