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

	Алгоритм		Функция контейнера
Что вы хотите узнать	Несортированный интервал	Сортированный интервал	Для set и map	Для multiset и multimap
Присутствует ли заданное значение?	find	binary_search	count	find
Присутствует ли заданное значение? И если присутствует, то где находится первый объект с этим значением?	find	equal_range	find	find или lower_bound (см. ранее)
Где находится первый объект со значением, не предшествующим заданному?	find_if	lower_bound	lower_bound	lower_bound
Где находится первый объект со значением, следующим после заданного?	find_if	upper_bound	upper_bound	upper_bound
Сколько объектов имеют заданное значение?	count	equal_range	count	count
Где находятся все объекты с заданным значением?	equal_range	equal_range	equal_range	find (итеративный вызов)

Несколько странно выгладит частое присутствие equal_range в столбце, относящемся к сортированным интервалам. Оно связано с особой ролью проверки эквивалентности при поиске. Использование lower_bound и upper_bound чревато ошибочной проверкой равенства, а при использовании equal_range более естественно выглядит проверка эквивалентности. Во второй строке предпочтение отдается equal_range еще по одной причине: equal_range работает с логарифмическим временем, а вызов find связан с линейными затратами времени.

Для контейнеров multiset и multimap в качестве возможных кандидатов для поиска первого объекта с заданным значением указаны два алгоритма, find и lower_bound. Обычно для решения этой задачи выбирается find — возможно, вы обратили внимание, что именно этот алгоритм указан в таблице для контейнеров set и map. Однако multi-контейнеры не гарантируют, что при наличии нескольких элементов с заданным значением find найдет первый элемент в контейнере; известно лишь то, что будет найден один из этих элементов. Если вы действительно хотите найти первый объект с заданным значением, воспользуйтесь lower_bound и выполните вручную вторую часть проверки эквивалентности, описанной в совете 19 (без этой проверки можно обойтись при помощи equal_range, но вызов equal_range обходится дороже, чем вызов lower_bound).

Выбрать между count, find, binary_search, lower_bound, upper_bound и equal_range несложно. Предпочтение отдается тому алгоритму или функции, которые обладают нужными возможностями, обеспечивают нужное быстродействие и требуют минимальных усилий при вызове. Следуйте этой рекомендации (или обращайтесь к таблице), и у вас никогда не будет проблем с выбором.

Совет 46. Передавайте алгоритмам объекты функций вместо функций

Часто говорят, что повышение уровня абстракции языков высокого уровня приводит к снижению эффективности сгенерированного кода. Александр Степанов, изобретатель STL, однажды разработал небольшой комплекс тестов для оценки «платы за абстракцию» при переходе с C на C++. В частности, результаты этих тестов показали, что код, сгенерированный для работы с классом, содержащим double, почти всегда уступает по эффективности соответствующему коду, непосредственно работающему с double. С учетом сказанного вас может удивить тот факт, что передача алгоритмам объектов функций STL — то есть объектов, маскирующихся под функции, — обычно обеспечивает более эффективный код, чем передача «настоящих» функций.

Предположим, вы хотите отсортировать вектор чисел типа double по убыванию. Простейшее решение этой задачи средствами STL основано на использовании алгоритма sort с объектом функции типа greater:

vector v;

…

sort(v.begin, v.end, greater);

Вспомнив о «плате за абстракцию», программист решает заменить объект функции «настоящей» функцией, которая к тому же оформлена как подставляемая (inline):

inline bool doubleGreater(double d1, double d2) {

 return d1 > d2;

}

…

sort(v.begin, v.end, doubleGreater);