Язык программирования C++. Вводный курс. С для начинающих

• Название: С для начинающих
• Дата: 24.08.2022
• Размер: 5.41 Mb.
• Имя файла: Язык программирования C++. Вводный курс.pdf
• Тип: Документы; #652350
• страница: 55 из 93

573
Любому алгоритму, которому необходим итератор записи, можно передавать также и итераторы других категорий, перечисленных в пунктах 3, 4 и 5;
•
однонаправленный итератор можно использовать для чтения и записи в контейнер, но только в одном направлении обхода (обход в обоих направлениях поддерживается итераторами следующей категории). К числу обобщенных алгоритмов, требующих как минимум однонаправленного итератора, относятся adjacent_find(), swap_range()
и replace(). Конечно, любому алгоритму, которому необходим подобный итератор, можно передавать также и итераторы описанных ниже категорий;
•
двунаправленный итератор может читать и записывать в контейнер, а также перемещаться по нему в обоих направлениях. Среди обобщенных алгоритмов, требующих как минимум двунаправленного итератора, выделяются place_merge(), next_permutation()
и reverse();
•
итератор с произвольным доступом, помимо всей функциональности, поддерживаемой двунаправленным итератором, обеспечивает доступ к любой позиции внутри контейнера за постоянное время. Подобные итераторы требуются таким обобщенным алгоритмам, как binary_search(), sort_heap() и nth- element()
Упражнение 12.6
Объясните, почему некорректны следующие примеры. Какие ошибки обнаруживаются во время компиляции?
(e) sort( ivec1.begin(), ivec3.end() );
Упражнение 12.7
Напишите программу, которая читает последовательность целых чисел из стандартного ввода с помощью потокового итератора чтения istream_iterator. Нечетные числа поместите в один файл посредством ostream_iterator, разделяя значения пробелом.
Четные числа таким же образом запишите в другой файл, при этом каждое значение должно размещаться в отдельной строке.
12.5.
Обобщенные алгоритмы
Первые два аргумента любого обобщенного алгоритма (разумеется, есть исключения, которые только подтверждают правило) – это пара итераторов, обычно называемых first и last, ограничивающих диапазон элементов внутри контейнера или встроенного массива, к которым применяется этот алгоритм. Как правило, диапазон элементов
(a) const vector file_names( sa, sa+6 ); vector::iterator it = file_names.begin()+2;
(b) const vector ivec; fill( ivec.begin(), ivec.end(), ival );
(c) sort( ivec.begin(), ivec.end() );
(d) list ilist( ia, ia+6 ); binary_search( ilist.begin(), ilist.end() );

С++ для начинающих
574
(иногда его называют интервалом с включенной левой границей) обозначается следующим образом:
[ first, last )
Эта запись говорит о том, что диапазон начинается с элемента first и продолжается до элемента last, исключая последний. Если first == last то говорят, что диапазон пуст.
К паре итераторов предъявляется следующее требование: если начать с элемента first и последовательно применять оператор инкремента, то возможно достичь элемента last.
Однако компилятор не в состоянии проверить выполнение этого ограничения; если оно нарушается, поведение программы не определено, обычно все заканчивается аварийным остановом и дампом памяти.
В объявлении каждого алгоритма указывается минимально необходимая категория итератора (см. раздел 12.4). Например, для алгоритма find(), реализующего однопроходный обход контейнера с доступом только для чтения, требуется итератор чтения, но можно передать и однонаправленный или двунаправленный итератор, а также итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что ошибки, связанные с передачей итератора не той категории, будут обнаружены во время компиляции, поскольку категории итераторов – это не собственно типы, а лишь параметры-типы, передаваемые шаблону функции.
Некоторые алгоритмы существуют в нескольких версиях: в одной используется встроенный оператор, а во второй – объект-функция или указатель на функцию, которая предоставляет альтернативную реализацию оператора. Например, unique() по умолчанию сравнивает два соседних элемента с помощью оператора равенства, определенного для типа объектов в контейнере. Но если такой оператор равенства не определен или мы хотим сравнивать элементы иным способом, то можно передать либо объект-функцию, либо указатель на функцию, обеспечивающую нужную семантику.
Встречаются также алгоритмы с похожими, но разными именами. Так, предикатные версии всегда имеют имя, оканчивающееся на _if, например find_if(). Скажем, есть алгоритм replace(), реализованный с помощью встроенного оператора равенства, и replace_if()
, которому передается объект-предикат или указатель на функцию.
Алгоритмы, модифицирующие контейнер, к которому они применяются, обычно имеют две версии: одна преобразует содержимое контейнера по месту, а вторая возвращает копию исходного контейнера, в которой и отражены все изменения. Например, есть алгоритмы replace() и replace_copy() (имя версии с копированием всегда заканчивается на _copy). Однако не у всех алгоритмов, модифицирующих контейнер, имеется такая версия. К примеру, ее нет у алгоритма sort(). Если же мы хотим, чтобы сортировалась копия, то создать и передать ее придется самостоятельно.
Для использования любого обобщенного алгоритма необходимо включить в программу заголовочный файл
#include
// читается так: включает первый и все последующие элементы,
// кроме последнего

С++ для начинающих
575
А для любого из четырех численных алгоритмов – adjacent_differences(), accumulate()
, inner_product() и partial_sum() – включить также заголовок
#include
Все существующие алгоритмы для удобства изложения распределены нами на девять категорий (они перечислены ниже). В Приложении алгоритмы рассматриваются в алфавитном порядке, и для каждого приводится пример применения.
12.5.1.
Алгоритмы поиска
Тринадцать алгоритмов поиска предоставляют различные способы нахождения определенного значения в контейнере. Три алгоритма equal_range(), lower_bound() и upper_bound()
выполняют ту или иную форму двоичного поиска. Они показывают, в какое место контейнера можно вставить новое значение, не нарушая порядка сортировки. upper_bound(), search(), search_n()
12.5.2.
Алгоритмы сортировки и упорядочения
Четырнадцать алгоритмов сортировки и упорядочения предлагают различные способы упорядочения элементов контейнера. Разбиение (partition) – это разделение элементов контейнера на две группы: удовлетворяющие и не удовлетворяющие некоторому условию. Так, можно разбить контейнер по признаку четности/нечетности чисел или в зависимости от того, начинается слово с заглавной или со строчной буквы. Устойчивый
(stable) алгоритм сохраняет относительный порядок элементов с одинаковыми значениями или удовлетворяющих одному и тому же условию. Например, если дана последовательность:
{ "pshew", "honey", "Tigger", "Pooh" } то устойчивое разбиение по наличию/отсутствию заглавной буквы в начале слова генерирует последовательность, в которой относительный порядок слов в каждой категории сохранен:
{ "Tigger", "Pooh", "pshew", "honey" }
При использовании неустойчивой версии алгоритма сохранение порядка не гарантируется. (Отметим, что алгоритмы сортировки нельзя применять к списку и ассоциативным контейнерам, таким, как множество (set) или отображение (map).) stable_partition() adjacent_find(), binary_search(), count(),count_if(), equal_range(), find(), find_end(), find_first_of(), find_if(), lower_bound(), inplace_merge(), merge(), nth_element(), partial_sort(), partial_sort_copy(), partition(), random_shuffle(), reverse(), reverse_copy(), rotate(), rotate_copy(), sort(), stable_sort(),

С++ для начинающих
576
12.5.3.
Алгоритмы удаления и подстановки
Пятнадцать алгоритмов удаления и подстановки предоставляют различные способы замены или исключения одного элемента или целого диапазона. unique() удаляет одинаковые соседние элементы. iter_swap() обменивает значения элементов, адресованных парой итераторов, но не модифицирует сами итераторы. 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.
Численные алгоритмы
Следующие четыре алгоритма реализуют численные операции с контейнером. Для их использования необходимо включить заголовочный файл . accumulate(), partial_sum(), inner_product(), adjacent_difference()
12.5.6.
Алгоритмы генерирования и модификации
Шесть алгоритмов генерирования и модификации либо создают и заполняют новую последовательность, либо изменяют значения в существующей. fill(), fill_n(), for_each(), generate(),generate_n(), transform()
12.5.7.
Алгоритмы сравнения
Семь алгоритмов дают разные способы сравнения одного контейнера с другим
(алгоритмы min()
и max() сравнивают два элемента).
Алгоритм 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(),

С++ для начинающих
577
lexicographical_compare()
выполняет лексикографическое (словарное) упорядочение
(см. также обсуждение перестановок и Приложение). min(), min_element(), mismatch()
12.5.8.
Алгоритмы работы с множествами
Четыре алгоритма этой категории реализуют теоретико-множественные операции над любым контейнерным типом. При объединении создается отсортированная последовательность элементов, принадлежащих хотя бы одному контейнеру, при пересечении – обоим контейнерам, а при взятии разности – принадлежащих первому контейнеру, но не принадлежащих второму. Наконец, симметрическая разность – это отсортированная последовательность элементов, принадлежащих одному из контейнеров, но не обоим. set_symmetric_difference()
12.5.9.
Алгоритмы работы с хипом
Хип (heap) – это разновидность двоичного дерева, представленного в массиве.
Стандартная библиотека предоставляет такую реализацию хипа, в которой значение ключа в любом узле больше либо равно значению ключа в любом потомке этого узла. make_heap(), pop_heap(), push_heap(), sort_heap()
12.6.
Когда нельзя использовать обобщенные алгоритмы
Ассоциативные контейнеры (отображения и множества) поддерживают определенный порядок элементов для быстрого поиска и извлечения. Поэтому к ним не разрешается применять обобщенные алгоритмы, меняющие порядок, такие, как sort() и partition()
. Если в ассоциативном контейнере требуется переставить элементы, то необходимо сначала скопировать их в последовательный контейнер, например в вектор или список.
Контейнер list (список) реализован в виде двусвязного списка: в каждом элементе, помимо собственно данных, хранятся два члена-указателя – на следующий и на предыдущий элементы. Основное преимущество списка – это эффективная вставка и удаление одного элемента или целого диапазона в произвольное место списка, а недостаток – невозможность произвольного доступа. Например, можно написать: vector::iterator vec_iter = vec.begin() + 7; equal(), includes(), lexicographical_compare(), max(), max_element(), set_union(), set_intersection(), set_difference(),

С++ для начинающих
578
Такая форма вполне допустима и инициализирует vec_iter адресом восьмого элемента вектора, но запись list::iterator list_iter = slist.begin() + 7; некорректна, так как элементы списка не занимают непрерывную область памяти. Для того чтобы добраться до восьмого элемента, необходимо посетить все промежуточные.
Поскольку список не поддерживает произвольного доступа, то алгоритмы merge(), remove()
, reverse(), sort() и unique() лучше к таким контейнерам не применять, хотя ни один из них явно не требует наличия соответствующего итератора. Вместо этого для списка определены специализированные версии названных операций в виде функций-членов, а также операция splice():
•
list::merge()
объединяет два отсортированных списка
•
list::remove()
удаляет элементы с заданным значением
•
list::remove_if()
удаляет элементы, удовлетворяющие некоторому условию
•
list::reverse()
переставляет элементы списка в обратном порядке
•
list::sort()
сортирует элементы списка
•
list::splice()
перемещает элементы из одного списка в другой
•
list::unique()
оставляет один элемент из каждой цепочки одинаковых смежных элементов
12.6.1.
Операция list_merge()
void list::merge( list rhs, Compare comp );
Элементы двух упорядоченных списков объединяются либо на основе оператора
“меньше”, определенного для типа элементов в контейнере, либо на основе указанной пользователем операции сравнения. (Заметьте, что элементы списка rhs перемещаются в список, для которого вызвана функция-член merge(); по завершении операции список rhs будет пуст.) Например:
// ошибка: арифметические операции над итераторами
// не поддерживаются списком void list::merge( list rhs ); template

С++ для начинающих
579
ilist1.merge( ilist2 );
После выполнения операции merge() список ilist2 пуст, а ilist1 содержит первые 15 чисел Фибоначчи в порядке возрастания.
12.6.2.
Операция list::remove()
void list::remove( const elemType &value );
Операция remove() удаляет все элементы с заданным значением: ilist1.remove( 1 );
12.6.3.
Операция list::remove_if()
void list::remove_if( Predicate pred );
Операция remove_if() удаляет все элементы, для которых выполняется указанное условие, т.е. предикат pred возвращает true. Например: ilist1.remove_if( Even() ); удаляет все четные числа из списка, определенного при рассмотрении merge().
12.6.4.
Операция list::reverse()
void list::reverse(); int array1[ 10 ] = { 34, 0, 8, 3, 1, 13, 2, 5, 21, 1 }; int array2[ 5 ] = { 377, 89, 233, 55, 144 }; list< int > ilist1( array1, array1 + 10 ); list< int > ilist2( array2, array2 + 5 );
// для объединения требуется, чтобы оба списка были упорядочены ilist1.sort(); ilist2.sort(); template < class Predicate > class Even { public: bool operator()( int elem ) { return ! (elem % 2 ); }
};

С++ для начинающих
580
Операция reverse()
изменяет порядок следования элементов списка на противоположный: ilist1.reverse();
12.6.5.
Операция list::sort()
void list::sort( Compare comp );
По умолчанию sort() упорядочивает элементы списка по возрастанию с помощью оператора “меньше”, определенного в классе элементов контейнера. Вместо этого можно явно передать в качестве аргумента оператор сравнения. Так, list1.sort(); упорядочивает list1 по возрастанию, а list1.sort( greater() ); упорядочивает list1 по убыванию, используя оператор “больше”.
12.6.6.
Операция list::splice()
iterator first, iterator last );
Операция splice() имеет три формы: перемещение одного элемента, всех элементов или диапазона из одного списка в другой. В каждом случае передается итератор, указывающий на позицию вставки, а перемещаемые элементы располагаются непосредственно перед ней. Если даны два списка: list< int > ilist2( array, array + 2 ); // содержит 0, 1 то следующее обращение к splice() перемещает первый элемент ilist1 в ilist2.
Теперь ilist2 содержит элементы 0, 1 и 0, тогда как в ilist1 элемента 0 больше нет. void list::sort(); template void list::splice( iterator pos, list rhs ); void list::splice( iterator pos, list rhs, iterator ix ); void list::splice( iterator pos, list rhs, int array[ 10 ] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 }; list< int > ilist1( array, array + 10 );

С++ для начинающих
581
ilis2.splice( ilist2.end(), ilist1, ilist1.begin() );
В следующем примере применения splice() передаются два итератора, ограничивающие диапазон перемещаемых элементов: ilist2.splice( ilist2.begin(), ilist1, first, last );
В данном случае элементы 2, 3, 5 и 8 удаляются из ilist1 и вставляются в начало ilist2
. Теперь ilist1 содержит пять элементов 1, 1, 13, 21 и 34. Для их перемещения в ilist2 можно воспользоваться третьей вариацией операции splice(): ilist2.splice( pos, ilist1 );
Итак, список ilist1 пуст. Последние пять элементов перемещены в позицию списка ilist2
, предшествующую той, которую занимает элемент 5.
12.6.7.
Операция list::unique()
void list::unique( BinaryPredicate pred );
Операция unique() удаляет соседние дубликаты. По умолчанию при сравнении используется оператор равенства, определенный для типа элементов контейнера.
Например, если даны значения {0,2,4,6,4,2,0}, то после применения unique() список останется таким же, поскольку в соседних позициях дубликатов нет. Но если мы сначала отсортируем список, что даст {0,0,2,2,4,4,6}, а потом применим unique(), то получим четыре различных значения {0,2,4,6}. ilist.unique();
Вторая форма unique() принимает альтернативный оператор сравнения. Например,
// ilist2.end() указывает на позицию, куда нужно переместить элемент
// элементы вставляются перед этой позицией
// ilist1 указывает на список, из которого перемещается элемент
// ilist1.begin() указывает на сам перемещаемый элемент list< int >::iterator first, last; first = ilist1.find( 2 ); last = ilist1.find( 13 ); list< int >::iterator pos = ilist2.find( 5 ); void list::unique(); template

С++ для начинающих