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

Вообще говоря, попытки модификации компонентов std действительно запрещены, поскольку их последствия могут оказаться непредсказуемыми, но в некоторых ситуациях минимальные изменения все же разрешены. А именно, программистам разрешается специализировать шаблоны std для пользовательских типов. Почти всегда существуют альтернативные решения, но в отдельных случаях такой подход вполне разумен. Например, разработчики классов умных указателей часто хотят, чтобы их классы при сортировке вели себя как встроенные указатели, поэтому специализация std::less для типов умных указателей встречается не так уж редко. Далее приведен фрагмент класса shared_ptr из библиотеки Boost, упоминающегося в советах 7 и 50:

namespace std {
template<typename T> // Специализация std::less
 struct less<boost::shared_ptr<T> >: // для boost::shared_ptr<T>
 public // (boost - пространство имен)
 binary_function<boost::shared_ptr<T>,
 boost::shared_ptr<T>, // Базовый класс описан
 bool> { // в совете 40
 bool operator(const boost::shared_ptr<T>& a,
 const boost::shared_ptr<T>& b) const {
 return less<T*>(a.get, b.get); // shared_ptr::get возвращает
 } // встроенный указатель
 }; // из объекта shared_ptr
}

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

Программисты C++ часто опираются на предположения. Например, они предполагают, что копирующие конструкторы действительно копируют (как показано в совете 8, невыполнение этого правила приводит к удивительным последствиям). Они предполагают, что в результате взятия адреса объекта вы получаете указатель на этот объект (в совете 18 рассказано, что может произойти в противном случае). Они предполагают, что адаптеры bind1st и not2 могут применяться к объектам функций (см. совет 40). Они предполагают, что оператор + выполняет сложение (кроме объектов string, но знак «+» традиционно используется для выполнения конкатенации строк), что оператор – вычитает, а оператор == проверяет равенство. И еще они предполагают, что функция less эквивалентна operator<.

В действительности operator< представляет собой нечто большее, чем реализацию less по умолчанию — он соответствует ожидаемому поведению less. Если less вместо вызова operator< делает что-либо другое, это нарушает ожидания программистов и вступает в противоречие с «принципом минимального удивления». Конечно, поступать так не стоит — особенно если без этого можно обойтись.

В STL нет ни одного случая использования less, когда программисту бы не предоставлялась возможность задать другой критерий сравнения. Вернемся к исходному примеру с контейнером multiset<Widget>, упорядоченному по атрибуту maxSpeed. Задача решается просто: для выполнения нужного сравнения достаточно создать класс функтора практически с любым именем, кроме less. Пример:

struct MaxSpeedCompare:
 public binary_function<Widget, Widget, bool> {
 bool operator(const Widget& lhs, const Widget& rhs) const {
 return lhs.maxSpeed < rhs.maxSpeed;
 }
};

При создании контейнера multiset достаточно указать тип сравнения MaxSpeedCompare, тем самым переопределяя тип сравнения по умолчанию (less<Widget>):

multiset<Widget, MaxSpeedCompare> widgets;

Смысл этой команды абсолютно очевиден: мы создаем контейнер multiset с элементами Widget, упорядоченными в соответствии с классом функтора MaxSpeedCompare. Сравните со следующим объявлением:

multiset<Widget> widgets;

В нем создается контейнер multiset объектов Widget, упорядоченных по стандартному критерию. Строго говоря, упорядочение производится по критерию less<Widget>, но большинство программистов будет полагать, что сортировка производится функцией operator<. Не нужно обманывать их ожидания и подменять определение less. Если вы хотите использовать less (явно или косвенно), проследите за тем, чтобы этот критерий был эквивалентен operator<. Если объекты должны сортироваться по другому критерию, создайте специальный класс функтора и назовите его как-нибудь иначе.

Программирование в STL

STL традиционно характеризуется как совокупность контейнеров, итераторов, алгоритмов и объектов функций, однако программирование в STL заключает в себе нечто большее. Этот термин означает, что программист способен правильно выбирать между циклами, алгоритмами или функциями контейнеров; знает, в каких случаях equal_range предпочтительнее lower_bound, когда lower_bound предпочтительнее find и когда find превосходит equal_range. Термин означает, что программист умеет повышать быстродействие алгоритма посредством замены функций эквивалентными функторами и избегает написания непереносимого или плохо читаемого кода. Более того, к этому понятию даже относится умение читать сообщения об ошибках компилятора, состоящие из нескольких тысяч символов, и хорошее знание Интернет-ресурсов, посвященных STL (документация, расширения и даже полные реализации).

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

Совет 43. Используйте алгоритмы вместо циклов

Каждому алгоритму передается по крайней мере одна пара итераторов, определяющих интервал объектов для выполнения некоторой операции. Так, алгоритм min_element находит минимальное значение в интервале, алгоритм accumulate вычисляет сводную величину, характеризующую интервал в целом (см. совет 37), а алгоритм partition делит элементы интервала на удовлетворяющие и не удовлетворяющие заданному критерию (см. совет 31). Чтобы алгоритм мог выполнить свою задачу, он должен проанализировать каждый объект в переданном интервале (или интервалах), для чего объекты в цикле перебираются от начала интервала к концу. Некоторые алгоритмы (такие как find и find_if) могут вернуть управление до завершения полного перебора, но и в этих алгоритмах задействован внутренний цикл. Ведь даже алгоритмы find и find_if должны проанализировать все элементы интервала, прежде чем принять решение об отсутствии искомого элемента.

Итак, внутренняя реализация алгоритмов построена на использовании циклов. Более того, благодаря разнообразию алгоритмов STL многие задачи, естественно кодируемые в виде циклов, могут решаться при помощи алгоритмов. Рассмотрим класс Widget с функцией redraw:

class Widget {
public:
 …
 void redraw const;
 …
};

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

list<Widget> lw;
…
for (list<Widget>::iterator = lw.begin; i != lw.end; ++i) {
 i->redraw;
}

С другой стороны, с таким же успехом можно воспользоваться алгоритмом for_each:

for_each(lw.begin, lw.end; // Функция mem_fun_ref
 mem_fun_ref(&Widget::redraw)); // описана в совете 41

Многие программисты C++ считают, что циклы естественнее алгоритмов, а прочитать цикл проще, чем разбираться в mem_fun_ref и получении адреса Widget::redraw. Но в заголовке этого совета рекомендуется отдавать предпочтение алгоритмам. В сущности, заголовок означает, что вызов алгоритма предпочтительнее любого явно запрограммированного цикла. Почему?