复习内容部分来自NOI大纲中入门级和提高级的内容。
联合体（Union）
联合体是一种复合数据类型，其的定义上与结构体的定义类似。
与结构体不同，联合体中的所有元素共用一块内存，所以它占空间大小一般是最大成员的大小（不考虑对齐的情况下），相应地，任意时刻只有一个成员带有值，如果访问其他成员，得到的值可能有损坏。
对于不同的时刻需要使用不同类型的数据，且只使用刚赋值的成员的情况，无需开多种类型的变量，只需要用联合体即可，更节省空间。
union node{
int a;
char b;
double c;
short d[5];
}t;
int main(){
cout<<sizeof(t)<<"\n";//Output : 16
//解释：最大成员是short d[5]，占2*5=10字节，
// 再对其到double的8字节，即为16
t.a=100;
t.c=114514.191981;
t.d[3]=32767;
cout<<t.a<<" "<<t.c<<" "<<t.d[3]<<"\n";
//Output : 307931975 nan 32767
//解释：因为是共用空间，所以一般最后赋值的位置才不被损坏
return 0;
}
原码和补码
我们用原码表示有符号整数，就是把二进制的最高位作为符号位。拿\(8\)位整数举例，\(-2\)的原码是1000 0010，\(5\)的原码是0000 0101。
然后我们可以发现一些问题：
- 原码不能直接相加。比如\(-2+5\)，按原码计算
1000 0010+0000 0101得到10000111，是十进制的\(-7\)。 - 原码的\(0\)有正负之分。这不仅是对空间的浪费，还会引发一系列冲突。
我们之所以要设计数在计算机里的表示法，就是为了能够方便地对它们进行运算。我们不妨先思考一下，什么样的表示法能支持数的相加。
首先我们要相加，那么依照的就是无符号整数相加、自然溢出的逻辑，相应地就不存在符号位的概念。
根据相加的逻辑，我们很容易得出\(0\)应该表示为0000 0000，\(1\)应该表示为0000 0001……也就是说，非负数的表示和原码一样。
负数呢？这就可以用自然溢出嘛，\(-1\)就相当于\(+255\)，\(-2\)就相当于\(+254\)……所以\(-1\sim -128\)分别表示为1111 1111\(\sim\)1000 0000。同时我们发现，\(\pm 0\)的问题也被解决了。
这种表示法就叫做补码，计算机中有符号整数都是用它来存储的。
和原码对比一下：
虽然说补码不存在符号位，但我们也可以用最高位来判断正负，\(1\)是负数，\(0\)非负。
补码的系统定义：
- 非负数的补码就是原码。
- 负数的补码是原码除符号位全部取反，再\(+1\)。
- 特别地，\(-128\)的补码是
1000 0000（这里拿\(8\)位整数举例，其他同理）。
理解起来也很简单，\(x<0\)时，\(x\)的补码是\(256+x=255+x+1\)，其中“\(255+x\)”，就是把\(x\)的原码除符号位外都取反。
然而\(-128\)没有原码，我们正好发现原来那个\(-0\)给空出来了，人为规定为\(-128\)。
一些笔记用“\(127+1=-128\)”作为例子来引入，实际上有符号整数的溢出是未定义行为：
#include<bits/stdc++.h> using namespace std; int x; int main(){ cin>>x; cout<<x+1<<"\n"; if(x+1<x) cout<<"overflow"; else cout<<"not overflow"; return 0; }可以试试上面的代码，如果编译器比较新，或者吸了氧，输入
2147483647时，可能输出是-2147483647 not overflow，原因是编译器看到\(x+1<x\)，知道只有溢出才可能为真，而溢出是未定义行为，所以直接认定它为假了（以上内容来自洛谷日报#265）。
补码还有一个不错的特性，补码的补码\(=\)原码，能直接从表格观察出来。证明：设\(x<0\)，则\(x\)的补码就是\(256+x\)，作为原码对应的数是\(-128-x\)（去掉最高位\(128\)再取反），\(x\)的补码是\(-128-x\)的原码，故得证。
哈夫曼编码
对于一个字符串，我们为了便于传输，常常把它编码成一个01串。编码方式有很多种，最简单的就是用每个字符的ASCII码值来编码，这种编码方式叫等长编码，每个字符都用\(8\)位二进制来表示。
虽然操作简单，但传输效率却不高，而哈夫曼编码是变长编码，它可以让出现频率更高的字符，编码长度更短，同时不会出现冲突问题。
举例子，AAAAABBBBCCCDDE中，每种字母出现次数如下表所示：
| A | B | C | D | E |
|---|---|---|---|---|
| 5 | 4 | 3 | 2 | 1 |
我们按出现次数从小到大排序：
| E | D | C | B | A |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
我们把字母看作树上的节点，出现次数作为该点的权值，初始节点之间不相连。然后重复进行下面的操作：
- 取出森林里权值最大的\(2\)个根节点，把它们作为一个新节点的左右儿子（顺序无所谓），新节点的权值是两点权值的和。
最后得到一棵树，这就是哈夫曼树：
根据构造过程，非叶子节点一定有\(2\)个子节点。我们用\(0\)和\(1\)分别表示连接左孩子的边、连接右孩子的边：
这样每个叶子节点就有一个唯一的二进制表示了，比如D的表示就是001，这就是每个字母的哈夫曼编码。
哈夫曼编码一定是最优编码，因为编码的总位数实际上是\(\sum\limits_{i=1}^{n} cnt[i]\times len[i]\)，其中\(cnt[i],len[i]\)分别表示第\(i\)个字母出现次数和编码长度。我们根据贪心的思想，一定把\(len\)最小的放在最下面，最大的放在最上面。
迭代器
迭代器是一种用于遍历容器的指针。
迭代器有\(3\)中类型：前向迭代器，双向迭代器，随机访问迭代器。
- 前向迭代器：只能单项移动，即
p++、++p，支持取值，赋值，可以用!=、==比较位置。 - 双向迭代器：包含前向迭代器的功能，并支持
p--、--p。 - 随机访问迭代器：包含双向迭代器的功能，并支持直接返回\(p\)的第\(i\)个元素的引用，支持
p-=x、p+=x、p+x、p-x，支持用>=、<=、>、<比较位置，还可以用两个迭代器相减，得到它们下标的差。
不同容器支持的迭代器类型：
- 前向迭代器：unordered_map , unordered_multimap , unordered_set , unordered_multiset
- 双向迭代器：list , set , multiset , map , multimap
- 随机访问迭代器：vector , deque , array
- 不支持迭代器：stack , queue
迭代器数据类型的定义：[type]::iterator it;，例如map<string,int>::iterator it;，有时可以直接用auto代替，让编译器自动填充类型。
遍历（用vector举例）：
for(auto it=v.begin();it!=v.end();it++)
cout<<*it<<" ";
倒序遍历需要把iterator改成reverse_iterator，循环写成：
for(auto it=v.rbegin();it!=v.rend();it++)
cout<<*it<<" ";
其中，这四个方法返回位置的关系可以画成下图：
注意：如果在遍历list、vector等容器中途有删除操作的话，一定要该写遍历格式：
for(auto it=lis.begin();it!=lis.end();){
if(/* 条件 */){
/* Something ... */
it=lis.erase(it);
}else{
/* Something ... */
it++;
}
}
这是因为erase后迭代器会自动失效，而删除方法返回的就是删除元素的下一个元素。
第\(4\)行写作lis.erase(it++);也可以。