Герб Саттер - Стандарты программирования на С++. 101 правило и рекомендация
• Предикаты используются в предопределенном документированном порядке. В общем случае стандартные алгоритмы не дают никакой гарантии относительно порядка применения предикатов к элементам диапазона. При отсутствии гарантий по поводу порядка обработки элементов, операция наподобие "пометить третий элемент" (см. примеры) имеет мало смысла, поскольку не определено, какой именно элемент будет обработан третьим.
Первое условие можно обойти, написав предикат с использованием счетчика ссылок. Этот метод решает проблему копирования предикатов, поскольку в таком случае предикаты могут безопасно копироваться без изменения их семантики при применении к объектам (см. [Sutter02]). Однако обойти второе условие оказывается невозможно.
Всегда объявляйте оператор предиката operator() как константную функцию-член, чтобы компилятор мог помочь вам избежать неприятностей, выводя сообщение об ошибке при попытках изменить любые данные-члены, которые могут быть у предиката. Это не позволяет пресечь все злоупотребления, например, доступ к глобальным данным, но, по крайней мере, поможет избежать наиболее распространенных ошибок.
ПримерыПример. FlagNth. Перед вами классический пример из [Sutter02], в котором выполняется попытка удалить третий элемент из контейнера 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
88. В качестве аргументов алгоритмов и компараторов лучше использовать функциональные объекты, а не функции
Предпочтительно передавать алгоритмам функциональные объекты, а не функции, а компараторы ассоциативных контейнеров просто должны быть функциональными объектами. Функциональные объекты адаптируемы и, вопреки ожиданиям, обычно дают более быстрый по сравнению с функциями код.
ОбсуждениеВо-первых, функциональные объекты легко сделать адаптируемыми (и такими их и следует делать — см. рекомендацию 89). Даже если у вас есть готовая функция, иногда для ее использования требуется "обертка" из ptr_fun или mem_fun. Например, такая обертка требуется при построении более сложных выражений с использованием связывателей (см. также рекомендацию 84):
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&) и создает внутренний механизм, который, в свою очередь, пытается добавить другой &, а ссылка на ссылку в настоящее время в C++ не разрешена. Имеются способы исправлений языка и/или библиотека для решения данной проблемы (например, позволяя ссылке на ссылку свернуться в обычную ссылку; см. также рекомендацию 89), но на сегодняшний день проблема остается нерешенной.
Прибегать ко всем этим ухищрениям совершенно излишне, если у вас имеется корректно написанный функциональный объект (см. рекомендацию 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
89. Корректно пишите функциональные объекты
Разрабатывайте функциональные объекты так, чтобы их копирование выполнялось как можно эффективнее. Там, где это возможно, делайте их максимально адаптируемыми путем наследования от 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) на (возможно, большого размера) реализацию необходимой функциональности.
• Иметь оператор(ы) вызова функции. Эти операторы передают вызовы объекту-реализации.
