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

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

vector values:// См. ранее

vector 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 values;// См. ранее

vector 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 results;

if ( results.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).