vt.erase(vt.begin, lower_bound(vt.begin, // Удалить из vt все объекты,
vt.end, // предшествующие значению
ageLimit)); // ageLimit
Слегка изменим условия задачи. Допустим, требуется удалить все объекты, предшествующие или равные
ageLimit
. Для этого необходимо найти первый объект после
ageLimit
. Для решения задачи идеально подходит алгоритм
upper_bound
:
vt.erase(vt.begin, upper_bound(vt.begin, //
Удалить из vt все объекты,
vt.end, // предшествующие или
ageLimit)); // эквивалентные ageLimit
Алгоритм
upper_bound
также часто применяется при вставке в сортированные интервалы, когда объекты с эквивалентными значениями должны следовать в контейнере в порядке вставки. Рассмотрим сортированный список объектов
Person
, в котором объекты сортируются по имени:
class Person {
public:
…
const string& name const;
…
}
struct PersonNameLess:
public binary_function<Person, Person, bool> { // См. совет 40
lp.sort(PersonNameLess); // Отсортировать lp по критерию
// PersonNameLess
Чтобы список сортировался требуемым образом (по имени, с хранением эквивалентных имен в порядке вставки), можно воспользоваться алгоритмом
upper_bound
для определения позиции вставки:
Person newPerson;
…
lp.insert(upper_bound(lp.begin, // Вставить newPerson за последним
lp.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
Присутствует ли заданное значение? И если присутствует, то где находится первый объект с этим значением?