Язык программирования C Пятое издание
 Скачать 1.85 Mb.
|
|
Упражнение 10.23. Сколько аргументов получает функции bind()? Упражнение 10.24. Используйте функции bind() и check_size() для поиска первого элемента вектора целых чисел, значение которого больше длины заданного строкового значения. Упражнение 10.25. В упражнениях раздела 10.3.2 была написана версия функции biggies(), использующая алгоритм partition(). Перепишите эту функцию так, чтобы использовать функции check_size() и bind(). 10.4. Возвращаясь к итераторам В дополнение к итераторам, определяемым для каждого из контейнеров, библиотека определяет в заголовке iterator несколько дополнительных видов итераторов. • Итератор вставки (insert iterator). Связан с контейнером и применяется для вставки элементов в контейнер. • Потоковый итератор (stream iterator). Может быть связан с потоком ввода или вывода и применяется для перебора связанного потока ввода- вывода. • Реверсивный итератор (reverse iterator). Перемещается назад, а не вперед. У всех библиотечных контейнеров, кроме forward_list, есть реверсивные итераторы. • Итератор перемещения (move iterator). Итератор специального назначения; он перемещает элементы, а не копирует. Эти итераторы рассматриваются в разделе 13.6.2. Page 506/1103 10.4.1. Итераторы вставки Адаптер вставки (inserter), или адаптер inserter, — это адаптер итератора (см. раздел 9.6), получающий контейнер и возвращающий итератор, позволяющий вставлять элементы в указанный контейнер. Присвоение значения при помощи итератора вставки приводит к вызову контейнерной функции, добавляющей элемент в определенную позицию заданного контейнера. Операторы, поддерживающие эти итераторы, приведены в табл. 10.2. Таблица 10.2. Операторы итератора вставки it = t Вставляет значение t в позицию, обозначенную итератором it. В зависимости от вида итератора вставки и с учетом того, что он связан с контейнером с, вызывает функции c.push_back(t), c.push_front(t) и c.insert(t, p), где p — позиция итератора, заданная адаптеру вставки *it, ++it, it++ Эти операторы существуют, но ничего не делают с итератором it. Каждый оператор возвращает итератор it Существуют три вида адаптеров вставки, которые отличаются позицией добавляемых элементов. • Адаптер back_inserter (см. раздел 10.2.2) создает итератор, использующий функцию push_back(). • Адаптер front_inserter создает итератор, использующий функцию push_front(). • Адаптер inserter создает итератор, использующий функцию insert(). Кроме имени контейнера, адаптеру inserter передают второй аргумент: итератор, указывающий позицию, перед которой должна начаться вставка. Адаптер front_inserter можно использовать, только если у контейнера есть функция push_front(). Аналогично адаптер back_inserter можно использовать, только если у контейнера есть функция push_back(). Важно понимать, что при вызове адаптера inserter(с, iter) возвращается итератор, который при использовании вставляет элементы перед элементом, первоначально обозначенным итератором iter. Таким образом, если it — итератор, созданный адаптером inserter, то присвоение *it = val; ведет себя, как следующий код: it = c.insert(it, val); // it указывает на недавно добавленный элемент ++it; // инкремент it, чтобы он указывал на тот же элемент, // что и прежде Итератор, созданный адаптером front_inserter, ведет себя прямо противоположно итератору, созданному адаптером inserter. При использовании адаптера front_inserter элементы всегда вставляются перед текущим первым элементом контейнера. Даже если переданная адаптеру inserter позиция первоначально обозначает первый элемент, то, как только будет вставлен Page 507/1103 элемент перед этим элементом, он больше не будет элементом в начале контейнера: list<int> lst = {1,2,3,4}; list<int> lst2, lst3; // пустой список // после завершения копирования, lst2 содержит 4 3 2 1 copy(lst.cbegin(), lst.cend(), front_inserter(lst2)); // после завершения копирования, lst3 содержит 1 2 3 4 copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin())); Когда происходит вызов front_inserter(c), возвращается итератор вставки, который последовательно вызывает функцию push_front(). По мере вставки каждого элемента он становится новым первым элементом контейнера с. Следовательно, адаптер front_inserter возвращает итератор, который полностью изменяет порядок последовательности, в которую осуществляется вставка; адаптеры inserter и back_inserter так не поступают. Упражнения раздела 10.4.1 Упражнение 10.26. Объясните различия между тремя итераторами вставки. Упражнение 10.27. В дополнение к функции unique() (см. раздел 10.2.3) библиотека определяет функцию unique_copy(), получающую третий итератор, обозначающий назначение копирования уникальных элементов. Напишите программу, которая использует функцию unique_copy() для копирования уникальных элементов вектора в первоначально пустой список. Упражнение 10.28. Скопируйте вектор, содержащий значения от 1 до 9, в три других контейнера. Используйте адаптеры inserter, back_inserter и front_inserter соответственно для добавления элементов в эти контейнеры. Предскажите вид результирующей последовательности в зависимости от вида адаптера вставки и проверьте свои предсказания на написанной программе. 10.4.2. Потоковые итераторы Хотя типы iostream не относятся к контейнерам, есть итераторы, применимые к объектам типов ввода-вывода (см. раздел 8.1). Итератор istream_iterator (табл. 10.3) читает входной поток, а итератор ostream_iterator (табл. 10.4) пишет в поток вывода. Эти итераторы рассматривают свой поток как последовательность элементов определенного типа. Используя потоковый итератор, можно применять обобщенные алгоритмы для чтения или записи данных в объекты потоков. Таблица 10.3. Операторы итератора istream_iterator istream_iterator<T> in(is); in читает значения типа T из входного потока is istream_iterator<T> end; Итератор после конца для Page 508/1103 итератора istream_iterator, читающего значения типа Т in1 == in2 in1 != in2 in1 и in2 должны читать одинаковый тип. Они равны, если оба они конечные или оба связаны с тем же входным потоком *in Возвращает значение, прочитанное из потока in->mem Синоним для (*in).mem ++in, in++ Читает следующее значение из входного потока, используя оператор >> для типа элемента. Как обычно, префиксная версия возвращает ссылку на итератор после инкремента. Постфиксная версия возвращает прежнее значение Использование итератора istream_iterator Когда создается потоковый итератор, необходимо определить тип объектов, которые итератор будет читать или записывать. Итератор istream_iterator использует оператор >> для чтения из потока. Поэтому тип, читаемый итератором istream_iterator, должен определять оператор ввода. При создании итератор istream_iterator следует связать с потоком. В качестве альтернативы итератор можно инициализировать значением по умолчанию. В результате будет создан итератор, который можно использовать как значение после конца. istream_iterator<int> int_it(cin); // читает целые числа из cin istream_iterator<int> int_eof; // конечное значение итератора ifstream in("afile"); istream_iterator<string> str_it(in); // читает строки из "afile" Для примера используем итератор istream_iterator для чтения со стандартного устройства ввода в вектор: istream_iterator<int> in_iter(cin); // читает целые числа из cin istream_iterator<int> eof; // "конечный" итератор istream while (in_iter != eof) // пока есть что читать // постфиксный инкремент читает поток и возвращает прежнее значение // итератора. Обращение к значению этого итератора предоставляет // предыдущее значение, прочитанное из потока vec.push_back(*in_iter++); Page 509/1103 Этот цикл читает целые числа из потока cin, сохраняя прочитанное в вектор vec. На каждой итерации цикл проверяет, не совпадает ли итератор in_iter со значением eof. Этот итератор был определен как пустой итератор istream_iterator, который используется как конечный итератор. Связанный с потоком итератор равен конечному итератору, только если связанный с ним поток достиг конца файла или произошла ошибка ввода-вывода. Самая трудная часть этой программы — аргумент функции push_back(), который использует обращение к значению и постфиксные операторы инкремента. Это выражение работает точно так же, как и другие выражения, совмещающие обращение к значению с постфиксным инкрементом (см. раздел 4.5). Постфиксный инкремент переводит поток на чтение следующего значения, но возвращает прежнее значение итератора. Это прежнее значение содержит прежнее значение, прочитанное из потока. Для того чтобы получить это значение, осуществляется обращение к значению этого итератора. Особенно полезно то, что эту программу можно переписать так: istream_iterator<int> in_iter(cin), eof; // читает целые числа из cin vector<int> vec(in_iter, eof); // создает вектор vec из // диапазона итераторов Здесь вектор vec создается из пары итераторов, которые обозначают диапазон элементов. Это итераторы istream_iterator, следовательно, диапазон получается при чтении связанного потока. Этот конструктор читает поток cin, пока он не встретит конец файла, или ввод, тип которого отличается от int. Прочитанные элементы используются для создания вектора vec. Использование потоковых итераторов с алгоритмами Поскольку алгоритмы используют функции итераторов, а потоковые итераторы поддерживают по крайней мере некоторые функции итератора, потоковые итераторы можно использовать с некоторыми из алгоритмов. Какие именно алгоритмы применимы с потоковыми итераторами, рассматривается в разделе 10.5.1. В качестве примера рассмотрим вызов функции accumulate() с парой итераторов istream_iterators: istream_iterator<int> in (cin), eof; cout << accumulate(in, eof, 0) << endl; Этот вызов создаст сумму значений, прочитанных со стандартного устройства ввода. Если ввод в этой программе будет таким: 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23 то результат будет 664. Итераторы istream_iterator позволяют использовать ленивое вычисление То, что итератор istream_iterator связан с потоком, еще не гарантирует, что он начнет читать поток немедленно. Некоторые реализации разрешают задержать чтение потока, пока итератор не будет использован. Гарантированно, что поток будет прочитан перед первым обращением к значению итератора. Для большинства программ не имеет никакого значения, будет ли чтение немедленным или отсроченным. Но если создается итератор istream_iterator, Page 510/1103 который удаляется без использования, или если необходима синхронизация чтения того же потока из двух разных объектов, то тогда придется позаботиться и о моменте чтения. Использование итератора ostream_iterator Итератор ostream_iterator может быть определен для любого типа, у которого есть оператор вывода (оператор <<). При создании итератора ostream_iterator можно (необязательно) предоставить второй аргумент, определяющий символьную строку, выводимую после каждого элемента. Это должна быть символьная строка в стиле С (т.е. строковый литерал или указатель на массив с нулевым символом в конце). Итератор ostream_iterator следует связать с определенным потоком. Не бывает пустого итератора ostream_iterator или такового после конца. Таблица 10.4. Операторы итератора ostream_iterator ostream iterator<T> out(os); out пишет значения типа T в поток вывода os ostream_iterator<T> out(os, d); out пишет значения типа T, сопровождаемые d в поток вывода os. d указывает на символьный массив с нулевым символом в конце out = val Записывает val в поток вывода, с которым связан out, используя оператор <<. Тип val должен быть совместим с типом, который можно писать в out *out, ++out, out++ Эти операторы существуют, но ничего не делают с out. Каждый оператор возвращает итератор out Итератор ostream_iterator можно использовать для записи последовательности значений: ostream_iterator<int> out_iter(cout, " "); for (auto e : vec) *out_iter++ = e; // это присвоение запишет элемент в cout cout << endl; Эта программа запишет каждый элемент вектора vec в поток cout, сопровождая каждый элемент пробелом. При каждом присвоении значения итератора out_iter происходит запись. Следует заметить, что при присвоении итератору out_iter можно пропустить обращение к значению и инкремент. Таким образом, этот цикл можно переписать так: for (auto е : vec) out_iter = е; // это присвоение запишет элемент в cout cout << endl; Операторы * и ++ ничего не делают с итератором ostream_iterator, поэтому их пропуск никак не влияет на программу. Но предпочтительней писать цикл как в первом варианте. Он использует итератор единообразно с тем, как используются итераторы других типов. Этот цикл можно легко изменить так, чтобы он выполнялся итераторами других типов. Кроме того, поведение этого цикла понятней читателям нашего кода. Чтобы не сочинять цикл самостоятельно, можно легко ввести элементы в вектор vec при помощи алгоритма copy(): Page 511/1103 copy(vec.begin(), vec.end(), out_iter); cout << endl; Использование потоковых итераторов с типами класса Итератор istream_iterator можно создать для любого типа, у которого есть оператор ввода (>>). Точно так же итератор ostream_iterator можно определить для любого типа, обладающего оператором вывода (<<). Поскольку у класса Sales_item есть оба оператора (ввода и вывода), итераторы ввода-вывода вполне можно использовать, чтобы переписать программу книжного магазина из раздела 1.6: istream_iterator<Sales_item> item_iter(cin), eof; ostream_iterator<Sales_item> out_iter(cout, "\n"); // сохранить первую транзакцию в sum и читать следующую запись Sales_item sum = *item_iter++; while (item_iter != eof) { // если текущая транзакция (хранимая в item_iter) имеет тот же ISBN if (item_iter->isbn() == sum.isbn()) sum += *item_iter++; // добавить ее к sum и читать следующую // транзакцию else { out_iter = sum; // вывести текущую сумму sum = *item_iter++; // читать следующую транзакцию } } out_iter = sum; // не забыть вывести последний набор записей Эта программа использует итератор item_iter для чтения транзакций Sales_item из потока cin. Она использует итератор out_iter для записи полученной суммы в поток cout, сопровождая каждый вывод символом новой строки. Определив итераторы, используем итератор item_iter для инициализации переменной sum значением первой транзакции: // Page 512/1103 сохранить первую транзакцию в sum и читать следующую запись Sales_item sum = *item_iter++; Выражение осуществляет обращение к значению результата постфиксного инкремента итератора item_iter. Затем оно читает следующую транзакцию и инициализирует переменную sum значением, предварительно сохраненным в item_iter. Цикл while выполняется до тех пор, пока поток cin не встретит конец файла. В цикле while осуществляется проверка, не относится ли содержимое переменной sum и только что прочитанная запись к той же книге. Если это так, то только что прочитанный объект класса Sales_item добавляется в переменную sum. Если ISBN отличаются, переменная sum присваивается итератору out_iter, который выводит текущее значение переменной sum, сопровождаемое символом новой строки. После вывода суммы для предыдущей книги переменной sum присваивается копия последней прочитанной транзакции и осуществляется инкремент итератора для чтения следующей транзакции. Цикл продолжается до конца файла или ошибки чтения. Перед завершением следует вывести значения по последней книге во вводе. Упражнения раздела 10.4.2 Упражнение 10.29. Напишите программу, использующую потоковые итераторы для чтения текстового файла в вектор строк. Упражнение 10.30. Используйте потоковые итераторы, а также функции sort() и copy() для чтения последовательности целых чисел со стандартного устройства ввода, их сортировки и последующего вывода на стандартное устройство вывода. Упражнение 10.31. Измените программу из предыдущего упражнения так, чтобы она выводила только уникальные элементы. Программа должна использовать алгоритм unique_copy() (см. раздел 10.4.1). Упражнение 10.32. Перепишите программу книжного магазина из раздела 1.6. Используйте вектор для хранения транзакции и различные алгоритмы для обработки. Используйте алгоритм sort() с собственной функцией compareIsbn() из раздела 10.3.1 для упорядочивания транзакций, а затем используйте алгоритмы find() и accumulate() для вычисления суммы. Упражнение 10.33. Напишите программу, получающую имена входного и двух выходных файлов. Входной файл должен содержать целые числа. Используя итератор istream_iterator, прочитайте входной файл. Используя итератор ostream_iterator, запишите нечетные числа в первый выходной файл. За каждым значением должен следовать пробел. Во второй файл запишите четные числа. Каждое из этих значений должно быть помещено в отдельную строку. 10.4.3. Реверсивные итераторы Реверсивный итератор (reverse iterator) перебирает контейнер в обратном направлении, т.е. от последнего элемента к первому. Реверсивный итератор инвертирует смысл инкремента (и декремента): оператор ++it переводит реверсивный итератор на предыдущий элемент, а оператор --it — на следующий. Реверсивные итераторы есть у всех контейнеров, кроме forward_list. Для получения реверсивного итератора используют функции-члены rbegin(), rend(), crbegin() и crend(). Они возвращают реверсивные итераторы на последний элемент в контейнере и на "следующий" Page 513/1103 (т.е. предыдущий) перед началом контейнера. Подобно обычным итераторам, существуют константные и неконстантные реверсивные итераторы. Взаимное положение этих четырех итераторов на гипотетическом векторе vec представлено на рис. 10.1. Рис. 10.1. Взаимное положение итераторов, возвращаемых функциями begin()/cend() и rbegin()/crend() Рассмотрим, например, следующий цикл, выводящий элементы вектора vec в обратном порядке: vector<int> vec = {0,1,2,3,4,5,6,7,8,9}; // реверсивный итератор вектора (от конца к началу) for (auto r_iter = vec.crbegin(); // связывает r_iter с последним // элементом r_iter != vec.crend(); // crend ссылается на 1 элемент // перед 1-м ++r_iter) // декремент итератора на один элемент cout << *r_iter << endl; // выводит 9, 8, 7, ... 0 Хотя смысл оператора декремента реверсивного итератора может показаться неправильным, этот оператор позволяет применять для обработки контейнера стандартные алгоритмы. Например, передав функции sort() два реверсивных итератора, вектор можно отсортировать в порядке убывания. sort(vec.begin(), vec.end()); // сортирует вектор vec // в "нормальном" порядке // обратная сортировка: самый маленький элемент располагается Page 514/1103 // в конце вектора vec sort(vec.rbegin(), vec.rend()); Реверсивным итераторам необходим оператор декремента Нет ничего удивительного в том, что реверсивный итератор можно создать только из такого класса итератора, для которого определены операторы -- и ++. В конце концов, задача реверсивного итератора заключается в переборе последовательности назад. Кроме контейнера forward_list, итераторы всех стандартных контейнеров поддерживают как инкремент, так и декремент. Однако потоковые итераторы к ним не относятся, поскольку невозможно перемещать поток в обратном направлении. Следовательно, создать из потокового итератора реверсивный итератор невозможно. Отношения между реверсивными и другими итераторами Предположим, что существует объект line класса string( строка ), содержащий разделяемый запятыми список слов. Используя функцию find(), можно отобразить, например, первое слово строки line: // найти первый элемент в списке, разделенном запятыми auto comma = find(line.cbegin(), line.cend(), ','); cout << string(line.cbegin(), comma) << endl; Если в строке line есть запятая, итератор comma будет указывать на нее, в противном случае он будет равен итератору, возвращаемому функцией line.cend(). При выводе содержимого строки от позиции line.cbegin() до позиции comma будут отображены символы от начала до запятой или вся строка, если запятых в ней нет. Но если понадобится последнее слово в списке, то вместо обычных можно использовать реверсивные итераторы: // найти последний элемент в списке, разделенном запятыми auto rcomma = find(line.crbegin(), line.crend(), ','); Поскольку функции find() в качестве аргументов передаются результаты выполнения функций crbegin() и crend(), поиск начинается с последнего символа в строке line в обратном порядке. По завершении поиска, если запятая найдена, итератор rcomma будет указывать на последнюю запятую в строке, т.е. первую запятую с конца. Если запятой нет, итератор rcomma будет равен итератору, возвращаемому функцией line.crend(). Весьма интересна та часть, в которой осуществляется вывод найденного слова. Попытка прямого вывода создает несколько странный результат: // ошибка: создаст слово в обратном порядке cout << string(line.crbegin(), rcomma) << endl; Например, если введена строка "FIRST,MIDDLE,LAST", будет получен результат "TSAL"! Page 515/1103 Эта проблема проиллюстрирована на рис. 10.2. Здесь реверсивные итераторы используются для перебора строки в обратном порядке. Поэтому оператор вывода выводит строку line назад, начиная от crbegin(). Вместо этого следует выводить строку от rcomma и до конца. Но итератор rcomma нельзя использовать непосредственно, так как это реверсивный итератор, обеспечивающий перебор от конца к началу. Поэтому необходимо преобразовать его назад в обычный итератор, перебирающий строку вперед. Для преобразования итератора rcomma можно применить функцию-член base(), которой обладает каждый реверсивный итератор. // ok: получить прямой итератор и читать до конца строки cout << string(rcomma.base(), line.cend()) << endl; С учетом того, что введены те же данные, в результате отобразится слово "LAST", как и ожидалось. Рис. 20.2. Отношения между реверсивными и обычными итераторами Объекты, представленные на рис. 10.2, наглядно иллюстрируют взаимоотношения между обычными и реверсивными итераторами. Например, итераторы rcomma и возвращаемый функцией rcomma.base() указывают на разные элементы, так же как и возвращаемые функциями line.crbegin() и line.cend(). Эти различия вполне обоснованны: они позволяют гарантировать возможность одинаковой обработки диапазона элементов при перемещении как вперед, так и назад. С технической точки зрения отношения между обычными и реверсивными итераторами приспособлены к свойствам диапазона, включающего левый элемент (см. раздел 9.2.1). Дело в том, что [line.crbegin(), rcomma) и [rcomma.base(), line.cend()) ссылаются на тот же элемент в строке line. Для этого rcomma и rcomma.base() должны возвращать соседние позиции, а не ту же позицию, как функции crbegin() и cend(). Тот факт, что реверсивные итераторы предназначены для представления диапазонов и что эти диапазоны являются асимметричными, имеет важное последствие: при инициализации или присвоении реверсивному итератору простого итератора полученный в результате итератор не будет указывать на тот же элемент, что и исходный. Упражнения раздела 10.4.3 Упражнение 10.34. Используйте итератор reverse_iterator для вывода содержимого вектора в обратном порядке. Упражнение 10.35. Теперь отобразите элементы в обратном порядке, используя обычные итераторы. Упражнение 10.36. Используйте функцию find() для поиска в списке целых чисел последнего элемента со значением 0. Упражнение 10.37. С учетом того, что вектор содержит 10 элементов, скопируйте в список диапазон его элементов от позиции 3 до позиции 7 в обратном порядке. 10.5. Структура обобщенных алгоритмов Фундаментальное свойство любого алгоритма — это список функциональных возможностей, которые он требует от своего итератора (итераторов). Некоторые алгоритмы, например find(), Page 516/1103 требуют только возможности получить доступ к элементу через итератор, прирастить итератор и сравнить два итератора на равенство. Другие, такие как sort(), требуют возможности читать, писать и произвольно обращаться к элементам. По своим функциональным возможностям, обязательным для алгоритмов, итераторы группируются в пять категорий (iterator categories), перечисленных в табл. 10.5. Каждый алгоритм определяет, итератор какого вида следует предоставить для каждого из его параметров. Таблица 10.5. Категории итераторов Итератор ввода Обеспечивает чтение, но не запись; поддерживает только инкремент Итератор вывода Обеспечивает запись, но не чтение; поддерживает только инкремент Прямой итератор Обеспечивает чтение и запись; поддерживает только инкремент Двунаправленный итератор Обеспечивает чтение и запись; поддерживает инкремент и декремент Итератор произвольного доступа Обеспечивает чтение и запись; поддерживает все арифметические операции итераторов Второй способ классификации алгоритмов (приведенный в начале этой главы) основан на том, читают ли они элементы, пишут или переупорядочивают их в последовательности. В приложении А все алгоритмы перечислены согласно этой классификации. Алгоритмы имеют также ряд общих соглашений по передаче параметров и соглашений об именовании, рассматриваемых после категорий итераторов. 10.5.1. Пять категорий итераторов Подобно контейнерам, для итераторов определен общий набор операций. Некоторые из них поддерживаются всеми итераторами, а другие — лишь некоторыми видами итераторов. Например, итератор ostream_iterator поддерживает только инкремент, обращение к значению и присвоение. Итераторы векторов, строк и двухсторонних очередей поддерживают эти операции, а также декремент, сравнение и арифметические операторы. Таким образом, итераторы можно классифицировать на основании набора функций, которыми они обладают, а категории формируют своего рода иерархию. За исключением итераторов вывода, итераторы более высокой категории поддерживают все функции итераторов более низких категорий. Стандарт определяет минимальную категорию для каждого параметра итератора обобщенных и числовых алгоритмов. Например, алгоритм find(), реализующий перебор последовательности только для чтения и в одном направлении, минимально требует только итератор ввода. Алгоритму replace() требуется два итератора, являющихся, по крайней мере, прямыми итераторами. Аналогично алгоритм replace_copy() требует прямые итераторы для своих первых двух итераторов. Его третий итератор, представляющий назначение, должен, по крайней мере, быть итератором вывода и т.д. Итератор для каждого параметра должен обладать не меньшим набором параметров, чем предусмотренный минимум. Передача итератора с меньшими возможностями недопустима. Большинство компиляторов не заметит ошибки передачи алгоритму итератора неправильный категории. Категории итераторов Итератор ввода (input iterator) позволяет читать элементы контейнера, но записи не Page 517/1103 гарантирует. Итератор ввода обязательно должен поддерживать следующий минимум функций. • Операторы равенства и неравенства (==, !=), используемые для сравнения двух итераторов. • Префиксный и постфиксный инкременты (++), используемые для перемещения итератора. • Оператор обращения к значению (*), позволяющий прочитать элемент. Оператор обращения к значению может быть применен только к операнду, расположенному справа от оператора присвоения. • Оператор стрелки (->), равнозначный выражению (*it).member. То есть обращение к значению итератора и доступ к члену класса объекта. Итераторы ввода могут быть использованы только последовательно. Гарантирована допустимость инкремента *it++, но приращение итератора ввода может сделать недопустимыми все другие итераторы в потоке. В результате нет никакой гарантии того, что можно сохранить состояние итератора ввода и исследовать элемент с его помощью. Поэтому итераторы ввода можно использовать только для однопроходных алгоритмов. Алгоритмам find() и accumulate() требуются итераторы ввода, а итератор istream_iterator — имеет тип итератора ввода. Итератор вывода (output iterator) можно рассматривать как итератор ввода, обладающий дополнительными функциональными возможностями. Итератор вывода применяется для записи в элемент, но чтения он не гарантирует. Для итераторов вывода обязательны следующие функции. • Префиксный и постфиксный инкременты (++), используемые для перемещения итератора. • Оператор обращения к значению (*) может быть применен только к операнду, расположенному слева от оператора присвоения. Присвоение при обращении к значению итератора вывода позволяет осуществить запись в элемент. Значение итератору вывода можно присвоить только однажды. Подобно итераторам ввода, итераторы вывода можно использовать только для однопроходных алгоритмов. Итераторы, используемые как итераторы назначения, обычно являются итераторами вывода. Например, третий параметр алгоритма copy() является итератором вывода. Итератор ostream_iterator имеет тип итератора вывода. • Прямой итератор (forward iterator) позволяет читать и записывать данные в последовательность. Они перемещаются по последовательности только в одном направлении. Прямые итераторы поддерживают все операции итераторов ввода и вывода. Кроме того, они позволяют читать и записывать значение в тот же элемент несколько раз. Поэтому сохраненное состояние прямого итератора можно использовать. Следовательно, алгоритмы, использующие прямые итераторы, могут осуществить несколько проходов через последовательность. Алгоритму replace() требуется прямой итератор; итераторы контейнера forward_list являются прямыми итераторами. • Двунаправленный итератор (bidirectional iterator) позволяет читать и записывать данные в последовательность в обоих направлениях. Кроме всех функциональных возможностей прямого итератора, двунаправленный итератор поддерживает также префиксный и Page 518/1103 постфиксный декременты (--). Алгоритму reverse() требуется двунаправленный итератор. Все библиотечные контейнеры, кроме forward_list, предоставляют итераторы, соответствующие требованиям для двунаправленного итератора. • Итератор прямого доступа (random-access iterator) обеспечивает доступ к любой позиции последовательности в любой момент. Эти итераторы обладают всеми функциональными возможностями двунаправленных итераторов. Кроме того, они поддерживают операции, приведенные в табл. 3.7. • Операторы сравнения <, <=, > и >=, позволяющие сравнить относительные позиции двух итераторов. • Операторы сложения и вычитания (+, +=, - и -=), обеспечивающие арифметические действия между итератором и целочисленным значением. В результате получается итератор, перемещенный в контейнере вперед (или назад) на соответствующее количество элементов. • Оператор вычитания (-), применяемый к двум итераторам, позволяет получить дистанцию между двумя итераторами. • Оператор индексирования (iter[n]), равнозначный выражению *(iter + n). Итератор прямого доступа необходим алгоритму sort(). Итераторы контейнеров array, deque, string и vector являются итераторами прямого доступа, подобно указателям массива. Упражнения раздела 10.5.1 Упражнение 10.38. Перечислите пять категорий итераторов и операции, которые каждый из них поддерживает. |