Почему ~ size_t (0) (== 0xFFFFFFFF в большинстве 32-разрядных систем) не является допустимым индексом массива?

Ответ 1

ВАЖНОЕ ПРИМЕЧАНИЕ: Термин "индекс памяти" неоднозначен и запутан. Связанная статья относится строго к индексам массива, а не к адресам в памяти. Для size_t вполне справедливо быть неспособным представлять все адреса памяти, поэтому у нас есть тип intptr_t на C99. Конечно, это не относится к вашей рабочей станции, что, несомненно, имеет простую архитектуру типа фон Неймана. (С тех пор этот вопрос был отредактирован для удаления ссылок на "индексы памяти".)

Стандарт C гарантирует, что size_t может содержать размер любого массива. Однако для любого массива a[N] стандарт гарантирует, что a + N должен быть допустимым указателем и сравнивать не равным любому указателю на элемент a.

Следовательно, size_t должен иметь возможность представлять хотя бы одно значение, большее любого возможного индекса массива. Поскольку ~(size_t)0 гарантированно является максимальным значением size_t, это хороший выбор дозорного для индексов массива.

Обсуждение:

• Почему ~(size_t)0 гарантированно является максимальным? Поскольку стандарт явно говорит так: из § 6.5.3.3: "Если продвигаемый тип является неподписанным типом, выражение ~E эквивалентно максимальному значению, представленному в этом тире минус E". Обратите внимание, что (size_t)-1 гарантированно также будет максимальным по правилам преобразования от подписанных к неподписанным типам. К сожалению, не всегда легко найти определение для SIZE_MAX на вашей платформе, поэтому (size_t)-1 и ~(size_t)0 являются предпочтительными. (Обратите внимание, что это уже не так, если int может представлять SIZE_MAX... но это не то, что произойдет в реальной системе.)

• Каков размер массива с индексом от 0 до ~ 0? Такой массив не может существовать в соответствии со стандартом C, аргументом, изложенным в верхней части этого сообщения.

• Если вы malloc(-1), результирующая область памяти должна начинаться с нуля (FALSE). Есть много действительно странных случаев, которые стандарт позволяет, но на практике это не встречается. Например, представьте себе систему, где (uintptr_t)-1 > (size_t)-1. Стандарт C формулируется точно так, как это происходит, потому что он не просто запускается на вашем ПК, он работает на причудливых небольших DSP с архитектурой Гарварда, и он работает на архаичных системах с византийскими схемами сегментирования памяти. Существуют также некоторые системы, представляющие исторический интерес, где указатели NULL не имеют того же представления, что и 0.

Ответ 2

Интуиция такова:

x = malloc(~size_t(0));    // the most you can allocate
x[~size_t(0) -1];          // the highest valid index

Ответ 3

Ну, как @Apprentice Queue правильно отметили в своем ответе, так как размер самого большого непрерывного объекта в C или С++-программе ограничен SIZE_MAX (так же, как (size_t) -1, то же, что и ~size_t(0)), максимальный индекс вам нужно будет индексировать байты этого объекта SIZE_MAX - 1. Но в то же время, как @Dietrich Epp правильно отмечает в своем ответе, C и С++ разрешают арифметику адреса одного элемента за пределами массива, что делает SIZE_MAX допустимым индексом, если не для доступа к элементам массива, тогда на наименее для арифметики указателя. Таким образом, формально говоря SIZE_MAX является допустимым индексом, хотя он не может стоять за существующий элемент массива.

Однако вся идея использования size_t как типа, который позволяет "индексировать всю память", действительна только в пределах некоторой конкретной платформы, где size_t действительно оказывается достаточным для индексирования памяти ( К этой категории относятся платформы с плоской памятью, такие как Win32, Win64, Linux). В действительности, с общей точки зрения, тип size_t недостаточен для индексирования памяти. Тип size_t гарантирован только для того, чтобы индексировать байты в одном непрерывном объекте в программе C или С++. Ни C, ни С++ не гарантируют поддержку непрерывных объектов, которые охватывают все адресное пространство. Другими словами, тип size_t, как гарантируется, будет достаточным для индексации любого явно объявленного объекта массива в программе C/С++, но, как правило, этого недостаточно для подсчета узлов в связанном списке. Тем не менее, в предположении, что на некоторой конкретной платформе диапазон size_t покрывает всю память, значение (size_t) -1 выглядит как хороший выбор "зарезервированного" значения, так как этот индекс может стоять только за последний байт в массив байтов, охватывающий все адресное пространство. Очевидно, что никто никогда не будет нуждаться в этом индексе на практике для фактической индексации.

Тем не менее, если вас действительно интересует формально соответствующий тип, который может индексировать всю память (и, следовательно, способен хранить количество элементов в любом контейнере в памяти), это будет uintptr_t, а не size_t. Автор этого блога, похоже, понимает общую проблему здесь, так как он отмечает, что size_t не подходит для индексирования файлов (т.е. Для хранения размеров или смещений файлов). Тем не менее, было бы неплохо заметить, что для тех же самых причин тип size_t не подходит для индексирования памяти. Тип size_t на самом деле не связан с ОЗУ или адресным пространством процесса, вопреки тому, что автор утверждает в своей записи в блоге. Тип uintptr_t связан с адресным пространством процесса, но не size_t. Тот факт, что size_t достаточно на платформах, которые он упоминает, является не чем иным, как специфическим свойством этих платформ.

Ответ 4

Да; До сих пор я прочитал все ответы. Теперь я добавлю простой пример с двумя значительными битами. Максимальное представляемое 2-битное значение без знака равно 3, что означает, что мы можем выделить в лучшем случае 3 единицы хранения.

Индексы к единицам: [0, 1, 2] - обратите внимание, что максимальное значение 3 не находится в пределах диапазона адресов, потому что невозможно выделить хранилище с большим количеством всего с двумя битами.

Основной причиной этого является то, что индексирование в C и С++ начинается с нуля. Индексы "отключены на единицу", потому что размер 1 перекрывает смещение 0. Это приводит к тому, что индексы с таким же количеством бит достигают одного элемента, кроме размера.

Это версия ответа ELI-5.

Практические примеры:

char [4];//ОШИБКА: 4 не представляется с 2 битами

uint32_t buffer [1];//HACK: мы выделили 4 символа.. теперь что?

Ответ 5

Ответ Дитрих Эпп, конечно, совершенно правильный. Тем не менее, я хочу добавить к нему техническую причину: просто невозможно выделить массив настолько большой, чтобы ~size_t(0) мог его индексировать.

Дело в том, что в вашем адресном пространстве в каждый момент времени есть как минимум несколько байтов кода, поэтому вы просто не имеете всего виртуального адресного пространства в вашем распоряжении для сопоставления массива. (И я даже не упоминал о распределении для пространства стека и нулевой страницы!) Понимаете, единственное место, где массив, который может быть проиндексирован с помощью ~size_t(0), может быть сопоставлен, равен нулю, и он будет распространяться на каждый байт виртуальной памяти, так что последний байт может быть проиндексирован. Это невозможно сделать.

Также рассмотрите это: ваш ЦП не заботится о знаке при добавлении чисел. Для CPU добавление ~size_t(0) к значению совпадает с уменьшением этого значения на единицу. И уменьшение любого указателя на один указывает на то, что оно находится за пределами выделенного диапазона памяти, если только это не указатель null, который не может указывать на допустимый диапазон памяти...

Ограничение языкового стандарта, что распределения не могут быть больше ~size_t(0), намного слабее, чем эти технические ограничения.