vector
- 变长数组
- 长度根据需要而自动改变的数组
- 可以用来以邻接表的方式储存图
使用
- 头文件：
#include <vector> - 命名空间：
using namespace std;
定义
vector<typename> name;
相当于一维数组name[SIZE]，但长度可变。typename可以为任何类型，例如int、double、char、结构体登，也可以是STL标准容器，如vector、set、queue等。如果typename也是一个STL容器，定义时要在>>中间加上空格。
vector<int> name;
vector<double> name;
vector<char> name;
vector<node> name; // node是结构体类型
vector<vector<int> > name; // >>之间要加空格
容器内元素的访问
-
通过下标访问：
vi[index] -
通过迭代器访问：
迭代器类似指针，定义为
vector<typename>::iterator it;把迭代器指向开头：
it = vi.begin()用迭代器访问值：
*(it + i)vi[i]和*(vi.begin() + i)是等价的。尾元素地址的下一个地址：
vi.end()iterator还有自加操作：it++、++it只有在
vector和string中才允许使用vi.begin()+i这种迭代器加整数的写法。
常用函数
push_back(x)：在vector后面添加一个元素pop_back()：删除vector的尾元素size()：获得vector中元素的个数clear()：清空vector中的所有元素insert(it, x)：向vector的任意迭代器it处插入一个元素xerase(it)：删除it处的元素erase(first, last)：删除[first, last)内的所有元素
set
- 集合
- 内部自动递增排序且不含重复元素
使用
- 头文件：
#include <set> - 命名空间：
using namespace std;
定义
set<typename> name;
和vector写法类似
set<int> name;
set<double> name;
set<char> name;
set<node> name;
set<set<int> > name;
容器内元素的访问
只能通过迭代器访问：set<typename>::iterator it;
可以通过*it访问set里的元素。不能使用*(it + i)。
for (set<int>::iterator it = st.begin(); it != st.end(); it++) {
...
}
常用函数
insert(x)：将元素插入set容器中find(value)：返回set中对应值为value的迭代器erase(it)：要删除的元素的迭代器erase(value)：要删除元素的值erase(first, last)：first为要删除区间的起始迭代器，last为要删除区间的末尾迭代器的下一个地址size()：获得set内元素的个数clear()：清空set中的所有元素
延伸
- 元素不唯一用
multiset - 不排序用
unordered_set
string
使用
- 头文件：
#include <string> - 命名空间：
using namespace std;
定义
string str = "abcd";
内容访问
- 通过下标访问（和字符数组类似）
- 如果要读入和输出整个字符串，只能用
cin和cout；或者用str.c_str()将string类型转换为字符数组 - 通过迭代器访问：和
vector一样
常用函数
+=：string的加法，可以直接把两个string拼接起来==、!=、<、<=、>、>=：两个string可以直接比较大小，规则是字典序length()、size()：返回字符串的长度insert(pos, string)：在pos位置处插入字符串stringinsert(it, it2, it3)：it为原字符串欲插入的位置，it2和it3为待插字符串首尾迭代器（左闭右开区间）erase(it)：删除单个元素，it为要删除元素的迭代器erase(first, last)：删除区间内元素，first和last为首尾迭代器（左闭右开区间）erase(pos, length)：pos为要删除的起始位置，length为要删除的字符个数clear()：清空string中的数据substr(pos, len)：返回从pos开始、长度为len的子串string::npos：常数-1find(str2)：返回str2在str中的位置，如果没找到返回-1find(str2, pos)：从pos开始找str2replace(pos, len, str2)：把str从pos位置开始、长度为len的子串替换为str2replace(it1, it2, str2)：把迭代器[it1, it2)范围的子串替换为str2
map
- 将任何基本类型（包括STL）映射到任何基本类型（包括STL）
- 会以键的顺序从小到大自动排序
使用
- 头文件：
#include <map> - 命名空间：
using namespace std;
定义
map<typename1, typename2> mp;
typename1是键的类型，typename2是键值的类型。键是唯一的。
字符串必须使用string，不能使用字符串数组。
内容访问
-
通过下标访问，
map[key] -
通过迭代器访问
it->first访问键，it->second访问值
常用函数
find(key)：返回键为key的映射的迭代器erase(it)：删除迭代器处的元素erase(key)：删除键处的元素erase(first, last)：删除[first, last)的元素，first和last是迭代器size()：获取映射的对数clear()：清空map中的所有元素
延伸
- 一个键对应多个值用
multimap - 不排序用
unordered_map（C++11）
queue
- 先进先出的队列
使用
- 头文件：
#include <queue> - 命名空间：
using namespace std;
定义
queue<typename> name;
内容访问
用front()访问队首元素，用back()访问队尾元素。
常用函数
push(x)：将元素x入队front()：队首元素back()：队尾元素pop()：令队首元素出队empty()：检测队列是否为空size()：返回元素个数
注意：使用front()和pop()之前，必须用empty()判断队列是否为空。
priority_queue
- 优先队列
- 底层用堆（heap）实现
- 队首元素是当前队列中优先级最高的
用法
- 头文件：
#include <queue> - 命名空间：
using namespace std;
定义
priority_queue<typename> name;
元素访问
top()：访问队首（堆顶）元素
常用函数
push(x)：将元素x入队top()：获得队首（堆顶）元素pop()：令队首（堆顶）元素出队empty()：检测队列是否为空size()：返回队列内的元素个数
优先级设置
-
基本数据类型
数字大的优先级越高，队首元素就是优先队列内元素最大的。
priority_queue<int> q; priority_queue<int, vector<int>, less<int> > q;对基本数据类型来说，这两种定义是等价的。
vector<int>写的是承载底层数据结构堆的容器，less<int>是对第一个参数的比较类，表示数字大的优先级大，greater<int>表示数字小的优先级大。 -
结构体类型
重载运算符“
<”（不能重载“>”，会编译错误）struct fruit { string name; int price; friend bool operator < (fruit f1, fruit f2) { return f1.price < f2.price; } }
注意：使用top()前必须用empty()判断优先队列是否为空。
stack
使用
- 头文件：
#include <stack> - 命名空间：
using namespace std;
定义
stack<typename> name;
容器内元素访问
只能用top()访问栈顶元素。
常用函数
push(x)：将元素x入栈top()：获得栈顶元素pop()：弹出栈顶元素empty()：检测栈是否为空size()：返回栈内元素个数
pair
用处不大，略
algorithm头文件常用函数
- 因为是C++的东西所以要加
using namespace std;才能用
max()
max(x, y)返回x和y中的最大值，如果要返回三个数的最大值可以用max(x, max(y, z))的写法。
min()
min(x, y)返回x和y中的最小值。
abs()
abs(x)返回整数x的绝对值。如果要浮点数的绝对值，需要用math头文件下的fabs()。
swap()
swap(x, y)交换x和y的值。
reverse()
reverse(it, it2)将数组指针或迭代器[it, it2)内的元素进行反转。
next_permutation()
next_premutation(it, it2)给出一个序列在全排列中的下一个序列。如果有下一个序列返回true，否则返回false。在原数组上操作，范围为[it, it2)。
fill()
fill(it, it2)将数组或某容器的某一段区间内赋某个相同的值。可以是数组类型中对应范围内的任意值。
sort()
在第4章中已经说过。
lower_bound()和upper_bound()
- 用在有序数组或容器中
lower_bound(first, last, val)：在[first, last)中寻找第一个值大于等于val的元素的位置，如果是数组返回指针，如果是容器返回迭代器upper_bound(first, last, val)：在[first, last)中寻找第一个值大于val的元素的位置，如果是数组返回指针，如果是容器返回迭代器- 如果找不到元素，则返回可以插入该元素的位置的指针或迭代器
总结
元素访问
| 容器 | 下标 | 迭代器 | 首 | 尾 | 其他 |
|---|---|---|---|---|---|
vector |
√ | *(it + i) |
|||
set |
*it |
||||
string |
√ | *(it + i) |
str.c_str() |
||
map |
√（键） | it->first、it->second |
|||
queue |
front() |
back() |
|||
priority_queue |
top() |
||||
stack |
top() |
常用函数
| 容器 | 添加 | 删除 | 清除 | 查找 | 大小 | 空检测 | 其他 |
|---|---|---|---|---|---|---|---|
vector |
push_back(x)insert(it, x) |
pop_back()erase(it)erase(first, last) |
clear() |
size() |
|||
set |
insert(x) |
erase(it)erase(value)erase(first, last) |
clear() |
find(value) |
size() |
||
string |
insert(pos, str)insert(dst, src1, src2) |
erase(it)erase(first, last)erase(pos, length) |
clear() |
find(str2)find(str2, pos)substr(pos, len) |
length()size() |
replace(pos, len, str2)replace(it1, it2, str2) |
|
map |
erase(it)erase(key)erase(first, last) |
clear() |
find(key) |
size() |
|||
queue |
push(x) |
pop() |
size() |
empty() |
|||
priority_queue |
push(x) |
pop() |
size() |
empty() |
|||
stack |
push(x) |
pop() |
size() |
empty() |