发现每个数据结构都单独成文会显得文章有点多，且内容不充实。于是决定分组放了，下一部分就是『集合、映射和栈了』，基础数据结构复习完毕后，刷题就提上日程。在进入之前，先扯一点STL的东西。

STL

Standard template library，C++标准库的重要组成部分，由这几部分组成：

容器：保存一组数据，各种各样的类型，数据个体是元素。
迭代器：一种泛型指针，和容器共同使用，访问容器中的元素(非下标)。是将*, ++, ->进行了重载的类模板，不同容器的迭代器不一样。
算法：操作容器里面数据的一种方法，和具体容器无关。查找，排序，替换等。
函数对象
空间分配器

容器分类

顺序容器：线性数据结构，vector, list, deque，多个元素的有序集合，元素有前有后
关联容器：非线性数据结构，map, set，多个元素的无序集合，元素无前无后，用于存储键值对
容器适配器：依赖顺序容器的受限版本，处理特殊情况。stack, queue, priority_queue。

vector，直接访问任意元素，快速插入、删除尾部元素
deque，直接访问任意元素，快速插入、删除头部和尾部元素，但开销大
list，快速插入删除任意位置的元素，不能使用数组下标，所以没办法访问任意位置元素
set，快速查询元素，无重复关键字
multiset，允许重复关键字
map，键值对，不允许重复关键字，使用关键字快速查询元素
multimap，允许重复关键字
stack，后进先出
queue，先进先出
priority_queue，元素出队顺序取决于优先级的队列

所有容器的共同函数：

构造函数
拷贝函数
empty()判空
size()元素数目
operator()=将容器复制
>, <, ==, !=的判断

一级容器的共同函数（顺序容器+关联容器）：

a.swap(b)交换
a.max_size()最大容纳的元素数量
clear()删除
begin()返回容器首元素的迭代器
end()返回容器尾元素之后位置的迭代器
rbegin()容器最后位置的迭代器，逆序遍历
rend()容器首元素之前位置的迭代器
erase(begin, end)删除[begin, end-1]位置的元素，两者都是迭代器

顺序容器

随机迭代器：vector，deque（双端队列）
双向迭代器：list
vector：一端操作的数组，满了之后申请新的数组，并拷贝原有数组
deque：双端操作，先入先出，内部有多个数组容纳新的元素
list：若干节点，节点有两个指针，有前驱和后继，插入和删除快

共同函数：

assign(n, elem)元素做n份拷贝，覆盖原有内容
assign(beg, end)迭代器[beg, end)之间的元素赋值给当前容器
push_back尾部添加
pop_back删除尾部
front返回首部
back返回尾部
insert(pos, elem)元素插入到指定位置

关联容器

使用key快速存取元素，元素按默认规则进行排序。共同函数：

find(key)搜索容器中具有key的元素，返回指向的迭代器，没找到返回指向容器最后一个元素后面的迭代器
lower_bound(key)搜索具有key的第一个元素，返回指向元素的迭代器
upper_bound(key)搜索具有key的最后一个元素，返回指向元素之后位置的迭代器
count(key)具有key元素的数量

vector

相对于array数组大小固定不能动态变化的缺陷，vector能很好的避免这一点。同array，使用时需要引入头文件，并在std空间中声明。

声明与初始化

#include <vector>
using std::vector;
...
double values[] {1, 2, 3, 4, 5, 6, 7};
// values 是数组首地址的指针，这里隐式转换为迭代器
vector<double> v(values, values + 7);
// 也可以 resize 重新制定大小
v.resize(100);
// 也可以直接赋值
vector<int> v5 = { 1,2,3,4,5 };

其他操作

// 支持随机访问
for (int i = 0; i < v.size(); i++){
    cout << v[i] << " ";
} cout << endl;

// assign 用法 分配 3 个 11.8
v.assign(3, 11.8);
for (auto i : v){
    cout << i << " ";
} cout << endl;

// 随机访问
v.at(0) = 22.4;
for (auto i : v){
    cout << i << " ";
} cout << endl;

// 迭代器
vector<double>::iterator itr = v.begin();
// 1 号元素之前
v.insert(itr + 1, 321);
for (auto i : v){
    cout << i << " ";
} cout << endl;

// insert 之后，itr可能指歪了，所以重新赋值
itr = v.begin();

// 删除元素，区间左闭又开
v.erase(itr, itr + 2);
for (auto i : v){
    cout << i << " ";
} cout << endl;

// 清空与判空
v.clear();
if (v.empty()){
    cout << "True";
}

// 访问第一个元素
cout << v5.front() << endl; 
// 访问最后一个元素
cout << v5.back() << endl; 
// 删除最后一个元素
v5.pop_back(); 
// 加入一个元素并把它放在最后
v5.push_back(6); 
// 删除索引为3的元素
v5.erase(v5.begin() + 3);  
// 连续插入 7 个 8
v5.insert(v5.begin() + 1, 7, 8);
// 判断容器中元素的数量   
v5.size();

也许你会有疑问，insert可以在队首插入元素，为啥vector还是单端操作的容器呢？因为push_back只会在队尾追加元素，不到迫不得已vector是不会在内存中移动的，除非申请新的空间或删除大部分元素。而insert会强制vector去移动元素，这就造成了大量的内存开销。这里脑补『数据结构』中顺序结构插入元素时，其它元素的移动吧。或者这里的回答。

deque

de表示单词double，que取自单词queue，表示这是可以双端操作的队列。因其开销较大，所以一般使用vector。

#include <deque>
double values[] {1, 2, 3, 4, 5, 6, 7};
// values 是数组首地址的指针，这里用作迭代器
deque<double> q(values, values + 7);

// 其他和 vector 类似
// insert, erase 等改变元素数量的操作可能会导致迭代器失效
// 所以要重新赋值

// 队首操作
q.push_front(0);
for (auto i : q){
    cout << i << " ";
} cout << endl;

q.pop_front();
q.pop_back();
for (auto i : q){
    cout << i << " ";
} cout << endl;

list

list是链表，众所周知链式结构不支持随机访问。

#include <iostream>
#include <list>     // 引入头文件

using namespace std;

int main(){

    // 声明与初始化
    int values[] = {1, 2, 3, 4};
    list<int> l(values, values + 4);

    // 不支持随机访问
    list<int>::iterator p;
    for (p = l.begin(); p != l.end(); p++){
        cout << *p << " ";
    } cout << endl;

    // list 插入后，迭代器所指内容不受影响，仍然指向上次所指的内容
    list<int>::iterator itr = l.begin();
    itr ++;
    l.insert(itr, 90);
    for (p = l.begin(); p != l.end(); p++){
        cout << *p << " ";
    } cout << endl;
    cout << *itr << endl;

    // push_front, pop_back, pop_front 一样

    return 0;
}

list特有

// list 特有，升序和反转
l.sort();
l.reverse();
for (p = l.begin(); p != l.end(); p++){
    cout << *p << " ";
} cout << endl;

// list 特有，有序链表的合并
int values1[] = {6, 7, 8, 9};
list<int> l1(values1, values1 + 4);

l.sort();
// merge 后 l1 被清空
l.merge(l1);
for (p = l.begin(); p != l.end(); p++){
    cout << *p << " ";
} cout << endl;

// 删除所有和 90 相等的元素
l.remove(90);

p = l.end();
l1.push_back(32);
// 列表插入到指定位置 同样 l1 被清空
l.splice(p, l1);
for (p = l.begin(); p != l.end(); p++){
    cout << *p << " ";
} cout << endl;

Just for Life.

C++数据结构篇『二』顺序容器：向量、链表与双端队列

STL