В правильном решении функция reserve используется в сочетании с итератором вставки:

vector<int> values; См. ранее

vector<int> results:

results.reserveCresults.sizeO+values.SizeO): См. ранее

transformCvalues.beginO,values.endO, Результаты вызова

back inserter(results), transmogrify записываются

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

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

памяти

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

Допустим, вызов transform должен записывать результаты в results поверх существующих элементов. Если количество элементов в results не меньше их количества в val ues, задача решается просто. В противном случае придется либо воспользоваться функцией resize для приведения results к нужному размеру:

vector<int> results;

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

results.resizeCvalues.sizeO); results по крайней мере

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

transformCvalues.beginO.values.endO, Перезаписать первые

back inserter(results), values.sizeO элементов results

transmogrify):

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

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

results.reserveCvalues.SizeO): Зарезервировать память

transformCvalues.beginO .values.endO, Занести выходные данные back inserter(results), transform в results

transmogrify);

В данном совете было продемонстрировано немало вариаций на заданную тему, но я надеюсь, что в памяти у вас останется основная мелодия. Каждый раз, когда вы используете алгоритм, требующий определения приемного интервала, позаботьтесь о том, чтобы приемный интервал имел достаточные размеры или автоматически увеличивался во время работы алгоритма. Второй вариант реализуется при помощи итераторов вставки - таких, как ostream i terator, или возвращаемых в результате вызова back inserter, front inserter и inserter. Вот и все, о чем необходимо помнить.

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

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

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

bool qualityCompareCconst WidgetS Ihs. const WidgetS rhs) {

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

partial sort(widgets.begin(). Разместить 20 элементов widgets.begin()+20. с максимальным рангом widgets.endO. в начале вектора widgets qualityCompare):

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

После вызова parti al sort первые 20 элементов wi dgets находятся в начале контейнера и располагаются по порядку, то есть wi dgets [0] содержит Wi dget с наибольшим рангом, затем следует widgets[l] и т. д.

Если вы хотите выделить 20 объектов Widget и передать их 20 клиентам, но при этом вас не интересует, какой объект будет передан тому или иному клиенту, даже алгоритм partial sort превышает реальные потребности. В описанной ситуации требуется выделить 20 лучших объектов Widget в произвольном порядке. В STL имеется алгоритм, который решает именно эту задачу, однако его имя выглядит несколько неожиданно - он называется nthel ement.

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

nth element(widgets.begin(). Переместить 20 лучших элементов

widgets.begin()+20. в начало widgets

wi dgets. endO, в произвольном порядке qualityCompare):

Термин употребляется в статистике. - Примеч. ред.

Как видите, вызов nth element практически не отличается от вызова parti al sort. Единственное различие заключается в том, что partial sort сортирует элементы в позициях 1-20, а nthel ement этого не делает. Впрочем, оба алгоритма перемещают 20 объектов Wi dget с максимальными значениями ранга в начало вектора.

Возникает важный вопрос - что делают эти алгоритмы для элементов с одинаковыми значениями атрибута? Предположим, вектор содержит 12 элементов с рангом 1 и 15 элементов с рангом 2. В этом случае выборка 20 лучших объектов Widget будет состоять из 12 объектов с рангом 1 и 8 из 15 объектов с рангом 2. Но как алгоритмы parti al sort и nthel ement определяют, какие из 15 объектов следует отобрать в верхнюю двадцатку ? И как алгоритм sort выбирает относительный порядок размещения элементов при совпадении рангов?

Алгоритмы partial sort и nthel ement упорядочивают эквивалентные элементы по своему усмотрению, и сделать с этим ничего нельзя (понятие эквивалентности рассматривается в совете 19). Когда в приведенном примере возникает задача заполнения объектами Widget с рангом 2 восьми последних позиций в верхней двадцатке , алгоритм выберет такие объекты, какие сочтет нужным. Впрочем, такое поведение вполне разумно. Если вы запрашиваете 20 лучших объектов Widget, а некоторых объекты равны, то в результате возвращенные объекты будут по крайней мере не хуже тех, которые возвращены не были.

Полноценная сортировка обладает несколько большими возможностями. Некоторые алгоритмы сортировки стабильны. При стабильной сортировке два эквивалентных элемента в интервале сохраняют свои относительные позиции после сортировки. Таким образом, если Widget А предшествует Widget В в несортированном векторе widgets и при этом ранги двух объектов совпадают, стабильный алгоритм сортировки гарантирует, что после сортировки Widget А по-прежнему будет предшествовать Widget В. Нестабильный алгоритм такой гарантии не дает.

Алгоритм partial sort, как и алгоритм nth el ement, стабильным не является. Алгоритм sort также не обладает свойством стабильности, но существует специальный алгоритм stable sort, который, как следует из его названия, является стабильным. При необходимости выполнить стабильную сортировку, вероятно, следует воспользоваться stablesort. В STL не входят стабильные версии parti al sort и nth el ement.

Следует заметить, что алгоритм nth el ement чрезвычайно универсален. Помимо выделения п верхних элементов в интервале, он также может использоваться для вычисления медианы по интервалу и поиска значения конкретного процентиля:

vector<Widget>;:iterator beginCwidgets.beginO); Вспомогательные переменные vector<W1dget>: iterator endCwidgets.endO): для начального и конечного

итераторов widgets

vector<W1dget>::iterator goalPosition; Итератор, указывающий на

интересующий нас объект Widget Следующий фрагмент находит Widget с рангом median

goalPosition = begin + widgets.size()/2; Нужный объект находится

в середине отсортированного вектора