浅谈C++指针在OI中的应用
龙之吻—水货
2019-01-02 18:43:47
# 浅谈C++指针在OI中的应用
## 前言
作为一个指针党，在写各种数据结构的时候都会用到指针，但是，随着学习的深入，却发现指针的用途远远不止于此，于是就在这里整理一下。
## 在说指针之前
我们都知道，我们程序中的每一个变量，都在计算机的内存中有一个空间，而每个空间都有它对应的地址。
对于这个地址，我们可以通过取地址符`&`来得到它，并可以通过输出来看到它。
```cpp
int a = 0;
printf("%p", &a);
cout << &a;
```
以上的两种方法都可以让我们得到`a`的地址，通过这个地址，我们就可以访问到这个变量。
## 指针是什么？
指针实际上就是一个用于存储地址的变量，比如说：
```cpp
int a = 0;
int *p = &a;
printf("%p %p", &a, p);
```
我们会发现指针`p`的值和`a`的地址的值是一样的。
## 指针的定义
在类型后面加上`*`即可，比如说：
```cpp
int *a;
long long *b;
double *c;
```
我们就分别定义了一个指向`int`，`long long`，`double`地址的指针。
但是有一点需要注意：
```cpp
int *a, b;
```
这样你只会定义一个指针和一个变量，而如果需要两个指针的话就需要：
```cpp
int *a, *b;
```
在定义指针的时候，如果该指针没有初值，则应该将其赋值为空指针`NULL`。
```cpp
int *a = NULL;
printf("%p", a);
```
其中，NULL是位于stdio.h中的宏定义
```cpp
#define NULL ((void *)0)
```
再其中，如果我们无法确定一个指针的类型，则可以：
```cpp
void *p;
```
以上这部分的输出结果为`0`。
再说一下：
```cpp
int *a = NULL;
if (a) {
printf("233");
} else {
printf("666");
}
```
上面的代码的运行结果为输出`666`，应该比较显然可以理解吧？
## 指针的基本操作
### 赋值与输出
前面举的例子里面已经包括了这部分。
```cpp
int *p = &a;
```
这样就把`a`的地址赋值给了`p`或者说把`a`的地址存入了`p`。
`cout`可以直接输出，而`printf`需要用`%p`。
### 加减操作
指针资瓷这4种运算：`+`，`-`，`++`，`--`。
举个栗子：
```cpp
int a = 0, *p = a, *q = a;
printf("%p %p", p, p + 1);
printf("%p %p", q, ++p);
```
但是显然对于单个指针，对它进行加减操作并没有什么用处，甚至可能会访问到不应该访问的内存。
我们稍后在说它的作用。
### 访问指针变量中可用地址的值
显然，访问一个空指针地址的值是不清真的，这会导致你的程序出现`RE`的情况，所以我们这里所有的指针均不为空指针。
如果我们需要访问一个指针存储的地址的值，可以利用`*`来实现。
```cpp
int a = 2333, *p = &a;
printf("%d", *p);
```
以上代码的输出结果为`2333`。
如果我们的指针存储的是一个结构体（或者类）的地址，我们显然可以通过下面这种方式来得到结构体里面的值。
```cpp
struct Node{
int l, r;
};
int main() {
Node a;
a.l = 2, a.r = 232;
Node *p = a;
printf("%d %d", (*p).l, (*p).r);
}
```
但是这样又显然过于麻烦，于是`c++`又给了我们一个更好的方法：
```cpp
Node *p = a;
printf("%d %d", p->l, p->r);
```
以上两段代码输出的结果均为`2 232`。
## 指针的一些应用
### 遍历数组
指针的加减操作终于有用处了，先上代码：
```cpp
#include<cstdio>
int n, a[10001], *start, *end;
int main() {
scanf("%d", &n);
start = &a[0], end = &a[n];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int *p = start; p < end; ++p) {
printf("%d\n", *p);
}
}
```
上面这份代码可以将读入的数组输出出来。
我们稍微解释一下，在`c++`中，一个数组中的每个数字地址是连续的（可以感性理解一下），那么我们就可以通过对指向一个地址的指针进行加减操作来得到下一个地址或者上一个地址。就比如说：
```cpp
int a[10], *p = &a[6];
```
`++p`之后，`p`指向的地址就是`a[7]`所在的地址；`--p`之后，`p`指向的地址就是`a[5]`所在的地址。
通过这些，我们大概能猜到，对于上面那个例子，`p + 1`指向的是`a[7]`所在的地址，`p + 2`指向的是`a[8]`所在的地址，`p - 3`指向的是`a[3]`所在的地址。
另外，我们对`start`，`end`的赋值并不需要那么麻烦，只需要：
```cpp
start = a, end = a + i;
```
你可以尝试一下代码：
```cpp
printf("%p %p", a, &a[0]);
printf("%p %p", a + n, &a[n]);
```
会发现他们的值是一样的。
这样，我们大概就可以理解下面这种读入方式了：
```cpp
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
}
```
利用指针遍历数组，可以极大地减少寻址时间，优化常数。
### 动态分配内存
利用指针动态分配内存的时候会用到两个运算符`new`和`delete`，分别用于分配内存与释放内存。
#### new
以`int`为例，分配单个内存用两种方法：
```cpp
int *a = new int;
```
这是最简单的分配，但是无法保证分配到的地址上的值是什么。
如果要初始值的话只需要：
```cpp
int *a = new int(233);
```
这样就可以了，特别地，如果是`new int()`则值为0。
如果要分配一个数组的话，只需要：
```cpp
int *a = new int[n];
```
然后`a`就可以当做一个长度为`n`的`int`数组来用了，不过要注意的是里面的初始值并没有保证，需要`memset`或者逐个赋值。
当然了，我们还可以利用指针的指针来开多维数组，比如说：
```cpp
int **a = new int*[n];
for (int i = 0; i < n; i++) {
a[i] = new int[n];
}
```
我们就相当于开了一个`a[n][n]`的数组。
这和直接开一个数组有什么区别呢？
直接开一个数组的话，必须要用常量，就比如说：
```cpp
const int maxn = 1e4 + 7;
int a[maxn], b[10007];
```
而用指针动态分配内存的话，则可以使用变量，比如说：
```cpp
int main() {
int n, *a;
scanf("%d", &n);
a = new int[n + 1];
}
```
开了一个长度为`n + 1`的`int`数组。
对于结构体（或者类）来说也是如此，举个栗子：
```cpp
struct Node{
int l, r;
Node() {}
};
int main() {
Node *a = new Node(), *b = new Node[100];
}
```
在进行分配内存的时候会运行这个结构体（或者类）的构造函数，也就是`Node() {}`，具体初始值会变成什么样子与构造函数有关。
#### delete
delete掉一个指针会将这个指针指向的地址那一部分的内存释放出来。
如果这个指针只是单个的话，可以直接：
```cpp
int *p = new int;
delete p;
```
如果是被分配了一个数组的话，则需要：
```cpp
int *p = new int[102];
delete[] p;
```
在`delete`一个结构体（或者类）的时候会调用它的析构函数。
#### 个人观点
`delete`在OI中几乎没有什么作用，因为通常情况下并不需要去释放分配的内存，我唯一用到`delete`的时候就是替罪羊和`KDTree`在重构时候才会用到。
`new`的确很好用，但它唯一的缺点就是速度太慢，本来应该更快的指针版数据结构会因为`new`的原因比数组版的慢不少，使用内存池可以解决`new`的问题（这在之后会说到）。
### fread快读
利用指针高效遍历数组的特点，我们可以用指针+`fread`进行快读。
先简单介绍一下`fread`函数，它有4个参数，用简单的语言说：
```cpp
fread(读入到哪里,每次读入多少,读入多少次,从哪里读入)
```
它的返回值是读入字符的实际个数。
我们显然可以用一个很大字符数组（因为如果数组过小的话反复读入的次数过多反而会变慢）来存读入的字符，然后通过遍历这个字符数组依次得到要得到的数据，但是由于这个数组很大（通常会达到1e6的级别），因此直接寻址的常数巨大，这时就需要利用指针了。
```cpp
char Getchar() {
static const int LEN = 1000000;
static char buf[LEN], *s = buf, *t = buf;
if (s == t) {
t = (s = buf) + fread(buf, 1, LEN, stdin);
}
return *s++;
}
```
上面那个函数可以当做`getchar()`但是比`getchar`快到不知道哪里去了。
### 各种数据结构
这里以线段树为例。
在写高级数据结构的时候，我们其实很需要这样一种东西：
```cpp
struct Node{
Node child[2];
int val, ...;
};
```
但不幸的是，它连编译都过不去。
于是很多人用数组实现了这样的功能，但是，有没有更直观一些的方法呢，指针做到。
既然我们不能存下一个节点左右儿子的值，那么我们就存下这个节点左右儿子的地址：
```cpp
struct Node{
Node *child[2];
int val, ...;
};
```
这个代码是可以通过编译的！
那么我们该如何使用呢？我们以建树为例：
```cpp
void BuildTree(Node *now, int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) >> 1;
now->child[0] = new Node();
now->child[1] = new Node();
BuildTree(now->child[0], left, mid);
BuildTree(now->child[1], mid + 1, right);
}
```
我们只需要在函数中传入指向当前节点的指针，就可以很好的使用了。
等等，刚才不是说过`new`很慢，而可以用内存池代替吗，那该怎么办呢？
```cpp
struct Node{
Node *child[2];
int val, ...;
};
Node *root, pool[1000001], *tp;
Node *NewNode() {
*++tp = Node();
return tp;
}
void Init() {
tp = pool;
root = NewNode();
}
```
这样就可以啦！
在`NewNode`函数中我们将`tp`向后挪了一个位置并将那个地址上的信息初始化，最后再返回`tp`的值，这样就能得到一个全新的节点了，注意内存池`pool`一定要开得够大。
不过有一点需要注意，就是在32位系统上，一个指针大小是4字节，而在64位系统上，一个指针的大小是8字节，所以在64位系统的评测机上可能出现被卡空间的情况QAQ
## 留坑
就先说这么多吧，再学到什么再补坑吧。