文档介绍：第十一章标准模板库(STL)
库(library)是一系列程序组件的集合,它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性,模板(template)为通用性带来了不可估量的前景,我们可以在使用模板时才对某些类型作选择。模板是标准C++实现代码复用的有力工具,特别是在有关数据结构的算法方面。为程序员提供大量实用的库是C++的又一特色。
标准模板库(Standard Template Library)是ANSI/ISO C++最有特色、最实用的部分之一。STL包含了容器类(container)、迭代子(iterator)和算法(algorithm)三个部分。泛型算法(generic algorithm)和函数对象(function object)的概念与使用使算法摆脱了对不同类型数据个性操作的依赖,这样就可以编出更具通用性的算法。
ANSI(American National Standards Institute,美国国家标准学会)的X3J16是C++语言标准的标准化委员会的名称,它于1989年正式启动,现在简称为J16。ISO(International anization,国际标准化组织)的JTC1/SC22/WG21技术委员会,与前者合作制定C++的标准。1997年11月完成的标准ISO14882,于1998年通过,它将相对稳定5年以上,其中一个较大的改动就是把模板引入标准库,使用模板类来代替传统的C++中定义的类。
STL(Standard Template Library,标准模板库)由惠普公司的专家开发,并在1994年首次加入到C++标准草案中的。
标准模板库简介
面向对象程序设计如果只改善可维护性,是不能取得程序员的青睐,程序员首先看中的是面向对象的可复用性。标准模板库(Standard Template Library)正是提供了这种可复用性。本书前面介绍的顺序表、链表、栈、队等数据结构,如果由程序员自己来开发也许比较困难。STL提供了一个标准化的模板化的对象容器库,其中包含多种数据结构及其算法,可以节省大量的时间和精力,而且程序是高质量的。
容器类是管理序列的类,是容纳一组对象或对象集的类。通过由容器类提供的成员函数,可以实现诸如向序列中插入元素,删除元素,查找元素等操作,这些成员函数通过返回迭代子来指定元素在序列中的位置。
迭代子是面向对象版本的指针,它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。
泛型算法不依赖于具体的容器,通用的算法更易于扩充。泛型算法中采用函数对象(function object)引入不同情况下同一算法的差异。它没有使用继承和多态,避免了虚函数的开销,使STL效率更高。
容器分为三大类:
顺序容器(sequence container or sequential container)
关联容器(associative container)
容器适配器(container adopter)
。
标准库容器类
标准库容器类
说明
顺序容器
vector(参量)
deque(双端队列)
list(列表)
从后面快速插入与删除,直接访问任何元素
从前面或后面快速插入与删除,直接访问任何元素
从任何地方快速插入与删除,双链表
关联容器
set(集合)
multiset(多重集合)
map(映射)
multimap(多重映射)
快速查找,不允许重复值
快速查找,允许重复值
一对一映射,基于关键字快速查找,不允许重复值
一对多映射,基于关键字快速查找,允许重复值
容器适配器
stack(栈)
queue(队列)
priority_queue(优先级队列)
后进先出(LIFO)
先进先出(FIFO)
最高优先级元素总是第一个出列
顺序容器和关联容器称为第一类容器(first-class container)。另外有四种容器称为近容器(near container):C语言风格数组、字符串string、操作1/0标志值的bitset和进行高速数学矢量运算的valarray。这四种容器称为近容器,是因为虽然提供与第一类容器类似的功能,但没有全部功能。
正如在Windows下所有应用软件都有类似的窗口一样,STL也使容器提供类似的接口。许多基本操作是所有容器都适用的,而有些操作则适用于类似容器的子集。这样就可以用新的类来扩展STL。。这些函数和运算符可通称为容器的接口。各容器的具体接口参见附录C。
所有标准库容器共有的函数
所有标准库容器共有的函数
说明
默认构造函数
拷贝构造函数
析构函数
e