数据结构——向量（vector）_vector 输入数据结构

1.向量与数组

数组是可以寻秩访问的在连续内存中存储的一系列数据，而向量也是用数组来实现的（向量模板类中包括三个成员变量，分别是规模、容量以及开辟的数组首地址），只不过多了一些接口，如插入、删除、排序、去重、查找。

2.平均分析与分摊分析

平均分析：以插入排序为例，其时间复杂度是输入敏感的，和输入的数列的逆序对数量有关，平均分析更多是对输入采取一个平均的概率分布，然后得出时间复杂度的期望值（区别于最坏的情况，插入排序最坏为O（n^2））

分摊分析：从一个更长的时间的序列来考虑，考虑连续的一系列操作，把总体的时间分配给具体的某一个步骤。

其实都是平均的思想，不过一个是概率，一个是实际的操作序列角度。

3.向量元素的遍历

可以传入函数指针或者是仿函数？（仿函数是一个类，但是里面的括号被重载了，因此这个类的对象加一个括号就能实现函数的功能，因此叫仿函数，这样可以把这个类的对象传入即可）

函数指针之前很少接触，由下例子可以学习。

如果在程序中定义了一个函数，那么在编译时系统就会为这个函数代码分配一段存储空间，这段存储空间的首地址称为这个函数的地址。而且函数名表示的就是这个地址。既然是地址我们就可以定义一个指针变量来存放，这个指针变量就叫作函数指针变量，简称函数指针。

int(*p)(int, int);

这个语句就定义了一个指向函数的指针变量 p。首先它是一个指针变量，所以要有一个“*”，即（*p）；其次前面的 int 表示这个指针变量可以指向返回值类型为 int 型的函数；后面括号中的两个 int 表示这个指针变量可以指向有两个参数且都是 int 型的函数。所以合起来这个语句的意思就是：定义了一个指针变量 p，该指针变量可以指向返回值类型为 int 型，且有两个整型参数的函数。p 的类型为 int(*)(int，int)。

4.有序向量的查找

对于有三个分支的比较，可以采取二分查找以及fibonac查找，fibonacci查找用递归深度弥补向右关键码比较需要两次，在常数上比二分查找更好。

而且可以证明fibonacci查找的系数0.618是最好的，最后的最好的平均情况是1.44log2 n.

上述是用fib的视角去改进二分查找的，还有一种视角是每次只进行一次比较，产生两个分支。（即在命中是无法立即返回，不会有最好的情况发生，每一次基本都需要递归到最后，是一种更加平稳的算法，输入不是很敏感）所以如果以后想用稳定的就用bin-C的代码就行，应该是最常用的吧；

插值查找：假设一个序列的每个值是在一个区间独立随机取，所以大体上分布是均匀的。那么给定一个值要去search，可以先有一个判断的轴点去比较（不像是前面取一个固定的中间的轴点或者是黄金分割点），可以看作是版本Abinsearch的延申（进行两次比较）。但是这种算法最坏情况下可能要O（n）的复杂度（如0000000······100查询1，原因是不是均匀分布，很想什么基尼系数的图），但是平均情况每一次比较可以使得规模缩减到根号n（可以证明但是没看），那么平均的复杂度只需要loglogn。但是logn到loglogn进步不是很明显，4G的数据（2^32 ,10^9,10亿级别）一个是32一个是5

所以除非数据太大了，一般也不用这种最坏情况很坏的的（虽然平均很好）。综合来看，可以先用插值查找，再用二分查找，再用顺序查找（200左右）。

5.向量排序

1.bubble冒泡排序

改进的c版（没有冒泡可以把尾部哨兵前移）可以实现最好O（n），但最坏还是O（n^2）

2.归并排序

首个nlogn的排序算法，而且是顺序访问，可以适用于列表（当然冒泡也是），缺点是空间复杂度n，而且输入不敏感（没有最好的情况）

6.位图

1.char类型占一个字节。位图中有三个成员变量，一个是M（指向连续的char类型数据），N（char类型数据数量，类比于向量中的容量，因为char占一个字节，所以也表示M内存中的字节数），n代表总位数，_size表示有效位，即所有位中为1的位数

2.与向量的联系：位图中的元素更像是一个个bit，所以取值只有0和1。bits2string( Rank n )这函数有点意思，将前n位变成字符串，变成了n+1个字节的数据（最后一个\0不知道什么意思）

3.位图的应用：1.用于小数据大规模的去重操作2.用筛法求小于n的所有素数

本质上都是对一组数的筛选。

4.校验环在初始化的应用：初始化创建的时候，可能里面有0也有1？（为什么开辟一个新数组空间不会默认里面全是0啊）如果不用校验环的话要O（m）的时间。

而用了校验环技术可以直接用top=0来初始化，可以使得由O（m）变成O（1），这种原理和思想其实是删除向量尾部的元素一样（直接缩减_size大小），在逻辑上删除。校验环技术本质上是把m的空间变为2m+1（一个F数组一个T数组，还有1个top数），测试、插入、删除、初始化等操作都可以对这三个玩意进行处理，有点东西的。