Скотт Мейерс - Эффективное использование STL

set s; // Создать множество, заполнить данными

…

Widget w; // Искомое значение

…

if ( s.count(w)) { // Существует значение, эквивалентное w

…

} else {

… // Эквивалентное значение не существует

}

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

Тем не менее при подсчете объектов в ассоциативных контейнерах countнадежно занимает свою нишу. В частности, вызов countпредпочтительнее вызова equal_rangeс последующим применением distanceк полученным итераторам. Во-первых, само название функции подсказывает ее смысл — слово countозначает «подсчет». Во-вторых, countупрощает работу программиста, поскольку ему не приходится создавать пару и передавать ее компоненты при вызове distance. В-третьих, countработает чуть быстрее.

Попробуем подвести итог всему, о чем говорилось в настоящем совете. Информация собрана в следующей таблице.

Несколько странно выгладит частое присутствие 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несложно. Предпочтение отдается тому алгоритму или функции, которые обладают нужными возможностями, обеспечивают нужное быстродействие и требуют минимальных усилий при вызове. Следуйте этой рекомендации (или обращайтесь к таблице), и у вас никогда не будет проблем с выбором.

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