Блог

Нужно ли мне использовать size_t always при индексации массива, даже если массив недостаточно велик, чтобы превышать размер int ?

Вопрос не в том, когда я должен использовать size_t . Я просто хочу знать, имеет ли, например, программа, имеющая 2 ГБ доступной памяти (все эти поля могут быть проиндексированы с помощью int32), но при этом эта память (виртуальная память) назначается «полям» 14 ГБ — 16 ГБ оперативной памяти компьютера.

Будет ли всегда сбой при индексации памяти, если я использую an int32 вместо a size_t (или an unsigned long int ) в этом случае?

Возможно, вопрос больше касается виртуальной памяти, чем указателей.

size_t это целое число без знака, способное содержать размер самого большого объекта, который вы можете выделить. Это полезно для индексации, потому что это означает, что он может индексироваться в самый большой массив, который вы можете выделить.

Это не означает, что это обязательно или даже обязательно рекомендуется для индексации. Вы можете использовать любой целочисленный тип, достаточно большой для индексации массива. int_fast32_t может быть быстрее, uint_least16_t может быть меньше в структуре и так далее. Знайте свои данные, и вы сможете сделать правильный выбор.

Одно из соображений, которое вы должны учитывать, заключается в том, что на некоторых платформах для использования подписанного индекса может потребоваться дополнительная инструкция расширения знака. В качестве примера, вот x86-64:

 // ; zero-extending idx (in edx) is "free" by simply using rdx.
// movzx eax, BYTE PTR [rcx rdx]
// ret
char get_index(char *ptr, unsigned idx)
{
   return ptr[idx];
}

// ; sign extending idx from 32 bits to 64 bits with movsx here.
// movsx rdx, edx     
// movzx eax, BYTE PTR [rcx rdx]
// ret
char get_index(char *ptr, int idx)
{
   return ptr[idx];
}
  

Виртуальная память выходит за рамки C или C . С их точки зрения, вы просто индексируете в память, и ваша платформа должна заставить ее работать. На практике ваше приложение использует только виртуальные адреса; ваш процессор / ОС незаметно преобразует виртуальный адрес в физический адрес. Это не то, о чем вам нужно беспокоиться.

Нужно ли мне использовать size_t always при индексации массива, даже если массив недостаточно велик, чтобы превышать размер an int ?

Нет, потому что индекс не является адресом или даже смещением в байтах. Это значение используется для вычисления смещения от указателя. Пока целочисленный тип достаточно велик, чтобы представлять наибольший индекс, вы можете получить доступ к любому элементу в массиве.

Тем не менее, есть некоторые подробности о том, как обрабатываются различные типы в контексте индекса массива. Этот вопрос помечен как C, так и C , и, несмотря на большое сходство, есть некоторые дополнительные колебания, которые могут возникнуть в C . Но давайте начнем с общих частей.

Чтобы упростить это объяснение, давайте предположим, что у вас есть машина с адресным пространством 4 ГБ и 16-битными int s.

 int a[8000];
  

Очевидно, что это объявляет массив из 8000 int s, проиндексированный от 0 до 7999. Компилятор обрабатывает 8000 литерал как an int , поэтому особых сюрпризов нет.

Но если бы литерал был 0x8000 , это было бы сложнее. Поскольку 16-разрядный int не может представлять 32768 (десятичный эквивалент 0x8000), он должен выбрать другой тип, например a long . Но, хотите верьте, хотите нет, если литерал был выражен в шестнадцатеричном формате, вместо этого он выберет an unsigned int . (Правила для литералов не совсем совпадают с правилами для целых продвижений.) На самом деле это не имеет значения, поскольку чистый эффект тот же.

Обратите внимание, что если бы мы использовали 0x8000, мы бы создали массив, который можно полностью проиндексировать с помощью 16-разрядного int , но нам пришлось бы использовать другой тип для представления его размера.

Индексирование в C является причудливым, и C наследует эту причудливость. Языкам все равно, меняете ли вы местами индекс и имя массива.

 a[3] = 42;
printf("%dn", 3[a]);  // legal, and prints "42"!
  

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

 a[3] = 42;
int *p = a   6;
printf("%dn", p[-3]);  // also legal, and prints "42"!

// off-topic
printf("%dn", -3[p]);  // legal, but does *not* print "42"!
  

Это говорит нам, что индексы могут быть целочисленными типами со знаком, но size_t всегда являются целочисленным типом без знака.

Все вышесказанное также относится к C , но C имеет некоторые дополнительные недостатки, если вы думаете о стандартных типах контейнеров библиотек, таких как std::vector и std::array .

Стандартные контейнеры определяют свои собственные типы размеров, например std::vector::size_type . Это почти всегда тот же базовый тип, std::size_t что и .

Стандартные контейнеры — это просто классы, определенные в библиотеке, поэтому причудливый синтаксис swap-pointer-and-index с ними не работает.

 std::vector<int> v = { 0, 1, 2, 3 };
std::cout << 3[v] << 'n';  // std container types cannot emulate this
                            // kind of array indexing
  

Итак, какого типа должен быть индекс? Ну, мы знаем, что это законно писать:

 std::cout << v[3] << 'n';
  

И мы знаем, что литерал 3 обрабатывается как an int , который подписан и, вероятно, имеет меньший диапазон, чем std::size_t —er, std::vector<int>::size_type . Надеюсь, это дает понять, что вам не нужно использовать тип size для индекса, если любой тип, который вы используете, может представлять желаемый индекс.

Индексирование со стандартными типами контейнеров осуществляется путем перегрузки operator[] типа размера контейнера. Итак, 3 может быть an int , но, чтобы соответствовать определению перегрузки, оно сначала будет преобразовано в std::vector<int>::size_type .

Другими словами, со стандартными типами контейнеров C вы эффективно всегда используете size_t для индексов, независимо от того, какой тип вы на самом деле используете.

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

• size_t в случае char[N] , uint8_t[N] , int[N] и т. Д
• size_t в случае std::vector и std::list
• int в случае QList и QVector
• целое число произвольной точности (aint) в случае bitarrays (если метод bitarray size() возвращает значение aint)
• нет в случае массивов, сжатых в памяти (если метод массива size() возвращает значение aint)
• нет в случае массивов, охватывающих несколько компьютеров (если метод массива size() возвращает значение aint)
• Другие языки, кроме C :
  • int в случае java.util.Collection и его подклассов

Вкратце: безопасный тип индекса — это тип, возвращаемый size() методом.

Примечание: если size() метод возвращает unsigned size_t , то signed int и ssize_t не являются безопасными типами индексов. В случае gcc и clang флаги компилятора -Wsign-compare (enabled by -Wall ) и -Wconversion могут использоваться для предотвращения большинства этих случаев.