STL 学习资料

Published: at 05:19 AM | 15 min read

收集的一些STL的学习资料：

什么是STL？

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于 C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库 包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的 应用框架，高度体现了软件的可复用性。这种现象有些类似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL(Visual Component Library)，对于此二者， 大家一定不会陌生吧。

从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比 如像需求（requirements），概念（concept），模型（model），容器（Container），算法（algorithmn），迭 代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种 软件的复用技术。

从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先 C++标准中没有出现的语言特性—模板（template）。如果查阅任何一个版本的STL源代码，你就会发现，模板 作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C++的新特性为STL的实现提供了方便。

stack,queue,priority_queue的相同点

之所以把stack,queue,priority_queue三者放在一起，是因为这三种容器再STL中均属于特殊容器。他们都具有 如下特征： 它们均是为满足特定需求而建立的容器。stack是为了满足FILO，queue是为了满足FIFO，priority_queue则是 为了满足优先级高的元素先出队列。 它们均具有一组含义非常明确的函数接口，比如stack的top,pop, push分别表示获取栈顶元素，出栈和入栈， queue的front,back, pop, push分别表示获取队列首元素，队列尾元素,出队列和入队列。 它们均不是标准的STL容器，却都是以标准STL容器为基础。stack和queue默认是在deque的基础上封装的， priority_queue默认是在vector的基础上封装出来的。stack和queue的基础容器之所以选择deque而不选择vector 等容器，是因为deque在删除元素的时候可以释放空间，同时在重新申请空间的时候无需拷贝所有元素。 它们均对基础容器有一定的要求，这个要求是由他们满足的需求确定的。比如stack需要从栈顶进出元素和获取 栈顶元素，它的基础容器则需要提供back(), push_back(), pop_back()的函数。同理queue的基础容器需要能够 提供back(), push_back(), pop_front(), priority_queue的基础容器需要提供back(), push_back(), pop_back()的函 数。 你可以你的需要，通过参数传递修改它们的基础容器。比如

stack<int, vector > st 对于stack和queue还有一个共同点，他们均有重载比较运算符，也就是说你可以对二个stack或者二个queue进 行字典许的比较和排序。

vector

向量相当于一个数组 在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个 非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配 一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成 大部分情况下的存储。

优点：

缺点：

list

双向链表 每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的 进行添加和删除操作。使用的是非连续的内存空间进行存储。 优点：

deque

双端队列 double-end queue deque是在功能上合并了vector和list。

是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两 端进行。双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈 一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点 允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除， 另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双 端队列就蜕变为两个栈底相邻的栈了。

尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应用程序中远不及栈和队列有用。 优点：

map

map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次 ，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时 候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平 衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有 序的好处。

下面举例说明什么是一对一的数据映射。比如一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关 系，这个模型用map可能轻易描述，很明显学号用int描述，姓名用字符串描述(本篇文章中不用char *来描述字 符串，而是采用STL中string来描述),下面给出map描述代码：

map<int, string> mapStudent;

hash_map

hash_map基于hash table（哈希表）。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几 乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间 换时间的做法是值得的。另外，编码比较容易也是它的特点之一。

其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数 ），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个 元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方， 称为桶。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了 相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接 定址”与“解决冲突”是哈希表的两大特点。

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存 。其插入过程是：

其取值过程是:

比较桶的内部元素是否与key相等，若都不相等，则没有找到。 取出相等的记录的value。 hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一 个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候). 由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时 需要指定的参数。

set,multiset

set是STL中一种标准关联容器（vector,list,string,deque都是序列容器，而set，multiset，map，multimap是标准 关联容器），它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不 涉及到内存移动和拷贝，所以效率比较高。set，顾名思义是“集合”的意思，在set中元素都是唯一的，而且默认 情况下会对元素自动进行升序排列，支持集合的交(set_intersection),差(set_difference) 并(set_union)，对称差 (set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用multiset.

bitset

有些程序需要处理二进制位的有序集，每个位可能包含0（关）值或1（开）值。位是用来保存一组项或条件的yes/no信息（又是也称标志）的简洁方法。

2011-07-07