STL 漫谈

引

STL 是 Standard Template Library 的简称，中文名标准模板库，惠普实验室开发的一系列软件的统称。STL 现在是 C++ 标准的一部分，所以正常的 C++ 编译器都包含相应的库文件，可以在编程时直接使用。由于 C++ 标准中只规定 STL 中应该包含接口，不同的编译器在实现这些功能时会有细节上的不同。

STL 版本

目前的编译器中所带的 STL 源代码，都是经过很多工程技巧优化，所以可读性很差。推荐阅读一些早期的版本，比如 SGI STL v3.0等。同时可以搭配《STL 源码剖析》阅读。

STL 组成

STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

image.png

空间配置器(allocator)

内存分配相关，漫谈中不关注

容器（containers）

容器是指一些 STL 中一些常用的数据结构，取名为容器是应为，这些数据结构可以介绍不同的数据类型。在实现上使用了类模板。

image.png

简单容器 Simple containers

pair

• 将两个数据类型合成为一个数据类型，类似结构体
• 头文件 <utility>
• 定义：pair<T1, T2> myPair
• 生成对象：make_pair( T1 t, T2 u )
• 成员变量：.first和.second

序列式容器 Sequence containers

array

• 定长数组
• 头文件：<array>
• 定义：array<int,3> a = {1,2,3}
• 方法：.size() .max_size() .empty()

vector

• 不定长数组
• 头文件：<vector>
• 定义：vector<int> v
• 方法：.push_back() .pop_back()

Associative containers

map

• 关联容器
• 头文件：<map>
• 定义：map<int, string> myMap
• 方法：.clear()

set

• 集合
• 头文件： <set>
• 定义：set<int> mySet
• 方法：.insert() .find()

Unordered associative containers

unordered_map、unordered_mulitmap、unordered_set、unordered_multiset 都是通过 hash 实现的版本，查询时速度比红黑树版本效率高。

算法(algorithms)

STL 中与算法相关的文件有<algorithm>，<numeric>和<functional>。下面介绍一些在 ACM 中常用的算法。

sort

这里介绍一些排序相关的算法。

• sort(first, last, comp)
• stable_sort(first, last, comp)：sort 的稳定版本
• is_sorted(first, last, comp) ：判断序列是否有序
• is_sorted_until(first, last, comp)：返回第一个无须的迭代器
• partial_sort(first, mid, last) ：部分排序
• nth_element(first, nth, last, comp)：确定第 n 大的元素

permutation

排列相关的算法。

• next_permutation(first, last, comp) ：全排列的下一个
• prev_permutation(first, last, comp) ：全排列的上一个
• is_permutation()：判断是否排列

search

• lower_bound(first, last, value, comp) ：下界
• upper_bound(first, last, value, comp) ：上界
• binary_search(first, last, value, comp) ：二分查找
• equal_range(first, last, value, comp)：第一个可以插入的位置，以及最后一个可以插入的位置

参考

• 三十分钟掌握STL

文档软件

通过安装Zeal或者Dash等软件，可以快速查阅相关的语法手册。

image.png