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

Мейерс Скотт

 transmogrify); // в конец вектора results

// без лишних перераспределений

// памяти

До настоящего момента предполагалось, что алгоритмы (такие как

transform

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

Допустим, вызов

transform

должен записывать результаты в

results

поверх существующих элементов. Если количество элементов в

results

не меньше их количества в

values

, задача решается просто. В противном случае придется либо воспользоваться функцией

resize

для приведения

results

к нужному размеру:

vector<int> results;

…

if (results.size < values.size) { // Убедиться в том, что размер

 results.resize(values.size); // results по крайней мере

} // не меньше размера values

transform(values,begin, values.end, // Перезаписать первые

 back_inserter(results), // values.size элементов results

 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

с максимальными значениями ранга в начало вектора.

Возникает важный вопрос — что делают эти алгоритмы для элементов с одинаковыми значениями атрибута? Предположим, вектор содержит 12 элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20 «лучших» объектов

Widget

будет состоять из 12 объектов с рангом 1 и 8 из 15 объектов с рангом 2. Но как алгоритмы

partial_sort

и

nth_element

определяют, какие из 15 объектов следует отобрать в «верхнюю двадцатку»? И как алгоритм

sort

выбирает относительный порядок размещения элементов при совпадении рангов?