Предпочитайте алгоритмы циклам.

(— Бьярн Страуструп (Bjarne Stroustrup),) ([Stroustrup00] §18.12)

Алгоритмы представляют собой циклы — только они лучше циклов. Алгоритмы — это "шаблоны" циклов, с добавлением дополнительной семантики по сравнению с простыми

for

do

В этом разделе мы считаем наиболее значимой рекомендацию 83 — "Используйте отладочную реализацию STL".

Безопасность превыше всего (см. рекомендацию 6). Используйте отладочную реализацию STL[4], даже если она имеется только для одного из ваших компиляторов, и даже если она используется только для отладочного тестирования.

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

Ряд ошибок при работе с STL часто допускают даже опытные программисты.

• Использование недействительных или неинициализированных итераторов. В особенности легко допустить первое.

• Передача индекса, выходящего за границы контейнера. Например, обращение к 113-му элементу 100-элементного контейнера.

• Использование "диапазона" итераторов, который на самом деле не является диапазоном. Например, передача двух итераторов, первый из которых не предшествует второму, или когда они указывают на разные контейнеры.

• Передача неверной позиции итератора. Вызов функции-члена контейнера, которая получает позицию итератора (как, например, позиция, передаваемая функции

insert

• Использование неверного упорядочения. Предоставление неверного правила для упорядочения ассоциативного контейнера или в качестве критерия сравнения в алгоритме сортировки (см. примеры в [Meyers01]). Если не использовать отладочной версии STL, такие ошибки обычно проявляются в процессе выполнения программы как неверное поведение или бесконечные циклы, но не как аварийный останов.

Большинство отладочных реализаций STL автоматически обнаруживают такие ошибки, при помощи дополнительной отладочной и системной информации, хранящейся в контейнерах и итераторах. Например, итератор может запомнить контейнер, к которому он обращается, а контейнер — запомнить все итераторы, ссылающиеся на него, так что можно отследить использование ставшего недействительным итератора. Конечно, это увеличивает размер итераторов и контейнеров, а также требует выполнения дополнительных действий при каждом изменении контейнера. Но возможность отслеживания ошибок стоит того — по крайней мере, в процессе отладки, а возможно, и в окончательной версии программы (вспомните рекомендацию 8; не отключайте полезные проверки для повышения производительности до тех пор, пока не убедитесь в необходимости такого шага непосредственными измерениями).

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

Пример 1. Использование недействительного итератора. Очень просто забыть, что итераторы стали недействительны, и воспользоваться таким недействительным итератором (см. рекомендацию 99). Рассмотрим подобный пример, адаптированный из [Meyers01], где происходит вставка элементов в начало

deque

deque<double>::iterator current = d.begin();

for (size_t i =0; i < max; ++i )

 d.insert(current++, data[i] + 41); // Видите ли вы ошибку?

Быстро ответьте — увидели ли вы ошибку в приведенном фрагменте или нет? У вас только три секунды!

Время вышло! Если вы не заметили ошибку за отпущенное время, не волнуйтесь — это достаточно тонкая и понятная ошибка. Отладочная версия STL обнаружит данную ошибку на второй итерации цикла, так что вам не придется полагаться на свой невооруженный взгляд. (Исправленная версия данного кода и альтернативные варианты вы найдете в рекомендации 84.)

Пример 2. Использование диапазона итераторов, на самом деле не являющегося диапазоном. Диапазон итераторов представляет собой пару итераторов

first

last

last

first

first

second

for_each(c.end(),с.begin(),Something); // не всегда очевидно

На каждой итерации своего внутреннего цикла алгоритм

for_each

first

first

first

second

Вторая распространенная ошибка возникает, когда итераторы указывают в разные контейнеры:

for_each(c.begin(),d.end(),Something); // не всегда очевидно

Результат такой ошибки аналогичен результату предыдущей. Однако поскольку итераторы отладочной версии STL помнят контейнер, с которым работают, такую ошибку можно выявить во время выполнения программы.

[Dinkumware-Safe] • [Horstmann95] • [Josuttis99] §5.11.1 • [Metrowerks] • [Meyers01] §21, §50 • [STLport-Debug] • [Stroustrup00] §18.3.1, §19.3.1

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

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

bind2nd

plus

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

Главное преимущество алгоритмов и шаблонов проектирования в общем случае заключается в том, что они позволяют нам говорить на более высоком уровне абстракции. В современном программировании мы не говорим "пусть несколько объектов следят за одним объектом и получают автоматические уведомления при изменении его состояния". Вместо этого мы говорим просто о "шаблоне проектирования Observer". Аналогично, мы говорим "Bridge", "Factory" и "Visitor". Использование словаря шаблонов проектирования позволяет повысить уровень, эффективность и корректность нашего обсуждения. Точно так же при использовании алгоритмов мы не говорим "выполняем действие над каждым элементом диапазона и записываем результат в некоторое место"; вместо этого мы говорим просто —

transform

for_each

replace_if

partition

for

while

Алгоритмы обычно более корректны, чем циклы. В разрабатываемых самостоятельно циклах легко допустить ошибку, например, такую как использование недействительных итераторов (см. рекомендации 83 и 99); алгоритмы в библиотеке отлажены на предмет использования недействительных итераторов и других распространенных ошибок.

И наконец, алгоритмы зачастую также более эффективны, чем простые циклы (см. [Sutter00] и [Meyers01]). В них устранены небольшие неэффективности, такие как повторные вычисления

container.end()

Подумайте об использовании лямбда-функций [Boost]. Лямбда-функции представляют собой важный инструмент, который позволяет справиться с основным недостатком алгоритмов, а именно с удобочитаемостью. Без их применения вы должны использовать либо функциональные объекты (но тогда тела даже простых циклов находятся в отдельном месте, далеко от точки вызова), либо стандартные связыватели и функциональные объекты наподобие

bind2nd

plus

Вот два примера, адаптированных из [Meyers01].

Пример 1. Преобразование

deque

doublе

deque<doublе>

deque<double>::iterator current = d.begin();

for (size_t i =0; i < max; ++i) {

 // Сохраняем current действительным

 current = d.insert(current, data[i] + 41);

 ++current; // Увеличиваем его, когда это

}           // становится безопасным

Вызов алгоритма позволяет легко обойти все ловушки в этом коде:

transform(

 data.begin(), data.end(),    // Копируем элементы

 data inserter(d, d.begin()), // в d с начала контейнера,

 bind2nd(plus<double>(),41)); // добавляя к каждому 41

Впрочем,

bind2nd

plus

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

transform(data, data+max, inserter(d,d.begin()), _1 + 41);

Пример 2. Найти первый элемент между

x

у

vector<int> v

x

y

v.end()

vector<int>::iterator i = v.begin();

for (; i != v.end(); ++i)

 if (*i > x && *i < y) break;

Вызов алгоритма достаточно проблематичен. При отсутствии лямбда-функций у нас есть два варианта — написание собственного функционального объекта или использование стандартных связывателей. Увы, в последнем случае мы не можем обойтись только стандартными связывателями и должны использовать нестандартный (хотя и достаточно распространенный) адаптер

compose2

vector<int>::iterator i =

 find_if(v.begin(), v.end(),

 compose2(logical_and<bool>(),

 bind2nd(greater<int>(), x), bind2nd(less<int>(), y)));

Другой вариант, а именно — написание собственного функционального объекта — достаточно жизнеспособен. Он достаточно хорошо выглядит в точке вызова, а главный его недостаток— необходимость написания функционального объекта

BetweenValues

template<typename T>

class BetweenValues : public unary_function<T, bool> {

public:

 BetweenValues(const T& low, const T& high)

  : low_(low), high_(high) { }

 bool operator()(const T& val) const

  { return val > low_ && val < high_; }

private:

 T low_, high_;

};

vector<int>::iterator i =

 find_if( v.begin(), v.end(), BetweenValues<int>(x, y));

При применении лямбда-функций можно написать просто:

vector<int>::iterator i =

 find_if(v.begin(), v.end(), _1 > x && _1 < y);

При использовании функциональных объектов тело цикла оказывается размещено в некотором месте, удаленном от точки вызова, что затрудняет чтение исходного текста. (Использование простых объектов со стандартными и нестандартными связывателями представляется нереалистичным.)

Лямбда-функции [Boost] решают проблему и надежно работают на современных компиляторах, но они не годятся для более старых компиляторов и могут выдавать большие запутанные сообщения об ошибках при некорректном использовании. Вызов же именованных функций, включая функции-члены, все равно требует синтаксиса с использованием связывателей.

[Allison98] §15 • [Austern99] §11-13 • [Boost] Lambda library • [McConnell93] §15 • [Meyers01] §43 • [Musser01] §11 • [Stroustrup00] §6.1.8, §18.5.1 • [Sutter00] §7

Данная рекомендация применима к поиску определенного значения в диапазоне. При поиске в неотсортированном диапазоне используйте алгоритмы

find

find_if

count

count_if

lower_bound

upper_bound

equal_range

binary_search

binary_search

В случае неотсортированных диапазонов,

find

find_if

count

count_if

find

find_if

В случае сортированных диапазонов лучше использовать алгоритмы бинарного поиска —

binary_search, lower_bound

upper_bound

equal_range

binary_search

типа

lower_bound

upper_bound

equal_range

lower_bound

upper_bound

Алгоритм

lower_bound

upper_bound

Для сортированных диапазонов в качестве быстрой версии

count(first, last, value);

p = equal_range(first, last, value);

distance(p.first, p.second);

При поиске в ассоциативном контейнере лучше использовать вместо алгоритмов-не членов функции-члены с тем же именем. Функции-члены обычно более эффективны; например, функция-член

count

equal_range

[Austern99] §13.2-3 • [Bentley00] §13 • [Meyers01] §34, §45 • [Musser01] §22.2 • [Stroustrup00] §17.1.4.1, §18.7.2

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

Вам не всегда требуется полный

sort

partition

stable_partition

nth_element

partial_sort

partial_sort_copy

sort

stable_sort

Время работы алгоритмов

partition

stable_partition

nth_element

Алгоритмы

nth_element

partial_sort

sort

stable_sort

list<T>::iterator

Версии

stable_

partial_sort

nth_element

stable_sort

Само собой разумеется, не следует прибегать ни к каким алгоритмам сортировки, если вы можете обойтись без них. Если вы пользуетесь стандартным ассоциативным контейнером (

set

multiset

map

multimap

priority_queue

Пример 1.

partition

partition

• Кто из студентов имеет средний бал не ниже 4.5? Для ответа на этот вопрос можно воспользоваться вызовом

partition(students.begin(), students.end(), GradeAtLeast(4.5));

• Какие из товаров имеют вес менее 10 кг? Вызов

partition(products.begin(), products.end(), WeightUnder(10));

Пример 2.

nth_element

nth_element

• Перечислите 20 лучших покупателей. Вызов

nth_element(s.begin(), s.begin()+19, s.end(), SalesRating);

• Какое изделие имеет медианное значение качества в данном наборе? Искомый элемент находится в средней позиции отсортированного диапазона. Для его поиска достаточно вызова

nth_element(run.begin(), run.begin() + run.size()/2, run.end(), itemQuality);

• У какого изделия уровень качества находится на 75-м перцентиле? Искомый элемент находится в позиции, отстоящей на 25% от начала отсортированного диапазона. Для его поиска достаточно вызова

nth_element(run.begin(), run.begin()+run.size()*.25, run.end(), ItemQuality);

Пример 3.

partial_sort

partial_sort

nth_element

partial_sort

nth_element

partial_sort(contestants.begin(), contestants.begin()+3, contestants.end(), ScoreCompare);

Хотя обычно алгоритм

partial_sort

sort

[Austern99] §13.1 • [Bentley00] §11 • [Josuttis99] §9.2.2 • [Meyers01] §31 • [Musser01] §5.4, §22.26 • [Stroustrup00] §17.1.4.1, §18.7

Предикат представляет собой функциональный объект, который возвращает ответ да/нет, обычно в виде значения типа

bool

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

operator()

operator()

Алгоритмы создают неизвестное количество копий предикатов в неизвестные моменты времени и в неизвестном порядке, так что приходится полагаться на то, что все копии эквивалентны.

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

operator()

Предикаты с состояниями могут показаться полезными, но они явно не очень полезны при использовании с алгоритмами стандартной библиотеки С++, и это сделано преднамеренно. В частности, предикаты с состояниями могут быть полезны только при выполнении ряда условий.

• Предикат не копируется. Стандартные алгоритмы не дают такой гарантии; в действительности алгоритмы, напротив, предполагают, что предикаты могут безопасно копироваться.

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

Первое условие можно обойти, написав предикат с использованием счетчика ссылок. Этот метод решает проблему копирования предикатов, поскольку в таком случае предикаты могут безопасно копироваться без изменения их семантики при применении к объектам (см. [Sutter02]). Однако обойти второе условие оказывается невозможно.

Всегда объявляйте оператор предиката

operator()

Пример.

FlagNth

v

class FlagNth {

public:

 FlagNth(size_t n) : current_(0), n_(n) { }

 // Возвращаем значение true только при третьем вызове

 template<typename T>

 bool operator()(const T&)     // Плохо: неконстантная

  { return ++current_ == n_; } // функция

private:

 size_t current_, n_;

};

// ... позже ...

v.erase(remove_if(v.begin(), v.end(), FlagNth(3)));

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

remove_if

find_if

remove_copy_if

Концептуально этот пример неверен, поскольку алгоритм

remove_if

Корректный способ удаления третьего элемента — выполнить итерации для его поиска и вызвать функцию

erase

[Austern99] §4.2.2 • [Josuttis99] §5.8.2, §8.1.4 • [Meyers01] §39 • [Stroustrup00] §10.2.6 • [Sutter02] §2-3

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

Во-первых, функциональные объекты легко сделать адаптируемыми (и такими их и следует делать — см. рекомендацию 89). Даже если у вас есть готовая функция, иногда для ее использования требуется "обертка" из

ptr_fun

mem_fun

inline bool isHeavy(const Thing&) { /* ... */ }

find_if(v.begin(), v.end(), not1(IsHeavy)); // Ошибка

Обойти эту ошибку обычно можно путем применения

ptr_fun

mem_fun

mem_fun_ref

inline bool IsHeavy(const Thing&) { /* ... */ }

find_if(v.begin(), v.end(),

 not1(ptr_fun(IsHeavy))); // Героическая попытка...

Беда в том, что этот способ не будет работать, даже если вы явно укажете аргументы шаблона

ptr_fun

ptr_fun

const Thing&

&

Прибегать ко всем этим ухищрениям совершенно излишне, если у вас имеется корректно написанный функциональный объект (см. рекомендацию 89), который можно использовать без какого-либо специального синтаксиса:

struct IsHeavy : unary_function<Thing, bool> {

 bool operator()(const Thing&) const { /* ... */ }

};

find_if(v.begin(), v.end(), not1(IsHeavy())) ; // OK

Еще более важно то, что для определения сравнения в ассоциативных контейнерах вам нужен именно функциональный объект, а не функция. Это связано с тем, что нельзя инстанцировать шаблон с функцией в качестве параметра:

bool CompareThings(const Thing&, const Thing&);

set<Thing, CompareThings> s; // Ошибка

Вместо этого следует написать:

struct CompareThings

 : public binary_function<Thing,Thing,bool> {

 bool operator()( const Thing&, const Thing& ) const;

};

set<Thing, CompareThings> s; //OK

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

template<typename Iter, typename Compare>

Iter find_if(Iter first, Iter last, Compare comp);

Если мы передадим алгоритму в качестве компаратора функцию

inline bool Function(const Thing&) { /* ... */ }

find_if(v.begin(), v.end(), Function);

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

find_if

Давайте передадим алгоритму

find_if

struct FunctionObject : unary_function<Thing, bool> {

 bool operator()(const Thing&) const { /* ... */ }

};

find_if(v.begin(), v.end(), FunctionObject());

Если мы передаем объект, который имеет (явно или неявно) встраиваемый оператор

operator()

Примечание. Эта методика не является преждевременной оптимизацией (см. рекомендацию 8); ее следует рассматривать как препятствие преждевременной пессимизации (см. рекомендацию 9). Если у вас имеется готовая функция — передавайте указатель на нее (кроме тех ситуаций, когда вы должны обязательно обернуть ее в

ptr_fun

mem_fun

[Austern99] §4, §8, §15 • [Josuttis99] §5.9 • [Meyers01] §46 • [Musser01] §8 • [Sutter04] §25

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

unary_function

binary_function

Функциональные объекты моделируют указатели на функции. Подобно указателям на функции, они обычно передаются в функции по значению. Все стандартные алгоритмы передают объекты по значению, и то же должны делать и ваши алгоритмы, например:

template<class InputIter, class Func>

Function for_each(InputIter first, InputIter last, Function f);

Следовательно, функциональные объекты должны легко копироваться и быть мономорфными (для защиты от срезки), так что избегайте виртуальных функций (см. рекомендацию 54). Конечно, у вас могут быть большие и/или полиморфные функциональные объекты — их тоже вполне можно использовать; просто скройте их размер с помощью идиомы Pimpl (указателя на реализацию; см. рекомендацию 43). Эта идиома позволяет, как и требуется, получить внешний мономорфный класс малого размера, обеспечивающий доступ к богатой функциональности. Внешний класс должен удовлетворять следующим условиям.

• Быть адаптируемым. Наследуйте его от

unary_function

binary_function

• Использовать идиому Pimpl. Такой класс содержит указатель (например,

shared_ptr

• Иметь оператор(ы) вызова функции. Эти операторы передают вызовы объекту-реализации.

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

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

typedef

unary_function

binary_function

unary_function

binary_function

operator()

const

&

Постарайтесь избежать наличия нескольких операторов

operator()

typedef

typedef

operator()

Не все функциональные объекты являются предикатами — предикаты представляют собой подмножество функциональных объектов (см. рекомендацию 87).

[Allison98] §15, §C • [Austern99] §4, §8, §15 • [Gamma95] Bridge • [Josuttis99] §8.2.4 • [Koenig97] §21, §29 • [Meyers97] §34 • [Meyers01] §38, §40, §46 • [Musser01] §2.4, §8, §23 • [Sutter00] §26-30 • [Vandevoorde03] §22

Примечания:

4

Checked implementation — под этим подразумевается реализация STL с дополнительными проверками в коде, необязательными с точки зрения стандарта. — Прим. перев.