Допуская подобную ошибку, программист почти всегда рассчитывает на то, что результаты вызова алгоритма будут вставлены в приемный контейнер вызовом insert. Если вы хотите, чтобы это произошло, так и скажите. В конце концов, STL — всего лишь библиотека, и читать мысли ей не положено. В нашем примере задача решается построением итератора, определяющего начало приемного интервала, вызовом back_inserter:
vector<int> values;
transform(values.begin(), // Применить transmogrify к каждому
values.end(), // объекту вектора values
back_inserter(results), // и дописать значения в конец results
transmogrify);
При использовании итератора, возвращаемого при вызове back_inserter, вызывается push_back, поэтому back_inserter может использоваться со всеми контейнерами, поддерживающими push_back (то есть со всеми стандартными последовательными контейнерами: vector, string, deque и list). Если вы предпочитаете, чтобы алгоритм вставлял элементы в начало контейнера, Воспользуйтесь front_inserter. Во внутренней реализации front_inserter используется push_front, поэтому front_inserter работает только с контейнерами, поддерживающими эту функцию (то есть deque и list).
… //См. ранее
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 записываются
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(), // Занести выходные данные
