C++-STL详解

西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaACM/ICPC程序设计C++标准模板库C++StandardTemplateLibarary计算机学院万波西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,China主要内容STL概述：组件、容器、迭代器（iterator）、算法STL容器：常用容器：vector、deque、list、map/multimap、set特殊容器：stack、queue，priority_queue其他容器：hashtableSTL算法：搜寻、排序、拷贝、数值运算西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL是C++标准程序库的核心，深刻影响了标准程序库的整体结构STL是泛型（generic）程序库，利用先进、高效的算法来管理数据STL由一些可适应不同需求的集合类（collectionclass），以及在这些数据集合上操作的算法（algorithm）构成STL内的所有组件都由模板（template）构成，其元素可以是任意类型STL是所有C++编译器和所有操作系统平台都支持的一种库西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述//普通C++代码#includeiostreamintmain(void){doublea[]={1,2,3,4,5};std::coutmean(a,5);std::coutstd::endl;return0;}//使用了STL的代码#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;}西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述//使用了STL的代码#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);v.clear();return0;西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述模板（template）函数模板针对一个或多个尚未明确的类型所撰写的函数或类#includeiostream#includestringusingnamespacestd;//定义函数模板templatetypenameTTMAX(Ta,Tb){return(ab)?a:b;}intmain(){intx=2,y=6;doublex1=9.123,y1=12.6543;coutMAX(x,y)endl;coutMAX(x1,y1)endl;}西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述模板（template）类模板针对一个或多个尚未明确的类型所撰写的函数或类#includeiostreamusingnamespacestd;//定义名为ex_class的类模板templatetypenameTclassex_class{Tvalue;public:ex_class(Tv){value=v;}voidset_value(Tv){value=v;}Tget_value(void){returnvalue;}};intmain(){//测试char类型数据ex_classcharch('A');coutch.value:ch.get_value()endl;ch.set_value('a');coutch.value:ch.get_value()endl;//测试double类型数据ex_classdoubled(5.5);cout“d.value:d.get_value()endl;x.set_value(7.5);cout“d.value:x.get_value()endl;}西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL组件容器（Container）－管理某类对象的集合迭代器（Iterator）－在对象集合上进行遍历算法（Algorithm）－处理集合内的元素容器适配器（containeradaptor）函数对象(functor)容器Container容器Container容器Container算法Algorithm迭代器Iterator迭代器Iterator迭代器IteratorSTL组件之间的协作西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL容器类别序列式容器－排列次序取决于插入时机和位置关联式容器－排列顺序取决于特定准则listdequevector序列式容器mapset关联式容器西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL容器的共通能力所有容器中存放的都是值而非引用，即容器进行安插操作时内部实施的是拷贝操作。因此容器的每个元素必须能够被拷贝。如果希望存放的不是副本，容器元素只能是指针。所有元素都形成一个次序（order），可以按相同的次序一次或多次遍历每个元素各项操作并非绝对安全，调用者必须确保传给操作函数的参数符合需求，否则会导致未定义的行为西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL容器元素的条件必须能够通过拷贝构造函数进行复制必须可以通过赋值运算符完成赋值操作必须可以通过析构函数完称销毁动作序列式容器元素的默认构造函数必须可用某些动作必须定义operator==，例如搜寻操作关联式容器必须定义出排序准则，默认情况是重载operator对于基本数据类型（int,long,char,double,…）而言，以上条件总是满足西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL容器的共通操作初始化（initialization）产生一个空容器以另一个容器元素为初值完成初始化以数组元素为初值完成初始化std::listintl;…std::vectorfloatc(l.begin(),l.end());intarray[]={2,4,6,1345};…std::setintc(array,array+sizeof(array)/sizeof(array[0]));std::listintl;西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL容器的共通操作与大小相关的操作（sizeoperator）size()－返回当前容器的元素数量empty()－判断容器是否为空max_size()－返回容器能容纳的最大元素数量比较（comparison）==,!=,,=,,=比较操作两端的容器必须属于同一类型如果两个容器内的所有元素按序相等，那么这两个容器相等采用字典式顺序判断某个容器是否小于另一个容器西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述STL容器的共通操作赋值（assignment）和交换（swap）swap用于提高赋值操作效率与迭代器（iterator）相关的操作begin()－返回一个迭代器，指向第一个元素end()－返回一个迭代器，指向最后一个元素之后rbegin()－返回一个逆向迭代器，指向逆向遍历的第一个元素rend()－返回一个逆向迭代器，指向逆向遍历的最后一个元素之后西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述容器的共通操作元素操作insert(pos,e)－将元素e的拷贝安插于迭代器pos所指的位置erase(beg,end)－移除[beg，end]区间内的所有元素clear()－移除所有元素西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述迭代器（iterator）（示例:iterator）可遍历STL容器内全部或部分元素的对象指出容器中的一个特定位置迭代器的基本操作操作效果*返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以operator-取用++将迭代器前进至下一元素==和!=判断两个迭代器是否指向同一位置=为迭代器赋值（将所指元素的位置赋值过去）西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述迭代器（iterator）所有容器都提供获得迭代器的函数操作效果begin()返回一个迭代器，指向第一个元素end()返回一个迭代器，指向最后一个元素之后begin()end()半开区间[beg,end)的好处：1.为遍历元素时循环的结束时机提供了简单的判断依据（只要未到达end()，循环就可以继续）2.不必对空区间采取特殊处理（空区间的begin()就等于end()）西安电子科技大学计算机学院-SchoolofComputerScience&Engineering,XidianUniversity,ChinaSTL概述迭代器（iterator）所有容器都提供两种迭代器container::iterator以“读/写”模式遍历元素container::const_iterator以“只读”模式遍历元