Динамо-машины  Метод Сократа 

1 2 3 4 5 6 [ 7 ] 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

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

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

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

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

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

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

vector lt;int gt; v;

V.reserveC 2 );

assert( v.capacityC) == 2 );

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

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

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

assert( V.capacityC) gt;= 2 );

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

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

= 1;

= 2;

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

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

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

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

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

gt; Рекомендация

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

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

vector lt;int gt; v; V.reserveC 100 );

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

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

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

Само собой разумеется, присваивания v[0] = 1; v[l] =2; будут вполне корректны и осмысленны, если заменить вызов v.reserve(2) вызовом v.resize(2). Можно также получить корректный код, заменив присваивания вызовами v.push back(l); v.push back(2);, которые обеспечивают безопасный способ размещения элементов в конце контейнера.

for(vector lt;int gt;::iterator i = v.beginC); i lt;v.end(); i++){ cout laquo; *i laquo; end!;

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

То есть формально в цикле нет ошибки, что, однако, не исключает необходимости привести ряд стилистических замечаний.

1. Старайтесь по возможности использовать const-вариант итератора. Если итератор не используется для модификации содержимого вектора, следует использовать const... i terator.

2. Итераторы следует сравнивать при помощи оператора сравнения ! = , но не при помощи lt;. Конечно, так как vector lt;int gt;: : iterator - итератор произвольного доступа (само собой разумеется, не обязательно типа i nt*!), нет никаких проблем при сравнении lt; v.endO, использованном в примере. Однако такое сравнение при помощи lt; работает только с итераторами произвольного доступа, в то время как сравнение с использованием оператора != работает со всеми типами итераторов. Поэтому мы должны везде использовать именно такое сравнение, а сравнение lt; оставить только для тех случаев, где это действительно необходимо. (Заметим, что сравнение != существенно облегчит переход к использованию другого типа контейнера в будущем, если это вдруг потребуется. Например, итераторы std: : 1 i st не поддерживают сравнение с использованием оператора lt;, так как являются би-направленными итераторами.)

3. Лучше использовать префиксную форму операторов -- и ++ вместо постфиксной. Возьмите за привычку писать в циклах по умолчанию ++i вместо i ++, если только вам действительно не требуется старое значение i. Например, постфиксная форма оператора естественна при использовании кода наподобие v[i++] для обращения к /-му элементу и одновременно увеличения счетчика цикла.

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

Примечание. Если ваша реализация vector lt;i nt gt;:: i terator представляет собой простой указатель i nt*, а функция end() встраиваемая, то при определенном уровне оптимизации накладные расходы будут сведены практически к нулю, так как интеллектуальный компилятор будет способен обнаружить, что значение, возвращаемое end О, не изменяется в процессе работы цикла. Современные компиляторы вполне способны справиться с такой задачей. Однако если vec-tor lt;int gt;: : iterator не является i nt- (например, в большинстве отладочных реализаций это тип класса), функции не являются встраиваемыми и/или компилятор не способен выполнить необходимую оптимизацию, вьтесение вычислений из цикла может существенно повысить производительность кода.

5. Предпочтительнее использовать \п вместо end!. Использование endl заставляет выполнить сброс внутренних буферов потока. Если поток буферизован, а сброс буферов

1 2 3 4 5 6 [ 7 ] 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90