Страница 8 из 13
Перечислим функции-члены, которые имеются у обеих реализаций списков – как 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 элементов без автоматического увеличения количества ячеек.
1.2.9. Дополнение: обратные итераторы
Получить обратный итератор r можно из обычного (прямого) итератора p явным приведением типа, например:
Имеется функция-член rbegin(), которая возвращает приведенный к типу обратного итератора итератор end(), и функция-член rend(), возвращающая приведенный к типу обратного итератора итератор begin().
Операции инкремента и декремента прямого и обратного оператора взаимно обратны: r++ перемещает итератор в том же направлении, что и p–, а r– – в том же направлении, что и p++.
Для операции разыменования * выполняется следующее базовое соотношение: если r может быть получен из p, то *r равно *(p – 1).
Функция-член base() обратного итератора возвращает прямой итератор, который можно было бы использовать для получения данного обратного итератора явным приведением типа: если r может быть получен из p, то r.base() == p. Или, иначе говоря, ((reverse_iterator)p).base == p.