数组
数组在内存中的排列是连续的，这是数组最大的特征。
C++中的数组
在c++中有vector、string（用于字符串）、array（固定长度）担任着数组的角色，在这里只介绍vector的常用成员函数。
| 功能 | 函数 |
|---|---|
| 访问 | seq.front(),seq.back(),seq[n],seq.at(n) |
| 插入 | seq.push_back(),seq.insert(q,t),seq.insert(q,n,t),seq.insert(b,e),seq.insert(q,i1) |
| 删除 | seq.pop_back(),seq.erase(q),seq.erase(b,e),seq.clear() |
| 交换 | seq.swap(seq’),swap(seq,seq') |
| 迭代器 | seq.begin(),seq.end() |
| 大小 | seq.size(),seq.max_size(),seq.empty() |
需要注意的是数组不支持push/pop_front。
链表
链表相比于数组的优势
- 数组在内存中的排列必须是连续的，在分配内存时通常是固定的，这会造成两个问题。首先，没有用到但已经分配的内存是浪费的；其次，达到内存上限时会重新申请内存，转移数据还需要花费一定的时间。然而，链表就没有这个问题，可以随意地存储在内存中。
- 数组的插入以及删除操作的时间复杂度通常是较高的（数组的优势在于可以随机访问而链表只支持顺序访问）。
链表相比数组的劣势
- 链表无法实现随机访问；
- 链表的每个元素所占的内存空间较大。
C++中的链表
c++中的链表有list（双向链表）和forward_list（单向链表）。
关于list，
| 区别 | 函数 |
|---|---|
| 插入 | +push_front |
| 删除 | +pop_front |
| 访问 | -seq[n],-seq.at(n) |
关于forward_list，
- 不支持
push_back，pop_back，back(); - 有自己版本的insert和erase：
insert_after(p,t)等共计四种形，erase_after(p)等共计两种形态； - 另外还有
seq.before_begin()。
栈
栈的最大特点就是先进后出（FILO）。
C++中的栈
C++的栈的组成采用的是适配器模式，即通过传统的几个顺序容器实现栈。
由于栈需要用到push_back这样的操作，所以forward_list和array是直接pass掉的。
因此我们可以通过deque、vector、string、list来实现stack。
| stack | 含义 |
|---|---|
stack<int,vector> s | 定义一个空栈 |
s.top() | 返回栈顶元素 |
s.push(t) | 向栈顶压入元素 |
s.pop() | 从栈顶弹出元素 |
调用栈
计算机在内部使用被称为调用栈的栈。
存在函数嵌套函数的一段程序：
void greet(name)
greet2(name);
于是，在计算及内部，greet先入栈，greet2再入栈，之后greet2调用完毕，返回并出栈，同理，greet出栈。
递归的过程也使用了调用栈。
队列
队列遵循着先进先出（FIFO）的原则。
C++中的队列
deque实际上是一个很好的双端队列。但是对于最基础的队列，是通过适配器的形式实现的。
queue因为涉及到对于队头元素的删除，所以说vector是不能用的，同样forward_list和array也是。
| queue | 含义 |
|---|---|
back | 返回队尾元素 |
front | 返回队头元素 |
top | 返回队头元素 |
push(item) | 入队 |
pop | 出队 |
散列表
字典是由形如(k,v)的数对构成的集合。散列（hashing）是一种表示字典的方式。通过一个散列函数把字典的数对映射到一个散列表的具体位置。如果数对p的关键字是k，散列函数为f，在理想情况下，p在散列表中的位置为f(k)。
散列表的优势应该是查找很快，其他数据结构往往需要借助查找算法来确认某一元素是否在其中。
散列表的实际应用有：
- 用于查找，比如：电话簿；
- 防止重复，比如：确认某人是否投过票；
- 用作缓存，缓存的工作原理是“将数据记住，避免重新计算”，如此一来，服务器的工作开销就小了很多。缓存是一种常用的加速方式，所有的大型网站都使用缓存，而缓存的数据则存储在散列表中。比如当我们请求了www.baidu.com（URL，网页地址），如果在缓存里有的话，直接从缓存中获取数据，反之请求服务器。
理想的情况下，散列函数+数组的组合十分的便于理解。但是散列函数往往会将多个key映射到同一个位置，这称之为冲突。
比较简单的解决方法是，在这一位置安排一个链表。