C语言数组和指针笔记

虽然在C++中完全不需要处理C语言中原始数组和原始指针等，C++提供了很多更好的替代实现，但是还是顺手整理一下吧。在本文中的代码会涉及到几个运算符优先级的细节，这里备注一下：

数组取下标（[]）的优先级高于解引用（*）和取地址（&）；
解引用（*）和取地址（&）的优先级相同，连续出现时，按照从右到左结合；
解引用（*）和取地址（&）是互逆的，因此连续出现时（&*和*&）直接抵消。

数组基础

一维数组

定义数组的语法很简单

int a[5];

此时变量a的类型是int [5]。

在定义时可以赋初值，此时可以省略数组长度，长度会通过初值个数自动获取，例如

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

如果同时提供了数组长度和初值，那么数组长度必须大于等于提供的初值个数（否则报错），此时会对数组元素从前到后赋初值，剩余的元素会被初始化为0，例如

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

sizeof作用在数组名，返回数组整体占用的字节数，即数组长度乘以每一个元素的字节数，可以用如下方式获取数组长度

1	unsigned long len = sizeof(a)/sizeof(a[0]);

如果不赋初值，那么数组的初值在Release模式下通常是随机的，这可能导致程序BUG。

需要通过索引读写数组的元素，数组的索引从0开始，例如

1
2
3

int a[5];
a[0] = 100;
print("%d",a[1]);

C语言不会检查索引的合法性，对越界的索引进行的读写操作是未定义的危险行为，需要结合下面的指针理解。

二维数组

定义二维数组

1	int a[2][3];

此时变量a的类型是int [2][3]。

二维数组赋初值的细节和一维数组类似

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

二维数组通过行索引和列索引读写元素

1
2
3

int a[2][3];
a[0][1] = 100;
print("%d",a[0][0]);

C语言保证数组始终在内存中连续分布，无论一维，二维还是高维数组。对于多维数组在内存中按照行优先的顺序拼接：保证在索引的最后一个分量发生变化时，数据在内存中是相应的连续变化，例如

1 2	int a[2][3]; // a[0][0] -> a[0][1] -> a[0][2] -> a[1][0] -> a[1][1] -> a[1][2]

高维数组和二维数组在原理上没什么区别，但是记号比较繁琐，这里省略。

指针基础

下面的内容仅仅是针对普通指针的，C语言对函数指针有不一样的处理。

一级指针

定义指针

1	int *p; // pointer -> int

指针需要使用一个类型匹配的地址（对变量使用&运算符即可获取它的地址）进行初始化，让指针指向这个地址

1 2	int x = 5; int *p = &x;

可以在初始化时将指针指向空地址，这表明指针是一个空指针

1	int *p = NULL;

使用解引用运算*可以访问指针指向的值

1
2
3

int x = 10;
int *p = &x;
printf("%d",*p);

指针的移动通过加减整数或自增自减实现，例如

int x = 10;
int *p = &x;
p = p + 2;
p++;

这会使得指针指向不同的地址，每次移动的实际字节长度是加减操作数乘以指向类型的字节长度，例如

char s1 = 'a';
char *p1 = &s1;
assert((int)(p1 + 1) == (int)p1 + sizeof(char));

double s2 = 0;
double *p2 = &s2;
assert((int)(p2 + 1) == (int)p2 + sizeof(double));

两个同类型的指针还可以进行相减操作，得到的结果是两个指针之间的字节差除以指向类型的字节长度，如果这两个指针指向同一个数组的不同元素，那么得到的结果就是两个元素的索引之差，具体见下文。不允许对两个指针进行加法、乘除法操作。

二级指针

定义一个二级指针

1	int **pp; // pointer -> (pointer -> int)

初始化一个二级指针时需要使用一个类型匹配的一级指针的地址

1
2
3

int x = 10;
int *p = &x;    // pointer -> int
int **pp = &p;  // pointer -> (pointer -> int)

获取二级指针指向的值，需要使用两次解引用运算

int x = 10;
int *p = &x;        // pointer -> int
int **pp = &p;      // pointer -> (pointer -> int)
printf("%d",**pp);

使用一次解引用运算得到的结果可以用来给一级指针赋值

int x = 10;
int *p = &x;        // pointer -> int
int **pp = &p;      // pointer -> (pointer -> int)
int *q = *pp;       // pointer -> int

多级指针与二级指针在原理上没什么区别，这里省略。

指针常量 vs 常量指针

辨析一下指针常量和常量指针的概念，考虑下面几个定义

char tmp;
char* const p1 = &tmp;          // const pointer -> char
char const* p2;                 // pointer -> const char
const char* p3;                 // pointer -> const char
const char* const p4 = &tmp;    // const pointer -> const char

其中

p1是一个指针常量，即const修饰自身，表示指针自身不可被修改，但是指向内容char可以修改；
p2和p3是一样的，表示常量指针，即const修饰char，表示指针自身可以被修改，但是指向内容const char不可修改；
p4是常量指针常量，指针自身不可修改，指向的内容也不可修改。

理解的关键在于const会和右侧的语义相结合，先结合到变量就修饰指针自身，否则修饰指针指向的类型。

如果指针本身是const的，也称为顶层const，如果指针指向的内容是const的，也称为底层const。

对于二级指针如果再加上常量的修饰，结果就更多了（\(2^3=8\)种组合）

// [000] 结果一：全是可变的
int **p1;

// [001] 结果二：所指一级指针指向的数据是不可变的
const int **p2;
int const **p2; // or

// [010] 结果三：所指向的一级指针是不可变的
int *const *p3;

// [011] 结果四：二级指针本身是可变的，所指一级指针是不可变的，一级指针指向的数据是不可变的
const int tmp1 = 55;
const int *tmp2 = &tmp1;
const int *const *p4 = &tmp2;
int const *const *p4 = &tmp2;  // or

// [100] 结果五：二级指针本身是不可变的
int *tmp;
int **const p5 = &tmp;

// [101] 结果六：二级指针本身是不可变的，所指向的一级指针是可变的，一级指针指向的数据是不可变的
int tmp1 = 55;
const int *tmp2 = &tmp1;
const int **const p6 = &tmp2;
int const **const p6 = &tmp2;  // or

// [110] 结果七：二级指针本身是不可变的，所指向的一级指针是不可变的
int tmp1 = 55;
const int *tmp2 = &tmp1;
int *const *const p7 = &tmp2;

// [111] 结果八：二级指针本身是不可变的，所指一级指针是不可变的，一级指针指向的数据是不可变的
const int tmp1 = 55;
const int *tmp2 = &tmp1;
const int *const *const p8 = &tmp2;
int const *const *const p8 = &tmp2;  // or

由于指向常量的指针是允许指向变量的，指向变量的指针却不允许指向常量，在实际使用中不会按照严格匹配的类型进行赋值，实际情况会更加复杂。

数组 + 指针

指针数组 vs 数组指针

辨析一下指针数组和数组指针的概念：

指针数组：一个数组，其中的元素类型是指针
数组指针：一个指针，指向一个数组

指针数组的定义如下

1 2	int x = 1, y = 2, z = 3; int arr[3] = {&x, &y, &z}; // (int ) [3]

注意由于[]比*的优先级更高，因此这里定义的arr是一个数组，数组类型是(int *) [3]，每一个元素的类型是int *。获取指针数组中的元素所指向的内容的示例如下

1	int value_x = *arr[0]; // x

这里的运算顺序：先获取数组元素（即arr[0]，得到int *指针），再对其解引用。

数组指针的定义如下

1 2	int arr[5] = {1, 2, 3, 4, 5}; int (*p)[5] = &arr; // pointer -> int [5]

注意这里使用小括号()改变了语法的优先级，因此p是一个指针，指向的类型是int [5]。对数组指针解引用就可以得到数组，可以继续对其运算，例如获取数组中元素

1	int first_element = (*p)[0]; // arr[0]

这里同样需要小括号()改变优先级：先解引用得到数组（即*p，类型是arr [5]），再获取数组的元素。

数组索引退化

编译器在实际处理数组时，[]操作通常会退化为指针操作。

一维数组的名称可以自动转换为指向数组首位元素的一级指针常量

1 2	int a[4] = {1,2,3,4}; int * const b = a; // const pointer -> int

此时对a和b进行读写操作是等效的

a[0] = 100;
*b = 100;

a[1] = 200;
*(b+1) = 200;

但是它们并不是完全等价的，因为编译器确实将int [4]和int * const视作不同的类型，只是在某些情况下进行了自动的类型转换。

数组索引操作总是会被编译器处理为对应指针的移动（实际的字节偏移量是操作数乘以元素类型大小）再加上解引用

1	a[b] == *(a+b)

例如

int a[4] = {1,2,3,4};
int * const b = a;      // const pointer -> int

a[2] = 100;
*(a+2) = 100;
b[2] = 100;
*(b+2) = 100;

这些读写语句是等价的，甚至还带来了2[a]这样的奇怪语法，下面的读写语句的效果也是等价的

1
2
3

*(a+2) = 100;
a[2] = 100;
2[a] = 100;

二维数组的名称相当于指向数组首行数组的一级指针常量（即数组指针常量）

1 2	int a[10][5]; int (* const b)[5] = a; // const pointer -> int [5]

对二维数组的索引需要理解为两次解引用操作，分别加上对应层次上的指针移动

a[2][3] = 100;

*(*(a + 2) + 3) = 100;
*(*(b + 2) + 3) = 100;

其中+2是指向数组int [5]的指针（类型为 int (*)[5]）的移动，因此实际的字节偏移量为2*5*sizeof(int)， +3是指向元素int的指针（类型为int *）移动，因此实际的字节偏移量为3*sizeof(int)。a[2][3]的总偏移量为

1 2	move = 2 * sizeof(int [5]) + 3 * sizeof(int) = 2 * 5 * sizeof(int) + 3 * sizeof(int)

考虑到运行的效率，编译器并不会实时检查数组索引的合法范围，即使是越界的数组访问，索引操作仍然会根据上述运算规则继续进行指针的偏移和解引用。

数组名传参退化

C语言在函数调用时将一维数组作为参数传递时，会自动退化为对应的指针，也就是丢弃了数组的长度信息，对于多维数组，也会退化为指针，丢弃的是第一个维度的长度信息。

具体来说，一维数组int [n]的名称用于函数传参时，会自动退化为指向元素的指针int *，丢弃数组第一个维度的长度信息n。

考虑下面三个函数的例子，它们实际上没有什么区别。

#include <stdio.h>

void func1(int arr[5]) { printf("%d\n", arr[2]); }

void func2(int arr[]) { printf("%d\n", arr[2]); }

void func3(int *arr) { printf("%d\n", *(arr+2)); }

int main(void) {
    int arr[5] = {1, 2, 3, 4, 5};

    func1(arr);
    func2(arr);
    func3(arr);

    return 0;
}

尤其注意的是：即使在func1的定义中写了数组长度，编译器也不会保留，数组传递给函数会始终退化为一个指针。

通常的做法是在传递指针的同时附带传递数组长度

#include <stdio.h>

void printArray(int *arr, int length) {
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int arr[5] = {1, 2, 3, 4, 5};
    printArray(arr, 5);
    return 0;
}

二维数组int [m][n]用于函数传参时，会自动退化为指向行数组的指针int (*)[n]，丢弃数组第一个维度的长度信息m。

考虑下面三个函数的例子，它们实际上没有什么区别。

#include <stdio.h>

void func1(int arr[3][4]) { printf("%d\n", arr[1][2]); }

void func2(int arr[][4]) { printf("%d\n", arr[1][2]); }

void func3(int (*arr)[4]) { printf("%d\n", arr[1][2]); }

int main(void) {
    int arr[3][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};

    func1(arr);
    func2(arr);
    func3(arr);

    return 0;
}

这里二维数组int [m][n]会退化为一维数组指针int (*)[n]，这和int **是完全不一样的，因为前者还含有行数组的长度信息：

对于int (*)[n]类型指针，移动的字节偏移量以size(int [n])为单位，一次解引用后得到的是int [n]数组，二次解引用是对数组元素的访问
对于int **类型指针，移动的字节偏移量以size(int *)为单位，一次解引用后得到的是int *指针，二次解引用可以得到指向的数据

如果将除了第一个维度之外的维度省略（例如int [][]），会导致编译器报错，因为这不是一个合法类型。

数组名 vs 数组名取地址

需要辨析一下两个操作：

对于int [m]数组，数组名在某些情况下会自动退化为指向首位元素的int *指针，加减运算的实际偏移量是操作数乘以sizeof(int)；
但是如果直接对int [m]数组的数组名取地址，会得到指向数组的int (*)[m]数组指针，加减运算的实际偏移量是操作数乘以sizeof(int [m])。

考虑下面的例子

#include <stdio.h>

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

    printf("a = %p\n", a);              // a
    printf("&a = %p\n", &a);            // &a
    printf("&a[0] = %p\n", &a[0]);      // &(a[0]) = &(*(a+0)) = a
    printf("&a[1] = %p\n", &a[1]);      // &(a[1]) = &(*(a+1) = a+1
    printf("(&a)[1] = %p\n", (&a)[1]);  // (&a)[1] = *(&a+1)

    return 0;
}

测试结果如下

a = 0x7ffc793603bc
&a = 0x7ffc793603bc
&a[0] = 0x7ffc793603bc
&a[1] = 0x7ffc793603c0
(&a)[1] = 0x7ffc793603c8

解释一下：

&a 获取数组的地址，必然等于首位元素地址，也就是a或&a[0]，下面以此作为基准；
&a[1] 是获取 a[1] 的地址，相比于首位元素地址的字节偏移量为 sizeof(int)，即 4 个字节；
(&a)[1] 是获取 a 的地址，接下来的+1操作是基于int (*)[5]进行的，相比于首位元素地址的字节偏移量为 sizeof(int [3])，即 12 个字节；

数组遍历

考虑如何遍历一个一维数组，有两类做法：

基于下标，那么关键就是获取数组长度；
基于指针，那么关键就是获取数组最后一个元素之后的地址。

获取数组长度的常见方法如下：

int arr[] = {1, 1, 2, 3, 5, 8, 13};

int len1 = sizeof(arr) / sizeof(arr[0]);
printf("len: %d\n",len1);  // 7

int len2 = *(&arr + 1) - arr;
printf("len: %d\n",len2);  // 7

其中 len2 的计算需要更详细的解释：

数组指针&arr的偏移量是整个数组长度，因此&arr + 1就是指向数组后面的同长度数组（记作arr2）的数组指针
对&arr+1解引用得到arr2，将arr2与arr进行相减运算，会自动退化为指向两个数组的首位元素指针的相减运算。
最终得到的不是arr[0]和arr2[0]的偏移字节数，而是偏移字节数除以每一个元素的字节数，因此可以得到数组长度。

更直观的拆解过程如下

int arr[] = {1, 1, 2, 3, 5, 8, 13};
int(*arr_ptr1)[7] = &arr;
int(*arr_ptr2)[7] = arr_ptr1 + 1;

int *p1 = *arr_ptr1;
int *p2 = *arr_ptr2;

int len3 = p2 - p1;
printf("len: %d\n", len3);  // 7

获取了数组长度之后，基于下标的遍历就非常简单了

int arr[] = {1, 1, 2, 3, 5, 8, 13};
for (int i = 0; i < len; ++i) {
    printf("%d\n", arr[i]);
}

基于指针的遍历则更加简便，只需要不等于恰好越界时的地址即可

int arr[] = {1, 1, 2, 3, 5, 8, 13};
for (int *p = arr; p != *(&arr + 1); ++p) {
    printf("%d\n", *p);
}

数组作为返回值?

在 C 语言中，数组除了在传参过程中会退化为指针，还有额外的限制：不允许作为函数的返回值类型。

下面这种语法是无效的

1	int func()[4]; // compile error

即使通过别名定义的方式也无法绕过

1
2
3

typedef int arr4[4];

arr4 func(); // compile error

虽然无法通过返回数组达到返回多值的目的，但是满足语法要求的替代方案有很多，例如：

返回指向（非动态分配）数组的指针；（最不推荐，因为这涉及到指向的数组的生命周期问题，除非返回的是函数体内的静态数组，否则都是非常危险的）
返回指向动态分配数组的指针，由调用方自行负责释放；
使用输入输出参数，调用方直接在参数中提供一个指向数组的指针；
返回结构体，将数组作为结构体的成员即可。

补充

举个栗子

考虑下面的例子

1 2	char s[] = "hello"; // 自动补充\0 char *p = "hello";

这两个语句有如下区别：

类型不同，s是char [6]类型的数组，p是char *类型的指针；
s有时会自动退化为指向（存储在栈上的）数组首位元素的指针，指针 p 始终指向一个（保存在静态存储区的）常量字符串的首位元素；
可以修改 s 的内容，不可修改 p 指向的内容，但是可以调整 p 自身，让其指向其他位置。

再考虑下面的语句

1	char *p2 = s;

这里的p2就指向了数组的首位元素。

下面这个语句则是对数组取地址，得到char (*)[6]类型的指针，将其赋值给q

1	char (*q)[6] = &s;

值得注意的是，这里如果提供了错误的数组长度，会导致编译报错

1 2	char (q)[3] = &s; // compile error // Cannot initialize a variable of type 'char ()[3]' with an rvalue of type 'char (*)[6]'

如果缺省了数组长度，虽然编译不会对这个语句报错，但是某些操作仍然会报错，因为缺少了数组长度信息

1
2
3

char (*q)[] = &s;
printf("%p\n", q+1); // compile error
// Arithmetic on a pointer to an incomplete type 'char[]'

C的数组索引炫技

下面这个函数就使用了各种数组索引的花样

1
2
3

int func(int a){
    return 0[(1[(int [2][1]){3,a}])];
}

显然func是一个接受整数参数a并返回整数的函数，可以将其展开为更清晰的形式

int func(int a){
    int temp[2][1] = {{3}, {a}};
    int *row = 1[temp]; // temp[1]
    int value = 0[row]; // row[0]

    return value;
}

虽然看起来很复杂，但是实质就是原样返回输入的参数

1	int func(int a){ return a; }

数组指针作为参数和返回值

虽然数组名直接传参会退化为指向首位元素的指针，并且损失长度信息，但是数组名取地址得到的是数组指针，它仍然附带了数组的长度信息，而且语法上允许作为参数类型和返回值类型。

虽然这种用法在语法上是完全合法的，但是代码过于晦涩，实践中非常不推荐使用。

考虑下面的例子

#include <stdio.h>

// 参数类型为数组指针
void func(int (*arr_ptr)[5]) {
    int len = *(arr_ptr+1) - *arr_ptr;
    printf("len = %d\n", len); // 5
}

// 返回类型为数组指针
int (*getArray())[5] {
    static int arr[5] = {1, 2, 3, 4, 5};
    return &arr;
}

int main() {
    int a5[5];
    func(&a5);       // ok

    int a3[3];
    // func(a3);    // compile error

    int *p = a3;
    // func(p);     // compile error

    int (*arr_ptr)[5] = getArray();
    for (int i = 0; i < 5; ++i) {
        printf("%d\n", (*arr_ptr)[i]);
    }

    return 0;
}

可以看到，无论是作为参数还是返回值，它们都保留了长度信息。

可以用类型别名改善一下可读性

typedef int (*arr5_ptr_type)[5];

void func(arr5_ptr_type arr);

arr5_ptr_type getArray();

数组引用作为参数和返回值（C++）

由于c++还提供了引用，前文中使用数组指针的做法在c++中可以几乎等价地转换为数组引用类型的方式实现，两者使用上的差异就是引用和指针本身的差异。

使用数组引用作为函数参数的例子如下

void func(int (&arr)[5]) {
    //...
}

int (&getArray())[5] {
    static int arr[5] = {1, 2, 3, 4, 5};
    return arr;
}

可以用类型别名改善一下可读性

using Array5Ref = int (&)[5];

void func(Array5Ref arr){
    //...
}

Array5Ref getArray() {
    static int arr[5] = {1, 2, 3, 4, 5};
    return arr;
}

这里的数组引用类型实际上会牵连出很多语法细节的问题，它导致类型的解析变得更加复杂，尤其是把这些和面向对象等 C++ 的语法结合起来时，会有非常多的麻烦，例如override的位置问题

struct Base {
    virtual int (&CArray())[5] = 0;
};

// (1)
struct Derived : Base {
    int (&CArray())[5] override {
        static int arr[5]{11, 22, 33, 44, 55};
        return arr;
    }
};

// (2)
struct Derived : Base {
    int (&CArray() override)[5] {
        static int arr[5]{11, 22, 33, 44, 55};
        return arr;
    }
};

这两种做法将 override 关键词放在了不同位置，不同的编译器给出了不同的测试结果：在MSVC和clang中只有前者可以编译通过，在gcc中只有后者可以编译通过。

当然，使用类型别名就不存在两种写法的问题了，在三大编译器中都可以编译通过

using Array5Ref = int (&)[5];

struct Derived : Base {
    Array5Ref CArray() override {
        static int arr[5]{11, 22, 33, 44, 55};
        return arr;
    }
};

除了数组（左值）引用，我们甚至还能写成数组的右值引用，考虑下面的例子

#include <iostream>
#include <utility>

int (&&func())[3] {
    static int arr[3] = {1, 2, 3};
    return std::move(arr);
}

int main() {
    auto s = func();

    for (int i = 0; i < 3; ++i) {
        std::cout << s[i] << '\n'; // 1 2 3
    }

    return 0;
}

虽然我暂时还不知道这玩意有啥实际意义，但是它确实是可以通过编译并且正常运行的合法代码。

C++ 看起来并不鼓励这篇笔记中的几乎所有做法，Modern C++ 提供了包括std::array在内的，很多更好的，可读性更高的工具和语法来实现对应的功能。