C++. Сборник рецептов - Д. Стефенс

Random-access iterator (Итератор произвольного доступа)

Итератор произвольного доступа делает все, что делает двунаправленный iterator, но также поддерживает операции, аналогичные операциям с указателями.. Для доступа к элементу, расположенному в позиции n после p последовательности, можно использовать p[n], можно складывать его значение или вычитать из него с помощью +, +=, - или -=, перемещая его вперед или назад на заданное количество элементов. Также с помощью <, >, <= или >= можно сравнивать два итератора p1 и p2, определяя их относительный порядок (при условии, что они оба относятся к одной и той же последовательности).

Или можно представить все в виде диаграммы Венна. Она представлена на рис. 7.1.

Рис. 7.1. Категории итераторов

Большая часть стандартных контейнеров поддерживает как минимум двунаправленный iterator, некоторые (vector и deque) предоставляют iterator произвольного доступа. Категория итератора, поддерживаемая контейнером, определяется стандартом.

В большинстве случае вы будете использовать iterator для простейших задач: поиск элемента и его удаление или что-либо подобное. Для этой цели требуется только однонаправленный iterator, который доступен для всех контейнеров. Но когда потребуется написать нетривиальный алгоритм или использовать алгоритм из стандартной библиотеки, часто потребуется нечто большее, чем простой однонаправленный iterator. Но как определить, что вам требуется? Здесь на сцену выходят категории итераторов.

Различные категории итераторов позволяют стандартным (и нестандартным) алгоритмам указать диапазон требуемой функциональности. Обычно стандартные алгоритмы работают с диапазонами, указываемыми с помощью итераторов, а не с целыми контейнерами. Объявление стандартного алгоритма говорит, какую категорию iterator он ожидает». Например, std::sort требует итераторов произвольного доступа, так как ему требуется за постоянное время ссылаться на несмежные элементы. Таким образом, объявление sort выглядит вот так.

template<typename RandomAccessIterator>

void sort(RandomAccessIterator first, RandomAccessIterator last);

По имени типа итератора можно определить, что он ожидает итератор произвольного доступа. Если попробовать откомпилировать sort для категории итератора, отличной от произвольного доступа, то она завершится ошибкой, так как младшие категории iterator не реализуют операций, аналогичных арифметике с указателями.

Категория итератора, предоставляемая определенным контейнером и требуемая определенным стандартным алгоритмом, — это то, что определяет, какой алгоритм с каким контейнером может работать. Многие из стандартных алгоритмов описаны далее в этой главе. Таблица 7.1 показывает сокращения, используемые в остальной части главы для указания типов итераторов, принимаемых алгоритмами в качестве аргументов.

Этот рецепт описывал итераторы, как они используются для контейнеров. Но шаблон итераторов используется не только для контейнеров, и, таким образом, имеются другие типы итераторов. Имеются потоковые итераторы, итераторы буферов потоков и итераторы хранения в необработанном виде, но они здесь не описываются.

Глава 6.

7.2. Удаление объектов из контейнера

Требуется удалить объекты из контейнера.

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

Пример 7.2. Удаление элементов из контейнера

#include <iostream>

#include <string>

#include <list>

#include <algorithm>

#include <functional>

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 list<string> lstStr;

 lstStr.push_back("On");

 lstStr.push_back("a");

 lstStr.push_back("cloudy");

 lstStr.push_back("cloudy");

 lstStr.push_back("day");

 list<string>::iterator p;

 // Найти то что требуется, с помощью find

 p = find(lstStr.begin(), lstStr.end(), "day");

 p = lstStr.erase(p); // Теперь p указывает на последний элемент

 // Или для удаления всех вхождений чего-либо используйте remove

 lstStr.erase(remove(lstStr.begin(), lstStr.end(), "cloudy"),

  listStr.end());

 printContainer(lstStr); // См. 7.10

}

Для удаления одного или нескольких элементов из контейнера используйте метод erase. Все контейнеры содержат два перегруженных erase: один принимает единственный аргумент iterator, который указывает на элемент, который требуется удалить, а другой принимает два аргумента, которые представляют диапазон удаляемых элементов. Чтобы удалить один элемент, получите iterator, указывающий на этот элемент, и передайте этот iterator в erase, как в примере 7.2.

p = find(lstStr.begin(), lstStr.end(), "day");

p = lstStr.erase(p);

В результате объект, на который указывает p, будет удален, для чего будет вызван его деструктор, а после этого оставшиеся элементы будут реорганизованы. Реорганизация зависит от типа контейнера, и, следовательно, сложность этой операции от контейнера к контейнеру будет различаться. Сигнатура и поведение при использовании последовательного контейнера и ассоциативного контейнера также будут различаться.

В последовательностях erase возвращает iterator, который ссылается на первый элемент, следующий непосредственно за последним удаленным элементом, что может оказаться end, если был удален последний элемент последовательности. Сложность этой операции для каждого контейнера различна, так как последовательности реализованы по- разному. Например, из-за того, что все элементы vector хранятся в непрерывном фрагменте памяти, удаление из него элемента, кроме первого и последнего, с целью заполнения образовавшегося промежутка требует сдвига всех последующих элементов в сторону начала. Это приводит к значительному снижению производительности (в линейном отношении), и именно по этой причине не следует использовать vector, если требуется удалять (или вставлять, что в данном случае приводит к таким же последствиям) элементы где-либо, кроме концов. Более подробно этот вопрос обсуждается в рецепте 6.2.

В ассоциативных контейнерах erase возвращает void. При удалении одного элемента сложность имеет вид амортизированной константы, а при удалении диапазона — логарифмической зависимости плюс количество удаляемых элементов. Причина этого заключается в том, что ассоциативные контейнеры часто реализуются как сбалансированные деревья (например, красно-черное дерево).

erase удобен, но не интересен. Если требуется большая гибкость в выражении того, что требуется удалить, следует обратить внимание на стандартные алгоритмы (из <algorithm>). Рассмотрим такую строку из примера 7.2.

lstStr.erase(std::remove(lstStr.begin(), lstStr.end(), "cloudy"),

 lstStr.end());

Обратите внимание, что я использую erase, но на этот раз по какой-то причине мне требуется удалить из list<string> все вхождения слова «cloudy», remove возвращает iterator, который передается в erase как начало удаляемого диапазона, a end передается в erase как конечная точка диапазона. В результате удаляются все объекты obj (вызывая их метод delete) из диапазона, для которого obj == "cloudy" равно истине. Но поведение этой строки может оказаться не совсем таким, как ожидается. Здесь мне требуется пояснить некоторую терминологию.

remove на самом деле ничего не удаляет. Он перемещает все, что не равно указанному значению, в начало последовательности и возвращает iterator, который ссылается на первый элемент, следующий за этими перемещенными элементами. Затем вы должны вызвать erase для контейнера, чтобы удалить объекты между [p, end), где p — это iterator, возвращенный remove.

remove также имеет несколько вариантов. Что, если требуется удалить элементы, которые удовлетворяют некоторому предикату, а не просто равны какому-то значению? Используйте remove_if. Например, представьте, что есть класс с именем Conn, который представляет какой-то тип соединений. Если это соединение простаивает больше определенного значения, его требуется удалить. Во-первых, создайте функтор, как здесь.

struct IdleConnFn :

 public std::unary_function<const Conn, bool> { // Включите эту строку,

 bool operator() (const Conn& c) const {        // чтобы он работал с