Герб Саттер - Стандарты программирования на С++. 101 правило и рекомендация

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

Данная рекомендация применима к поиску определенного значения в диапазоне. При поиске в неотсортированном диапазоне используйте алгоритмы 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

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

Вам не всегда требуется полный sort; обычно надо меньшее, и весьма редко — большее. В общем случае стандартные алгоритмы сортировки располагаются от наиболее дешевых до наиболее дорогих в следующем порядке: partition, stable_partition, nth_element, partial_sort(и его вариант partial_sort_copy), sortи stable_sort. Используйте наименее дорогой из алгоритмов, которые выполняют необходимую вам работу; применение излишне мощного алгоритма — расточительство.