C++标准模板库STL

vector 常见用法

特点

动态数组

定义 vector

vector<type> name;

如果 type 也是一个 STL 容器，定义时需要注意“>>”之间要加空格：

vector<vector<int> > name;

元素访问

v[index]
vector<type>::iterator it

常用函数

1. push_back(x) ：元素后新增一个元素，复杂度为 O(1)
2. pop_back(x) ：删除容器的尾元素，复杂度为 O(1)
3. size() ：获得容器中的元素个数，复杂度为 O(1)
4. clear() ：清空容器中所有元素，复杂度为 O(N)
5. insert(it, x) ：在容器任意迭代器处插入元素，复杂度为 O(N)
6. erase(it)[erase(it1, it2)] ：删除容器中单个元素或者某一范围中的元素，复杂度为 O(N)

set 常见用法

特点

1. 内部自动有序
2. 不含重复元素

定义 set

和 vector 类似

元素访问

set 只能通过迭代器访问，遍历 set 方法：

for (set<type>::iterator it = st.begin(); it != st.end(); ++it) {
  ...
}

常用函数

1. insert(x) ：插入容器并自动递增 排序 和去重，复杂度为 O(logN)
2. find(val) ：返回容器中对应值为 val 的迭代器，复杂度为 O(logN)
3. erase(it[val])[erase(it1, it2)] ：删除容器中元素，删除单个元素复杂度为 O(1) 或者 O(logN) ，删除多个元素复杂度为 O(it1\sim it2)
4. size() ：获得容器中元素的个数，复杂度为 O(1)
5. clear() ：清空容器中的元素，复杂度为 O(N)

string 常见用法

定义 string

string s = "xxx";

元素访问

string::iterator it

常用函数

1. += ：可以将两个 string 拼接起来
2. ==/!=/>/<... ：通过字典序比较两个 string 的大小
3. length()/size() ：返回 string 的长度，复杂度为 O(1)
4. insert(n, string)[insert(it, it1, it2)] ：将 string 插入 n 位置，或将另一 string 的 it1 到 it2 插入到当前 string 的 it 处，复杂度为 O(N)
5. erase(it)[erase(it1, it2)][erase(n, length)] ：删除容器中元素，复杂度为 O(N)
6. clear() ：清空容器中的元素，复杂度为 O(1)
7. substr(n, len) ：返回从 n 开始，长度为 len 的子串，复杂度为 O(len)
8. string::npos ：find 函数失配时的返回值
9. find(str)[find(str, n)] ：从头或从 n 处开始匹配 str，复杂度为 O(nm) ，其中 n 为主串的长度，m 为 str 的长度
10. replace(n, len, str)[replace(it1, it2, str)] ：将主串某一范围内的子串替换为 str，复杂度为 O(L) ，L 为主串的长度

map 常见用法

特点

1. 提供多类型键值对映射

定义 map

map<type1, type2> name;

元素访问

1. 通过下标
2. 通过迭代器： map<type1, type2>::iterator it ，其中 it->first 是键， it->second 是值

常用函数

1. find(key) ：返回键为 key 的映射的迭代器，复杂度为 O(logN)
2. erase(it)[erase(key)][erase(it1, it2)] ：删除元素，删除单个元素，迭代器复杂度为 O(1) ，通过键删除复杂度为 O(logN) ，删除所有元素复杂度为 O(it1\sim it2)
3. size() ：获得映射的对数，复杂度为 O(1)
4. clear() ：清空容器中所有元素，复杂度为 O(1)

queue 常见用法

定义 queue

和上述容器类似

元素访问

front()
back()

常用函数

1. push(x)/pop(x) ：入队出队，复杂度都为 O(1)
2. front()/back() ：获得队首、队尾元素，复杂度都为 O(1)
3. empty() ：判断队列是否为空，复杂度为 O(1)
4. size() ：返回队列中元素个数，复杂度为 O(1)

priority_queue 常见用法

特点

1. 底层用堆实现
2. 队首元素一定是当前队列中优先级最高的

定义 priority_queue

和上述容器类似

元素访问

只能通过 top() 访问队首元素

常用函数

1. push(x)/pop(x) ：入队出队，复杂度都为 O(logN)
2. top() ：获得队首元素，复杂度为 O(1)
3. empty() ：判断队列是否为空，复杂度为 O(1)
4. size() ：返回队列中元素个数，复杂度为 O(1)

元素优先级设置

基本数据类型

以 int 为例

priority_queue<int, vector<int>, less<int> > name;

其中多出来的两个参数：

vector<int>
less<int>

结构体

首先在结构体中重载运算符（使用 & 引用提高效率）

struct struct_name {
  string name;
  int value;
  friend bool operator < (struct_name& s1, struct_name& s2) {
    return f1.value < f2.value;
  }
}

接着直接定义 struct_name 类型的优先队列

priority_queue<struct_name> name;

或者可以把重载函数写在结构体外面

struct cmp {
   bool operator () (struct_name& s1, struct_name& s2) {
     return f1.value < f2.value;
   }
 }

这时定义优先队列的方法为

priority_queue<int, vector<int>, cmp > name;

stack 常见用法

定义 stack

和上述容器类似

元素访问

只能通过 top() 访问栈顶元素

常用函数

1. push(x)/pop(x) ：入栈出栈，复杂度都为 O(1)
   2. top() ：获得栈顶元素，复杂度为 O(1)
   3. empty() ：判断队列是否为空，复杂度为 O(1)
   4. size() ：返回队列中元素个数，复杂度为 O(1)

pair 常见用法

特点

方便地绑定两个元素

定义 pair

pair<type1, type2> name;

元素访问

通过 name.first 和 name.second 访问

常用函数

1. ==/!=/>/<... ：比较，先比较 first，当 first 相等时再比较 second

常见用途

1. 用来替代二元结构体，节省时间
2. 作为 map 的键值对进行插入

algorithm 常用函数

max()、min() 和 abs()

max(x, y)/min(x, y) 用来返回 x 和 y 中的最大值/最小值， abs(x) 返回 x 的绝对值，如果需要返回三个数的最大值，可使用

max(x, max(y, z));

swap()

swap(x, y) 用来交换 x 和 y 的值

reverse()

reverse(it1, it2) 将 it1 到 it2 之间的元素反转，it 可以是数组指针或者容器的迭代器

next_permutation()

用来给出一个序列在全排列中的下一个序列

fill()

用来把数组或容器中的某一段区间赋为某个相同的值

sort()

sort 的使用方法为：

sort(首元素地址, 尾元素的下一个地址， [比较函数])

不填写比较函数时，默认进行递增排序，而比较函数的构造方法为：

bool cmp(type a, type b) {
  return a > b;
}

lower_bound() 和 upper_bound()

二者需要用在有序数组或者容器中，其中

lower_bound(it1, it2, val)
upper_bound(it1, it2, val)

它们的复杂度均为 O(log(it1 – it2))