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

Совет 30. Следите за тем, чтобы приемный интервал имел достаточный размер

Контейнеры STL автоматически увеличиваются с добавлением новых объектов (функциями insert, push front, push back ит. д.). Автоматическое изменение размеров чрезвычайно удобно, и у многих программистов создается ложное впечатление, что контейнер сам обо всем позаботится и им никогда не придется следить за наличием свободного места. Если бы так!

Проблемы возникают в ситуации, когда программист думает о вставке объектов в контейнер, но не сообщает о своих мыслях STL. Типичный пример:

int transmogrifyCint х); Функция вычисляет некое новое значение

по переданному параметру х

vector<int> values:

Заполнение вектора values данными vector<int> results: Применить transmogrify к каждому объекту

transform(values.begin(), вектора values и присоединить возвращаемые

values.endO. значения к results.

results.end. Фрагмент содержит ошибку!

transmogrify):

В приведенном примере алгоритм transform получает информацию о том, что приемный интервал начинается с results.end. С этой позиции он и начинает вывод значений, полученных в результате вызова transmogri fy для каждого элемента val ues. Как и все алгоритмы, использующие приемный интервал, transform записывает свои результаты, присваивая значения элементам заданного интервала. Таким образом, transform вызовет transmogri fy для val ues[0] и присвоит результат *results.end(). Затем функция transmogrify вызывается для values[l] с присваиванием результата *(results.end()+l). Происходит катастрофа, поскольку в позиции *results.end() (и тем более в *(results.end()+l)) не существует объекта] Вызов transform некорректен из-за попытки присвоить значение несуществующему объекту (в совете 50 объясняется, как отладочная реализация STL позволит обнаружить эту проблему на стадии выполнения).

Допуская подобную ошибку, программист почти всегда рассчитывает на то, что результаты вызова алгоритма будут вставлены в приемный контейнер вызовом insert. Если вы хотите, чтобы это произошло, так и скажите. В конце концов, STL - всего лишь библиотека, и читать мысли ей не положено. В нашем примере задача решается построением итератора, определяющего начало приемного интервала, вызовом back i nserter:

vector<int> values:

transform(values.begin(). Применить transmogrify к каждому

values.endO. объекту вектора values

back inserter(results), и дописать значения в конец results transmogrify):

При использовании итератора, возвращаемого при вызове backinserter, вызывается pushback, поэтому backi nserter может использоваться со всеми контейнерами, поддерживающими pushback (то есть со всеми стандартными последовательными контейнерами: vector, stri ng, deque и 1 i st). Если вы предпочитаете, чтобы алгоритм вставлял элементы в начало контейнера, воспользуйтесь front i nserter. Во внутренней реализации front i nserter используется push front, поэтому front i nserter работает только с контейнерами, поддерживающими эту функцию (то есть deque и 1 i st).

См. ранее

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

контейнер list

transformCvalues.beginO.values.endO, Результаты вызова transform front inserter(results), вставляются в начало results transmogrify): в обратном порядке

Поскольку при использовании f ront i nserter новые элементы заносятся в начало results функцией push front, порядок следования объектов в results будет обратным по отношению к порядку соответствующих объектов в val ues. Это лишь одна из причин, по которым front i nserter используется реже back i nserter. Другая причина заключается в том, что vector не поддерживает push front, поэтому f ront i nserter не может использоваться с vector.

Чтобы результаты transform выводились в начале results, но с сохранением порядка следования элементов, достаточно перебрать содержимое val ues в обратном порядке:

list<int> results: См. ранее

transform(values.rbegin().values.rendO. Результаты вызова transform front 1nserter(results), вставляются в начало results transmogrify); с сохранением исходного порядка

Итак, f ronti nserter заставляет алгоритмы вставлять результаты своей работы в начало контейнера, а backi nserter обеспечивает вставку в конец контейнера. Вполне логично предположить, что inserter заставляет алгоритм выводить свои результаты с произвольной позиции:

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

vector<int> results: См. ранее - за исключением того, что

results на этот раз содержит данные перед вызовом transform. transformCvalues.beginO, Результаты вызова transmogrify

values.endO, выводятся в середине results

i nserter(results,results.begi n()+results.si 2e()/2), transmogrify):

Независимо от выбранной формы - back inserter, front inserter или inserter - объекты вставляются в приемный интервал по одному. Как объясняется в совете 5, это может привести к значительным затратам для блоковых контейнеров (vector, string и deque), однако средство, предложенное в совете 5 (интервальные функции), неприменимо в том случае, если вставка выполняется алгоритмом. В нашем примере transform записывает результаты в приемный интервал по одному элементу, и с этим ничего не поделаешь.

При вставке в контейнеры vector и string для сокращения затрат можно последовать совету 14 и заранее вызвать reserve. Затраты на сдвиг элементов при каждой вставке от этого не исчезнут, но по крайней мере вы избавитесь от необходимости перераспределения памяти контейнера:

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

vector<int> results:

results.reserveCresults.sizeO+values.SizeO); Обеспечить наличие

в векторе results

емкости для value.sizeO

элементов

transformCvalues.beginO, values.endO. То же, что и ранее.

inserterCresults.results.begin()+results.sizeO/2). но без лишних trannragrify): перераспределений памяти

При использовании функции reserve для повышения эффективности серии вставок всегда помните, что reserve увеличивает только емкость контейнера, а размер остается неизменным. Даже после вызова reserve при работе с алгоритмом, который должен включать новые элементы в vector или string, необходимо использовать итератор вставки (то есть итератор, возвращаемый при вызове Ьаск inserter, fronti nserter или inserter).

Чтобы это стало абсолютно ясно, рассмотрим ошибочный путь повышения эффективности для примера, приведенного в начале совета (с присоединением результатов обработки элементов values к results):

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

vector<int> results:

results.reserveCresults.sizeO+values.SizeO): См. ранее transformCvalues.beginO.values.endO, Результаты вызова

results.endO, transmogrify записываются

transmogrify): в неинициализированную

память: последствия непредсказуемы!

В этом фрагменте transform в блаженном неведении пытается выполнить присваивание в неинициализированной памяти за последним элементом results. Обычно подобные попытки приводят к ошибкам времени выполнения, поскольку операция присваивания имеет смысл лишь для двух объектов, но не между объектом и двоичным блоком с неизвестным содержимым. Но даже если этот код каким-то образом справится с задачей, вектор results не будет знать о новых объектах , якобы созданных в его неиспользуемой памяти. С точки зрения results вектор после вызова transform сохраняет прежний размер, а его конечный итератор будет указывать на ту же позицию, на которую он указывал до вызова transform. Мораль? Использование reserve без итератора вставки приводит к непредсказуемым последствиям внутри алгоритмов и нарушению целостности данных в контейнере.