Алгоритмы представляют собой циклы — только они лучше циклов. Алгоритмы — это "шаблоны" циклов, с добавлением дополнительной семантики по сравнению с простыми for и do. Конечно, начав использовать алгоритмы, вы начнете использовать и функциональные объекты и предикаты; корректно пишите их и широко используйте в своих программах.

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

 

83. Используйте отладочную реализацию STL

Резюме

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

Обсуждение

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

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

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

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

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

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

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

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

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

Примеры

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

deque::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. Известны два распространенных вида ошибки, когда происходит попытка использовать диапазон, который на самом деле диапазоном не является. Первая ошибка возникает, когда два итератора ограничивают диапазон в пределах одного контейнера, но итератор first на самом деле не предшествует итератору second:

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

На каждой итерации своего внутреннего цикла алгоритм for_each будет проверять итератор first на равенство итератору second, и до тех пор, пока они не равны, он будет увеличивать итератор 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

 

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

Резюме

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

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

Обсуждение

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

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

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

И наконец, алгоритмы зачастую также более эффективны, чем простые циклы (см. [Sutter00] и [Meyers01]). В них устранены небольшие неэффективности, такие как повторные вычисления container.end()). Не менее важно, что стандартные алгоритмы, используемые вами, были реализованы теми же программистами, кто реализовывал и используемые вами стандартные контейнеры, и понятно, что их знание конкретных реализаций позволяет им написать алгоритмы более эффективно, чем это сможете сделать вы. Важнее всего, однако, то, что многие алгоритмы имеют высокоинтеллектуальные реализации, которые мы никогда не сможем реализовать в собственноручно разработанном коде (не считая случаев, когда нам не нужна та степень обобщенности, которую предоставляют алгоритмы). Вообще говоря, более используемая библиотека всегда оказывается лучше отлаженной и более эффективной просто потому, что у нее больше пользователей. Вряд ли вы найдете и сможете использовать в своей программе библиотеку, настолько же широко применяемую, как и реализация вашей стандартной библиотеки. Воспользуйтесь ею. Алгоритмы STL уже написаны — так почему бы не воспользоваться ими?

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

Примеры

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

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

deque::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(),41)); // добавляя к каждому 41

Впрочем, bind2nd и plus достаточно неудобны. Откровенно говоря, в действительности их мало кто использует, и связано это в первую очередь с плохой удобочитаемостью такого кода (см. рекомендацию 6).

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

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

Пример 2. Найти первый элемент между x и у . Рассмотрим простой цикл, который выполняет поиск в vector v первого элемента, значение которого находится между x и y. Он вычисляет итератор, который указывает либо на найденный элемент, либо на v.end():

vector::iterator i = v.begin();

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

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

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

vector::iterator i =

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

 compose2(logical_and(),

 bind2nd(greater(), x), bind2nd(less(), y)));

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

template

class BetweenValues : public unary_function {

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::iterator i =

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

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

vector::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

 

85. Пользуйтесь правильным алгоритмом поиска

Резюме

Данная рекомендация применима к поиску определенного значения в диапазоне. При поиске в неотсортированном диапазоне используйте алгоритмы 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 практически всегда бесполезен, поскольку возвращает всего лишь значение типа bool, указывающее, найден искомый элемент или нет. Обычно вам требуется алгоритм 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 с последующим distance, что имеет смысл для функции count, не являющейся членом).

Ссылки

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

 

86. Пользуйтесь правильным алгоритмом сортировки

Резюме

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

Обсуждение

Вам не всегда требуется полный 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::iterator). Если вам нужны данные алгоритмы, но у вас нет итераторов произвольного доступа, вы можете воспользоваться идиомой индексного контейнера: создайте контейнер, поддерживающий итераторы произвольного доступа (например, vector), в котором будут храниться итераторы, указывающие на элементы интересующего вас диапазона, и затем примените к нему более мощный алгоритм с использованием разыменовывающей версии вашего предиката (в которой перед обычным сравнением выполняется разыменование итераторов).

Версии 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));, который вернет итератор, указывающий на первого студента, чей средний балл ниже 4.5.

• Какие из товаров имеют вес менее 10 кг? Вызов partition(products.begin(), products.end(), WeightUnder(10)); вернет итератор, указывающий на первый товар, вес которого не ниже 10 кг.

Пример 2. nth_element . Алгоритм nth_element можно использовать для того, чтобы получить один элемент в корректной n-й позиции, в которой он бы находился при полной сортировке всего диапазона, при этом все прочие элементы корректно располагаются до или после этого n-го элемента. Этого достаточно, чтобы ответить на вопросы наподобие следующих.

• Перечислите 20 лучших покупателей. Вызов nth_element(s.begin(), s.begin()+19, s.end(), SalesRating); помещает 20 наилучших покупателей в начало контейнера.

• Какое изделие имеет медианное значение качества в данном наборе? Искомый элемент находится в средней позиции отсортированного диапазона. Для его поиска достаточно вызова 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, но кроме того обеспечивает корректное отсортированное размещение всех элементов до n-го. Алгоритм 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

 

87. Делайте предикаты чистыми функциями

Резюме

Предикат представляет собой функциональный объект, который возвращает ответ да/нет, обычно в виде значения типа bool. Функция является "чистой" в математическом смысле, если ее результат зависит только от ее аргументов (обратите внимание — в данном случае термин "чистая" не имеет никакого отношения к чисто виртуальным функциям).

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

Обсуждение

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

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

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

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

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

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

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

Примеры

Пример. FlagNth . Перед вами классический пример из [Sutter02], в котором выполняется попытка удалить третий элемент из контейнера v.

class FlagNth {

public:

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

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

 template

 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 {

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

};

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

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

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

set s; // Ошибка

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

struct CompareThings

 : public binary_function {

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

};

set s; //OK

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

template

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 {

 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

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