STL标准模板库小结
STL就是Standard Template Library,标准模板库。这可能是一个历史上最 令人兴奋的工具的最无聊的术语。从根本上说,STL是一些“容器”的集合,这 些“容器“有list, vector,set,map等,STL也是算法和其它一些组件的集合。这 里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。是C++标 准库的一个重要组成部分,它由Stepanov and Lee等人最先开发,它是与C + +几乎同时开始开发的;一开始STL选择了 Ada作为实现语言,但Ada有点不争 气,最后他们选择了 C + + , C+ +中已经有了模板。STL又被添加进了 C++库。 1996年,惠普公司又免费公开了 STL,为STL的推广做了很大的贡献。STL提供 了类型安全、高效而易用特性的STL无疑是最值得C++程序员骄傲的部分。每一 个C++程序员都应该好好学习STLo大体上包括container (容器)、algorithm (算法)和iterator (迭代器),容器和算法通过迭代器可以进行无缝连接。 一、基础知识 1、泛型技术 泛型技术的实现方法有多种,比如模板,多态等。模板是编译时决定,多态是运 行时决定,其他的比如RTTI也是运行时确定。多态是依靠虚表在运行时查表实 现的。比如一个类拥有虚方法,那么这个类的实例的内存起始地址就是虚表地址, 可以把内存起始地址强制转换成int*,取得虚表,然后(int*)*(int*)取得虚表里的 第一个函数的内存地址,然后强制转换成函数类型,即可调用来验证虚表机制。 泛型编程(generic programming,以下直接以GP称呼)是一种全新的程序设 计思想,和0。,OB, P0这些为人所熟知的程序设计想法不同的是GP抽象度 更高,基于GP设计的组件之间偶合度底,没有继承关系,所以其组件间的互交 性和扩展性都非常高。我们都知道,任何算法都是作用在一种特定的数据结构上 的,最简单的例子就是快速排序算法最根本的实现条件就是所排序的对象是存贮 在数组里面,因为快速排序就是因为要用到数组的随机存储特性,即可以在单位 时间内交换远距离的对象,而不只是相临的两个对象,而如果用联表去存储对象, 由于在联表中取得对象的时间是线性的即0[n],这样将使快速排序失去其快速 的特点。也就是说,我们在设计一种算法的时候,我们总是先要考虑其应用的数 据结构,比如数组查找,联表查找,树查找,图查找其核心都是查找,但因为作 用的数据结构不同将有多种不同的表现形式。数据结构和算法之间这样密切的关 系一直是我们以前的认识。泛型设计的根本思想就是想把算法和其作用的数据结 构分离,也就是说,我们设计算法的时候并不去考虑我们设计的算法将作用于何 种数据结构之上。泛型设计的理想状态是一个查找算法将可以作用于数组,联表, 树,图等各种数据结构之上,变成一个通用的,泛型的算法。 2、四种类型转换操作符 static_cast将一个值以符合逻辑的方式转换。应用到类的指针上,意思是说它 允许子类类型的指针转换为父类类型的指针(这是一个有效的隐式转换),同时, 也能够执行相反动作:转换父类为它的子类。 例如:float x; Count<