Герб Саттер - Стандарты программирования на С++. 101 правило и рекомендация
Главное преимущество алгоритмов и шаблонов проектирования в общем случае заключается в том, что они позволяют нам говорить на более высоком уровне абстракции. В современном программировании мы не говорим "пусть несколько объектов следят за одним объектом и получают автоматические уведомления при изменении его состояния". Вместо этого мы говорим просто о "шаблоне проектирования 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<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 достаточно неудобны. Откровенно говоря, в действительности их мало кто использует, и связано это в первую очередь с плохой удобочитаемостью такого кода (см. рекомендацию 6).
При использовании лямбда-функций, генерирующих для нас функциональные объекты, мы можем написать совсем простой код:
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
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 возвращает итератор, указывающий на элемент, следующий за последним найденным элементом (если таковой имеется), т.е. на позицию, куда можно добавить следующий эквивалентный элемент; это полезно при поиске правильного места для вставки новых значений в отсортированную последовательность, чтобы поддерживать упорядоченность, при которой равные элементы располагаются в последовательности в порядке их вставки.
