Как этот кусок кода определяет размер массива без использования sizeof ()?

134

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

#include <stdio.h>

int main() {
    int a[] = {100, 200, 300, 400, 500};
    int size = 0;

    size = *(&a + 1) - a;
    printf("%d\n", size);

    return 0;
}

Как и ожидалось, возвращается 5.

редактировать: люди указали на этот ответ, но синтаксис немного отличается, то есть метод индексации

size = (&arr)[1] - arr;

поэтому я считаю, что оба вопроса верны и имеют несколько иной подход к проблеме. Спасибо всем за огромную помощь и подробное объяснение!

janojlic
источник
13
Ну, не могу найти его, но, похоже, так оно и есть. В Приложении J.2 четко указано: операнд унарного оператора * имеет недопустимое значение и является неопределенным поведением. Здесь &a + 1не указывается ни на один действительный объект, поэтому он недействителен.
Евгений Ш.
5
Возможный дубликат Find size of array без использования sizeof в C
Alma Do
@Alma Хорошо, синтаксис немного отличается, то есть часть индексации, так что я считаю, что этот вопрос по-прежнему актуален сам по себе, но я могу ошибаться. Спасибо за указание на это!
janojlic
1
@janojlicz Они, по сути, такие же, потому что (ptr)[x]такие же, как *((ptr) + x).
SS Anne

Ответы:

135

Когда вы добавляете 1 к указателю, результатом является местоположение следующего объекта в последовательности объектов указательного типа (т. Е. В массиве). Если pуказывает на intобъект, то p + 1будет указывать на следующий intв последовательности. Если pуказывает на массив из 5 элементов int(в данном случае это выражение &a), то p + 1будет указывать на следующий массив из 5 элементовint в последовательности.

Вычитание двух указателей (при условии, что они оба указывают на один и тот же объект массива или один указывает один за последним элементом массива) дает число объектов (элементов массива) между этими двумя указателями.

Выражение &aвозвращает адрес aи имеет тип int (*)[5](указатель на массив из 5 элементов int). Выражение &a + 1возвращает адрес следующего 5-элементного массива intследующего a, а также имеет тип int (*)[5]. Выражение *(&a + 1)разыменовывает результат &a + 1, так что оно дает адрес первого, intследующего за последним элементом a, и имеет тип int [5], который в этом контексте «распадается» на выражение типа int *.

Точно так же выражение a«распадается» на указатель на первый элемент массива и имеет тип int *.

Картинка может помочь:

int [5]  int (*)[5]     int      int *

+---+                   +---+
|   | <- &a             |   | <- a
| - |                   +---+
|   |                   |   | <- a + 1
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+
|   | <- &a + 1         |   | <- *(&a + 1)
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+

Это два представления одного и того же хранилища - слева мы рассматриваем его как последовательность из 5-элементных массивов int, а справа - как последовательность int. Я также показываю различные выражения и их типы.

Помните, что выражение *(&a + 1)приводит к неопределенному поведению :

...
Если результат указывает на один последний элемент массива, он не должен использоваться как операнд унарного * оператора, который оценивается.

C 2011 Онлайн проект , 6.5.6 / 9

Джон Боде
источник
13
Этот текст «не должен использоваться» является официальным: C 2018 6.5.6 8.
Eric Postpischil
@EricPostpischil: есть ли у вас ссылка на предварительный проект 2018 года (похожий на N1570.pdf)?
Джон Боде
1
@JohnBode: у этого ответа есть ссылка на Wayback Machine . Я проверил официальный стандарт в своей купленной копии.
Эрик Постпищил
7
Так что, если кто-то написал size = (int*)(&a + 1) - a;этот код будет полностью действительным? : o
Гизмо
@Gizmo они, вероятно, изначально не писали это, потому что таким образом вы должны указать тип элемента; оригинал, вероятно, был написан как макрос для универсального типа для разных типов элементов.
Леушенко
35

Эта строка имеет наибольшее значение:

size = *(&a + 1) - a;

Как видите, он сначала берет адрес aи добавляет его к нему. Затем он разыменовывает этот указатель и вычитает из него исходное значение a.

Арифметика указателя в C заставляет это возвращать количество элементов в массиве, или 5. Добавление одного и &aуказателя на следующий массив через 5 intс после a. После этого этот код разыменовывает результирующий указатель и вычитает a(тип массива, который распался на указатель) из этого, давая количество элементов в массиве.

Подробности о том, как работает арифметика указателей:

Скажем, у вас есть указатель, xyzкоторый указывает на intтип и содержит значение (int *)160. Когда вы вычитаете любое число из xyz, C указывает, что фактическая сумма, вычитаемая из xyzэтого числа, равна размеру, на который он указывает. Например, если вы вычли 5из xyz, значение xyzрезультата будет, xyz - (sizeof(*xyz) * 5)если арифметика указателя не применяется.

Как aи массив 5 intтипов, полученное значение будет 5. Однако это не будет работать с указателем, только с массивом. Если вы попробуете это с указателем, результат всегда будет 1.

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

a + 0 | [a[0]] | &a points to this
a + 1 | [a[1]]
a + 2 | [a[2]]
a + 3 | [a[3]]
a + 4 | [a[4]] | end of array
a + 5 | [a[5]] | &a+1 points to this; accessing past array when dereferenced

Это означает, что код вычитает aиз &a[5](или a+5), давая 5.

Обратите внимание, что это неопределенное поведение, и его не следует использовать ни при каких обстоятельствах. Не ожидайте, что такое поведение будет одинаковым на всех платформах, и не используйте его в производственных программах.

СС Энн
источник
27

Хм, я подозреваю, что это что-то, что не сработало бы в первые дни C. Хотя это умно.

Делая шаги по одному:

  • &a получает указатель на объект типа int [5]
  • +1 получает следующий такой объект, предполагая, что есть массив этих
  • * эффективно преобразует этот адрес в указатель типа на int
  • -a вычитает два указателя int, возвращая количество экземпляров int между ними.

Я не уверен, что это полностью законно (в данном случае я имею в виду юридическое сопровождение языка - не будет работать на практике), учитывая некоторые операции типа. Например, вам только «разрешено» вычитать два указателя, когда они указывают на элементы в одном массиве. *(&a+1)был синтезирован путем доступа к другому массиву, хотя и к родительскому массиву, поэтому фактически не является указателем на тот же массив, что и a. Кроме того, хотя вам разрешено синтезировать указатель за последним элементом массива, и вы можете рассматривать любой объект как массив из 1 элемента, операция разыменования ( *) не «разрешена» для этого синтезированного указателя, даже если она не имеет поведения в этом случае!

Я подозреваю, что в первые дни C (синтаксис K & R, кто-нибудь?) Массив распадался на указатель гораздо быстрее, поэтому он *(&a+1)мог бы только вернуть адрес следующего указателя типа int **. Более строгие определения современного C ++ определенно позволяют указателю на тип массива существовать и знать размер массива, и, вероятно, стандарты C последовали его примеру. Весь код функции C принимает в качестве аргументов только указатели, поэтому видимая техническая разница минимальна. Но я только догадываюсь здесь.

Такой подробный вопрос о легальности обычно применяется к интерпретатору C или к инструменту типа lint, а не к скомпилированному коду. Интерпретатор может реализовать двумерный массив в виде массива указателей на массивы, потому что существует одна функция на этапе выполнения, которую нужно реализовать, и в этом случае разыменование +1 будет фатальным, и даже если это сработает, даст неправильный ответ.

Другая возможная слабость может заключаться в том, что компилятор C может выравнивать внешний массив. Представьте, что это был массив из 5 символов ( char arr[5]), когда программа выполняет &a+1ее, она вызывает поведение «массив массива». Компилятор может решить, что массив массива из 5 chars ( char arr[][5]) фактически сгенерирован как массив массива из 8 chars ( char arr[][8]), так что внешний массив хорошо выравнивается. Код, который мы обсуждаем, теперь сообщает о размере массива как 8, а не 5. Я не говорю, что определенный компилятор определенно сделает это, но это возможно.

Джем Тейлор
источник
Справедливо. Однако по причинам, которые трудно объяснить, все используют sizeof () / sizeof ()?
Джем Тейлор
5
Большинство людей делают. Например, sizeof(array)/sizeof(array[0])дает количество элементов в массиве.
SS Anne
Компилятору C разрешено выравнивать массив, но я не уверен, что после этого можно изменять тип массива. Выравнивание будет более реалистично реализовано путем вставки байтов заполнения.
Кевин
1
Вычитание указателей не ограничивается только двумя указателями в одном и том же массиве - указатели также могут находиться за одним концом массива. &a+1определено. Как отмечает Джон Боллинджер, *(&a+1)это не так, поскольку он пытается разыменовать объект, который не существует.
Эрик Постпищил
5
Компилятор не может реализовать char [][5]как char arr[][8]. Массив - это просто повторяющиеся объекты в нем; там нет отступов. Кроме того, это нарушило бы (ненормативный) пример 2 в C 2018 6.5.3.4 7, который говорит нам, что мы можем вычислить количество элементов в массиве с sizeof array / sizeof array[0].
Эрик Постпищил