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

// эквивалентные ageLimit

Алгоритм upper_bound также часто применяется при вставке в сортированные интервалы, когда объекты с эквивалентными значениями должны следовать в контейнере в порядке вставки. Рассмотрим сортированный список объектов Person, в котором объекты сортируются по имени:

class Person { public:
const string& name() const;
…
 }
struct PersonNameLess:
	public binary_function<Person, Person, bool> { // См. совет 40
	bool operator()(const Person& lhs, const Person& rhs) const
{
	return lhs.name()<rhs.name();
}
list<Person> lp;
lp.sort(PersonNameLess());// Отсортировать lp по критерию
// PersonNameLess

Чтобы список сортировался требуемым образом (по имени, с хранением эквивалентных имен в порядке вставки), можно воспользоваться алгоритмом upper_ bound для определения позиции вставки:

Person newPerson;
lp.insert(upper_bound(lp.begin(),// Вставить newPerson за последним
	Ip.end(),	// объектом lр. предшествующим
	newPerson,	// или эквивалентным newPerson
	PersonNameLess()).
newPerson);

Приведенное решение работоспособно и достаточно удобно, но не стройте иллюзий насчет того, что оно каким-то волшебным способом обеспечивает поиск точки вставки в контейнер list с логарифмической сложностью. Как объясняется в совете 34, при работе с list поиск занимает линейное время, но при этом выполняется логарифмическое количество сравнений.

До настоящего момента рассматривался только случай, когда поиск осуществляется в интервале, определяемом парой итераторов. Довольно часто работать приходится со всем контейнером вместо интервала. В этом случае необходимо различать последовательные и ассоциативные контейнеры. Для стандартных последовательных контейнеров (vector, string, deque и list) достаточно следовать рекомендациям, изложенным ранее, используя начальный и конечный итераторы контейнера для определения интервала.

Со стандартными ассоциативными контейнерами (set, multiset, map, multimap) дело обстоит иначе. В них предусмотрены функции поиска, которые по своим возможностям обычно превосходят алгоритмы STL Превосходство функций контейнеров перед алгоритмами подробно рассматривается в совете 44; если говорить кратко — они быстрее работают и ведут себя более последовательно. К счастью, имена функций обычно совпадают с именами соответствующих алгоритмов, поэтому там, где речь идет об алгоритмах count, find, lower_bound, upper_bound и equal_range, при поиске в ассоциативных контейнерах вместо них достаточно выбрать одноименную функцию. К сожалению, для алгоритма binary_search парной функции не существует. Чтобы проверить наличие значения в контейнере set или map, воспользуйтесь идиоматической ролью count как условия проверки:

set<Widget> s;// Создать множество, заполнить данными
Widget w:// Искомое значение
if (s.count(w)) { // Существует значение, эквивалентное w
 } else {
// Эквивалентное значение не существует
}

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

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

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

	Алгоритм	Функция контейнера
Что вы хотите узнать	Несортированный интервал	Сортированный интервал	Для 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
заданное значение?