С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 99
Текст из файла (страница 99)
Пять категорий итераторовДля поддержки полного набора обобщенных алгоритмов стандартная библиотекаопределяет пять категорий итераторов, положив в основу классификации множествоопераций. Это итераторы чтения (InputIterator), записи (OutputIterator),однонаправленные(ForwardIterator)идвунаправленныеитераторы(BidirectionalIterator),а также итераторы с произвольным доступом(RandomAccessIterators). Ниже приводится краткое обсуждение характеристик каждойкатегории:•итератор чтения можно использовать для получения элементов из контейнера, ноподдержка записи в контейнер не гарантируется. Такой итератор долженобеспечиватьследующие операции (итераторы,поддерживающие такжедополнительные операции, можно употреблять в качестве итераторов чтения приусловии, что они удовлетворяют минимальным требованиям): сравнение двухитераторов на равенство и неравенство, префиксная и постфиксная формаинкремента итератора для адресации следующего элемента (оператор ++), чтениеэлемента с помощью оператора разыменования (*).
Такого уровня поддержкитребуют, в частности, алгоритмы find(), accumulate() и equal(). Любомуалгоритму, которому необходим итератор чтения, можно передавать также иитераторы категорий, описанных в пунктах 3, 4 и 5;•итератор записи можно представлять себе как противоположный пофункциональности итератору чтения. Иными словами, его можно использовать длязаписи элементов контейнера, но поддержка чтения из контейнера не гарантируется.Такие итераторы обычно применяются в качестве третьего аргумента алгоритма(например, copy()) и указывают на позицию, с которой надо начинать копировать.572С++ для начинающихЛюбому алгоритму, которому необходим итератор записи, можно передавать также иитераторы других категорий, перечисленных в пунктах 3, 4 и 5;•однонаправленный итератор можно использовать для чтения и записи в контейнер,но только в одном направлении обхода (обход в обоих направлениях поддерживаетсяитераторами следующей категории).
К числу обобщенных алгоритмов, требующихкак минимум однонаправленного итератора, относятся adjacent_find(),swap_range() и replace(). Конечно, любому алгоритму, которому необходимподобный итератор, можно передавать также и итераторы описанных нижекатегорий;•двунаправленный итератор может читать и записывать в контейнер, а такжеперемещаться по нему в обоих направлениях. Среди обобщенных алгоритмов,требующих как минимум двунаправленного итератора, выделяются place_merge(),next_permutation() и reverse();•итератор с произвольным доступом,помимо всей функциональности,поддерживаемой двунаправленным итератором, обеспечивает доступ к любойпозиции внутри контейнера за постоянное время.
Подобные итераторы требуютсятаким обобщенным алгоритмам, как binary_search(), sort_heap() и nthelement().Упражнение 12.6Объясните, почему некорректны следующие примеры. Какие ошибки обнаруживаются во(a) const vector<string> file_names( sa, sa+6 );vector<string>::iterator it = file_names.begin()+2;(b) const vector<int> ivec;fill( ivec.begin(), ivec.end(), ival );(c) sort( ivec.begin(), ivec.end() );(d) list<int> ilist( ia, ia+6 );binary_search( ilist.begin(), ilist.end() );время компиляции?(e) sort( ivec1.begin(), ivec3.end() );Упражнение 12.7Напишите программу, которая читает последовательность целых чисел из стандартноговвода с помощью потокового итератора чтения istream_iterator.
Нечетные числапоместите в один файл посредством ostream_iterator, разделяя значения пробелом.Четные числа таким же образом запишите в другой файл, при этом каждое значениедолжно размещаться в отдельной строке.12.5. Обобщенные алгоритмыПервые два аргумента любого обобщенного алгоритма (разумеется, есть исключения,которые только подтверждают правило) – это пара итераторов, обычно называемыхfirst и last, ограничивающих диапазон элементов внутри контейнера или встроенногомассива, к которым применяется этот алгоритм.
Как правило, диапазон элементов573С++ для начинающих(иногда его называют интервалом с включенной левой границей) обозначается// читается так: включает первый и все последующие элементы,// кроме последнегоследующим образом:[ first, last )Эта запись говорит о том, что диапазон начинается с элемента first и продолжается доэлемента last, исключая последний. Еслиfirst == lastто говорят, что диапазон пуст.К паре итераторов предъявляется следующее требование: если начать с элемента first ипоследовательно применять оператор инкремента, то возможно достичь элемента last.Однако компилятор не в состоянии проверить выполнение этого ограничения; если ононарушается, поведение программы не определено, обычно все заканчивается аварийнымостановом и дампом памяти.В объявлении каждого алгоритма указывается минимально необходимая категорияитератора (см.
раздел 12.4). Например, для алгоритма find(), реализующегооднопроходный обход контейнера с доступом только для чтения, требуется итераторчтения, но можно передать и однонаправленный или двунаправленный итератор, а такжеитератор с произвольным доступом.
Однако передача итератора записи приведет кошибке. Не гарантируется, что ошибки, связанные с передачей итератора не тойкатегории, будут обнаружены во время компиляции, поскольку категории итераторов –это не собственно типы, а лишь параметры-типы, передаваемые шаблону функции.Некоторые алгоритмы существуют в нескольких версиях: в одной используетсявстроенный оператор, а во второй – объект-функция или указатель на функцию, котораяпредоставляет альтернативную реализацию оператора. Например, unique() поумолчанию сравнивает два соседних элемента с помощью оператора равенства,определенного для типа объектов в контейнере.
Но если такой оператор равенства неопределен или мы хотим сравнивать элементы иным способом, то можно передать либообъект-функцию, либо указатель на функцию, обеспечивающую нужную семантику.Встречаются также алгоритмы с похожими, но разными именами. Так, предикатныеверсии всегда имеют имя, оканчивающееся на _if, например find_if(). Скажем, естьалгоритм replace(), реализованный с помощью встроенного оператора равенства, иreplace_if(), которому передается объект-предикат или указатель на функцию.Алгоритмы, модифицирующие контейнер, к которому они применяются, обычно имеютдве версии: одна преобразует содержимое контейнера по месту, а вторая возвращаеткопию исходного контейнера, в которой и отражены все изменения.
Например, естьалгоритмы replace() и replace_copy() (имя версии с копированием всегдазаканчивается на _copy). Однако не у всех алгоритмов, модифицирующих контейнер,имеется такая версия. К примеру, ее нет у алгоритма sort(). Если же мы хотим, чтобысортировалась копия, то создать и передать ее придется самостоятельно.Для использования любого обобщенного алгоритма необходимо включить в программузаголовочный файл#include <algorithm>574С++ для начинающихА для любого из четырех численных алгоритмов – adjacent_differences(),accumulate(), inner_product() и partial_sum() – включить также заголовок#include <numeric>Все существующие алгоритмы для удобства изложения распределены нами на девятькатегорий (они перечислены ниже).
В Приложении алгоритмы рассматриваются валфавитном порядке, и для каждого приводится пример применения.12.5.1. Алгоритмы поискаТринадцать алгоритмов поиска предоставляют различные способы нахожденияопределенного значения в контейнере. Три алгоритма equal_range(), lower_bound() иupper_bound() выполняют ту или иную форму двоичного поиска. Они показывают, вadjacent_find(), binary_search(), count(),count_if(), equal_range(),find(), find_end(), find_first_of(), find_if(), lower_bound(),какое место контейнера можно вставить новое значение, не нарушая порядка сортировки.upper_bound(), search(), search_n()12.5.2. Алгоритмы сортировки и упорядоченияЧетырнадцать алгоритмов сортировки и упорядочения предлагают различные способыупорядочения элементов контейнера.
Разбиение (partition) – это разделение элементовконтейнера на две группы: удовлетворяющие и не удовлетворяющие некоторомуусловию. Так, можно разбить контейнер по признаку четности/нечетности чисел или взависимости от того, начинается слово с заглавной или со строчной буквы.
Устойчивый(stable) алгоритм сохраняет относительный порядок элементов с одинаковымизначениями или удовлетворяющих одному и тому же условию. Например, если данапоследовательность:{ "pshew", "honey", "Tigger", "Pooh" }то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале словагенерирует последовательность, в которой относительный порядок слов в каждойкатегории сохранен:{ "Tigger", "Pooh", "pshew", "honey" }При использовании неустойчивой версии алгоритма сохранение порядка негарантируется. (Отметим, что алгоритмы сортировки нельзя применять к списку иinplace_merge(), merge(), nth_element(), partial_sort(),partial_sort_copy(), partition(), random_shuffle(), reverse(),reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),ассоциативным контейнерам, таким, как множество (set) или отображение (map).)stable_partition()575С++ для начинающих12.5.3.
Алгоритмы удаления и подстановкиПятнадцать алгоритмов удаления и подстановки предоставляют различные способызамены или исключения одного элемента или целого диапазона. unique() удаляетодинаковые соседние элементы. iter_swap() обменивает значения элементов,copy(), copy_backwards(), iter_swap(), remove(), remove_copy(),remove_if(),remove_if_copy(), replace(), replace_copy(),replace_if(), replace_copy_if(), swap(), swap_range(), unique(),адресованных парой итераторов, но не модифицирует сами итераторы.unique_copy()12.5.4. Алгоритмы перестановкиРассмотрим последовательность из трех символов: {a,b,c}. Для нее существует шестьразличных перестановок: abc, acb, bac, bca, cab и cba, лексикографическиупорядоченных на основе оператора “меньше”. Таким образом, abc – это перваяперестановка, потому что каждый элемент меньше последующего.
Следующаяперестановка – acb, поскольку в начале все еще находится a – наименьший элементпоследовательности. Соответственно перестановки, начинающиеся с b, предшествуюттем, которые начинаются с с. Из bac и bca меньшей является bac, так какпоследовательность ac лексикографически меньше, чем ca. Если дана перестановка bca,то можно сказать, что предшествующей для нее будет bac, а последующей – cab. Дляперестановки abc нет предшествующей, а для cba – последующей.next_permutation(), prev_permutation()12.5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
