【VC++开源代码栏目提醒】:本文主要为网学会员提供“STL教材 - 编程语言”,希望对需要STL教材 - 编程语言网友有所帮助,学习一下!
STL教材V2.0试用教材 参考书目:ltC沉思录gt ltC编程思想gt ltC Templatesgt ltC STL 开发技术引导gt ltC Primergt lt深蓝软件C教材卷3gt lt设计模式gtGof版 ltVC知识库gt 1 模版 模版好处: 1 相对宏来讲 模版增加了类型安全检测 2 相对继承来讲 模版解决了类和函数爆炸问题 3 做为Gof 23中模式之一 模版重要性不言而喻 目前只有C能够真正实现模版的功能其他语言无论在性能还是方法上都不是Gof的原意 模版是对设计架构和库的人用的不需要在
设计模版上投入太大的精力而应该在使用现成的模版库上投入更多的精力就好象学
Java的人不需要投入太大精力设计java库是一个道理世界上有很多成功的模版库我们的重点在STL上因为它是C的一部分其他优秀的库会逐步统一到C0X标准中. 1.1 模板的概念。
我们已经学过重载Overloading对重载函数而言C的检查机制能通过函数参数的不同及所属类的不同。
正确的调用重载函数。
例如为求两个数的最大值我们定义MAX函数需要对不同的数据类型分别定义不同重载Overload版本。
//函数1. int max int x int y return xgty x:y //函数2. float max float xfloat y return xgty x:y //函数3. double maxdouble xdouble y return cgty x:y 但如果在主函数中我们分别定义了 char ab 那么在执行maxab时 程序就会出错因为我们没有定义char类型的重载版本。
现在我们再重新审视上述的max函数它们都具有同样的功能即求两个数的最大值能否只写一套
代码解决这个问题呢这样就会避免因重载函数定义不 全面而带来的调用错误。
为解决上述
问题C引入模板机制模板定义模板就是实现
代码重用机制的一种工具它可以实现类型参数化即把类型定义为参数 从而实现了真正的
代码可重用性。
模版可以分为两类一个是函数模版另外一个是类模版。
1.2 函数模板的写法 函数模板的一般形式如下 template lt class或者也可以用typename T gt 返回类型 函数名形参表 //函数定义体 说明 template是一个声明模板的关键字表示声明一个模板关键字class不能省略如果类型形参多余一个 每个形参前都要加class lt类型 形参表gt可以包含基本数据类型可以包含类类型. 请看以下程序: //Test.cpp include ltiostreamgt using std::cout using std::endl //声明一个函数模版用来比较输入的两个相同数据类型的参数的大小class也可以被typename代替 //T可以被任何字母或者数字代替。
template lt class T gt T minT xT y returnxlty x:y void main int n12n210 double d11.5d25.6 coutltlt quot较小整数:quotltltminn1n2ltltendl coutltlt quot较小实数:quotltltmind1d2ltltendl systemquotPAUSEquot 程序分析main函数中定义了两个整型变量n1 n2 两个双精度类型变量d1 d2然后调用min n1 n2 即实例化函数模板T minT x T y其中为int型求出n1n2中的最小值同理调用mind1d2时求出d1d2中的最小值 1.3 类模板的写法 定义一个类模板 template lt class或者也可以用typename T gt class类名 类定义 说明其中template是声明各模板的关键字表示声明一个模板模板参数可以是一个也可以是多个。
例如定义一个类模板 // ClassTemplate.h ifndef ClassTemplate_HH define ClassTemplate_HH templatelttypename T1typename T2gt class myClass private: T1 I T2 J public: myClassT1 a T2 b//Constructor void show //这是构造函数 //注意这些格式 template lttypename T1 typename T2gt myClass lt T1 T2 gt::myClass T1 a T2 b :I a J b //这是void show template lttypename T1typename T2gt void myClass lt T1 T2 gt ::show coutltltquotIquotltltIltltquot JquotltltJltltendl endif // Test.cpp include ltiostreamgt include quotClassTemplate.hquot using std::cout using std::endl void main myClassltintintgt class135 class1.show myClassltintchargt class23a class2.show myClassltdoubleintgt class32.910 class3.show systemquotPAUSEquot 1.4非类型模版参数 一般来说非类型模板参数可以是常整数包括枚举或者指向外部链接对象的指针。
那么就是说浮点数是不行的指向内部链接对象的指针是不行的。
template lttypename T int MAXSIZEgt class Stack Private: T elemsMAXSIZE ?? Int main Stackltint 20gt int20Stack Stackltint 40gt int40Stack ?? 2 STL组成和基本概念 STL是 C的ANSI/ISO 标准的一部分可以用于所有C语言编译器和所有平台。
STL的同一版本在任意硬件配置下都是可用的STL 提供了大量的可复用
软件组织。
例如
程序员再也不用自己设计排序搜索算法了这些都已经是STL的一部分了。
使用STL编写的
代码更容易修改和阅读因为
代码更短了很多基础
工作代码已经被组件化了。
STL 的组成 STL有三大核心部分容器Container、算法Algorithms、迭代器Iterator容器适配器container adaptor函数对象functor除此之外还有STL其他标准组件。
?? HP STL 所有STL的源 ?? P.J. Plauger STL
VC ?? Rouge Wave STL ?? STLport
开源Cbuilder ?? SGI STL
linux 容器container 容器是数据在内存中组织的方法例如数组、堆栈、队列、链表或二叉树不过这些都不是STL标准容器。
STL中的容器是一种存储TTemplate类型值的有限集合的数据结构容器的内部实现一般是类。
这些值可以是对象本身如果数据类型T代表的是Class的话。
算法algorithm 算法是应用在容器上以各种方法处理其内容的行为或功能。
例如有对容器内容排序、复制、检索和合并的算法。
在STL中算法是由模板函数表现的。
这些函数不是容器类的成员函数。
相反它们是独立的函数。
令人吃惊的特点之一就是其算法如此通用。
不仅可以将其用于 STL容器而且可以用于普通的C数组或任何其他应用程序指定的容器。
迭代器iterator 一旦选定一种容器类型和数据行为算法那么剩下唯一要他做的就是用迭代器使其相互作用。
可以把达代器看作一个指向容器中元素的普通指针。
可以如递增一个指针那样递增迭代器使其依次指向容器中每一个后继的元素。
迭代器是 STL的一个关键部分因为它将算法和容器连在一起。
2.1组成简介 容器 STL中的容器有队列容器和关联容器容器适配器congtainer adaptersstackqueuepriority queue位集bit_set串包string_package等等。
在本文中我将介绍listvectordeque等队列容器和set和multisets map和multimaps等关联容器一共7种基本容器类。
队列容器顺序容器队列容器按照线性排列来存储T类型值的集合队列的每个成员都有自己的特有的位置。
顺序容器有向量类型、双端队列类型、
列表类型三种。
基本容器——顺序容器 向量vector容器类include ltvectorgtvector是一种动态数组是基本数组的类模板。
其内部定义了很多基本操作。
既然这是一个类那么它就会有自己的构造函数。
vector 类中定义了4中种构造函数 默认构造函数构造一个初始长度为0的空向量 如vectorltintgt v1 带有单个整形参数的构造函数此参数描述了向量的初始大小。
这个构造函数还有一个可选的参数这是一个类型为T的实例描述了各个向量种各成员的初始值 如vectorltintgt v2init_size0 如果预先定义了int init_size他的成员值都被初始化为0 复制构造函数构造一个新的向量作为已存在的向量的完全复制 如vectorltintgt v3v2 带两个常量参数的构造函数产生初始值为一个区间的向量。
区间由一个半开区间firstlastMS
word的显示可能会有问题first前是一个左方括号last后面是一个右圆括号来指定。
如vectorltintgt v4firstlast 下面一个例子用的是第四种构造方法其它的方法读者可以自己试试。
//程序初始化
演示 include ltcstringgt include ltvectorgt include ltiostreamgt using namespace std int ar10 12 45 234 64 12 35 63 23 12 55 char str quotHello Worldquot int mainvoid vector ltintgt vec1ar ar10 //firstarlastar10不包括ar10vector向量容器类 vector ltchargt vec2str strstrlenstr //firststrlast strstrlenstr不包括最后一个 coutltltquotvec1:quotltltendl //打印vec1和vec2const_iterator是迭代器后面会讲到 //当然也可以用for int i0 iltvec1.size icout ltlt veci输出 //size是vector的一个成员函数 forvectorltintgt::const_iterator pvec1.beginpvec1.end p coutltltp coutltltnltltquotvec2:quotltltendl forvectorltchargt::const_iterator p1vec2.beginp1vec2.end p1 coutltltp1 getchar return 0 vector的成员函数beginendpush_backassignfrontbackeraseemptyatsize。
push_back是将数据放入vector向量或deque双端队列的标准函数。
Insert是一个与之类似的函数然而它在所有容器中都可以使用但是用法更加复杂。
end实际上是取末尾加一以便让循环正确运行--它返回的指针指向最靠近数组界限的数据。
2.2迭代器includeltiteratorgt 迭代器提供对一个容器中的对象的访问方法并且定义了容器中对象的范围。
迭代器就如同一个指针。
事实上C的指针也是一种迭代器。
但是迭代器不仅仅是指针因此你不能认为他们一定具有地址值。
例如一个数组索引也可以认为是一种迭代器。
迭代器的类型 对于STL数据结构和算法你可以使用六种迭代器。
下面简要说明了这六种类型 ·输入迭代器 Input iterators 提供对数据的只读访问。
·输出迭代器 Output iterators 提供对数据的只写访问 ·前向迭代器 Forward iterators 提供读写操作并能向前推进迭代器。
·双向迭代器 Bidirectional iterators 提供读写操作并能向前和向后操作。
·随机迭代器 Random access iterators 提供读写操作并能在数据中随机移动。
·流迭代器可以直接输出、输入流中的值 尽管各种不同的STL实现细节方面有所不同还是可以将上面的迭代器想象为一种类继承关系。
从这个意义上说下面的迭代器继承自上面的迭代器。
由于这种继承关系你可以将一个Forward迭代器作为一个output或input迭代器使用。
同样如果一个算法要求是一个bidirectional 迭代器那么只能使用该种类型和随机访问迭代器。
下面的例子用到了输入输出迭代器 include ltiostreamgt include ltfstreamgt include ltiteratorgt include ltvectorgt include ltstringgt using namespace std int mainvoid vectorltstringgt v1 ifstream filequotText1.txtquot iffile.fail coutltltquotopen file Text1.txt failedquotltltendl return 1 copyistream_iteratorltstringgtfileistream_iteratorltstringgtinserterv1v1.begin copyv1.beginv1.endostream_iteratorltstringgtcoutquot quot coutltltendl cin.get return 0 这里用到了输入迭代器istream_iterator输出迭代器ostream_iterator。
程序完成了将一个文件输出到屏幕的功能先将文件读入然后通过输入迭代器把文件内容复制到类型为字符串的向量容器内最后由输出迭代器输出。
Inserter是一个输入迭代器的一个函数迭代器适配器它的使用方法是inserter container pos congtainer是将要用来存入数据的容器pos是容器存入数据的开始位置。
上例中是把文件内容存入copy到向量v1中。
查找函数 反转函数 2.3算法algorithminlcude ltalgorithmgt STL中算法的大部分都不作为某些特定容器类的成员函数他们是泛型的每个算法都有处理大量不同容器类中数据的使用。
值得注意的是STL中的算法大多有多种版本用户可以依照具体的情况选择合适版本。
在STL的泛型算法中有4类基本的算法 变序型队列算法可以改变容器内的数据 非变序型队列算法处理容器内的数据而不改变他们 排序值算法包涵对容器中的值进行排序和合并的算法还有二叉
搜索算法 通用数值算法 注STL的算法并不只是针对STL容器对一般容器也是适用的。
变序型队列算法mutating algorithms 又叫可修改的序列算法。
这类算法有复制copy算法、交换swap算法、 替代replace算法、删除remove算法移动transfer算法、翻转reverse算法等等。
这些算法可以改变容器中的数据数据值和值在容器中的位置。
下面介绍2个比较
常用的算法reverse和copy。
include ltiostreamgt include ltalgorithmgt include ltiteratorgt//下面用到了输出迭代器ostream_iterator using namespace std int mainvoid int arr611232121590 int arr17 int arr2625690-56 copyarrarr6arr1//将数组aar复制到arr1 coutltltquotarr6 copy to arr17now arr1: quotltltendl forint i0ilt7i coutltltquot quotltltarr1i reversearrarr6//将排好序的arr翻转 coutltltnltltquotarr reversed now arr:quotltltendl copyarrarr6ostream_iteratorltintgtcout quot quot//复制到输出迭代器 swap_rangesarrarr6arr2//交换arr和arr2序列 coutltltnltltquotarr swaped to arr2now arr:quotltltendl copyarrarr6ostream_iteratorltintgtcout quot quot coutltltnltltquotarr2:quotltltendl copyarr2arr26ostream_iteratorltintgtcout quot quot cin.get return 0 revese的功能是将一个容器内的数据顺序翻转过来它的原型是 templateltclass Bidirectional gt void reverseBidirectional first Bidirectional last 将first和last之间的元素翻转过来上例中你也可以只将arr中的一部分进行翻转 reversearr3arr6这也是有效的。
First和last需要指定一个操作区间。
Copy是要将一个容器内的数据复制到另一个容器内它的原型是 Templateltclass InputIterator class OutputIteratorgt OutputIterator copyInputIterator first InputIterator last OutputIterator result 它把firstlast1内的队列成员复制到区间resultresultlast-first-1中。
泛型交换算法Swap操作的是单值交换它的原型是 templateltclass Tgt void swapTamp aTamp b swap_ranges操作的是两个相等大小区间中的值它的原型是 templateltclass ForwardIterator1 class ForwardIterator2gt ForwardIterator2 swap_rangesForwardIterator1 first1ForwardIterator1 last1 ForwardIterator1 first2 交换区间first1last1-1和first2 first2last1-first1-1之间的值并假设这两个区间是不重叠的。
非变序型队列算法Non-mutating algorithm 又叫不可修改的序列算法。
这一类算法操作不影响其操作的容器的内容包括搜索队列成员算法等价性检查算法计算队列成员个数的算法。
我将用下面的例子介绍其中的findsearchcount //stl_cpp_15.cpp include ltiostreamgt include ltvectorgt include ltalgorithmgt using namespace std int mainvoid int a101233466 vectorltintgt v1aa10 vectorltintgt::iterator result1result2//result1和result2是随机访问迭代器 result1findv1.beginv1.end2 //在v1中找到2result1指向v1中的2 result2findv1.beginv1.end8 //在v1中没有找到8result2指向的是v1.end coutltltresult1-v1.beginltltendl //303或413屏幕结果是3 coutltltresult2-v1.endltltendl int b952235455522 vectorltintgt v2a2a8 vectorltintgt v3bb4 result1searchv1.beginv1.endv2.beginv2.end coutltltresult1ltltendl //在v1中找到了序列v2result1指向v2在v1中开始的位置 result1searchv1.beginv1.endv3.beginv3.end coutltltresult1-1ltltendl //在v1中没有找到序列v3result指向v1.end屏幕打印出v1的最后一个元素66 vectorltintgt v4bb9 int icountv4.beginv4.end5 int jcountv4.beginv4.end2 coutltltquotthere are quotltltiltltquot members in v4 equel to 5quotltltendl coutltltquotthere are quotltltjltltquot members in v4 equel to 2quotltltendl //计算v4中有多少个成员等于 52 cin.get return 0 find的原型是 templateltclass InputIteratorclass EqualityComparablegt InputIterator findInputIterator first InputIterator last const EqualityComparableamp value 其功能是在序列firstlast-1中查找value值如果找到就返回一个指向value在序列中第一次出现的迭代如果没有找到就返回一个指向last的迭代last并不属于序列。
search的原型是 template ltclass ForwardIterator1 class ForwardIterator2gt ForwardIterator1 searchForwardIterator1 first1 ForwardIterator1 last1 ForwardIterator2 first2 ForwardIterator2 last2 其功能是在源序列first1last1-1查找目标序列first2last2-1如果查找成功就返回一个指向源序列中目标序列出现的首位置的迭代。
查找失败则返回一个指向last的迭代。
Count的原型是 template ltclass InputIterator class EqualityComparablegt iterator_traitsltInputIteratorgt::difference_type countInputIterator first InputIterator last const EqualityComparableamp value 其功能是在序列firstlast-1中查找出等于value的成员返回等于value得成员的个数。
排序算法sort algorithm 这一类算法很多功能强大同时也相对复杂一些。
这些算法依赖的是关系运算。
在这里我只介绍其中比较简单的几种排序算法sortmergeincludes //stl_cpp_16.cpp include ltiostreamgt include ltalgorithmgt using namespace std int mainvoid int a1012053689343218 int b553689 int d15 sortaa10 forint i0ilt10i coutltltquot quotltltai sortbb5 ifincludesaa10bb5 coutltltnltltquotsorted b members are included in a.quotltltendl else coutltltquotsorted a dosnt contain sorted bquot mergeaa10bb5d forint j0jlt15j coutltltquot quotltltdj cin.get return 0 sort的原型是 template ltclass RandomAccessIteratorgt void sortRandomAccessIterator first RandomAccessIterator last 功能是对firstlast-1区间内的元素进行排序操作。
与之类似的操作还有partial_sort stable_sortpartial_sort_copy等等。
merge的原型是 template ltclass InputIterator1 class InputIterator2 class OutputIteratorgt OutputIterator mergeInputIterator1 first1 InputIterator1 last1 InputIterator2 first2 InputIterator2 last2OutputIterator result 将有序区间first1last1-1和first2last2-1合并到result result last1 - first1 last2 - first2-1区间内。
Includes的原型是.