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

class Timestamp {…};

bool operator<(const Timestamp& lhs, //Проверяет, предшествует ли

const Timestamp& rhs); // объект lhs объекту rhs по времени

vector vt; // Создать вектор, заполнить данными

… // и отсортировать так, чтобы

sort(vt.begin(), vt.end()); // "старые" объекты предшествовали "новым"

Предположим, из vtтребуется удалить все объекты, предшествующие некоторому пороговому объекту ageLimit. В данном случае не нужно искать в vtобъект Timestamp, эквивалентный ageLimit, поскольку объекта с точно совпадающим значением может и не быть. Вместо этого в vtищется граничная позиция, то есть первый элемент, не старший ageLimit. Задача решается элементарно, поскольку алгоритм loweboundпредоставляет всю необходимую информацию:

Timestamp ageLimit;

…

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 { // См. совет 40

bool operator()(const Person& lhs, const Person& rhs) const {

return lhs.name() < rhs.name();

}

};

list lp;

…

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как условия проверки: