数据结构域算法设计-stl学习总结大全教案

《数据结构域算法设计-stl学习总结大全教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、STL就是StandardTemplateLibrary，标准模板库。这可能是一个历史上最令人兴奋的工具的最无聊的术语。从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其它一些组件的集合。这里的“容器”和算法的集合指的是世界上很多聪明人很多年的杰作。是C＋＋标准库的一个重要组成部分，它由StepanovandLee等人最先开发，它是与C＋＋几乎同时开始开发的；一开始STL选择了Ada作为实现语言，但Ada有点不争气，最后他们选择了C＋＋，C＋＋中已经有

2、了模板。STL又被添加进了C＋＋库。1996年，惠普公司又免费公开了STL，为STL的推广做了很大的贡献。STL提供了类型安全、高效而易用特性的STL无疑是最值得C++程序员骄傲的部分。每一个C＋＋程序员都应该好好学习STL。大体上包括container（容器）、algorithm（算法）和iterator（迭代器），容器和算法通过迭代器可以进行无缝连接。一、基础知识1、泛型技术泛型技术的实现方法有多种，比如模板，多态等。模板是编译时决定，多态是运行时决定，其他的比如RTTI也是运行时确定。多态是依靠虚表在运行时查

3、表实现的。比如一个类拥有虚方法，那么这个类的实例的内存起始地址就是虚表地址，可以把内存起始地址强制转换成int*，取得虚表，然后(int*)*(int*)取得虚表里的第一个函数的内存地址，然后强制转换成函数类型，即可调用来验证虚表机制。泛型编程（genericprogramming，以下直接以GP称呼）是一种全新的程序设计思想，和OO，OB，PO这些为人所熟知的程序设计想法不同的是GP抽象度更高，基于GP设计的组件之间偶合度底，没有继承关系，所以其组件间的互交性和扩展性都非常高。我们都知道，任何算法都是作用在一种特

4、定的数据结构上的，最简单的例子就是快速排序算法最根本的实现条件就是所排序的对象是存贮在数组里面，因为快速排序就是因为要用到数组的随机存储特性，即可以在单位时间内交换远距离的对象，而不只是相临的两个对象，而如果用联表去存储对象，由于在联表中取得对象的时间是线性的即O[n]，这样将使快速排序失去其快速的特点。也就是说，我们在设计一种算法的时候，我们总是先要考虑其应用的数据结构，比如数组查找，联表查找，树查找，图查找其核心都是查找，但因为作用的数据结构不同将有多种不同的表现形式。数据结构和算法之间这样密切的关系一直是我们

5、以前的认识。泛型设计的根本思想就是想把算法和其作用的数据结构分离，也就是说，我们设计算法的时候并不去考虑我们设计的算法将作用于何种数据结构之上。泛型设计的理想状态是一个查找算法将可以作用于数组，联表，树，图等各种数据结构之上，变成一个通用的，泛型的算法。2、四种类型转换操作符static_cast将一个值以符合逻辑的方式转换。应用到类的指针上，意思是说它允许子类类型的指针转换为父类类型的指针（这是一个有效的隐式转换），同时，也能够执行相反动作：转换父类为它的子类。例如：floatx;Count<

6、st(x);//把x作为整型值输出dynamic_cast将多态类型向下转换为其实际静态类型。只用于对象的指针和引用。当用于多态类型时，它允许任意的隐式类型转换以及相反过程。dynamic_cast会检查操作是否有效。也就是说，它会检查转换是否会返回一个被请求的有效的完整对象。检测在运行时进行。如果被转换的指针不是一个被请求的有效完整的对象指针，返回值为NULL.例如：classCar;classCabriolet:publicCar{…};classLimousline:publicCar{…};voi

7、df(Car*cp){Cabriolet*p=dynamic_castcp;}reinterpret_cast转换一个指针为其它类型的指针。它也允许从一个指针转换为整数类型。反之亦然。这个操作符能够在非相关的类型之间转换。操作结果只是简单的从一个指针到别的指针的值的二进制拷贝。在类型之间指向的内容不做任何类型的检查和转换。例如：classA{};classB{};A*a=newA;B*b=reinterpret_cast(a);const_cast一般用于强制消除对象的常量性。例如：c

8、lassC{};constC*a=newC;C*b=const_cast(a);其它三种操作符是不能修改一个对象的常量性的。3、explicit修饰的构造函数不能担任转换函数。在很多情况下，隐式转换是有意的，并且是正当的。但有时我们不希望进行这种自动的转换。例如：为了避免这样的隐式转换，应该象下面这样显式声明该带单一参数的构造函数：classStri