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

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

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

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

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

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

vector<int> values;

… // Заполнение вектора values данными

vector<int> results;// Применить transmogrify к каждому объекту

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

values.end(). // значения к results.

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

transmogrify);

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

Допуская подобную ошибку, программист почти всегда рассчитывает на то, что результаты вызова алгоритма будут вставлены в приемный контейнер вызовом 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(), // Занести выходные данные back_inserter(results),// transform в results

transmogrify);

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Приемный буфер сокета UDP

Из книги автора

Приемный буфер сокета UDP Число дейтаграмм UDP, установленных в очередь UDP, для данного сокета ограничено размером его приемного буфера. Мы можем изменить его с помощью параметра сокета SO_RCVBUF, как мы показали в разделе 7.5. В FreeBSD по умолчанию размер приемного буфера сокета UDP


Глава 14 Вы следите за мной, я слежу за вами

Из книги автора

Глава 14 Вы следите за мной, я слежу за вами Plpki ytw eai rtc aaspx M llogw qj wef ms rh xq? [78] Через пару дней после встречи с другом отца Марком Касденом, который работал в бюро частных расследований, я отправился в долгий путь обратно в Лас-Вегас, чтобы забрать одежду и личные вещи. Отдел по


Часть IV Чтобы вас не рассекретили…

Из книги автора

Часть IV Чтобы вас не рассекретили… В этой небольшой части книги будут рассмотрены дополнительные рекомендации, позволяющие остаться незамеченным в


Интервал

Из книги автора

Интервал Междустрочный интервал – это вертикальное расстояние между строками текста внутри абзаца. По умолчанию в Microsoft Word используется одинарный интервал. Однако в зависимости от типа документа его можно изменять. Например, для некоторых типов научных работ


Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства

Из книги автора

Совет 21. Следите за тем, чтобы функции сравнения возвращали false в случае равенства Сейчас я покажу вам нечто любопытное. Создайте контейнер set с типом сравнения less_equal и вставьте в него число 10:set<int,less_equal<int> > s; // Контейнер s сортируется по критерию "<="s.insert(10); // Вставка


Совет 42. Следите за тем, чтобы конструкция less означала operator<

Из книги автора

Совет 42. Следите за тем, чтобы конструкция less<T> означала operator< Допустим, объект класса Widget обладает атрибутами weight и maxSpeed:class Widget { public:size_t weight() const;size_t maxSpeed() const;}Будем считать, что естественная сортировка объектов Widget осуществляется по атрибуту weight, что отражено в


Интервал времени

Из книги автора

Интервал времени Ошибочно предполагать, что тип TIME может хранить интервал времени. Он не может. Для вычисления интервала времени вычтите более позднюю дату или время из более раннего. Результатом будет число NUMERIC(18,9), выражающее интервал в днях. Поскольку точность


Размер страницы и размер кэша по умолчанию

Из книги автора

Размер страницы и размер кэша по умолчанию При восстановлении вы можете изменить размер страницы, включив в команду переключатель -р[age_size], за которым следует целое число, задающее размер в байтах. Допустимые размеры страниц см. в табл. 38.2.В этом примере gbak восстанавливает


Интервал чистки

Из книги автора

Интервал чистки Интервалом чистки (sweep interval) является установленное для базы данных целое число, которое определяет предел для некоторого набора условий, что приведет к выполнению автоматической чистки.Сервер Firebird ведет список транзакций. Любая транзакция, находящаяся


Следите за логами

Из книги автора

Следите за логами Изучайте свои логи, чтобы следить за дискуссиямиВам полезно знать, кто о вас говорит. Проверьте свои логи и узнайте, что откуда берется. Кто на вас ссылается? Кто ругается? Какие из блогов, попавшие в списки на Technorati, Blogdex, Feedster, Del.icio.us и Daypop, говорят о


Интервал синхронизации системных часов

Из книги автора

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


13-Я КОМНАТА: Чтобы чаще

Из книги автора

13-Я КОМНАТА: Чтобы чаще Вдохновленный читательскими письмами, я решил попытаться ответить на вопрос, от чего зависит частота упоминания той или иной компании в журнале, но ответ получился слишком громоздким, поэтому вместо «Письмоносца» даю его здесь.Компания должна


Чтобы было красиво

Из книги автора

Чтобы было красиво Первое, с чего нужно начать, – это настройка экрана и всего, что вы на нем видите. Вообще-то эту операцию нужно проделывать сразу, как вы сели за незнакомый компьютер (это не значит, что, например, придя в гости к другу, нужно настраивать его компьютер на


Размер головного мозга и размер социального окружения

Из книги автора

Размер головного мозга и размер социального окружения Дискуссии по поводу взаимосвязи между размером головного мозга какого-либо организма и размером группы, к которой этот организм принадлежит, ведутся нейробиологами уже давно. При этом взаимосвязь с социальной