收集的一些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即一个连续内存的大小的感觉。通常此默认的内存分配能完成 大部分情况下的存储。

优点:

  • 不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数组 进行动态操作。通常体现在push_back() pop_back()
  • 随机访问方便,即支持[ ]操作符和vector.at()
  • 节省空间。

    缺点:

  • 在内部进行插入删除操作效率低。
  • 只能在vector的最后进行push和pop,不能在vector的头进行push和pop。
  • 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释 放

list

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

  • 不使用连续内存完成动态操作。
  • 在内部方便的进行插入和删除操作
  • 可在两端进行push、pop 缺点:
  • 不能进行内部的随机访问,即不支持[ ]操作符和vector.at()
  • 相对于verctor占用内存多

deque

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

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

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

  • 随机访问方便,即支持[ ]操作符和vector.at()
  • 在内部方便的进行插入和删除操作
  • 可在两端进行push、pop 缺点:
  • 占用内存多 使用区别:
  • 如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
  • 如果你需要大量的插入和删除,而不关心随即存取,则应使用list
  • 如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque

map

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

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

map mapStudent;

hash_map

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

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

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

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

  • 得到key
  • 通过hash函数得到hash值
  • 得到桶号(一般都为hash值对桶数求模)
  • 存放key和value在桶内。
  • 其取值过程是:
  • 得到key
  • 通过hash函数得到hash值
  • 得到桶号(一般都为hash值对桶数求模)

比较桶的内部元素是否与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