Язык программирования C Пятое издание

• Название: Язык программирования C Пятое издание
• Дата: 15.07.2019
• Размер: 1.85 Mb.
• Имя файла: 620354-www.libfox.ru.pdf
• Тип: Документы; #84130
• страница: 26 из 54

"0123456789", что возвращает вызов функции numbers.find(name)?
Упражнение 9.49. У символов может быть надстрочная часть, расположенная выше середины строки, как у d или f, или подстрочная, ниже середины строки, как у p или g. Напишите программу, которая читает содержащий слова файл и сообщает самое длинное слово, не содержащее ни надстрочных, ни подстрочных элементов.
9.5.4. Сравнение строк
Кроме операторов сравнения (см. раздел 3.2.2), библиотека string предоставляет набор функций сравнения, подобных функции strcmp() библиотеки С (см. раздел 3.5.4). Подобно функции strcmp(), функция s.compare() возвращает нуль, положительное или отрицательное значение, в зависимости от того, равна ли строка s, больше или меньше строки, переданной ее аргументом.
Как показано в таб. 9.15, существует шесть версий функции compare(). Ее аргументы зависят от того, сравниваются ли две строки или строка и символьный массив. В обоих случаях
Page 466/1103

сравнивать можно либо всю строку, либо ее часть.
Таблица 9.15. Возможные аргументы функции s.compare() s2 Сравнивает строку s со строкой s2 pos1, n1, s2 Сравнивает n1 символов, начиная с позиции pos1 из строки s, со строкой s2
pos1, n1, s2, pos2, n2 Сравнивает n1 символов, начиная с позиции pos1 из строки s, со строкой s2, начиная с позиции pos2 в строке s2 cp Сравнивает строку s с завершаемым нулевым символом массивом, на который указывает указатель cp pos1, n1, cp Сравнивает n1
символов, начиная с позиции pos1 из строки s, со строкой cp pos1, n1, cp, n2 Сравнивает n1
символов, начиная с позиции pos1 из строки s, со строкой cp, начиная с символа n2 9.5.5. Числовые преобразования
Строки зачастую содержат символы, которые представляют числа. Например, числовое значение 15 можно представить как строку с двумя символами, '1' и '5'. На самом деле символьное представление числа отличается от его числового значения. Числовое значение
15, хранимое в 16-разрядной переменной типа short, будет иметь двоичное значение
0000000000001111, а символьная строка "15", представленная как два символа из набора
Latin-1, будет иметь двоичное значение 0011000100110101. Первый байт представляет символ '1', восьмеричное значение которого составит 061, а второй байт, представляющий символ '5', в наборе Latin-1 имеет восьмеричное значение 065.
Новый стандарт вводит несколько функций, осуществляющих преобразование между числовыми данными и библиотечным типом string.
Таблица 9.16. Преобразования между строками и числами to_string(val) Перегруженные версии функции возвращают строковое представление значения val. Аргумент val может иметь любой арифметический тип (см. раздел 2.1.1). Есть версии функции to_string() для любого типа с плавающей точкой и целочисленного типа, включая тип int и большие типы.
Малые целочисленные типы преобразуются, как обычно (см. раздел 4.11.1) stoi(s, p, b) stol(s,
p, b) stoul(s, p, b) stoll(s, p, b) stoull(s, p, b) Возвращают числовое содержимое исходной подстроки s как тип int, long, unsigned long, long long или unsigned long long соответственно.
Аргумент b задает используемое для преобразования основание числа; по умолчанию принято значение 10. Аргумент p — указатель на тип size_t, означающий индекс первого нечислового символа в строке s; по умолчанию p имеет значение 0. В этом случае функция не хранит индекс stof(s, p) stod(s, p) stold(s, p) Возвращают числовое содержимое исходной подстроки s как тип float, double или long double соответственно. Аргумент p имеет то же назначение, что и у целочисленных преобразований int i = 42; string s = to_string(i); // преобразует переменную i типа int в ее
// символьное представление double d = stod(s); //
Page 467/1103

преобразует строку s в значение типа double
Здесь для преобразования числа 42 в его строковое представление используется вызов функции to_string(), а затем вызов функции stod() преобразует эту строку в значение с плавающей точкой.
Первый преобразуемый в числовое значение символ строки должен быть цифрой: string s2 = "pi = 3.14";
// d = 3.14 преобразуется первая подстрока в строке s, начинающаяся
// с цифры; d = 3.14 d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
Для получения позиции первого символа строки s, который мог быть частью числа, в этом вызове функции stod() используется функция find_first_of() (см. раздел 9.5.3). Функции stod()
передается подстрока строки s, начиная с этой позиции. Функция stod() читает переданную строку до тех пор, пока не встретится символ, который не может быть частью числа. Затем найденное символьное представление числа преобразуется в соответствующее значение типа double.
Первый преобразуемый символ строки должен быть знаком + или - либо цифрой. Строка может начаться с части 0x или 0X, означающей шестнадцатеричный формат. У функций преобразования чисел с плавающей точкой строка может также начинаться с десятичной точки (.) и содержать символ е или E, означающий экспоненциальную часть. У функций преобразования в целочисленный тип, в зависимости от основания, строка может содержать алфавитные символы, соответствующие цифрам после цифры 9.
Если строка не может быть преобразована в число, эти функции передают исключение invalid_argument (см. раздел 5.6). Если преобразование создает значение, которое не может быть представлено заданным типом, они передают исключение out_of_range. Упражнения раздела 9.5.5
Упражнение 9.50. Напишите программу обработки вектора vector<string>, элементы которого представляют целочисленные значения. Вычислите сумму всех элементов вектора.
Измените программу так, чтобы она суммировала строки, которые представляют значения с плавающей точкой.
Упражнение 9.51. Напишите класс, у которого есть три беззнаковых члена, представляющих год, месяц и день. Напишите конструктор, получающий строку, представляющую дату.
Конструктор должен понимать множество форматов даты, такие как January 1,1900, 1/1/1900,
Jan 1,1900 и т.д.
9.6. Адаптеры контейнеров
Кроме последовательных контейнеров, библиотека предоставляет три адаптера последовательного контейнера: stack (стек), queue (очередь) и priority_queue (приоритетная
Page 468/1103

очередь).
Адаптер (adaptor[4]) — это фундаментальная концепция библиотеки. Существуют адаптеры контейнера, итератора и функции. По существу, адаптер — это механизм, заставляющий нечто одно действовать как нечто другое. Адаптер контейнера получает контейнер существующего типа и заставляет его действовать как другой. Например, адаптер stack получает любой из последовательных контейнеров (array и forward_list) и заставляет его работать подобно стеку. Функции и типы данных, общие для всех адаптеров контейнеров,
перечислены в табл. 9.17.
Таблица 9.17. Функции и типы, общие для всех адаптеров size_type Тип данных, достаточно большой, чтобы содержать размер самого большого объекта этого типа value_type Тип элемента container_type Тип контейнера, на базе которого реализован адаптер A a; Создает новый пустой адаптер по имени a A a(c); Создает новый адаптер по имени а, содержащий копию контейнера с операторы сравнения Каждый адаптер поддерживает все операторы сравнения: ==, !=, <,
<=, > и >=. Эти операторы возвращают результат сравнения внутренних контейнеров a.empty() Возвращает значение true, если адаптер а пуст, и значение false в противном случае a.size() Возвращает количество элементов в адаптере a swap(a, b) a.swap(b) Меняет содержимое контейнеров а и b; у них должен быть одинаковый тип, включая тип контейнера,
на основании которого они реализованы Определение адаптера
Каждый адаптер определяет два конструктора: стандартный конструктор, создающий пустой объект, и конструктор, получающий контейнер и инициализирующий адаптер, копируя полученный контейнер. Предположим, например, что deq — это двухсторонняя очередь deque<int>. Ее можно использовать для инициализации нового стека следующим образом: stack<int> stk(deq); // копирует элементы из deq в stk
По умолчанию оба адаптера, stack и queue, реализованы на основании контейнера deque, а адаптер priority_queue реализован на базе контейнера vector. Заданный по умолчанию тип контейнера можно переопределить, указав последовательный контейнер как второй аргумент при создании адаптера:
// пустой стек, реализованный поверх вектора stack<string, vector<string>> str_stk;
// str_stk2 реализован поверх вектора и первоначально содержит копию svec stack<string, vector<string>> str_stk2(svec);
Существуют некоторые ограничения на применение контейнеров с определенными адаптерами. Всем адаптерам нужна возможность добавлять и удалять элементы. В
результате они не могут быть основаны на массиве. Точно так же нельзя использовать контейнер forward_list, поскольку все адаптеры требуют функций добавления, удаления и обращения к последнему элементу контейнера. Стек требует только функций push_back(),
Page 469/1103

pop_back() и back(), поэтому для стека можно использовать контейнер любого из остальных типов. Адаптеру queue требуются функции back(), push_back(), front() и push_front(), поэтому он может быть создан на основании контейнеров list и deque, но не vector. Адаптеру priority_queue в дополнение к функциям front(), push_back() и pop_back() требуется произвольный доступ к элементам; он может быть основан на контейнерах vector и deque, но не list. Адаптер stack
Тип stack определен в заголовке stack. Функции-члены класса stack перечислены в табл. 9.18.
Следующая программа иллюстрирует использование адаптера stack: stack<int> intStack; // пустой стек
// заполнить стек for (size_t ix = 0; ix != 10; ++ix) intStack.push(ix); // intStack содержит значения 0...9 while (!intStack.empty()) { // пока в intStack есть значения int value = intStack.top();
// код, использующий, значение intStack.pop(); // извлечь верхний элемент и повторить
}
Сначала intStack объявляется как пустой стек целочисленных элементов: stack<int> intStack; // пустой стек
Затем цикл for добавляет десять элементов, инициализируя каждый следующим целым числом, начиная с нуля. Цикл while перебирает весь стек, извлекая его верхний элемент, пока он не опустеет.
Таблица 9.18. Функции, поддерживаемые адаптером контейнера stack, кроме приведенных в табл. 9.17 По умолчанию используется контейнер deque, но может быть также реализован на основании контейнеров list или vector. s.pop() Удаляет, но не возвращает верхний элемент из стека s.push( item ) s.emplace(
Page 470/1103

args ) Создает в стеке новый верхний элемент, копируя или перемещая элемент item либо создавая элемент из аргумента параметра args s.top() Возвращает, но не удаляет верхний элемент из стека
Каждый адаптер контейнера определяет собственные функции, исходя из функций,
предоставленных базовым контейнером. Использовать можно только функции адаптера, а функции основного контейнера использовать нельзя. Рассмотрим, например, вызов функции push_back() контейнера deque, на котором основан стек intStack: intStack.push(ix); // intStack содержит значения 0...9
Хотя стек реализован на основании контейнера deque, прямого доступа к его функциям нет.
Для стека нельзя вызвать функцию push_back(); вместо нее следует использовать функцию push(). Адаптеры очередей
Адаптеры queue и priority_queue определены в заголовке queue. Список функций,
поддерживаемых этими типами, приведен в табл. 9.19.
Таблица 9.19. Функции адаптеров queue и priority_queue, кроме приведенных в табл. 9.17 По умолчанию адаптер queue использует контейнер deque, а адаптер priority_queue — контейнер vector; адаптер queue может использовать также контейнер list или vector, адаптер priority_queue может использовать контейнер deque. q.pop() Удаляет, но не возвращает первый или наиболее приоритетный элемент из очереди или приоритетной очереди соответственно q.front() q.back() Возвращает, но не удаляет первый или последний элемент очереди q.
Допустимо только для адаптера queue q.top() Возвращает, но не удаляет элемент с самым высоким приоритетом.
Допустимо только для адаптера priority_queue q.push( item ) q.emplace( args ) Создает элемент со значением item или создает его исходя из аргумента args в конце очереди или в соответствующей позиции приоритетной очереди
Библиотечный класс queue использует хранилище, организованное по принципу "первым пришел, первым вышел" (first-in, first-out — FIFO). Поступающие в очередь объекты помещаются в ее конец, а извлекаются из ее начала.
Адаптер priority_queue позволяет установить приоритет хранимых элементов. Добавляемые элементы помещаются перед элементами с более низким приоритетом. По умолчанию для определения относительных приоритетов в библиотеке используется оператор <. Его переопределение рассматривается в разделе 11.2.2. Упражнения раздела 9.6
Упражнение 9.52. Используйте стек для обработки выражений со скобками. Встретив открывающую скобку, запомните ее положение. Встретив закрывающую скобку, после открывающей скобки, извлеките эти элементы, включая открывающую скобку, и поместите полученное значение в стек, переместив таким образом заключенное в скобки выражение.
Page 471/1103

Резюме
Библиотечные типы контейнеров — это шаблоны, позволяющие содержать объекты указанного типа. В последовательных контейнерах элементы упорядочены и доступны по позиции. У последовательных контейнеров общий, стандартизированный интерфейс: если два последовательных контейнера предоставляют некую функцию, то у нее будет тот же интерфейс и значение в обоих контейнерах.
Все контейнеры (кроме контейнера array) обеспечивают эффективное управление динамической памятью. Можно добавлять элементы в контейнер, не волнуясь о том, где хранить элементы. Контейнер сам управляет хранением. Контейнеры vector и string обеспечивают более подробное управление памятью, предоставляя функции-члены reserve()
и capacity().
По большей части, контейнеры определяют удивительно мало функций. Они определяют конструкторы, функции добавления и удаления элементов, функции выяснения размера контейнера и возвращения итераторов на те или иные элементы. Другие весьма полезные функции, такие как сортировка и поиск, определены не типами контейнеров, а стандартными алгоритмами, которые будут описаны в главе 10.
Функции контейнеров, которые добавляют или удаляют элементы, способны сделать существующие итераторы, указатели или ссылки некорректными. Большинство функций,
которые способны сделать итераторы недопустимыми, например insert() или erase(),
возвращают новый итератор, позволяющий не потерять позицию в контейнере. Особую осторожность следует соблюдать в циклах, которые используют итераторы и операции с контейнерами, способные изменить их размер.
Термины
Адаптер priority_queue (приоритетная очередь). Адаптер последовательных контейнеров,
позволяющий создать очередь, в которой элементы добавляются не в конец, а согласно определенному уровню приоритета. По умолчанию при определении приоритета используется оператор "меньше" для типа элемента.
Адаптер queue (очередь). Адаптер последовательных контейнеров, позволяющий создать очередь, в которой элементы добавляются в конец, а предоставляются и удаляются в начале.
Адаптер stack (стек). Адаптер последовательных контейнеров, позволяющий создать стек, в который элементы добавляют и удаляют только с одного конца.
Адаптер (adaptor). Библиотечный тип, функция или итератор, который заставляет один объект действовать подобно другому. Для последовательных контейнеров существуют три адаптера: stack, queue и priority_queue, каждый из которых определяет новый интерфейс базового последовательного контейнера.
Диапазон итераторов (iterator range). Диапазон элементов, обозначенный двумя итераторами.
Первый итератор относится к первому элементу в последовательности, а второй — к следующему элементу после последнего. Если диапазон пуст, итераторы равны (и наоборот,
Page 472/1103

если итераторы равны, они обозначают пустой диапазон). Если диапазон не пуст, второй итератор можно достичь последовательным увеличением первого итератора.
Последовательное приращение итератора позволяет обработать каждый элемент диапазона.
Интервал, включающий левый элемент (left-inclusive interval). Диапазон значений,
включающий первый элемент, но исключающий последний. Обычно обозначается как [i, j),
т.е. начальное значение последовательности i включено, а последнее, j, исключено.
Итератор после конца (off-the-end iterator). Итератор, обозначающий (несуществующий)
следующий элемент после последнего в диапазоне. Обычно называемый "конечным итератором" (end iterator).
Итератор после начала (off-the-beginning iterator). Итератор, обозначающий
(несуществующий) элемент непосредственно перед началом контейнера forward_list.
Возвращается функцией before_begin() контейнера forward_list. Подобно итератору,
возвращенному функцией end(), к значению данного итератора обратиться нельзя.
Контейнер array (массив). Последовательный контейнер фиксированного размера. Чтобы определить массив, кроме определения типа элемента следует указать его размер. К
элементам массива можно обратиться по их позиционному индексу. Обеспечивает быстрый произвольный доступ к элементам.
Контейнер deque (двухсторонняя очередь). Последовательный контейнер, к элементам которого можно обратиться по индексу (позиции). Двухсторонняя очередь подобна вектору во всех отношениях, за исключением того, что он обеспечивает быструю вставку как в начало,
так и в конец контейнера, без перемещения элементов.
Контейнер forward_list (односвязный список). Последовательный контейнер, представляющий односвязный список. К элементам контейнера forward_list можно обращаться только последовательно; начиная с данного элемента, можно добраться до другого элемента, только перебрав каждый элемент между ними. Итераторы класса forward_list не поддерживают декремент (--). Обеспечивает быструю вставку (или удаление) в любой позиции. В отличие от других контейнеров, вставка и удаление происходят после указанной позиции итератора. Как следствие, у контейнера forward_list есть итератор перед началом, для согласованности с обычным итератором после конца. При добавлении новых элементов итераторы остаются допустимыми. Когда элемент удаляется, некорректным становится лишь итератор удаленного элемента.
Контейнер list (список). Последовательный контейнер, к элементам которого можно обратиться только последовательно, т.е. начиная с одного элемента, можно перейти к другому, увеличивая или уменьшая итератор. Итераторы контейнера list поддерживают как инкремент (++), так и декремент (--). Обеспечивает быструю вставку (и удаление) в любой позиции. Добавление новых элементов никак не влияет ни на другие элементы, ни на существующие итераторы. Когда элемент удаляется, некорректным становится лишь итератор удаленного элемента.
Контейнер vector (вектор). Последовательный контейнер, к элементам которого можно обратиться по индексу (позиции). Эффективно добавить или удалить элементы вектора можно только с конца. Добавление элементов в вектор может привести к его перераспределению в памяти, что сделает некорректными все созданные ранее итераторы.
При добавлении (или удалении) элемента в середину вектора итераторы всех расположенных далее элементов становятся некорректными.
Контейнер (container). Тип (класс), который содержит коллекцию объектов определенного типа. Каждый библиотечный контейнер является шаблоном класса. Чтобы создать контейнер,
Page 473/1103

необходимо указать тип хранимых в нем элементов. За исключением массивов,
библиотечные контейнеры имеют переменный размер.
Последовательный контейнер (sequential container). Контейнер, позволяющий содержать упорядоченную коллекцию объектов одинакового типа. К элементам последовательного контейнера обращаются по позиции.
Функция begin(). Функция контейнера, возвращающая итератор на первый элемент в контейнере (если он есть), или итератор после конца, если контейнер пуст. Будет ли возвращенный итератор константным, зависит от типа контейнера.
Функция cbegin(). Функция контейнера, возвращающая итератор const_iterator на первый элемент в контейнере (если он есть), или итератор после конца (off-the-end iterator), если контейнер пуст.
Функция cend(). Функция контейнера, возвращающая итератор const_iterator на
(несуществующий) элемент после последнего элемента контейнера.
Функция end(). Функция контейнера, возвращающая итератор на (несуществующий) элемент после последнего элемента контейнера. Будет ли возвращенный итератор константным,
зависит от типа контейнера.
Глава 10
Обобщенные алгоритмы
В библиотечных контейнерах определен на удивление небольшой набор функций. Вместо того чтобы снабжать каждый контейнер большим количеством одинаковых функций,
библиотека предоставляет набор алгоритмов, большинство из которых не зависит от конкретного типа контейнера. Эти алгоритмы называют обобщенными (generic), поскольку применимы они и к контейнерам разных типов, и к разным типам элементов.
Темой данной главы являются не только обобщенные алгоритмы, но и более подробное изучение итераторов.
В последовательных контейнерах определено немного операций: по большей части они позволяют добавлять и удалять элементы, обращаться к первому или последнему элементу,
определять, не пуст ли контейнер, и получать итераторы на первый элемент или следующий после последнего.
Но может понадобиться и множество других вспомогательных операций: поиск определенного элемента, замена или удаление некого значения, переупорядочивание элементов контейнера и т.д.
Чтобы не создавать каждую из этих функций как член контейнера каждого типа, стандартная библиотека определяет набор обобщенных алгоритмов (generic algorithm).
Алгоритмами они называются потому, что реализуют классические алгоритмы, такие как сортировка и поиск, а
Page 474/1103

обобщенными — потому, что работают с контейнерами любых типов, включая массивы встроенных типов, и, как будет продемонстрировано далее, с последовательностями других видов, а не только с такими библиотечными типами, как vector или list.
10.1. Краткий обзор
Большинство алгоритмов определено в заголовке algorithm. Библиотека определяет также набор обобщенных числовых алгоритмов в заголовке numeric.
Обычно алгоритмы воздействуют не на сам контейнер, а работают, перебирая диапазон элементов, заданный двумя итераторами (см. раздел 9.2.1). Перебирая диапазон, алгоритм,
как правило, выполняет некое действие с каждым элементом. Предположим, например, что имеется вектор целых чисел и необходимо узнать, содержит ли этот вектор некое значение.
Проще всего ответить на этот вопрос, воспользовавшись библиотечным алгоритмом find(): int val = 42; // искомое значение
// result обозначит искомый элемент, если он есть в векторе,
// или значение vec.cend(), если нет auto result = find(vec.cbegin(), vec.cend(), val);
// отображение результата cout << "The value " << val
<< (result == vec.cend()
? " is not present" : " is present") << endl;
Первые два аргумента функции find() являются итераторами, обозначающими диапазон элементов, а третий аргумент — это значение. Функция find() сравнивает каждый элемент указанного диапазона с заданным значением и возвращает итератор на первый элемент,
соответствующий этому значению. При отсутствии соответствия функция find() возвращает свой второй итератор, означая неудачу поиска. Так, сравнив возвращаемое значение со вторым аргументом, можно определить, был ли найден элемент. Для проверки,
свидетельствующей об успехе поиска значения, в операторе вывода используется условный оператор (см. раздел 4.7).
Поскольку функция find() работает с итераторами, ее можно использовать для поиска значения в любом контейнере. Рассмотрим пример применения функции find() для поиска значения в списке строк: string val = "a value"; // искомое значение
Page 475/1103

// вызов, позволяющий найти строковый элемент в списке auto result = find(lst.cbegin(), lst.cend(), val);
Аналогично, поскольку указатели действуют как итераторы встроенных массивов, функцию find() можно использовать для поиска в массиве: int ia[] = {27, 210, 12, 47, 109, 83}; int val = 83; int* result = find(begin(ia), end(ia), val);
Здесь для передачи указателей на первый и следующий после последнего элементы массива ia используются библиотечные функции begin() и end() (см. раздел 3.5.3).
Искать также можно в диапазоне, заданном переданными итераторами (или указателями), на его первый и следующий после последнего элементы. Например, следующий вызов ищет соответствие в элементах iа[1], ia[2] и ia[3]:
// искать среди элементов, начиная с ia[1] и до, но не включая, ia[4] auto result = find(ia +1, ia + 4, val); Как работают алгоритмы
Для того чтобы изучить применение алгоритмов к контейнерам различных типов, немного подробней рассмотрим функцию find(). Ее задачей является поиск указанного элемента в не отсортированной коллекции элементов. Концептуально функция find() должна выполнить следующие действия.
1. Обратиться к первому элементу последовательности.
2. Сравнить этот элемент с искомым значением.
3. Если элемент соответствует искомому, функция find() возвращает значение,
идентифицирующее этот элемент.
4. В противном случае функция find() переходит к следующему элементу и повторяет этапы 2
и 3.
5. По достижении конца последовательности функция find() должна остановиться.
6. Достигнув конца последовательности, функция find() должна возвратить значение,
означающее неудачу поиска. Тип этого значения должен быть совместимым с типом значения, возвращенного на этапе 3.
Ни одно из этих действий не зависит от типа контейнера, который содержит элементы. Пока есть итераторы, применимые для доступа к элементам, функция find() в любом случае не зависит от типа контейнера (или даже хранимых в контейнере элементов). Итераторы делают алгоритмы независимыми от типа контейнера…
Все этапы работы функции find(), кроме второго, могут быть выполнены средствами итератора: оператор обращения к значению итератора предоставляет доступ к значению элемента; если элемент соответствует искомому, функция find() может возвратить итератор на этот элемент; оператор инкремента итератора переводит его на следующий элемент;
Page 476/1103

итератор после конца будет означать достижение функцией find() конца последовательности;
функция find() вполне может возвратить итератор после конца (см. раздел 9.2.1), чтобы указать на неудачу поиска. …но алгоритмы зависят от типа элементов
Хотя итераторы делают алгоритмы независимыми от контейнеров, большинство алгоритмов используют одну (или больше) функцию типа элемента. Например, этап 2 использует оператор == типа элемента для сравнения каждого элемента с предоставленным значением.
Другие алгоритмы требуют, чтобы тип элемента имел оператор <. Но, как будет продемонстрировано, большинство алгоритмов позволяют предоставить собственную функцию для использования вместо оператора, заданного по умолчанию. Упражнения раздела 10.1
Упражнение 10.1. В заголовке algorithm определена функция count(), подобная функции find().
Она получает два итератора и значение, а возвращает количество обнаруженных в диапазоне элементов, обладающих искомым значением. Организуйте чтение в вектор последовательности целых чисел. Осуществите подсчет элементов с указанным значением.
Упражнение 10.2. Повторите предыдущую программу, но чтение значений организуйте в список (list) строк. Ключевая концепция. Алгоритмы никогда не используют функции контейнеров
Общие алгоритмы никогда не используют функции контейнеров. Они работают исключительно с итераторами. Тот факт, что алгоритмы оперируют итераторами, а не функциями контейнера, возможно, удивителен, но он имеет глубокий смысл: когда используются "обычные" итераторы, алгоритмы не способны изменить размер исходного контейнера. Как будет продемонстрировано далее, алгоритмы способны изменять значения хранимых в контейнере элементов и перемещать их в контейнер. Однако они не способны ни добавлять, ни удалять сами элементы.
Как будет продемонстрировано в разделе 10.4.1, существуют специальные классы итераторов, которые способны на несколько большее, чем просто перебор элементов. Они позволяют выполнять операции вставки. Когда алгоритм работает с одним из таких итераторов , возможен побочный эффект добавления элемента в контейнер, однако в самих алгоритмах это никогда не используется.
10.2. Первый взгляд на алгоритмы
Библиотека предоставляет больше ста алгоритмов. К счастью, у алгоритмов, как и у контейнеров, единообразная архитектура. Понимание этой архитектуры упростит изучение и использование всех ста с лишним алгоритмов без необходимости изучать каждый из них. В
этой главе рассматривается использование алгоритмов и описаны характеризующие их общие принципы. В приложении А перечислены все алгоритмы согласно принципам их работы.
За небольшим исключением, все алгоритмы работают с диапазоном элементов. Далее этот диапазон мы будем называть исходным диапазоном (input range). Алгоритмы, работающие с исходным диапазоном, всегда получают его в виде двух первых параметров. Эти параметры являются итераторами,
используемыми для обозначения первого и следующего после последнего элемента,
Page 477/1103

подлежащих обработке.
Несмотря на то что большинство алгоритмов работают с одинаково обозначенным исходным диапазоном, они отличаются тем, как используются элементы этого диапазона. Проще всего подразделить алгоритмы на читающие, записывающие и меняющие порядок элементов.
10.2.1. Алгоритмы только для чтения
Много алгоритмов только читают значения элементов в исходном диапазоне, но никогда не записывают их. Функция find() и функция count(), использованная в упражнениях раздела
10.1, являются примерами таких алгоритмов.
Другим предназначенным только для чтения алгоритмом является accumulate(), который определен в заголовке numeric. Функция accumulate() получает три аргумента. Первые два определяют диапазон суммируемых элементов, а третий — исходное значение для суммы.
Предположим, что vec — это последовательность целых чисел.
// суммирует элементы вектора vec, начиная со значения 0 int sum = accumulate(vec.cbegin(), vec.cend(), 0);
Приведенный выше код суммирует значения элементов вектора vec, используя 0 как начальное значение суммы.
Тип третьего аргумента функции accumulate() определяет, какой именно оператор суммы будет использован и каков будет тип возвращаемого значения функции accumulate().
Алгоритмы и типы элементов
У того факта, что функция accumulate() использует свой третий аргумент как отправную точку для суммирования, есть важное последствие: он позволяет добавить тип элемента к типу суммы. Таким образом, тип элементов последовательности должен соответствовать или быть приводим к типу третьего аргумента. В этом примере элементами вектора vec могли бы быть целые числа, или числа типа double, или long long, или любого другого типа, который может быть добавлен к значению типа int.
Например, поскольку тип string имеет оператор +, функцию accumulate() можно использовать для конкатенации элементов вектора строк: string sum = accumulate(v.cbegin(), v.cend(), string(""));
Этот вызов добавляет каждый элемент вектора v к первоначально пустой строке sum.
Обратите внимание: третий параметр здесь явно указан как объект класса string. Передача строки как символьного литерала привела бы к ошибке при компиляции.
// ошибка: no + on const char* string sum = accumulate(v.cbegin(), v.cend(), "");
Если бы был передан строковый литерал, типом суммируемых значений оказался бы const char*. Этот тип и определяет используемый оператор +. Поскольку тип const char* не имеет
Page 478/1103

оператора +, этот вызов не будет компилироваться.
С алгоритмами, которые читают, но не пишут в элементы, обычно лучше использовать функции cbegin() и cend() (см. раздел 9.2.3). Но если возвращенный алгоритмом итератор планируется использовать для изменения значения элемента, то следует использовать функции begin() и end(). Алгоритмы, работающие с двумя последовательностями
Еще один алгоритм только для чтения, equal(), позволяет определять, содержат ли две последовательности одинаковые значения. Он сравнивает каждый элемент первой последовательности с соответствующим элементом второй. Алгоритм возвращает значение true, если соответствующие элементы равны, и значение false в противном случае. Он получает три итератора: первые два (как обычно) обозначают диапазон элементов первой последовательности, а третий — первый элемент второй последовательности:
// roster2 должен иметь по крайней мере столько же элементов,
// сколько и roster1 equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
Поскольку функция equal() работает с итераторами, ее можно вызвать для сравнения элементов контейнеров разных типов. Кроме того, типы элементов также не обязаны совпадать, пока можно использовать оператор == для их сравнения. Например, контейнер roster1 мог быть вектором vector<string>, а контейнер roster2 — списком list<const char*>.
Однако алгоритм equal() делает критически важное предположение: подразумевает, что вторая последовательность по крайней мере не меньше первой. Этот алгоритм просматривает каждый элемент первой последовательности и подразумевает, что для него есть соответствующий элемент во второй последовательности.
Алгоритмы, получающие один итератор, обозначающий вторую последовательность,
подразумевают, что вторая последовательность по крайней мере не меньше первой.
Упражнения раздела 10.2.1
Упражнение 10.3. Примените функцию accumulate() для суммирования элементов вектора vector<int>.
Упражнение 10.4. Если вектор v имеет тип vector<double>, в чем состоит ошибка вызова accumulate(v.cbegin(), v.cend(), 0) (если она есть)?
Упражнение 10.5. Что произойдет, если в вызове функции equal() для списков оба из них будут содержать строки в стиле С, а не библиотечные строки? Ключевая концепция.
Итераторы, передаваемые в качестве аргументов
Некоторые алгоритмы читают элементы из двух последовательностей. Составляющие эти последовательности элементы могут храниться в контейнерах различных видов. Например,
первая последовательность могла бы быть вектором (vector), а вторая списком (list),
двухсторонней очередью (deque), встроенным массивом или другой последовательностью.
Кроме того, типы элементов этих последовательностей не обязаны совпадать точно.
Обязательно необходима возможность сравнивать элементы этих двух последовательностей. Например, в алгоритме equal() типы элемента не обязаны быть идентичными, на самом деле нужна возможность использовать оператор == для сравнения
Page 479/1103

элементов этих двух последовательностей.
Алгоритмы, работающие с двумя последовательностями, отличаются способом передачи второй последовательности. Некоторые алгоритмы, такие как equal(), получают три итератора: первые два обозначают диапазон первой последовательности, а третий —
обозначает первый элемент во второй последовательности. Другие получают четыре итератора: первые два обозначают диапазон элементов в первой последовательности, а вторые два — диапазон второй последовательности.
Алгоритмы, использующие для обозначения второй последовательности один итератор, подразумевают , что вторая последовательность по крайней мере не меньше первой.
Разработчик должен сам позаботиться о том, чтобы алгоритм не пытался обратиться к несуществующим элементам во второй последовательности. Например, алгоритм equal()
сравнивает каждый элемент первой последовательности с соответствующим элементом второй. Если вторая последовательность является подмножеством первой, то возникает серьезная ошибка — функция equal() попытается обратиться к элементам после конца второй последовательности.
10.2.2. Алгоритмы, записывающие элементы контейнера
Некоторые алгоритмы способны записывать значения в элементы. Используя такие алгоритмы, следует соблюдать осторожность и предварительно удостовериться, что количество элементов, в которые алгоритм собирается внести изменения, по крайней мере не превосходит количество существующих элементов. Помните, что алгоритмы работают не с контейнерами, поэтому у них нет возможности самостоятельно изменить размер контейнера.
Некоторые алгоритмы осуществляют запись непосредственно в исходную последовательность. Эти алгоритмы в принципе безопасны: они способны переписать лишь столько элементов, сколько находится в указанном исходном диапазоне.
В качестве примера рассмотрим алгоритм fill(), получающий два итератора, обозначающих диапазон, и третий аргумент, являющийся значением. Функция fill() присваивает данное значение каждому элементу исходной последовательности: fill(vec.begin(), vec.end(), 0); // обнулить каждый элемент
// присвоить половине последовательности значение 10 fill(vec.begin(), vec.begin() + vec.size()/2, 10);
Поскольку функция fill() пишет в переданную ей исходную последовательность до тех пор,
пока она не закончится, запись вполне безопасна. Алгоритмы не проверяют операции записи
Некоторые алгоритмы получают итератор, обозначающий конкретное назначение. Эти алгоритмы присваивают новые значения элементам последовательности, начиная с элемента, обозначенного итератором назначения. Например, функция fill_n() получает один итератор, количество и значение. Она присваивает предоставленное значение заданному количеству элементов, начиная с элемента, обозначенного итератором. Функцию fill_n()
Page 480/1103

можно использовать для присвоения нового значения элементам вектора: vector<int> vec; // пустой вектор
// используя вектор vec, предоставить ему разные значения fill_n(vec.begin(), vec.size(), 0); // обнулить каждый элемент vec
Функция fill_n() подразумевала, что безопасно запишет указанное количество элементов.
Таким образом, следующий вызов функции fill_n() подразумевает, что dest указывает на существующий элемент и что в последовательности есть по крайней мере n элементов,
начиная с элемента dest. fill_n(dest, n, val)
Это вполне обычная ошибка для новичка: вызов функции fill_n() (или подобного алгоритма записи элементов) для контейнера без элементов: vector<int> vec; // пустой вектор
// катастрофа: попытка записи в 10 несуществующих элементов
// вектора vec fill_n(vec.begin(), 10, 0);
Этот вызов функции fill_n() ведет к катастрофе. Должно быть записано десять элементов, но вектор vec пуст, и никаких элементов в нем нет. Результат непредсказуем, но, вероятнее всего, произойдет серьезный отказ во время выполнения.
Алгоритмы, осуществляющие запись по итератору назначения, подразумевают , что контейнер достаточно велик для содержания всех записываемых элементов.Функция back_inserter()
Один из способов проверки, имеет ли контейнер достаточно элементов для записи,
подразумевает использование итератора вставки (insert iterator), который позволяет добавлять элементы в базовый контейнер. Как правило, при присвоении значения элементу контейнера при помощи итератора осуществляется присвоение тому элементу, на который указывает итератор. При присвоении с использованием итератора вставки в контейнер добавляется новый элемент, равный правому значению.
Более подробная информация об итераторе вставки приведена в разделе 10.4.1. Однако для
Page 481/1103

иллюстрации безопасного применения алгоритмов, записывающих данные в контейнер,
используем функцию back_inserter(), определенную в заголовке iterator.
Функция back_inserter() получает ссылку на контейнер и возвращает итератор вставки,
связанный с данным контейнером. Попытка присвоения значения элементу при помощи этого итератора приводит к вызову функции push_back(), добавляющей элемент с данным значением в контейнер. vector<int> vec; // пустой вектор auto it = back_inserter(vec); // присвоение при помощи it добавляет
// элементы в vec
*it = 42; // теперь vec содержит один элемент со значением 42
Функцию back_inserter() зачастую применяют для создания итератора, используемого в качестве итератора назначения алгоритмов. Рассмотрим пример: vector<int> vec; // пустой вектор
// ok: функция back_inserter() создает итератор вставки,
// который добавляет элементы в вектор vec fill_n(back_inserter(vec), 10, 0); // добавляет 10 элементов в vec
На каждой итерации функция fill_n() присваивает элемент заданной последовательности.
Поскольку ей передается итератор, возвращенный функцией back_inserter(), каждое присвоение вызовет функцию push_back() вектора vec. В результате этот вызов функции fill_n() добавит в конец вектора vec десять элементов, каждый со значением 0. Алгоритм copy()
Алгоритм copy() — это еще один пример алгоритма, записывающего элементы последовательности вывода, обозначенной итератором назначения. Этот алгоритм получает три итератора. Первые два обозначают исходный диапазон, а третий — начало последовательности вывода. Этот алгоритм копирует элементы из исходного диапазона в элементы вывода. Важно, чтобы переданный функции copy() контейнер вывода был не меньше исходного диапазона.
В качестве примера используем функцию copy() для копирования одного встроенного массива в другой:
Page 482/1103

int a1[] = {0,1,2,3,4,5,6,7,8,9}; int а2[sizeof(a1)/sizeof(*a1)]; // a2 имеет тот же размер, что и a1
// указывает на следующий элемент после последнего скопированного в а2 auto ret = copy(begin(a1), end(a1), a2); // копирует a1 в a2
Здесь определяется массив по имени a2, а функция sizeof() используется для гарантии равенства размеров массивов а2 и a1 (см. раздел 4.9). Затем происходит вызов функции copy() для копирования массива a1 в массив а2. После вызова у элементов обоих массивов будут одинаковые значения.
Возвращенное функцией copy() значение является приращенным значением ее итератора назначения. Таким образом, итератор ret укажет на следующий элемент после последнего скопированного в массив а2.
Некоторые алгоритмы обладают так называемой версией "копирования". Эти алгоритмы осуществляют некую обработку элементов исходной последовательности, но саму последовательность не изменяют. Они могут создавать новую последовательность, в которую и сохраняют результат обработки элементов исходной.
Например, алгоритм replace() читает последовательность и заменяет каждый экземпляр заданного значения другим значением. Алгоритм получает четыре параметра: два итератора,
обозначающих исходный диапазон, и два значения. Он заменяет вторым значением значение каждого элемента, которое равно первому.
// заменить во всех элементах значение 0 на 42 replace(ilst.begin(), ilst.end(), 0, 42);
Этот вызов заменяет все экземпляры со значением 0 на 42. Если исходную последовательность следует оставить неизменной, необходимо применить алгоритм replace_copy(). Этой версии функции передают третий аргумент: итератор, указывающий получателя откорректированной последовательности.
// использовать функцию back_inserter() для увеличения контейнера
// назначения до необходимых размеров replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);
После этого вызова список ilst останется неизменным, а вектор ivec будет содержать копию его элементов, но со значением 42 вместо 0.
Page 483/1103

10.2.3. Алгоритмы, переупорядочивающие элементы контейнера
Некоторые алгоритмы изменяют порядок элементов в пределах контейнера. Яркий пример такого алгоритма — sort(). Вызов функции sort() упорядочивает элементы исходного диапазона в порядке сортировки, используя оператор < типа элемента.
Предположим, необходимо проанализировать слова, использованные в наборе детских рассказов. Текст рассказов содержится в векторе. Необходимо сократить этот вектор так,
чтобы каждое слово присутствовало в нем только один раз, независимо от того, сколько раз оно встречается в любом из данных рассказов.
Для иллюстрации поставленной задачи используем в качестве исходного текста следующую простую историю: the quick red fox jumps over the slow red turtle
В результате обработки этого текста программа должна создать следующий вектор:
Устранение дубликатов
Для устранения повторяющихся слов сначала отсортируем вектор так, чтобы дубликаты располагались рядом друг с другом. После сортировки вектора можно использовать другой библиотечный алгоритм, unique(), чтобы расположить уникальные элементы в передней части вектора. Поскольку алгоритмы не могут работать с самими контейнерами, используем функцию-член erase() класса vector для фактического удаления элементов: void elimDups(vector<string> &words) {
// сортировка слов в алфавитном порядке позволяет найти дубликаты sort(words.begin(), words.end());
// функция unique() переупорядочивает исходный диапазон так, чтобы
// каждое слово присутствовало только один раз в начальной части
// диапазона, и возвращает итератор на элемент, следующий после
// диапазона уникальных значений auto end_unique = unique(words.begin(), words.end());
// для удаления не уникальных элементов используем
// функцию erase() вектора
Page 484/1103

words.erase(end_unique, words.end());
}
Алгоритм sort() получает два итератора, обозначающих диапазон элементов для сортировки.
В данном случае сортируется весь вектор. После вызова функции sort() слова упорядочиваются так:
Обратите внимание: слова red и the встречаются дважды. Алгоритм unique()
После сортировки слов необходимо оставить только один экземпляр каждого из них.
Алгоритм unique() перестраивает исходный диапазон так, чтобы устранить смежные повторяющиеся элементы, и возвращает итератор, обозначающий конец диапазона уникальных значений. После вызова функции unique() вектор выглядит так:
Размер вектора words не изменился: в нем все еще десять элементов. Изменился только порядок этих элементов — смежные дубликаты были как бы "удалены". Слово удалены заключено в кавычки потому, что функция unique() не удаляет элементы. Она переупорядочивает смежные дубликаты так, чтобы уникальные элементы располагались в начале последовательности. Возвращенный функцией unique() итератор указывает на следующий элемент после последнего уникального. Последующие элементы все еще существуют, но их значение уже не важно.
Библиотечные алгоритмы работают с итераторами, а не с контейнерами. Поэтому алгоритм не может непосредственно добавить или удалить элементы. Применение функций контейнера для удаления элементов
Для фактического удаления неиспользуемых элементов следует использовать контейнерную функцию erase() (см. раздел 9.3.3). Удалению подлежит диапазон элементов от того, на который указывает итератор end_unique, и до конца контейнера words. После вызова контейнер words содержит восемь уникальных слов из исходного текста.
Следует заметить, что вызов функции erase() окажется безопасным, даже если вектор не содержит совпадающих слов. В этом случае функция unique() возвратит итератор,
совпадающий с возвращенным функцией word.end(). Таким образом, оба аргумента функции erase() будут иметь одинаковое значение, а следовательно, обрабатываемый ею диапазон окажется пустым. Удаление пустого диапазона не приводит ни к какому результату, поэтому программа будет работать правильно даже тогда, когда в исходном тексте нет повторяющихся слов. Упражнения раздела 10.2.3
Упражнение 10.6. Напишите программу, использующую функцию fill_n() для обнуления последовательности целых чисел.
Упражнение 10.7. Определите, есть ли ошибки в следующих фрагментах кода, и, если есть,
как их исправить:
(a) vector<int> vec; list<int> lst; int i; while (cin >> i) lst.push_back(i); copy(lst.cbegin(), lst.cend(), vec.begin());
Page 485/1103

(b) vector<int> vec; vec.reserve(10); // reserve рассматривается в разделе 9.4 fill_n(vec.begin(), 10, 0);
Упражнение 10.8. Как упоминалось, алгоритмы не изменяют размер контейнеров, с которыми они работают. Почему использование функции back_inserter() не противоречит этому утверждению?
Упражнение 10.9. Реализуйте собственную версию функции elimDups(). Проверьте ее в программе, выводящей содержимое вектора после чтения ввода, после вызова функции unique() и после вызова функции erase().