Эффективное использование STL

Мейерс Скотт

Правильная реализация

copy_if

должна выглядеть так:

template<typename InputIterator, // Правильная

 typename OutputIterator, // реализация copy_if

 typename Predicate>

OutputIterator copy_if(InputIterator begin, InputIterator end,

 OutputIterator destBegin, Predicate p) {

 while (begin != end) {

if (p(*begin)) *destBegn++ = *begin;

++begin;

 }

 return destBegn;

}

Поскольку

алгоритм

copy_if

чрезвычайно полезен, а неопытные программисты STL часто полагают, что он входит в библиотеку, можно порекомендовать разместить реализацию

copy_if

— правильную реализацию! — в локальной вспомогательной библиотеке и использовать ее в случае надобности.

Совет 37. Используйте accumulate или for_each для обобщения интервальных данных

Иногда возникает необходимость свести целый интервал к одному числу или, в более общем случае, к одному объекту. Для стандартных задач обобщения существуют специальные алгоритмы. Так, алгоритм

count

возвращает количество элементов в интервале, а алгоритм

count_if

возвращает количество элементов, соответствующих заданному предикату. Минимальное и максимальное значение элемента в интервале можно получить при помощи алгоритмов

min_element

и

max_element

.

Но в некоторых ситуациях возникает необходимость обработки интервальных данных по нестандартным критериям, и в таких случаях нужны более гибкие и универсальные средства, нежели алгоритмы

count

,

count_if

,

min_element

и

max_element

. Предположим, вы хотите вычислить сумму длин строк в контейнере, произведение чисел из заданного интервала, усредненные координаты точек и т. д. В каждом из этих случаев производится обобщение интервала, но при этом критерий обобщения вы должны определять самостоятельно. Для подобных ситуаций в STL предусмотрен специальный алгоритм

accumulate

. Многим программистам этот алгоритм незнаком, поскольку в отличие от большинства алгоритмов он не находится в

<algorthm>

, а вместе с тремя другими «числовыми алгоритмами» (

inner_product

,

adjacent_difference

и

partial_sum

) выделен в библиотеку

<numeric>

.

Как и многие другие алгоритмы,

accumulate

существует в двух формах. Первая форма, получающая пару итераторов и начальное значение, возвращает начальное значение в сумме со значениями из интервала, определяемого итераторами:

list<double> ld; // Создать список и заполнить

// несколькими значениями типа double.

double sum = accumulate(ld.begin, ld.end, 0.0); // Вычислить сумму чисел

// с начальным значением 0.0

Обратите внимание: в приведенном примере начальное значение задается в форме 0.0. Эта подробность важна. Число 0.0 относится к типу

double

, поэтому

accumulate

использует для хранения вычисляемой суммы переменную типа

double

. Предположим, вызов выглядит следующим образом:

double sum = accumulate(ld.begin, ld.end, 0); // Вычисление суммы чисел

// с начальным значением 0;

// неправильно!

В качестве начального значения используется int 0, поэтому accumulate накапливает вычисляемое значение в переменной типа

int

. В итоге это значение будет возвращено алгоритмом

accumulate

и использовано для инициализации переменной

sum

. Программа компилируется и работает, но значение

sum

будет неправильным. Вместо настоящей суммы списка чисел типа double переменная содержит сумму всех чисел, преобразуемую к

int

после каждого суммирования.

Алгоритм

accumulate

работает только с итераторами ввода и поэтому может использоваться даже с

istream_iterator

и

istreambuf_iterator

(см. совет 29):

cout << "The sum of the ints on the standard input is " // Вывести сумму

 << accumulate(istream_iterator<int>(cin), // чисел из входного

 istream_iterator<int>, // потока

 0);

Из-за своей первой, стандартной формы алгоритм

accumulate

был отнесен к числовым алгоритмам. Но существует и другая, альтернативная форма, которой при вызове передается начальное значение и произвольная обобщающая функция. В этом варианте алгоритм

accumulate

становится гораздо более универсальным.

В качестве примера рассмотрим возможность применения

accumulate

для вычисления суммы длин всех строк в контейнере. Для вычисления суммы алгоритм должен знать две вещи: начальное значение суммы (в данном случае 0) и функцию обновления суммы для каждой новой строки. Следующая функция берет предыдущее значение суммы, прибавляет к нему длину новой строки и возвращает обновленную сумму:

string::size_type // См. далее

stringLengthSum(string::size_type sumSoFar, const string& s) {

 return sumSoFar + s.size;

}

Тело функции убеждает в том, что происходящее весьма тривиально, но на первый взгляд смущают объявления

string::size_type

. На самом деле в них нет ничего страшного. У каждого стандартного контейнера STL имеется определение типа

size_type

, относящееся к счетному типу данного контейнера. В частности, значение этого типа возвращается функцией size. Для всех стандартных контейнеров определение

size_type

должно совпадать с

size_t

, хотя теоретически нестандартные STL-совместимые контейнеры могут использовать в

size_type

другой тип (хотя я не представляю, для чего это может понадобиться). Для стандартных контейнеров запись контейнер

::size_type

можно рассматривать как специальный синтаксис для

size_t

.