STL
是个部件库
(component library)
，其中的部件包括有容器
(container
，储存任意类型对象的对象
)
和算法。只要用户对自己定义的部件做点小小的要求，
STL
中的算法就可以工作在用户自定义的容器上，或者
STL
中的容器可以使用用户自定义的算法。
我们可以把软件部件想象成一个三位空间。第一维表示数据类型(int, double, char, …)，第二维表示容器(array, linked-list, …)
，
第三维表示算法
(sort, merge, search, …)
。
STL
包含
5
个主要的部分，
·算法
(Algorithm)
：能运行在不同容器
(container)
上的计算过程
·容器
(Container)
：能够保留并管理对象的对象
·迭代器
(Iterator)
：算法存取容器
(algorithm-access to containers)
的抽象，以便算法可以应用在不同的容器上
·函数对象
(Function Object)
：定义了函数调用操作符
(operator())
的类
·适应器
(Adaptor)
：封装一个部件以提供另外的接口
(
例如用
list
实现
stack)
正是因为有了Iterator,算法才和容器分开了.
容器
(Container)
是能够保存其他类型的对象的类。容器形成了
STL
的关键部件。当书写任何类型软件的时候，把特定类型的元素集聚起来都是很至关重要的任务。
STL
中有顺序容器
(Sequence Container)
和关联容器
(Associative Container)
。
STL
中支持的容器总结如下：
|
顺序容器
(Sequence Container)
|
向量
(Vector)
|
|
|
双向队列
(Deque)
|
|
|
线性表
(List)
|
|
关联容器
(Associative Container)
|
集合
(Set)
|
|
|
多集合
(MultiSet)
|
|
|
映射
(Map)
|
|
|
多映射
(MultiSet)
|
迭代器
(Iterator)
是指针
(pointer)
的泛化，它允许程序员以相同的方式处理不同的数据结构
(
容器
)
。
STL
中有
5
中类型的迭代器，它们分别满足一定的要求。不同的迭代器要求定义的操作不一样。
输入和输出迭代器
向前迭代器
双向迭代器
任意存取迭代器
算法
STL
库中的算法都以迭代器类型为参数，这就和数据结果的具体实现分离开了。基于此，这些算法被称作基本算法
(generic algorithm)
。
如“寻找(Find)”、“邻居寻找(Adjacent find)”、“计数(Count)”、“不匹配(Mismatch)”、“相等(Equal)”、“搜索(Search)
”拷贝(Copy)”、“交换(Swap)”、“变换(Transform)”、“替换(Replace)”、“填充(Fill)”、“产生(Generate)”、“迁移(Remove)”、“唯一(Unique)”、“翻转(Reverse)”、“旋转(Rotate)”、“任意洗牌(Random shuffle)”、“分区(Partitions)”
适应器
(Adaptor)
是提供接口映射的模板类
(Adaptors are template classes that provide interface mappings)
。适应器基于其他类来实现新的功能，成员函数可以被添加、隐藏，也可合并以得到新的功能。
栈
(Stack)
栈可以用向量
(vector)
、线性表
(list)
或双向队列
(deque)
来实现：
stack<vector<int>> s1;
stack<list<int> > s2;
stack<deque<int>>s3;
队列
(Queue)
队列可以用线性表
(list)
或双向队列
(deque)
来实现
(
注意
vector container
不能用来实现
queue
，
因为
vector
没有成员函数
pop_front!
)
：
queue<list<int>> q1;
queue<deque<int>> q2;
优先级队列
(Priority Queue)
优先级队列可以用向量
(vector)
或双向队列
(deque)
来实现
(
注意
list container
不能用来实现
queue
，
因为
list
的迭代器不是任意存取
iterator
，而
pop
中用到堆排序时是要求
random access iterator
的
!
)
：
priority_queue<vector<int>, less<int>> pq1; //
使用递增
less<int>
函数对象排序
priority_queue<deque<int>, greater<int>> pq2; //
使用递减
greater<int>
函数对象排序
迭代适应器
逆向迭代器
(Reverse Iterator)
顾名思义，逆向迭代器的递增是朝反方向前进的。对于顺序容器
(vector, list
和
deque)
，其成员函数
rbegin()
和
rend()
都返回了相应的逆向迭代器：
list<int> l;
for (int i = 1; i < 5; i++)
l.push_back(i);
copy(l.rbegin(), l.rend(), ostream_iterator<int> (cout, “ “));
输出结果是：
4 3 2 1
插入迭代器
(Insert Iterator)
插入迭代器简化了向容器中插入元素的工作。插入迭代器指定了向容器中插入元素的位置。
STL
中有三种插入迭代器：
·向后插入
(back_insert_iterator)
，在容器尾部插入
·向前插入
(front_insert_iterator)
，在容器头部插入
·插入
(insert_iterator)
，在容器中任一位置
STL
中提供了三个函数分别构造相应的插入迭代器：
·
back_inserter
·
front_inserter
·
inserter
原始存储迭代器
(Raw Storage Iterator)
该迭代器允许算法将其结果保存进没有初始化的内存中。
函数适应器
否认者
(Negator)
有两个否认者
not1
和
not2
分别是一元和二元函数，它们分别使用一元和二元的谓词
(Predicate)
，返回的是谓词的结果的取反。
包扎者
(Binder)
STL
中有两个包扎者函数
bind1st
和
bind2nd
，可以将一些值限定在指定区间中。
函数指针的适应器
(Adaptors for pointers to function)
STL
中的算法和容器一般都需要函数对象
(function object)
作为参数。如果想用到常用的
C++
函数时，可以用
ptr_fun
把普通函数转换成函数对象。比如
ptr_fun(strcmp)
就把常用的串比较函数
strcmp
包装成一个函数对象，就可用在
STL
算法和容器中了。