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

Мейерс Скотт

… //См. ранее

list<int> results; // Теперь используется

// контейнер list

transform(values.begin, values.end, // Результаты вызова transform

 front_inserter(results), // вставляются в начало results

 transmogrify); //в обратном порядке

Поскольку при использовании

front_inserter

новые элементы заносятся в начало

results

функцией

push_front

, порядок следования

объектов в

results

будет обратным по отношению к порядку соответствующих объектов в

values

. Это ишь одна из причин, по которым

front_inserter

используется реже

back_inserter

. Другая причина заключается в том, что

vector

не поддерживает

push_front

, поэтому

front_inserter

не может использоваться с

vector

.

Чтобы результаты

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 записываются