Напишите алгоритм в виде шаблона функции и с помощью имен параметров шаблона укажите свои требования к итератору. В примере 7.10 показан измененный стандартный алгоритм
сору
.
Пример 7.10. Написание собственного алгоритма
#include <iostream>
#include <istream>
#include <iterator>
#include <string>
#include <functional>
#include <vector>
#include <list>
#include "utils.h" // Для printContainer: см. 7.10
using namespace std;
template<typename In, typename Out, typename UnPred>
Out copyIf(In first, In last, Out result, UnPred pred) {
for ( ; first != last; ++first)
if (pred(*first)) *results = *first;
return(result);
}
int main {
cout << "Введите
несколько строк: ";
istream_iterator<string> start(cin);
istream_iterator<string> end; // Здесь создается "маркер"
Введите несколько строк: apple banana danish eclaire
^Z
– ----
apple banana
Вы видите, что он копирует в результирующий диапазон только те значения, которые меньше, чем «cookie».
Обсуждение
Стандартная библиотека содержит шаблон функции
сору
, который копирует элементы из одного диапазона в другой, но нет стандартной версии, которая принимает предикат и выполняет условное копирование элементов (т.е. алгоритм
copy_if
), так что пример 7.10 делает именно это. Его поведение довольно просто: при наличии диапазона-источника и начала диапазона-приемника производится копирование в целевой диапазон элементов, для которых унарный функтор-предикат возвращает
true
.
Этот алгоритм прост, но в его реализации есть еще кое-что, что привлекает внимание. Посмотрев на объявление, вы увидите, что в нем присутствует три параметра шаблона.
template<typename In, typename Out, typename UnPred>
Out copyIf(In first, In last, Out result UnPred pred) {
Первый параметр шаблона
In
— это тип входного итератора. Так как это входной диапазон, все, что должен иметь возможность сделать с ним
copyIf
, — это извлечь разыменованное значение этого итератора и перевести итератор на следующий элемент. Это дает описание категории итератора ввода (категории итераторов описаны в рецепте 7.1), так что с помощью указания имени параметра шаблона
In
мы объявляем именно этот тип итератора. Стандартного соглашения здесь нет (
In
и
Out
— это мои соглашения, которые я описал в первом рецепте этой главы), но вы легко можете придумать свои собственные соглашения об именах:
InIter
,
Input_T
или даже
InputIterator.
Второй параметр шаблона
Out
— это тип итератора, который указывает на диапазон, в который будут копироваться элементы,
copyIf
должен иметь возможность записать разыменованное значение в выходной итератор и увеличить его значение, что дает нам описание оператора вывода. Объявив требования к итераторам с помощью имен параметров шаблона, вы делаете соглашения о вызовах алгоритма понятными без документации. Но зачем использовать две разные категории итераторов?
Имеется, по крайней мере, две причины использования в
copyIf
двух различных категорий итераторов. Во-первых, операции с каждым диапазоном несколько отличаются друг от друга, и так как мне никогда не потребуется возвращаться назад по входному диапазону или присваивать ему значения, все, что мне требуется, — это итератор ввода. Аналогично мне никогда не потребуется читать из выходного диапазона, так что
все, что здесь требуется, — это итератор вывода. Имеются требования к каждому из итераторов, которые не применимы к другому итератору, так что нет никакого смысла использовать для обоих диапазонов, например, два двунаправленных итератора. Во-вторых, использование различных типов итераторов позволяет вызывающему коду читать из одного типа диапазона и записывать в другой. В примере 7.10 я читаю из
Если попробовать сделать то же самое, использовав в алгоритме один и тот же тип итераторов, то он просто не скомпилируется.
В примере 7.10 я в качестве начала выходного диапазона передаю
back_inserter
, а не, скажем, итератор, возвращаемый
lst.begin
. Это делается потому, что lst не содержит элементов, и в этом алгоритме (как и в стандартном алгоритме копирования) целевой диапазон должен быть достаточно большим, чтобы вместить все элементы, которые будут в него скопированы. В противном случае увеличение итератора вывода в
copyIf
приведет к неопределенному поведению.
back_inserter
возвращает итератор вывода, который при его увеличении вызывает для контейнера метод
push_back
. В результате этого при каждом увеличении выходного итератора размер
lst
увеличивается на один. Более подробно шаблон класса
back_inserter
я описываю в рецепте 7.5.
При написании собственного алгоритма для работы с диапазонами (т.е. со стандартными контейнерами) вы должны работать с аргументами-итераторами, а не с аргументами-контейнерами. У вас может возникнуть желание объявить
copyIf
так, чтобы он принимал два контейнера, а не итератор исходного и результирующего диапазонов, но это менее обобщенное решение, чем диапазоны. Во-первых, если передавать аргументы-контейнеры, то станет невозможно работать с подмножеством элементов контейнера. Далее, в теле
copyIf
появится зависимость от методов контейнеров
begin
и
end
, которые дадут требуемый диапазон, и возвращаемый тип будет зависеть от типа контейнера, используемого в качестве выходного. Это означает, что использование в
copyIf
нестандартных диапазонов, таких как встроенные массивы или собственные контейнеры, работать не будет. Именно по этим и некоторым другим причинам все стандартные алгоритмы оперируют с диапазонами.
Наконец, если вы пишете свой алгоритм, дважды убедитесь, что стандартные алгоритмы вас не устраивают. На первый взгляд они могут казаться очень простыми алгоритмами, но их кажущаяся простота проистекает из их обобщенности, и в девяти случаях из десяти их можно расширить так, что они подойдут для новых задач. Иногда следует стремиться к повторному использованию стандартных алгоритмов, так как это дает гарантию переносимости и эффективности.
Смотри также
Рецепт 7.5.
7.11. Печать диапазона в поток
Проблема
Имеется диапазон элементов, который требуется напечатать в поток, например, в
cout
с целью отладки.
Решение
Напишите шаблон функции, который принимает диапазон или контейнер, перебирает все его элементы и использует алгоритм
сору
и
ostream_iterator
для записи. Если требуется дополнительное форматирование, напишите свой простой алгоритм, который перебирает диапазон и печатает каждый элемент в поток. (См. пример 7.11)
Пример 7.11. Печать диапазона в поток
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;
int main {
// Итератор ввода - это противоположность итератору вывода: он
// читает элементы из потока так. как будто это контейнер.