• 容器: 可以容纳各种数据类型的通用结构, 是类模板.
• 迭代器: 用于遍历容器的对象
• 算法: 用于操作容器的函数模板

容器

顺序容器: 元素不是排序的, 插入和删除元素的复杂度都是线性级别.

• vector: 动态数组, 元素在内存中是连续的, 随机存取任何元素都能在常数时间内完成, 在尾部插入和删除元素也能在常数时间内完成.
• deque: 双端队列, 元素在内存中是连续的, 在头尾都能高效地插入和删除元素, 但是随机存取元素的效率比 vector 差.
• list: 双向链表, 元素在内存中是不连续的, 可以在任意位置以常数时间插入和删除元素, 不支持随机存取.

关联容器: 元素是排序的, 插入任何元素都按照排序规则来确定位置, 插入和搜索的复杂度都是对数级别.

• set/multiset: 集合, set 元素是唯一的, 不允许重复; multiset 元素可以重复.
• map/multimap: 映射, map 的键是唯一的, 不允许重复; multimap 的键可以重复.

适配器 是指将不适用的序列式容器转换为适用的序列式容器, 即通过封装某个序列式容器, 使其具有另一种序列式容器的特性.

• stack: 栈, 只能在栈顶插入和删除元素, 先进后出.
• queue: 队列, 只能在队尾插入元素, 在队头删除元素, 先进先出.
• priority_queue: 优先队列, 最高优先级元素先出列.

对于顺序容器和关联容器, 都有:

• begin end: 返回指向容器第一个元素的迭代器和指向容器最后一个元素的迭代器.
• rbegin rend: 返回指向容器最后一个元素的迭代器和指向容器第一个元素的迭代器.
• erase: 删除指定位置的元素.
• clear: 删除所有元素.

迭代器

用于指向顺序容器和关联容器中的元素, 迭代器用法和指针类似, 有 const 和非 const 两种.

1
2
3
4
5

vector<int<v>>;
vector<int>::const_iterator it;
for (it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

如果 p, p1 是双向迭代器, 则可以做:

1
2
3
4

++p, p++ // 指向下一个元素
--p, p-- // 指向上一个元素
p = p1 // 赋值
p == p1 // 判断是否相等 

如果 p, p1 是随机访问迭代器, 则可以做:

1
2
3
4
5

p += i // 向后移动 i 个元素
p -= i // 向前移动 i 个元素
p[i] // 第 i 个元素的引用
p < p1 // 判断大小
p - p1 // 计算距离

双向迭代器不支持比大小和 [] 运算符.

算法

算法就是一个个函数模板, 大多数在<algorithm> 中定义.

示例: find()

1
2

template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);

first 和 last 是迭代器, val 是要查找的值, 返回一个迭代器指向找到的元素, 如果没有找到则返回 last.

关联容器内部的元素是从小到大排序的, 称为 有序区间算法. 例如 binary_search; 有些算法会对区间进行从小到大排序, 称为 排序算法, 例如 sort.

有时, “x 和 y 相等” 等价于 “x==y 为真”, 例如 find; 有时等价于 “x 小于 y 和 y 小于 x 同时为假”, 例如 binary_search.

所有适用于 vector 的操作都适用于 deque. deque还有 push_front(将元素插入到前面) 和 pop_front (删除最前 面的元素) 操作, 复杂度是 O(1).

对于 list, 除了具有所有顺序容器都有的成员函数以外, 还支持 8 个成员函数:

• push_front: 在头部插入元素
• pop_front: 删除头部元素
• sort: 排序 (list 不支持 STL 的 sort 函数)
• remove: 删除指定元素
• unique: 删除相邻重复元素, 如果要求所有重复元素, 可以先排序, 然后调用 unique 函数.
• merge: 合并两个有序的 list, 操作后第二个容器变为空.
• reverse: 反转
• splice: 在指定位置前面插入另一链表中的一个或多个元素, 并在另一链表中删除被插入的元素.

函数对象

是对象, 但是可以像函数一样使用, 即重载 operator(). STL 中有 equal_to, less, greater 等函数对象, 用于比较两个值的大小关系.

1
2
3
4
5
6

template<class T>
struct greater : public binary_function<T, T, bool> {
    bool operator()(const T& x, const T& y) const {
        return x > y;
    }
};

list 有两个 sort 函数, 不带参数 sort 函数将 list 中的元素按 < 规定的比较方法升序排列. 还有带参数的版本:

1
2

template <class T2>
void sort(T2 op);

可以用 op 比较, 为 op(x, y) 为 true 则 x 在 y 前面.

1
2

list<int> lst;
lst.sort(greater<int>()); // greater<int>() 是个对象, 本句进行降序排序

比较规则:

1
2
3
4
5

struct MyStruct {
    bool operator()(const T & a1,const T & a2) const {
        // 若 a1 应该在 a2 前面, 则返回 true; 否则返回 false.
    }
}

• 比较规则返回 true, 意味着 a1 必须在 a2 前面.
• 返回 false, 意味着 a1 并非必须在 a2 前面.
• 排序规则的写法, 不能造成比较 a1,a2 返回 true, 比较 a2,a1 也返回 true, 否则会出问题, 比如 sort 会 runtime error. 比较 a1,a2 返回 false, 比较 a2,a1 也返回 false, 则没有问题.

集合和映射

set 和 multiset 内部元素有序排列, 新元素插入的位置取决于它的值, 查找速度快. 除了容器都有的函数之外, 还支持:

• find: 查找等于某个值的元素 (x小于y和y小于x同时不成立即为相等)
• lower_bound: 查找某个下界
• upper_bound: 查找某个上界
• equal_range: 同时查找上界和下界
• count: 计算等于某个值的元素个数 (x小于y和y小于x同时不成立即为相等)
• insert: 用以插入一个元素或一个区间

集合

1
2
3
4

template<class Key, class Pred = less<Key>, class A = allocator<Key>>
class multiset {
    // ...
};

Pred 类型的变量决定了 multiset 中的元素“一个比另一个小”是怎么定义的. multiset 运行过程中, 比较两个元素 x,y 的大小的做法, 就是生成一个 Pred 类型的变量, 假定为 op, 若表达式 op(x,y) 返回值为 true, 则 x 比 y 小. 缺省类型为 less.

插入元素时, multiset 会将被插入元素和已有元素进行比较. 由于less 模板是用 < 进行比较的, 所以,这都要求对象能用 < 比较, 即适当重载了 <. 当然也可以自定义 Pred 类型.

注意: multiset 集合元素不可修改 (返回的迭代器是 const 的), 只能添加和删除元素.

1
2
3
4
5

template<class Key, class Pred = less<Key>,
class A = allocator<Key> >
class set {
    // ...
}

set 与 multiset 的区别在于, set 中的元素是唯一的, 不允许重复. 对于 insert, multiset 会返回一个迭代器指向新插入的元素, set 则会返回插入是否成功的布尔值.

映射

1
2
3
4
5

template<class Key, class T, class Pred = less<Key>, class A = allocator<T>>
class multimap {
    typedef pair<const Key, T> value_type;
    // ...
}; 

multimap 中的元素由 <k, v> 组成, 每个元素是一个 pair 对象, 关键字就是 first 成员变量, 其类型是 Key. multimap 中允许多个元素的关键字相同. 元素按照 first 成员变量从小到大排列, 缺省情况下用 less<Key> 定义关键字的 < 关系. 拥有等价键的键值对的顺序就是插入顺序, 且不会更改. (C++11 起)

1
2
3
4
5

template<class Key, class T, class Pred = less<Key>, class A = allocator<T>>
class map {
    typedef pair<const Key, T> value_type;
    // ...
};

map 中的元素都是 pair 模板类对象. 关键字 (first 成员变量) 各不相同. 元素按照关键字从小到大排列, 缺省情况下用 less<Key>. map 则要求关键字唯一, 不允许重复. map 还重载了 [] 运算符, 用于访问元素. map 的 [] 运算符返回一个引用, 如果关键字不存在, 则会插入一个新的元素, 用无参构造初始化.

适配器

stack 是后进先出的的数据结构, 只能插入/删除/访问栈顶的元素. 可用 vector, list, deque 来实现. 缺省情况下, 用 deque 实现.

1
2

template<class T, class Cont = deque<T>>
class stack;

queue 是先进先出的数据结构, 即 push 在队尾, pop 在队头. 可用 vector, list, deque 来实现. 缺省情况下, 用 deque 实现.

1
2

template<class T, class Cont = deque<T>>
class queue;

priority_queue 是优先队列, 最高优先级元素先出列. 用堆排序技术实现, 即执行 pop 操作时, 删除的是最大的元素; 执行 top 操作时, 返回的是最大元素的常引用, 默认元素比较器是 less. 可用 vector, deque 来实现. 缺省情况下, 用 vector 实现.

1
2

template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue;

STL 算法

大多重载的算法都是有两个版本的, 其中一个是用 == 判断元素是否相等, 或用 < 来比较大小; 而另一个版本多出来一个类型参数 Pred, 以及函数形参 Pred op, 通过表达式 op(x,y) 的返回值是 true 还是 false来判断 x 是否“等于” y, 或者 x 是否“小于” y. 例如:

1
2

iterate min_element(iterate first, iterate last);
iterate min_element(iterate first, iterate last, Pred op);

不变序列算法

不修改容器或对象的算法, 适用于所有容器, 时间复杂度都是 $O(n)$.

• min: 求两个对象中较小的 (可自定义比较器)
• max: 求两个对象中较大的 (可自定义比较器)
• min_element: 求区间中的最小值 (可自定义比较器)
• max_element: 求区间中的最大值 (可自定义比较器)
• for_each: 对区间中的每个元素都做某种操作
• count: 计算区间中等于某值的元素个数
• count_if: 计算区间中符合某种条件的元素个数
• find: 在区间中查找等于某值的元素
• find_if: 在区间中查找符合某条件的元素
• find_end: 在区间中查找另一个区间最后一次出现的位置 (可自定义比较器)
• find_first_of: 在区间中查找第一个出现在另一个区间中的元素 (可自定义比较器)
• adjacent_find: 在区间中寻找第一次出现连续两个相等元素的位置 (可自定义比较器)
• search: 在区间中查找另一个区间第一次出现的位置 (可自定义比较器)
• search_n: 在区间中查找第一次出现等于某值的连续 n 个元素 (可自定义比较器)
• equal: 判断两区间是否相等 (可自定义比较器)
• mismatch: 逐个比较两个区间的元素, 返回第一次发生不相等的两个元素的位置 (可自定义比较器)
• lexicographical_compare: 按字典序比较两个区间的大小 (可自定义比较器)

变值算法

此类算法会修改源区间或目标区间元素的值. 值被修改的那个区间不可以是属于关联容器的.

• for_each: 对区间中的每个元素都做某种操作
• copy: 复制一个区间到别处
• copy_backward: 复制一个区间到别处, 但目标区从后往前被修改的
• transform: 将一个区间的元素变形后拷贝到另一个区间
• swap_ranges: 交换两个区间内容
• fill: 用某个值填充区间
• fill_n: 用某个值替换区间中的 n 个元素
• generate: 用某个操作的结果填充区间
• generate_n: 用某个操作的结果替换区间中的 n 个元素
• replace: 将区间中的某个值替换为另一个值
• replace_if: 将区间中符合某种条件的值替换成另一个值
• replace_copy: 将一个区间拷贝到另一个区间, 拷贝时某个值要换成新值拷过去
• replace_copy_if: 将一个区间拷贝到另一个区间, 拷贝时符合某条件的值要换成新值拷过去

删除算法

删除算法会删除一个容器里的某些元素. 这里所说的“删除”, 并不会使容器里的元素减少, 其工作过程是：将所有应该被删除的元素看做空位子, 然后用留下的元素从后往前移, 依次去填空位子

• remove: 删除区间中等于某个值的元素
• remove_if: 删除区间中满足某种条件的元素
• remove_copy: 拷贝区间到另一个区间. 等于某个值的元素不拷贝
• remove_copy_if: 拷贝区间到另一个区间. 符合某种条件的元素不拷贝
• unique: 删除区间中连续相等的元素, 只留下一个 (可自定义比较器)
• unique_copy: 拷贝区间到另一个区间. 连续相等的元素, 只拷贝第一个到目标区间 (可自定义比较器)

变序算法

变序算法改变容器中元素的顺序, 但是不改变元素的值. 变序算法不适用于关联容器. 此类算法复杂度都是 $O(n)$ 的.

• reverse: 颠倒区间的前后次序
• reverse_copy: 把一个区间颠倒后的结果拷贝到另一个区间, 源区间不变
• rotate: 将区间进行循环左移
• rotate_copy: 将区间以首尾相接的形式进行旋转后的结果拷贝到另一个区间, 源区间不变
• next_permutation: 将区间改为下一个排列 (可自定义比较器)
• prev_permutation: 将区间改为上一个排列 (可自定义比较器)
• random_shuffle: 随机打乱区间内元素的顺序
• partition: 把区间内满足某个条件的元素移到前面, 不满足该条件的移到后面
• stable_patitio: 把区间内满足某个条件的元素移到前面, 不满足该条件的移到后面. 而且对这两部分元素, 分别保持它们原来的先后次序不变

排序算法

排序算法比前面的变序算法复杂度更高, 一般是 $O(n \log n)$. 排序算法需要随机访问迭代器的支持, 因而不适用于关联容器和 list.

• sort: 将区间从小到大排序 (可自定义比较器)
• stable_sort: 将区间从小到大排序, 并保持相等元素间的相对次序 (可自定义比较器)
• partial_sort: 对区间部分排序, 直到最小的 n 个元素就位 (可自定义比较器)
• partial_sort_copy: 将区间前 n 个元素的排序结果拷贝到别处. 源区间不变 (可自定义比较器)
• nth_element: 对区间部分排序, 使得第 n 小的元素（n 从 0 开始算）就位, 而且比它小的都在它前面, 比它大的都在它后面 (可自定义比较器)
• make_heap: 使区间成为一个“堆” (可自定义比较器)
• push_heap: 将元素加入一个是“堆”区间 (可自定义比较器)
• pop_heap: 从“堆”区间删除堆顶元素 (可自定义比较器)
• sort_heap: 将一个“堆”区间进行排序, 排序结束后, 该区间就是普通的有序区间, 不再是“堆”了 (可自定义比较器)

sort 实际上是快速排序, 平均性能最优. stable_sort 是归并排序, 能保证最差情况下的性能.

有序区间算法

有序区间算法要求所操作的区间是已经从小到大排好序的, 而且需要随机访问迭代器的支持. 所以有序区间算法不能用于关联容器和 list.

• binary_search: 判断区间中是否包含某个元素.
• includes: 判断是否一个区间中的每个元素, 都在另一个区间中.
• lower_bound: 查找最后一个不小于某值的元素的位置.
• upper_bound: 查找第一个大于某值的元素的位置.
• equal_range: 同时获取 lower_bound 和 upper_bound.
• merge: 合并两个有序区间到第三个区间.
• set_union: 将两个有序区间的并拷贝到第三个区间
• set_intersection: 将两个有序区间的交拷贝到第三个区间
• set_difference: 将两个有序区间的差拷贝到第三个区间
• set_symmetric_difference: 将两个有序区间的对称差拷贝到第三个区间
• inplace_merge: 将两个连续的有序区间原地合并为一个有序区间

附注: STL 还提供了位图 bitset, 用于压缩存储.