2. 数组

2.1. 指针

 1#include <ctime>
 2using namespace std;
 3
 4struct TreeNode
 5{
 6    int val;
 7    TreeNode* left;
 8    TreeNode* right;
 9    TreeNode(int x) :val(x), left(nullptr), right(nullptr){} /* 唯一的构造函数,必须给定参数x */
10};
11
12int main(int argc, char ** argv)
13{
14    //int* p = new int(1); /* 这两行与下面三行等效 */
15    //cout << *p << endl;
16    int* p = new int;
17    *p = 1;                /* p已经申请了内存空间,可以直接赋值 */
18    cout << *p << endl;
19
20    TreeNode* q = new TreeNode(10);
21    cout << q->val << endl;
22
23    TreeNode node(100);
24    TreeNode* r = &node;   /* r 不能delete */
25    cout << r->val << endl;
26
27    delete p;
28    delete q;
29
30    return 0;
31}

Note

两个指针变量的值相同,则这两个指针 指向同一内存单元地址 或都为 空指针 。不存在多个变量占用同一内存单元的情形。

2.2. 指向函数的指针

定义形式:

函数返回值类型 (*指针变量名)(参数列表)

指向函数的指针是让函数的入口地址赋给指针变量,类似于指向数组的指针是把数组首地址赋给指针变量。

 1#include<iostream>
 2using namespace std;
 3
 4double square(double x)
 5{
 6    return x * x;
 7}
 8
 9int main()
10{
11    double (*p)(double x);
12    p = square; // 用函数名square初始化指针
13    cout << square(1.6) << endl;
14    cout << p(1.6) << endl;
15    cout << (*p)(1.6) << endl; // 三者等效
16    return 0;
17}

还可以定义指针数组,

1// 定义一个指向函数的指针类型,名为 MenuFood。函数参数列表为空,返回值为空。
2typedef void (* MenuFood)();
3
4void food1();
5void food2();
6void food3();
7void food4();
8
9MenuFood p[] = {food1, food2, food3, food4}; // 该数组的每一个元素都是指向函数的指针。

Note

指针数组:类型 *数组名[长度]

char *name[] = {"allen", "martin", "clark"};

指向行向量的指针变量:类型 (*变量名)[长度]

int (*pa)[10];
int *p;
int a[3][10];

p = a[0]; // 或 &a[0][0]
pa = a; // 使用:*(*(pa + i) + j)

2.3. 动态数组

声明与定义一个动态数组的格式一般如下:

1int** da = new int*[r];
2for(int i = 0; i < r; ++i)
3{
4    da[i] = new int[c];
5}

內存释放:

1for(int i = 0; i < r; ++i)
2{
3    delete[] da[i]; // 释放指针指向的内存空间
4    da[i] = nullptr; // 置为空指针,防止出现‘野指针’
5}
6delete[] da;
7da = nullptr;

内存组织形式:

动态数组在堆(heap)区分配内存,静态数组在栈(stack)区分配內存。

假如我们已经得到一个 3x4 的动态数组 da,其指针关系如下:

../_images/02_dynamicArray.png

其中,da[0]、da[1]、da[2]的 地址 是连续的,依次相差 sizeof(da[0]) (一个指针的大小,32 位编译器下为 4,64 位编译器下为 8),比如:

&da[0] + sizeof(da[0]) == &da[1]

如果把 da 看作 3 行 4 列的二维数组,那么 da 的每一行元素的地址是连续的,依次相差 sizeof(da[0][0]) ;但是行与行之间的地址是不连续的,比如:

da[0][0], da[0][1], da[0][2], da[0][3] 地址连续;
da[1][0], da[1][1], da[1][2], da[1][3] 地址连续;
da[0][3] 与 da[1][0] 地址不连续;

另外:

&da, &da[0], &da[0][0] 三者的数值是不相等的。
如果数组是静态数组,则 &da, &da[0], &da[0][0] 三者的数值是相等的;
且静态数组的行与行之间的地址连续。

Note

对于动态数组,指针的地址和指针的值不能混淆,我们讲 da[0]、da[1]、da[2] 的地址是连续的,但是他们本身的值没有关系,即 da[0] + sizeof(da[0]) != da[1] 。 注意有没有 & 的区别。

如果想要定义连续内存空间的动态数组,可以按如下方式进行:

 1// int** f; // f的声明
 2template<typename T>
 3void Init2DArray(T** &f, const int row, const int col)
 4{
 5    f = new T*[row];
 6    f[0] = new T[row * col];
 7    for(int i = 1; i < col; ++i)
 8    {
 9        f[i] = f[0] + col * i;
10    }
11}

内存释放方式如下:

 1template<typename T>
 2void Delete2DArray(T** &f)
 3{
 4    if(f != nullptr)
 5    {
 6        if(f[0] != nullptr)
 7        {
 8            delete[] f[0];
 9            f[0] = nullptr;
10        }
11        delete[] f;
12        f = nullptr;
13    }
14}

上面的 Init2DArray 在申请内存的时候,建立了 row x col 的二维动态数组。实际上,二维动态数组不强求列对齐,即各行的长度可以不一样, 因此可以下面像这样定义:

f[i] = f[0] + offset_i; // offset_i是第i行首地址相对于第0行首地址的偏移量

2.4. 另类的数组表达

有如下程序:

1int a[10];
2int b[7][5];
3
40[a] = 5;
59[a] = 7;
60[b][0] = 1;
70[b][1] = 2;
80[b][2] = 3;

这些表达式能够正常编译和执行,是因为对于 C/C++ 而言:

a[0] 等价于 *a 等价于 *(a+0) 等价于 *(0+a) ==> 等价于 0[a];

所以可以推出二维表达式:

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

Note

b: 相当于 &b[0],第 0 行的首地址。

*b: 相当于 b[0],&b[0][0],第 0 行第 0 列的首地址。

b[0][1] 等价于 *(b[0] + 1),*(*(b+0)+1),(*(b+0))[1]( [] 优先级高于 * )。

2.5. 数组实参

非引用 类型传递数组实参时,数组会退化为指针,形参复制的是这个指针的值( 指向数组的第一个元素)。通过指针形参做的任何改变,都是在修改数组元素本身。

如果以 引用 形式传递数组实参,那么编译器不会将数组实参转化为指针,而是传递数组的引用本身。

编译器会检查数组实参的大小与形参大小是否匹配。

非引用形式:

1void func1(int *arr); // 函数可能会改变数组
2void func2(const int *arr); // 不能改变数组
3
4void func3(int arr[100])
5{
6    cout << sizeof(arr) << endl; // 4
7}
8// int arr[100];
9// func3(arr); // 调用func3

引用形式:

1void func4(int (&arr)[100])
2{
3    cout << sizeof(arr) << endl; // 100
4}
5// int arr[100];
6// func4(arr); // 调用func4

2.6. 数组地址与加法

假设我们已经定义了一个数组:

int a[L][M][N];

1. a , a[0] , a[0][0] , &a , &a[0] , &a[0][0] , &a[0][0][0] 的数值都是一样的。

2. &a 是 4 级指针, 类型是 int (*)[L][M][N] ,指向 a 这个数组。

3. a 是 3 级指针,类型是 int (*)[M][N] ,三维数组的数组名,是数组 a 的首地址。

4. 大小计算如下:

sizeof(&a) = 4; // 指针的大小,32 位编译器
sizeof(a[0][0][0]) = sizeof(int);
sizeof(a[0][0]) = N * sizeof(int);
sizeof(a[0]) = M * N * sizeof(int);
sizeof(a) = L * M * N * sizeof(int); // 整个数组的大小

5. 加法运算:

a + i = a + i * sizeof(a[0]);
&a + i = a + i * sizeof(a);
这里(&a + 1)就已经跳过了整个数组。

6. 定义指针 int *ptr = (int *)(&a + 1) ,则 (ptr - 1) 指向数组a的最后一个元素。

2.7. malloc/free与new/delete

相同点

都可用于申请动态内存和释放内存。

不同点

  1. 属性

    malloc/free 是 C/C++ 的 库函数 ,在头文件 stdlib.h 中声明。

    void *malloc(size_t size);
    void free(void *pointer);
    

    因为 malloc 函数的返回值类型为 void* ,所以需要在函数前面进行相应的强制类型转换。

    new/delete 是 C++ 的 运算符

  2. 参数

    使用 new 操作符申请内存分配时无须指定内存块的大小,编译器会根据类型信息自行计算;

    int *pi = new int[n]; // 指针 pi 指向长度为 n 的数组,未初始化
    

    而 malloc 则需要显式地指出所需内存的尺寸。

    int *p = (int *)malloc(25*sizeof(int)); // 指向整型的指针 p 指向一个 25  int 整型空间的地址
    int *p = (int *)malloc(99); // 指向整型的指针 p 指向一个大小为 99 字节的内存的地址
    

    malloc 可以分配任意字节,new 只能分配实例所占内存的整数倍数大小。

  3. 分配失败

    new内存分配失败时,会抛出 bad_alloc 异常;malloc 分配内存失败时返回 NULL

  4. 功能

    new 做两件事,先分配内存,再调用类的构造函数;同样,delete 会调用类的析构函数和释放内存。而 malloc 和 free 只是分配和释放内存。

    对于内部数据类型(如 int , char 等)的对象,没有构造和析构的过程,对它们而言, malloc/freenew/delete 等价。

    对于非内部数据类型的对象而言, malloc/free 无法满足动态对象的要求。

  5. 重载(overload)

    new/delete 可以重载成为函数,可以自定义申请过程,比如记录申请内存的长度以及跟踪每个对象的指针。

    malloc/free 不能重载。

Warning

  • new 和 delete 一定要配对使用;new 对应 delete,new [] 对应 delete []。

  • 对空指针使用 delete 是安全的。

  • 不能使用 delete 释放绑定到对象的指针。

    int val = 5;
    int* p = &val;
    delete p; // error, memory not allocated by new
    

2.8. 参考资料

  1. 静态数组与动态数组:

  1. 浅谈new/delete和malloc/free的用法与区别:

  1. malloc/free与new/delete的区别: