Здравствуй, сообщество CodeForces!
Иногда бывает так, что удобнее было бы, если бы мы имели возможность обращаться к элементам массива, которые имеют отрицательный индекс. Распространенное решение — узнать минимальный возможный индекс (mn), максимальный возможный индекс (mx) и создать массив размером abs(mn) + mx + 1. В таком случае обращение к -1 элементу превращается в обращение к -1 + abs(mn) элементу. Этот подход имеет несколько недостатков: легко забыть дописать + abs(mn) при обращении к массиву, тяжелее дебагать, код становится громоздким.
Решая задачу с последнего контесте (383D - Antimatter), я придумал похожее, но более удобное решение (в этой задаче нужно было обращаться к отрицательной сумме в динамике). Допустим, вам необходим массив, индексы которого лежат в промежутке [mn; mx] и mn < 0. Заведем массив mem[mx + abs(mn) + 1] и int* dp. В начале программы проинициализируем dp = mem + abs(mn). Готово! Можно обращаться к dp по отрицательным индексам в промежутке [mn, 0).
Пример использования 5771473.
А теперь вопросы:
1) Бояниста ли идея? Существуют ли другие пути обратиться к отрицательному индексу массива?
2) Есть ли подводные камни у этого метода? Чем это может быть плохо?
На этом все, спасибо за внимание.
Надурить компилятор это хорошо, но будь в С++ какая-то проверка на выход за границы массива — это все просто получало бы RTE.
Для двумерных и более многомерных массивов придётся на нижних уровнях заполнять целые массивы вашими сдвинутыми указателями, а так — вполне себе нормальная идея. Она имеет право на существование, если хорошо понимать реальные границы "массива", который вы таким образом реализуете, что в общем и так всегда надо делать.
В посылке, которую я привел в качестве примера, необходим был двумерный массив. Вроде особых сложностей не возникло. Просто надо помнить, что двумерный массив — это массив массивов.
Как уже написали ниже, можно сделать шаблонную обертку, вот её пример:
Как видно она занимает не так мало кода, может быть можно уменьшить, но зато двумерный массив создается очень простым заклинанием Array<Array<int, -10, 10>, -10, 10>.
Upd: ну и здесь есть memory leaks, надо добавить в деструктор удаление, но на олимпиадах не очень страшно.
Upd: отредактировал код после замечания.
Можно написать T buf[to — from + 1]; раз уж они зачем то шаблонные параметры
Спасибо, действительно, так проще.
Шаблонные, чтобы при объявлении писать не
а
По-моему, второй вариант менее затратен(по написанию):)
1) Да. Писали про это тут давно уже. Да и самому нетрудно догадаться.
2) Нет. Ничем. Главное знать точные границы.
int * const dp = mem + abs(mn);, именно так, а неconst int *dp(для пояснения почитай эту статью).UPD. Еще один подводный камень: не стоит так реализовывать массив вида arr[5..10], т.к. наш вспомогательный указатель будет в таком случае указывать на отрицательный элемент массива, а такие элементы не определены (читай главу 5.4 книги Кернигана и Ритчи). С отрицательным правым индексом ситуация аналогичная.
наш вспомогательный указатель будет в таком случае указывать на отрицательный элемент массива, а такие элементы не определены
А в чем проблема? В указателе невалидный адрес, ну ничего страшного. Пока мы не пытаемся разыменовать его. А если попытаемся, то это можно понимать как обычный себе выход за пределы массива.
Проблема в том, что по стандарту поведение не опредлено и оптимизатор может попробовать это использовать
Неопределённое поведение возникает в момент разыменования указателя, а не тогда, когда в указатель записывают плохой адрес. Иначе бы даже такой код приводил бы к неопределённому поведению:
n3242, 5.7.2
When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined
Круто, я этого не знал.
riadwaw выше сослался на стандарт, но ничего не пояснил.
А суть в том, что Вы в-принципе правы, если опираться на то, что у нас архитектура x86 с плоской моделью памяти. Тут все наши адреса являются обыкновенными целыми числами, и указательная арифметика реализуется совсем втупую.
Но представим себе, что мы используем сегментную модель памяти. Тогда у нас вполне может быть такая ситуация, что куски нашего массива разбросаны по совершенно разным сегментам, и выразить указатель на элемент массива просто как линейный адрес не получится. Соответственно, чтобы вся наша указательная арифметика работала, компилятору придется хитрить (в стандарте вроде бы не сказано, что указатель дожен быть просто целым числом). ОК, все, что указано в стандарте, у нас работает. А теперь попробуйте представить, что будет, если мы попробуем сослаться на не определенный стандартом элемент массива (я уж молчу про разыменование такого указателя).
UPD. Раз уж Вы заговорили про нулевой указатель, напомню, что он стандартом еще как определен.
В MSDOS в 16-битных приложениях легко можно было словить ошибку в цикле вида:
если index становился меньше start_index и start_index находился на границе сегмента, то получался бесконечный цикл: н-р start_index = ABCD:0000
index: ABCD:0001 -> ABCD:ABCD:0000 -> ABCD:FFFF ну и дальше по накатанному, условие никогда не выполняется.
Мне кажется, у Вас в коде должно быть
while (--index >= start_index), нет?Верно, --index >= start_index. Исправил. Благодарю.
В принципе я сам так делаю, и сложностей не возникало. Но вообще есть подозрение вот какого рода. Не может ли оптимизатор сделать из таких действий каких-нибудь нехороших выводов. Например, если есть указатель и его разыменовывали, то оптимизатор имеет право предполагать, что он не NULL, потому что если это был NULL, то уже случилась ошибка, и в любом случае undefined behaviour. Нет ли здесь какого-то похожего эффекта.
Здесь всё в порядке. Неопределённое поведение вызывает обращение к памяти за пределами массива, а способ, как мы рассчитываем адрес ячейки, не имеет значения — главное не выйти за фактические пределы. Это то же самое, что сделать
и потом писать
Проблем быть точно не должно, оператор квадратные скобки, применённый к массиву A[i], превращается компилятором в *((A) + (i)).
Именно это позволяет нам написать такую конструкцию:
int A[17];
0[A] = 1;
Можно просто написать:
недостаточно удобно, надо сделать:
Тоже не так круто — а если несколько массивов в программе?
За такие define-ы руки надо отрывать :)