Задача 1. Вектор: потребление

и злоупотребление Сложность: 4

Почти все используют std:: vector, и это хорошо. К сожалению, многие не всегда верно понимают его семантику и в результате невольно применяют его странными, а порой и опасными способами. Сколько из перечисленных ниже проблем можно найти в ваших программах?

Вопрос для новичка

1. В чем разница между строками А и В?

void fС vector<int>& v ) {

v[0]; A

v.at(O); В

Вопрос для профессионала

2. Рассмотрим следующий код. vector<int> v;

V. reserveC 2 ) ;

assertC v.capacityO == 2 );

v[0] = 1;

v[l] = 2;

for(vector<i nt>::i terator i = v.beginC); i<v.end(); i++){ cout « *i « endl;

cout « v[0];

V.reserveC 100 );

assertC V.capacityO == 100 );

cout « v[0];

v[2] = 3; v[3] = 4;

v[99i"= 100;

forC vector<int>: : iterator i = v.beginO; i <v. endC) ; i++){ cout « *i « endl;

Раскритикуйте этот код, как с точки зрения стиля, так и с точки зрения корректности.

Решение

Обращение к элементу вектора

1. В чем разница между строками А и В?

void fС vector<int>& v ) {

v[0]; A

v.atCO); в

20 Обобщенное программирование и стандартная библиотека C-t

в примере 1-1, если вектор v не пуст, разницы между строками АиВ нет. Если же V пуст, то в строке В будет гарантированно сгенерировано исключение std: :out of range, но что произойдет в строке А, сказать невозможно.

Имеется два способа обращения к элементам, содержащимся в векторе. Первый, vector<T>::at, выполняет проверку диапазона значения индекса, чтобы убедиться, что требуемый элемент действительно содержится в векторе. Не имеет никакого смысла обращение к сотому элементу вектора, в котором содержится всего 10 элементов, и если вы попытаетесь сделать это, то функция at защитит вас от неверных действий, генерируя исключение std: :out..of range.

Оператор vector<T>: :operator[] может, но не обязан выполнять проверку диапазона. В стандарте об этом ничего не сказано, так что разработчик вашей стандартной библиотеки имеет полное право как добавить такую проверку, так и обойтись без нее. Если вы используете operate г [] для обращения к элементу, отсутствующему в векторе, вы делаете это на свой страх и риск, и стандарт ничего не говорит о том, что может произойти в данном случае (хотя описание этой ситуации может оказаться в документации к используемой вами реализации стандартной библиотеки). Возможно ваша программа аварийно завершится, или будет сгенерировано исключение, или же программа будет продолжать работать, выдавая неверные результаты, или аварийно завершится в каком-то совершенно ином месте.

Такая проверка диапазона защищает нас от множества проблем. Так почему же стандарт не требует ее выполнения в операторе operator[]? Краткий ответ прост: эффективность. Постоянная проверка диапазона может привести к накладным расходам (возможно, небольшим) во всех ваших программах, даже там, где гарантировашю не может быть нарушения границ. Согласно принципам С+ + , вы не должны платить за то, чего не используете, и поэтому проверка диапазона в операторе operator [] не является обязательной. В конкретном случае с векторами у нас есть еще одна причина для приоритета эффективности: векторы предназначены для использования вместо встроенных массивов, и поэтому они должны быть настолько же эффективны, как и массивы (в которых не выполняются проверки диапазона). Если вы хотите, чтобы такая проверка осуществлялась, - используйте функцию at.

Увеличение размера вектора

Теперь обратимся к примеру 1-2, который работает с vector<int> при помощи некоторых простых операций. 2. Рассмотрим следующий код.

vector<int> v;

V.reserveC 2 );

assert( V.capacityO == 2 ) ;

Раскритикуйте этот код, как с точки зрения стиля, так и с точки зрения корректности.

Данная проверка связана с двумя проблемами, смысловой и стилистической.

Смысловая проблема состоит в том, что проверка может сработать неверно. Почему? Потому что вызов reserve гарантирует, >гго емкость вектора становится равной как минимум 2, но может быть и больше 2. Обычно это так и есть, потому что типичная реализация вектора может всегда увеличивать внутренний буфер экспоненциально, невзирая на конкретный запрос посредством функции reserve. Поэтому корректная проверка датжна использовать оператор сравнения >=, а не строгое равенство.

assert( V.capacityO >= 2 ) ;

Во-вторых, стилистическая ошибка заключается в том, что проверка избыточна. Почему? Потому что стандарт гарантирует выполнение проверяемого условия. Зачем же нужна явная проверка? Она не имеет смысла, если только вы не подозреваете о

наличии ошибок в используемой вами реализации стандартной библиотеки и стремитесь избежать больших проблем.

= 1;

= 2;

Обе эти строки -- грубейшие, но трудно обнаруживаемые ошибки, поскольку такая программа вполне может "работать" (в зависимости от используемой конкретной реализации библиотеки).

Имеется сушественная разница между футткциями size/resize и capacity/reserve, т.е. между размером и емкостью вектора.

• size говорит нам, сколько элементов содержится в контейнере в настоящее время, а resize изменяет содержимое контейнера таким образом, чтобы он содержал указанное количество элементов в контейнере путем добавления или удаления их из конца контейнера. Обе эти функции присутствуют в контейнерах list, vector и deque и отсутствуют в остальных.

• capaci ty возвращает количество мест для элементов в контейнере, т.е. указывает, сколько элементов можно разместить в контейнере перед тем, как добавление очередного элемента вызовет выделение нового блока памяти. Функция reserve при необходимости увеличивает (но никогда не уменьшает) размер внугрсннего буфера , чтобы он был способен вместить как минимум указанное количество элементов. Обе функции предусмотрены только у контейнера vector.

В нашем случае мы использовали вызов v. reserve(2) и, таким образом, гарантировали, что V. capaci tyC) >= 2, но мы не добавляли элементы в вектор v, так что вектор V остается пуст! На данный момент все, что можно сказать о векторе --- это то, что в нем есть место как минимум для двух элементов.

> Рекомендация

Помните о разнице между size/resize и capacity/reserve.

Мы можем безопасно использовать оператор operator[] (или функцию at) только для изменения элементов, которые реально содержатся в контейнере, т.е. реально учтены в size. Вы можете удивиться, почему оператор operator[] не может быть достаточно интеллектуальным, чтобы добавить элемент в контейнер, если он еще не в контейнере. Но если бы operator!] позволял делать такие веши, мы бы могли создавать вектор с "дырами"! Рассмотрим, например, следующий фрагмент.

vector<int> v; V.reserveC 100 );

vL99] =42; Ошибка, но, допустим, такое возможно... ... что тогда можно сказать о значениях v[0..98]?

Увы, поскольку не предусмотрено, чтобы оператор ореrator [] выполнял проверку диапазона, в большинстве рссшизаций выражение v[0] будет просто возвращать ссылку на еще неиспользуемую память во внутреннем буфере вектора, а именно на то место в памяти, где в конечном итоге будет находиться первый элемент вектора. Следовательно, скорее всего, инструкция v[0] = 1; будет "[юрмально работать", т.е., например, при выводе cout « v[0] вы, вероятно, увидите на экране I, как и ожидалось (и совершенно необоснованно!).

Но описанный сценарий - не более чем типичный вариант того, что может случиться. На самом деле все зависит от реализации стандартной библиотеки. Стандарт ничего не говорит о том, что должно происходить при записи элемента v[0] в пусто.м векторе v, поскольку программист легко может узнать о том, что вектор пуст, чтобы не пытаться выполнять такую запись. В конце концов, если ему очень надо, он может обеспечить выполнение соответствующей проверки, воспользовавшись вызовом v.atCO)...