Скотт Мейерс - Эффективное использование STL
Чтобы результаты transform выводились в начале results, но с сохранением порядка следования элементов, достаточно перебрать содержимое values в обратном порядке:
list<int> results;// См. ранее
transform(values.rbegin().values.rend(). // Результаты вызова transform
front_inserter(results), // вставляются в начало results
transmogrify);
// с сохранением исходного порядка
Итак, front_inserter заставляет алгоритмы вставлять результаты своей работы в начало контейнера, a back_inserter обеспечивает вставку в конец контейнера. Вполне логично предположить, что inserter заставляет алгоритм выводить свои результаты с произвольной позиции:
vector<int> values;// См. ранее
vector<int> results;// См. ранее - за исключением того, что
// results на этот раз содержит данные
// перед вызовом transform.
transform(values.begin(),.// Результаты вызова transmogrify
values.end(),// выводятся в середине results
inserter (results, results. begin(_+results.size() /2),
transmogrify);
Независимо от выбранной формы — back_inserter, front_inserter или inserter — объекты вставляются в приемный интервал по одному. Как объясняется в совете 5, это может привести к значительным затратам для блоковых контейнеров (vector, string и deque), однако средство, предложенное в совете 5 (интервальные функции), неприменимо в том случае, если вставка выполняется алгоритмом. В нашем примере transform записывает результаты в приемный интервал по одному элементу, и с этим ничего не поделаешь.
При вставке в контейнеры vector и string для сокращения затрат можно последовать совету 14 и заранее вызвать reserve. Затраты на сдвиг элементов при каждой вставке от этого не исчезнут, но по крайней мере вы избавитесь от необходимости перераспределения памяти контейнера:
vector<int> values; // См. Ранее
...
vector<int> results;
...
results.reserve(results.size()+values.size()); // Обеспечить наличие
// в векторе results
// емкости для value.size()
// элементов
transform(values.begin(), values.end(), // То же, что и ранее,
inserter(results,results.begin()+results.size()/2). // но без лишних transmogrify);
// перераспределений памяти
При использовании функции reserve для повышения эффективности серии вставок всегда помните, что reserve увеличивает только емкость контейнера, а размер остается неизменным. Даже после вызова reserve при работе с алгоритмом, который должен включать новые элементы в vector или string, необходимо использовать итератор вставки (то есть итератор, возвращаемый при вызове back_ inserter, front_inserter или inserter).
Чтобы это стало абсолютно ясно, рассмотрим ошибочный путь повышения эффективности для примера, приведенного в начале совета (с присоединением результатов обработки элементов values к results):
vector<int> values:// См. ранее
vector<int> results;
results.reserve(results.size()+values.size()); // См. Ранее
transform(values.begin(),values.end(),// Результаты вызова
results.end(),// transmogrify записываются
transmogrify);// в неинициализированную
// память; последствия
// непредсказуемы!
В этом фрагменте transform в блаженном неведении пытается выполнить присваивание в неинициализированной памяти за последним элементом results. Обычно подобные попытки приводят к ошибкам времени выполнения, поскольку операция присваивания имеет смысл лишь для двух объектов, но не между объектом и двоичным блоком с неизвестным содержимым. Но даже если этот код каким-то образом справится с задачей, вектор results не будет знать о новых «объектах», якобы созданных в его неиспользуемой памяти. С точки зрения results вектор после вызова transform сохраняет прежний размер, а его конечный итератор будет указывать на ту же позицию, на которую он указывал до вызова transform. Мораль? Использование reserve без итератора вставки приводит к непредсказуемым последствиям внутри алгоритмов и нарушению целостности данных в контейнере.
В правильном решении функция reserve используется в сочетании с итератором вставки:
vector<int> values;// См. ранее
vector<int> results;
results.reserve(results.size()+values.size()); // См. ранее
transform(values.begin(),values.end(), // Результаты вызова
back_inserter(results),// transmogrify записываются
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[l] и т. д.
Если вы хотите выделить 20 объектов Widget и передать их 20 клиентам, но при этом вас не интересует, какой объект будет передан тому или иному клиенту, даже алгоритм partial_sort превышает реальные потребности. В описанной ситуации требуется выделить 20 «лучших» объектов Widget в произвольном порядке. В STL имеется алгоритм, который решает именно эту задачу, однако его имя выглядит несколько неожиданно — он называется nth_element.
Алгоритм nth_element сортирует интервал таким образом, что в заданной вами позиции п оказывается именно тот элемент, который оказался бы в ней при полной сортировке контейнера. Кроме того, при выходе из nth_element ни один из элементов в позициях до п не находится в порядке сортировки после элемента, находящегося в позиции п, а ни один из элементов в позициях после п не предшествует элементу, находящемуся в позиции п. Если такая формулировка кажется слишком сложной, это объясняется лишь тем, что мне приходилось тщательно подбирать слова. Вскоре я объясню причины, но сначала мы рассмотрим пример использования nth_element для перемещения 20 «лучших» объектов Widget в начало контейнера widgets:
nth_element(widgets.begin().//Переместить 20 «лучших» элементов
widgets.beginC)+20,//в начало widgets
widgets. end(),//в произвольном порядке
qualityCompare);
Как видите, вызов nth_element практически не отличается от вызова partial_sort. Единственное различие заключается в том, что partial_sort сортирует элементы в позициях 1-20, a nth_element этого не делает. Впрочем, оба алгоритма перемещают 20 объектов Widget с максимальными значениями ранга в начало вектора.
