ACM模板7

1免费模板~~~STL简介1概况..........................................................21.1STL是什么...............................................21.2为什么我们需要学习STL...................................21.3初识STL.................................................21.4STL的组成...............................................52容器..........................................................62.1基本容器——向量（vector）...............................62.2双端队列（deque容器类）...............................92.3表（List容器类）.......................................102.4集和多集（set和multiset容器类）：....................122.5映射和多重映射（map和multimap）.......................133算法（algorithm）：..........................................153.1翻转和复制（reverse()和copy()）........................153.2单值交换（Swap()）......................................163.3查找（find()）..........................................173.4得到数目（Count()）.....................................183.5排序（sort()）..........................................194迭代器（itertor）............................................215STL的其他标准组件............................................225.1函数对象（functor或者funtionobjects）.................225.2适配器（adapter）.......................................2321概况1.1STL是什么作为一个C++程序设计者，STL是一种不可忽视的技术。StandardTemplateLibrary(STL)：标准模板库,更准确的说是C++程序设计语言标准模板库。STL是所有C++编译器和所有操作系统平台都支持的一种库，说它是一种库是因为，虽然STL是一种标准，也就是说对所有的编译器来说，提供给C++程序设计者的接口都是一样的。也就是说同一段STL代码在不同编译器和操作系统平台上运行的结果都是相同的，但是底层实现可以是不同的。令人兴奋的是，STL的使用者并不需要了解它的底层实现。试想一下，如果我们有一把能打开所有锁的钥匙，那将是多么令人疯狂啊。STL的目的是标准化组件，这样你就不用重新开发它们了。你可以仅仅使用这些现成的组件。STL现在是C++的一部分，因此不用额外安装什么。它被内建在你的编译器之内。1.2为什么我们需要学习STLSTL是C++的ANSI/ISO标准的一部分,可以用于所有C++语言编译器和所有平台(Windows/Unix/Linux..)。STL的同一版本在任意硬件配置下都是可用的；STL提供了大量的可复用软件组织。例如，程序员再也不用自己设计排序，搜索算法了，这些都已经是STL的一部分了。嘎嘎，有意思吧。使用STL的应用程序保证了得到的实现在处理速度和内存利用方面都是高效的，因为STL设计者们已经为我们考虑好了。使用STL编写的代码更容易修改和阅读，这是当然的啦。因为代码更短了，很多基础工作代码已经被组件化了；使用简单，虽然内部实现很复杂。虽然，STL的优点甚多，但是STL的语法实在令初学者人头疼，许多人望而却步。可是STL是每个C++程序设计者迟早都要啃的一块骨头。1.3初识STL下面让我们来看几段代码吧：#includeiostreamintmain(void){doublea[]={1,2,3,4,5};std::coutmean(a,5)std::endl;//willprint3return0;}3好懂吧，除了那个std有点让人不舒服以外，这是一段普通的没有使用STL的C++代码。再看下面一段：#includevector#includeiostreamintmain(){std::vectordoublea;a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(4);a.push_back(5);for(inti=0;ia.size();++i){std::couta[i]std::endl;}return0;}如果你真的没有接触过STL的话，你会问，呀，vector是啥呀？这是一段纯种的STL代码，看到尖括号了吧，知道那是模板了吧。看到a.push_back(5)、a.size()你不感觉奇怪么？可是我们并没有定义这些函数啊。#includevector#includeiostreamintmain(){std::vectorintq;q.push_back(10);q.push_back(11);q.push_back(12);std::vectorintv;for(inti=0;i5;++i){v.push_back(i);}std::vectorint::iteratorit=v.begin()+1;it=v.insert(it,33);v.insert(it,q.begin(),q.end());it=v.begin()+3;v.insert(it,3,-1);it=v.begin()+4;v.erase(it);it=v.begin()+1;v.erase(it,it+4);4v.clear();return0;}这一段你又看到了新东西了吧：iterator、insert、erase、clear。不罗嗦了，等你看完这篇文章，回头再看就简单了。关于模板的其他细节，读者可以参阅《C++Templates中文版》在这里，简单的介绍一下模板类和函数模板的概念。模板是C++中实现代码重用机制的一种工具，可以实现类型参数化，把类型定义为参数。函数模板和类模板允许用户构造模板函数和模板类。下面我们来看一段函数模板的例子：#includeiostream#includestringusingnamespacestd;//定义函数模板templateclassT//template是关键字，T表示一种待实例化的类型//templatetypenameT也是对的TMAX(Ta,Tb)//函数模板，函数名为max，此函数有2个T类型的参数，返回类型为T{return(ab)?a:b;}//在此例实例化的时候，T可以是多种类型的，int,char,string…intmain(){intx=2,y=6;doublex1=9.123,y1=12.6543;cout把T实例化为int:MAX(x,y)endl;//实例化函数模板，把T实例化为intcout把T实例化为double:MAX(x1,y1)endl;//把T实例化为double}下面再看看，类模板：#includeiostreamusingnamespacestd;//定义名为ex_class的类模板templatetypenameTclassex_class{Tvalue;public:ex_class(Tv){value=v;}voidset_value(Tv){value=v;}Tget_value(void){returnvalue;}};//main()函数中测试ex_class类模板5intmain(){//测试int类型数据ex_classinta(5),b(10);couta.value:a.get_value()endl;coutb.value:b.get_value()endl;//测试char类型数据ex_classcharch('A');coutch.value:ch.get_value()endl;ch.set_value('a');coutch.value:ch.get_value()endl;//测试double类型数据ex_classdoublex(5.5);coutx.value:x.get_value()endl;x.set_value(7.5);coutx.value:x.get_value()endl;}1.4STL的组成STL有三大核心部分：容器（Container）、算法（Algorithms）、迭代器（Iterator），容器适配器（containeradaptor），函数对象(functor)，除此之外还有STL其他标准组件。通俗的讲：容器：装东西的东西，装水的杯子，装咸水的大海，装人的教室……STL里的容器是可容纳一些数据的模板类。算法：就是往杯子里倒水，往大海里排污，从教室里撵人……STL里的算法，就是处理容器里面数据的方法、操作。迭代器：往杯子里倒水的水壶，排污的管道，撵人的那个物业管理人员……STL里的迭代器：遍历容器中数据的对象。对存储于容器中的数据进行处理时，迭代器能从一个成员移向另一个成员。他能按预先定义的顺序在某些容器中的成员间移动。对普通的一维数组、向量、双端队列和列表来说，迭代器是一种指针。下面让我们来看看专家是怎么说的：容器（container）：容器是数据在内存中组织的方法，例如，数组、堆栈、队列、链表或二叉树（不过这些都不是STL标准容器）。STL中的容器是一种存储T（Template）类型值的有限集合的数据结构,容器的内部实现一般是类。这些值可以是对象本身，如果数据类型T代表的是Class的话。算法（algorithm）：算法是应用在容器上以各种方法处理其内容的行为或功能。例如，有对容器内容排序、复制、检索和合并的算法。在STL中，算法是由模板函数表现的。这些函数不是容器类的成员函数。相反，它们是独立的函数。令人吃惊的特点之一就是其算法如此通用。不仅可以将其用于STL容器，而且可以用于普通的C＋＋数组或任何其他应用程序指定的容器。迭代器(iterator)：一旦选定一种容器类型和数据行为(算法)，那么剩下唯一要他做的就是用迭代器使其相互作用。可以把达代器看作一个指向容器中元素的普6通指针。可以如递增一个指针那样递增迭代器，使其依次指向容器中每一个后继的元素。迭代器是STL的一个关键部分，因为它将算法和容器连在一起。下面我将依次介绍STL的这三个主要组件。2容器STL中的容器有队列容器和关联容器，容器适配器（congtaineradapters：stack,queue，priorityqueue），位集（bit_set），串包(string_package)等等。在本文中，我将介绍list,vector，deque等队列容器，和set和multisets,map和multimaps等关联容器，一共7种基本容器类。队列容器（顺序容器）：队列容器按照线性排列来存储T类型值的集合，队列的每个成员都有自