LINUX.ORG.RU

[c] многомерный массив


0

1

Из Output 1/2 видно, что одномерный (вектор) и многомерный массивы хранятся в памяти одинаково - в виде вектора [x1, x2, x3, x4] (запись идет по-строкам). При этом a и b - указатели на векторы, т. е. хранят адреса, по которым размещены векторы.

Вопрос вызывает Output 3. Если разобрать выражение *((*(a+i))+j)), получится:

1. К адресу первого элемента прибавляем число равное произведению индекса i и размера элемента.

2. Полученное в п1 значение трактуется как адрес переменной (указатель). Из этого адреса извлекается значение (происходит разыменование указателя) и складывается со вторым индексом j умноженным на размер элемента.

3. Полученное в п2 значение трактуется как адрес переменной (указатель). Из этого адреса извлекается значение (выполняется второе разыменование указателя) которое и является результатом выражения.

Как, при всем этом, Output 3 может работать правильно? Ведь у нас переменная "a" указатель на «одномерный» массив, а не указатель на массив указателей. Откуда _два_ разыменования?

       
 указатель на одномерный массив                  

  &---&       &-------------------&                      
  | a |------>| x1 | x2 | x3 | x4 |               
  &---&       &-------------------&                    
                                                  
 указатель на массив указателей                   

  &---&       &---------& 
  | a |------>| x1 | x2 | 
  &---&       &---------& 
                |     |  
                |     |  
                V     V  
               &--&  &--&
               |y1|  |y1|
               |y2|  |y2|
               &--&  &--&
Код:
#include <stdio.h>

int main() {
    int i, j;
    int a[2][2]={{1, 2},
                 {3, 4}};

    int b[4]={1, 2, 3, 4};

    printf("Output 1: ");

    for (i=0; i < 2; i++)
        for (j=0; j < 2; j++)
            printf("%d ",((int*)a)[i*2+j]);

    printf("\nOutput 2: ");

    for (i=0; i < 2; i++)
        for (j=0; j < 2; j++)
            printf("%d ",b[i*2+j]);

    printf("\nOutput 3: ");

    for (i=0; i < 2; i++)
        for (j=0; j < 2; j++)
            printf("%d ",*((*(a+i))+j));
    printf("\n");
    
    return 0;
}
Вывод:
$ ./test
Output 1: 1 2 3 4 
Output 2: 1 2 3 4 
Output 3: 1 2 3 4 


А в чем вопрос-то? У вас a - указатель на указатель. *(a+i) дает первый индекс (т.е. адрес i-й строки) и идентично &a[0], второе разыменование уже к адресации отдельного элемента, т.е. в вашем случае это то же самое, что и a[j].

Вы бы лучше спросили, почему ((int*)a)[i*2+j]) работает :)

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Да, а работает первый вариант лишь потому, что вы массив статически создали. А вот создавали бы вы его динамически, такая конструкция не сработала бы :)

Eddy_Em ☆☆☆☆☆ ()

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

вся магия в арифметике указателей. указатель + 1 = адрес + sizeof(типа)

anonymous ()
Ответ на: комментарий от anonymous

В том-то и «прикол», что при динамическом создании массивов эти самые строки могут быть разбросаны где угодно.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

в си все массивы одномерные и хранятся по строкам в последовательных участках памяти.

Значит, так:

 указатель на одномерный массив                  

  &---&       &-------------------&                      
  | a |------>| x1 | x2 | x3 | x4 |               
  &---&       &-------------------&   
Разыменовываем первый раз, получаем, допустим, x1. Дальше уперлись в _обычное число_ x1 (пусть будет x1 = 1), как его разыменовывать?

ipc ()

> int a[2][2]

*((*(a+i))+j)


0. a имеет тип int [][]
1. *(a + i) эквивалентно a[i]
2. a[i] имеет тип int []
3. *(a[i] + j) эквивалентно a[i][j]

Так в чем проблема?

geekless ★★ ()
Ответ на: комментарий от ipc

> Разыменовываем первый раз, получаем, допустим, x1. Дальше уперлись в _обычное число_ x1 (пусть будет x1 = 1), как его разыменовывать?

На тип переменной a посмотри и подумай, что за «число» будет, если его разименовать 1 раз. Это в памяти у тебя «плоский одномерный массив», а в семантике типов совсем не одномерный.

geekless ★★ ()
Ответ на: комментарий от Eddy_Em

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

При статическом создании двухмерного массива в памяти образуется a) или b)?

a)

  &---&       &-------------------&                      
  | a |------>| x1 | x2 | x3 | x4 |               
  &---&       &-------------------&                    
                                                  
b)

  &---&       &---------& 
  | a |------>| x1 | x2 | 
  &---&       &---------& 
                |     |  
                |     |  
                V     V  
               &--&  &--&
               |y1|  |y1|
               |y2|  |y2|
               &--&  &--&

ipc ()
Ответ на: комментарий от ipc

Вы заведомо неверно думаете. Вам уже разжевали же: a - двойной указатель, a[0] указывает на x1, а[1] - на x3, второе разыменование дает уже адреса элементов по строкам. То, что в вашем случае обе строки оказались в памяти последовательно - скорее исключение, чем правило!

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

> *(a+i) дает первый индекс (т.е. адрес i-й строки) и идентично &a[i][0]

Имхо, достаточно было указать, что операция p[i] эквивалентна *(p+i), и, соответственно, пример ТСа просто по определению эквивалентен a[i][j]. :)

geekless ★★ ()
Ответ на: комментарий от Eddy_Em

Вот:


      a[0] -> a[0][0], a[0][1], a[1][0], a[1][1]
a ->                             A
      a[1] ----------------------|

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от geekless

Дописал в конец той же программы:

    printf("\nOutput 4: ");

    for (i=0; i < 4; i++)
        printf("%d ",((int*)a)[i]);

    printf("\n");
Вывод:
Output 4: 1 2 3 4 

На тип переменной a посмотри и подумай, что за «число» будет, если его разименовать 1 раз.

Если разыменовать один раз, будет число 1..4. О чем и вопрос (про то, что *(a + i) эквивалентно a знаю), как такое может получиться.

ipc ()
Ответ на: комментарий от geekless

Указал уже.

Кстати, т.к. операция сложения коммутативна, то *(p+i) - то же самое, что и *(i+p), в результате возможны такие «фокусы», как p == i

:)

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от geekless

при определении a как int* a[] = { {...}, {...} }

А по-моему, int const *a и int a[] - одно и то же ==> int const *a[] и int a[][] - тоже одно и то же :)

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от ipc

[pre]
&---& &-----------------------&
| a |------>| a11 | a12 | a21 | a22 |
&---& &-----------------------&
[/pre]

a[x][y] = x + y * (sizeof(type_of_element(a)) * num_cols(a));

exception13 ★★★★★ ()
Ответ на: комментарий от ipc

> Дописал в конец той же программы:

Ну и? Взяли указатель на двумерный массив, проинтерпретировали его как указатель на одномерный массив, и в силу того, что в памяти данные расположены именно так, получили соответствующий результат.

Если разыменовать один раз, будет число 1..4.

Так в этом примере ты разыменовал int*, а не int[][]. Feel the difference.

geekless ★★ ()
Ответ на: комментарий от Eddy_Em

Вы заведомо неверно думаете. Вам уже разжевали же: a - двойной указатель, a[0] указывает на x1, а[1] - на x3,

Почему тогда

    int a[2][2]={{1, 2},
                 {3, 4}};

    printf("\nOutput 5: ");
    printf("a[1] = %d\n ",((int*)a)[1]);
дает
Output 5: a[1] = 2
а не a[1]= x3 = 3 ?

ipc ()
Ответ на: комментарий от Eddy_Em

> int const *a и int a[] - одно и то же ==> int const *a[] и int a[][]

Неверно.

int const *a - это указатель, int a[] - это кусок памяти из нескольких последовательно расположенных объектов (на который хранится указатель, да). То, что на уровне реализации они оба являются указателями не отменяет того, что у них разная семантика. Поэтому, например, int **a - всего лишь указатель на указатель, а int[N][M] - указатель на цельный кусок памяти, в котором расположено N объектов типа int[M].

geekless ★★ ()

6.5.2.1 Array subscripting
Constraints
1
One of the expressions shall have type ‘‘pointer to object type’’, the other expression shall
have integer type, and the result has type ‘‘type’’.
Semantics
2
A postfix expression followed by an expression in square brackets [] is a subscripted
designation of an element of an array object. The definition of the subscript operator []
is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion rules that
apply to the binary + operator, if E1 is an array object (equivalently, a pointer to the
initial element of an array object) and E2 is an integer, E1[E2] designates the E2-th
element of E1 (counting from zero).
3
Successive subscript operators designate an element of a multidimensional array object.
If E is an n-dimensional array (n ≥ 2) with dimensions i × j × . . . × k, then E (used as
other than an lvalue) is converted to a pointer to an (n − 1)-dimensional array with
dimensions j × . . . × k. If the unary * operator is applied to this pointer explicitly, or
implicitly as a result of subscripting, the result is the pointed-to (n − 1)-dimensional array,
which itself is converted into a pointer if used as other than an lvalue. It follows from this
that arrays are stored in row-major order (last subscript varies fastest).
4
EXAMPLE
Consider the array object defined by the declaration
int x[3][5];
Here x is a 3 × 5 array of ints; more precisely, x is an array of three element objects, each of which is an
array of five ints. In the expression x[i], which is equivalent to (*((x)+(i))), x is first converted to
a pointer to the initial array of five ints. Then i is adjusted according to the type of x, which conceptually
entails multiplying i by the size of the object to which the pointer points, namely an array of five int
objects. The results are added and indirection is applied to yield an array of five ints. When used in the
expression x[i][j], that array is in turn converted to a pointer to the first of the ints, so x[i][j]
yields an int.
Forward references: additive operators (6.5.6), address and indirection operators
(6.5.3.2), array declarators (6.7.5.2).
Murr ★★ ()
Ответ на: комментарий от geekless

Поэтому, например, int **a - всего лишь указатель на указатель, а int[N][M] - указатель на цельный кусок памяти, в котором расположено N объектов типа int[M].

А по скорости вроде бы одинаково...

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

А по скорости вроде бы одинаково...

$ cat qwert.c

int f1(int a[2][2])
{
	return a[1][1];
}

int f2(int** p)
{
	return p[1][1];
}

3:~$ cat qwert.s
	.file	"qwert.c"
	.text
	.p2align 4,,15
.globl f1
	.type	f1, @function
f1:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	popl	%ebp
	movl	12(%eax), %eax
	ret
	.size	f1, .-f1
	.p2align 4,,15
.globl f2
	.type	f2, @function
f2:
	pushl	%ebp
	movl	%esp, %ebp
	movl	8(%ebp), %eax
	popl	%ebp
	movl	4(%eax), %eax
	movl	4(%eax), %eax
	ret
	.size	f2, .-f2
	.ident	"GCC: (GNU) 4.5.2 20110127 (prerelease)"
	.section	.note.GNU-stack,"",@progbits
geekless ★★ ()
Ответ на: комментарий от Eddy_Em

Hint:

в первой функции:
movl 12(%eax), %eax -> eax = *(eax + 12)
во второй функции:
movl 4(%eax), %eax -> eax = *(eax + 4)
movl 4(%eax), %eax -> eax = *(eax + 4)

geekless ★★ ()
Ответ на: комментарий от Eddy_Em

почему ((int*)a)[i*2+j]) работает :)

очевидно же. 2 - размерность массива.

по теме: *(a+i) то же самое что a. размеры типов компилятор сам разруливает.

nanoo_linux ()
Ответ на: комментарий от ipc

потому что a сначала преобразуется в int*, а потом применяется оператор []. Ты же сам компилятору об этому указал.

Если написать так: a, то будет не 3, а адрес второй строки в твоём массиве (подозреваю, что компилер ругнётся).

nanoo_linux ()
Ответ на: комментарий от Eddy_Em

У вас a - указатель на указатель.

Т. е.

  указатель     на   указатель
  a (адрес) --------> (адрес) -------> (данные)  
Так?

Код:

    printf("\nOutput 6: ");
    printf("%x   %x\n ",*a, *((int*)a));
Вывод:
Output 6: bf8a7f28   1

Разыменование - взятие данных, находящихся по адресу. Тогда почему адрес трактуется по-разному в зависимости от cast'а?

ipc ()
Ответ на: комментарий от ipc

Cast - что-то большее, чем указка компилятору считать данную переменную принадлежащей определенному типу, при этом выполняются какие-то дополнительные действия?

ipc ()
Ответ на: комментарий от ipc

> Так?

Не так. Eddy_Em ошибся в том комменте. Перечитайте уже весь тред.

Разыменование - взятие данных, находящихся по адресу. Тогда почему адрес трактуется по-разному в зависимости от cast'а?


Потому что надо учитывать тип данных.

Дано: int a[N][M]
Применяем: a[2], что эквивалентно *(a+2). Чему равен тип a+2? Он по-прежнему равен int[N][M], ок. Чему равен тип *(a+2)? Он равен int[M]. А что такое, int[M]? Это кусок памяти, в котором лежит M объектов типа int. (Которые физически лежат внутри цельного int a[N][M], но это не важно.)

Если же ты принудительно кастуешь значение a в int*, то получаешь указатель на целое, и результат его разыменования будет int, а не массив int-ов. Осознай разницу.

geekless ★★ ()
Ответ на: комментарий от ipc

Тебе мама испекла пирожков. Ты маме говоришь: «Мам, а с чем пирожки?», Мама говорит: «Вот эти - с картошкой, в вот эти - с мясом!». Ты кричишь: «С мясом! мммммммм! Люблю с мясом!».

Вот так и ты компилятору говоришь: «Вот тебе указатель на int. А это - указатель на char, А это два - вообще на структуру вот такую то». И компилятор сам смещения разруливает. если так ((int *)a)[2] то смещение будет sizeof(int)*2 (8 байт например), если так ((char *)a)[2] то sizeof(char)*2 (2 байта например).

Скачай k&r что-ли.

nanoo_linux ()
Ответ на: комментарий от geekless

> Чему равен тип a+2? Он по-прежнему равен int[N][M], ок.

Строго горя, даже не так. Перед сложением int[N][M] прозрачно кастуется в int(*)[M] (указатель на массив). К нему прибавляется 2 (физически - 2 * sizeof(int[M]) ). Тип результа сложения - int(*)[M].

Затем к нему применяется разыменование, получаем тип int[M]. (Физически при этом никаких команд НЕ ВЫПОЛНЯЕТСЯ, поскольку указатель на массив и массив в реализации одинаковы: просто адрес ячейки памяти.)

geekless ★★ ()
Ответ на: комментарий от nanoo_linux

Вот так и ты компилятору говоришь: «Вот тебе указатель на int. А это - указатель на char, А это два - вообще на структуру вот такую то». И компилятор сам смещения разруливает. если так ((int *)a)[2] то смещение будет sizeof(int)*2 (8 байт например), если так ((char *)a)[2] то sizeof(char)*2 (2 байта например).

Где здесь смещения (8 байт умножить на ноль, 2 байта умножить на ноль)?

    printf("\nOutput 6: ");
    printf("%x   %x\n ",*a, *((int*)a)); // Output 6: bf8a7f28   1

ipc ()
Ответ на: комментарий от ipc

8 байт умножить на ноль, 2 байта умножить на ноль

ты упоротый штоле? если у тебя a указывает на первый элемент, то что 8, что 2, что 42 умножить на смещение ноль - будет первый элемент.

*a это АДРЕС первой строки твоего массива,
*((int *)a)) здесь ты свой массив приводишь к int * (это будет указатель на первый элемент) и потом его разименовываешь.

nanoo_linux ()
Ответ на: комментарий от geekless

Если же ты принудительно кастуешь значение a в int*, то получаешь указатель на целое, и результат его разыменования будет int, а не массив int-ов. Осознай разницу.

ОК,

printf("%x\n ",*a) // выводит bf8a7f28
возвращает массив int-ов. «bf8a7f28» это какая часть этого массива?

ipc ()
Ответ на: комментарий от ipc

> возвращает массив int-ов. «bf8a7f28» это какая часть этого массива?

Совсем упоротый? Это его адрес.

geekless ★★ ()
Ответ на: комментарий от Eddy_Em

Вот:

cat 1.c
#include <stdio.h>

main(){
	int a[2][2] = {{1,2},{3,4}}, i,j;
	printf("a[0]=%x, a[1]=%x\n\n", a[0], a[1]);
	for(i = 0; i < 4; i++) printf("&(*a)[%d]=%x\n", i, &(*a)[i]);
	printf("\n");
	for(j = 0; j < 2; j++)
		for(i = 0; i < 2; i++)
			printf("&a[%d][%d]=%x\n", j, i, &a[j][i]);
}

gcc 1.c && ./a.out 
a[0]=bfb92738, a[1]=bfb92740

&(*a)[0]=bfb92738
&(*a)[1]=bfb9273c
&(*a)[2]=bfb92740
&(*a)[3]=bfb92744

&a[0][0]=bfb92738
&a[0][1]=bfb9273c
&a[1][0]=bfb92740
&a[1][1]=bfb92744

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

И вот какая будет разница при динамическом создании:

cat 1.c
#include <stdio.h>
#include <stdlib.h>
main(){
	int **a, i,j;
	a = malloc(2*sizeof(int*));
	a[0] = malloc(2*sizeof(int));
	a[1] = malloc(2*sizeof(int));
	a[0][0] = 1; a[0][1] = 2; a[1][0] = 3; a[1][1] = 4;
	printf("a[0]=%x, a[1]=%x\n\n", a[0], a[1]);
	for(i = 0; i < 4; i++) printf("&(*a)[%d]=%x\n", i, &(*a)[i]);
	printf("\n");
	for(j = 0; j < 2; j++)
		for(i = 0; i < 2; i++)
			printf("&a[%d][%d]=%x\n", j, i, &a[j][i]);
}

gcc 1.c && ./a.out 
a[0]=8730018, a[1]=8730028

&(*a)[0]=8730018
&(*a)[1]=873001c
&(*a)[2]=8730020
&(*a)[3]=8730024

&a[0][0]=8730018
&a[0][1]=873001c
&a[1][0]=8730028
&a[1][1]=873002c

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Да, а при этом сам a имеет значение 8730008. И налицо какое-то выравнивание при выделении памяти malloc'ом (хотя, возможно, насчет выравнивания я заблуждаюсь).

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Стивен Прата Язык программирования C. Лекции и упражнения 5-е издание глава 10 Массивы и указатели в этой главе ключ к пониманию конвертации указателей в многомерных массивах и вообще must be read http://gold-ray.ru/dl/%D1%F2%E8%E2%E5%ED+%CF%F0%E0%F2%E0+%DF%E7%FB%EA+%EF%F0%...

anonymous ()
Ответ на: комментарий от Eddy_Em

Поэкспериментируйте не с int[2][2](где из-за размерностей можно запутаться), а, скажем, с int [2][10]. Возможно так вы сможете эмпирически понять.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.