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

 transmogrify);

либо очистить results и затем использовать итератор вставки стандартным способом:

…

results.clear;                // Удалить из results все элементы

results.reserve(values.size); // Зарезервировать память

transform(values.begin, values.end, // Занести выходные данные

 back_inserter(results),                // transform в results

 transmogrify);

В данном совете было продемонстрировано немало вариаций на заданную тему, но я надеюсь, что в памяти у вас останется основная мелодия. Каждый раз, когда вы используете алгоритм, требующий определения приемного интервала, позаботьтесь о том, чтобы приемный интервал имел достаточные размеры или автоматически увеличивался во время работы алгоритма. Второй вариант реализуется при помощи итераторов вставки — таких, как ostream_iterator, или возвращаемых в результате вызова back_inserter, front_inserter и inserter. Вот и все, о чем необходимо помнить.

Совет 31. Помните о существовании разных средств сортировки

Когда речь заходит об упорядочении объектов, многим программистам приходит в голову всего один алгоритм: sort (некоторые вспоминают о qsort, но после прочтения совета 46 они раскаиваются и возвращаются к мыслям о sort).

Действительно, sort — превосходный алгоритм, однако полноценная сортировка требуется далеко не всегда. Например, если у вас имеется вектор объектов Widget и вы хотите отобрать 20 «лучших» объектов с максимальным рангом, можно ограничиться сортировкой, позволяющей выявить 20 нужных объектов и оставить остальные объекты несортированными. Задача называется частичной сортировкой, и для ее решения существует специальный алгоритм partial_sort:

bool qualityCompare(const Widgets lhs, const Widgets rhs) {

 // Вернуть признак сравнения атрибутов quality

 // объектов lhs и rhs

}

…

partial_sort(widgets.begin, // Разместить 20 элементов

 widgets.begin+20,          // с максимальным рангом

 widgets.end,               // в начале вектора widgets

 qualityCompare);

… // Использование widgets

После вызова partial_sort первые 20 элементов widgets находятся в начале контейнера и располагаются по порядку, то есть widgets[0] содержит Widget с наибольшим рангом, затем следует widgets[1] и т. д.

Если вы хотите выделить 20 объектов Widget и передать их 20 клиентам, но при этом вас не интересует, какой объект будет передан тому или иному клиенту, даже алгоритм partial_sort превышает реальные потребности. В описанной ситуации требуется выделить 20 «лучших» объектов Widget в произвольном порядке. В STL имеется алгоритм, который решает именно эту задачу, однако его имя выглядит несколько неожиданно — он называется nth_element.

Алгоритм nth_element сортирует интервал таким образом, что в заданной вами позиции n оказывается именно тот элемент, который оказался бы в ней при полной сортировке контейнера. Кроме того, при выходе из nth_element ни один из элементов в позициях до n не находится в порядке сортировки после элемента, находящегося в позиции n, а ни один из элементов в позициях после n не предшествует элементу, находящемуся в позиции n. Если такая формулировка кажется слишком сложной, это объясняется лишь тем, что мне приходилось тщательно подбирать слова. Вскоре я объясню причины, но сначала мы рассмотрим пример использования nth_element для перемещения 20 «лучших» объектов Widget в начало контейнера widgets:

nth_element(widgets.begin, // Переместить 20 «лучших» элементов

 widgets.begin+20,         // в начало widgets

 widgets.end,              // в произвольном порядке

 qualityCompare);

Как видите, вызов nth_element практически не отличается от вызова partial_sort. Единственное различие заключается в том, что partial_sort сортирует элементы в позициях 1-20, a nth_element этого не делает. Впрочем, оба алгоритма перемещают 20 объектов Widget с максимальными значениями ранга в начало вектора.