5、泛型程序设计与C 标准模板库资料

C++标准模板库提高篇提高篇主要内容泛型程序设计与标准模板库有关的概念和术语C++标准模板库中的容器迭代器标准C++库中的算法函数对象2提高篇泛型程序设计将程序写得尽可能通用将算法从特定的数据结构中抽象出来，成为通用的C++的模板为泛型程序设计奠定了关键的基础STL是泛型程序设计的一个范例–容器(container)–迭代器(iterator)–算法（algorithms）–函数对象（functionobject）3提高篇STL组件之间的关系4提高篇示例5提高篇示例6提高篇容器容器类是容纳、包含一组元素或元素集合的对象。七种基本容器：–向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）分类：序列（顺序）容器，关联容器，容器适配器7概念和术语提高篇容器分类标准容器类说明1、顺序性容器vector从后面快速的插入与删除，直接访问任何元素deque从前面或后面快速的插入与删除，直接访问任何元素list双链表，从任何地方快速插入与删除2、关联容器set快速查找，不允许重复值multiset快速查找，允许重复值map一对多映射，基于关键字快速查找，不允许重复值multimap一对多映射，基于关键字快速查找，允许重复值3、容器适配器stack后进先出queue先进先出priority_queue最高优先级元素总是第一个出列8提高篇所有容器共有函数默认构造函数提供容器默认初始化的构造函数。复制构造函数将容器初始化为现有同类容器副本的构造函数析构函数不再需要容器时进行内存整理的析构函数empty()容器中没有元素时返回true,否则返回falsemax_size()返回容器中最大元素个数size()返回容器中当前元素个数=将一个容器赋给另一个容器如果第一个容器小于第二个容器，返回true，否则返回false，=如果第一个容器小于或等于第二个容器，返回true，否则返回false如果第一个容器大于第二个容器，返回true，否则返回false=如果第一个容器大于或等于第二个容器，返回true，否则返回false==如果第一个容器等于第二个容器，返回true，否则返回false相同的含义：容量相同，所有位置值相同。!=如果第一个容器不等于第二个容器，返回true，否则返回falseSwap()交换两个容器的元素9提高篇顺序容器和关联容器共有函数begin()该函数两个版本返回iterator或const_iterator，引用容器第一个元素end()该函数两个版本返回iterator或const_iterator,引用容器最后一个元素后面一位rbegin()该函数两个版本返回reverse_iterator或const_reverse_iterator,引用容器最后一个元素rend()该函数两个版本返回reverse_iterator或const_reverse_iterator，引用容器第一个元素前面一位erase()从容器中清除一个或几个元素clear()清除容器中所有元素10提高篇适配器适配器是一种接口类–为已有的类提供新的接口。–目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合。三种类型的适配器：–容器适配器用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器–迭代器适配器–函数对象适配器。11概念和术语提高篇迭代器迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方法。实际上指针也是一种迭代器。很多容器提供了类似current（）的成员函数，返回迭代器指向的元素的地址或引用。类似于指针，迭代器可以调用next（），previous（）进行遍历。12概念和术语提高篇算法C++标准模板库中包括70多个算法–其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等。这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型。13概念和术语提高篇顺序容器顺序容器的接口–插入方法push_front()，push_back()，insert()，运算符“=”–删除方法pop()，erase()，clear()–迭代访问方法使用迭代器–其他顺序容器访问方法（不修改访问方法）front()，back()，下标[]运算符14容器提高篇顺序容器——向量向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。例1–求范围2~N中的质数，N在程序运行时由键盘输入。15容器提高篇向量的函数-1向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。16容器函数表述c.assign(beg,end)c.assign(n,elem)将[beg;end)区间中的数据赋值给c。将n个elem的拷贝赋值给c。c.at(idx)传回索引idx所指的数据，如果idx越界，抛出out_of_range。c.back()传回最后一个数据，不检查这个数据是否存在。c.begin()传回迭代器重的可一个数据。c.capacity()返回容器中数据个数。c.clear()移除容器中所有数据。提高篇向量的函数-2向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。17容器函数表述c.empty()判断容器是否为空。c.end()指向迭代器中的最后一个数据地址。c.erase(pos)c.erase(beg,end)删除pos位置的数据，传回下一个数据的位置。删除[beg,end)区间的数据，传回下一个数据的位置。c.front()传回第一个数据。get_allocator使用构造函数返回一个拷贝。c.insert(pos,elem)c.insert(pos,n,elem)c.insert(pos,beg,end)在pos位置插入一个elem拷贝，传回新数据位置。在pos位置插入n个elem数据。无返回值。在pos位置插入在[beg,end)区间的数据。无返回值。c.max_size()返回容器中最大数据的数量。提高篇向量的函数-3向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。18容器函数表述c.pop_back()删除最后一个数据。c.push_back(elem)在尾部加入一个数据。c.rbegin()传回一个逆向队列的第一个数据。c.rend()传回一个逆向队列的最后一个数据的下一个位置。c.resize(num)重新指定队列的长度。c.reserve()保留适当的容量。c.size()返回容器中实际数据的个数。c1.swap(c2)swap(c1,c2)将c1和c2元素互换。同上操作。vectorElemcvectorElemc1(c2)vectorElemc(n)vectorElemc(n,elem)vectorElemc(beg,end)c.~vectorElem()创建一个空的vector。复制一个vector。创建一个vector，含有n个数据，数据均已缺省构造产生。创建一个含有n个elem拷贝的vector。创建一个以[beg;end)区间的vector。销毁所有数据，释放内存。提高篇向量的函数-3向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。19容器函数表述c.pop_back()删除最后一个数据。c.push_back(elem)在尾部加入一个数据。c.rbegin()传回一个逆向队列的第一个数据。c.rend()传回一个逆向队列的最后一个数据的下一个位置。c.resize(num)重新指定队列的长度。c.reserve()保留适当的容量。c.size()返回容器中实际数据的个数。c1.swap(c2)swap(c1,c2)将c1和c2元素互换。同上操作。vectorElemcvectorElemc1(c2)vectorElemc(n)vectorElemc(n,elem)vectorElemc(beg,end)c.~vectorElem()创建一个空的vector。复制一个vector。创建一个vector，含有n个数据，数据均已缺省构造产生。创建一个含有n个elem拷贝的vector。创建一个以[beg;end)区间的vector。销毁所有数据，释放内存。提高篇向量操作20函数描述operator[]返回容器中指定位置的一个引用。//1.cpp#includeiostream#includeiomanip#includevector//包含向量容器头文件usingnamespacestd;intmain(){vectorintA(10);intn;intprimecount=0,i,j;coutEnteravalue=2asupperlimit:;cinn;A[primecount++]=2;21例：求范围2-N中的质数，N在运行时有键盘输入。for(i=3;in;i++){if(primecount==A.size())A.resize(primecount+10);if(i%2==0)continue;j=3;while(j=i/2&&i%j!=0)j+=2;if(ji/2)A[primecount++]=i;}for(i=0;iprimecount;i++)//输出质数{coutsetw(5)A[i];if((i+1)%10==0)//每输出10个数换行一次coutendl;}coutendl;}22提高篇顺序容器——双端队列双端队列是一种放松了访问权限的队列。元素可以从队列的两端入队和出队，也支持通过下标操作符“[]”进行直接访问。例2–使用双端队列容器保存双精度数值序列23容器提高篇24//2.cpp#includeiostream#includedeque//包含双端队列容器头文件#includealgorithm//包含算法头文件usingnamespacestd;intmain(){dequedoublevalues;//声明一个双精度型deque序列容器ostream_iteratordoubleoutput(cout,);values.push_front(2.2);//应用函数push_front在deque容器开头插入元素values.push_front(3.5);values.push_back(1.1);//应用函数push_back在deque容器结尾插入元素coutvaluescontains:;提高篇25for(inti=0;ivalues.size();++i)coutvalues[i]'';values.pop_front();//应用函数push_front从deque容器中删除第一个元素cout\nAfterpop_frontvaluescontains:;copy(values.begin(),values.end(),output);values[1]=5.4;//应用操作符[]来重新赋值cout\nAftervalues[1]=5.4valuescontains:;copy(values.begin(),values.end(),output);couten