第14章标准模板库

1、1第第14章章 标准模板库标准模板库C+语言程序设计中山大学信息科学与技术学院2主要内容nSTL（Standard Template Library）n迭代器n容器n泛型算法31、STLn容器（container）：包含数据的数据结构n元素n栈、链表n迭代器（iterator）：相当于指向元素对象的指针n算法（algorithm）：在各种容器中通用的标准算法n排序，插入42、迭代器n指针的抽象，一般化的指针n标准库迭代器类别n输入迭代器n输出迭代器n正向迭代器n双向迭代器n随机访问迭代器所支持的操作不同（P371 表14-1）52、迭代器（续）n不同类型容器中定义的迭代器属于不同的类别nvec

2、tor容器和deque容器的迭代器是随机访问迭代器nlist容器的迭代器是双向迭代器n关联容器的迭代器是双向迭代器n容器适配器不支持迭代器n算法对作为参数的迭代器的类别要求63、容器n顺序容器（sequential container ）n按位置存储和访问元素n关联容器（associative container ）n元素按键（关键字）排序n容器适配器（container adaptor ）n使某种容器以另一种抽象类型的方式工作容器元素必须支持复制和赋值操作73、容器（续）n顺序容器nvectorn在尾端插入和删除 n支持随机访问 nListn双链表，可在任意位置快速插入和删除 nDequen

3、双端队列n在头端和尾端快速插入和删除n支持随机访问 83、容器（续）n顺序容器（续）n容器对象的定义及初始化(P371 表14-3)nC c; nC c(cx); nC c(b, e); nC c(n, t); nC c(n); 93、容器（续）n顺序容器（续）n容器中定义的类型别名(P373 表14-4)niterator nsize_type nconst_iterator nreverse_iterator nconst_reverse_iterator ndifference_type nvalue_type nreference nconst_reference 103、容器（续）n

4、顺序容器（续）n元素访问操作(P374 表14-5)nc.back() nc.front() ncindex nc.at(index) list无若index无效，则at操作会抛出out_of_range异常113、容器（续）n顺序容器（续）n获取迭代器的操作(P375 表14-6)nc.begin() nc.end() nc.rbegin() nc.rend 注：const容器对象的对应迭代器为const_迭代器（只读迭代器）123、容器（续）n顺序容器（续）n增加元素的操作(P376 表14-7)nc.insert(iter, t) nc.insert(iter, n, t) nc.ins

5、ert(iter, b, e) nc.push_back(t) nc.push_front(t) 在iter所指元素前插入vector无133、容器（续）n顺序容器（续）n删除元素的操作(P378 表14-8)nc.clear() nc.erase(iter) nc.erase(b, e) nc.pop_back() nc.pop_front(t) vector无143、容器（续）n顺序容器（续）n容器比较操作(P380 表14-9)n= n!= n nn= 结果取决于第一对不相等的对应元素153、容器（续）n顺序容器（续）n容器大小相关操作(P382 表14-10)nc.empty() nc

6、.size() nc.max_size() nc.resize(n) nc.resize(n, t) 163、容器（续）n顺序容器（续）n容器的赋值与交换(P383 表14-11)nc1 = c2 nc.assign(b, e) nc.assign(n, t) nc1.swap(c2) 不移动元素先删除，再复制插入173、容器（续）n关联容器n特点：通过键对元素进行存储和访问n标准库关联容器nmapnmultimapnsetnmultiset元素类型为pair类型（键-值对）以键本身为元素183、容器（续）n关联容器（续）npair类型n中定义的模板类n具有两个公有成员：first和secon

7、dn创建pair对象npair p npair p(v1, v2) nmake_pair(v1, v2) n比较pair对象nn=标准库函数193、容器（续）n关联容器（续）nmap容器nmap对象的定义及初始化 nmap m; nmap m(mx); nmap m(b, e); nmap容器中定义的类型别名n表14-4nkey_typenmapped_typenvalue_typepair类型类型K必须提供操作203、容器（续）n关联容器（续）nmap容器（续）n访问元素 n使用下标n下标类型与键类型相同n副作用：导致增加新元素 n使用迭代器 213、容器（续）n关联容器（续）nmap容器（

8、续）n增加元素 n使用下标n使用insert操作 nm.insert(e) nm.insert(iter, e)nm.insert(begin, end) 键已存在，则不插入223、容器（续）n关联容器（续）nmap容器（续）n查找元素 nm.find(k)-返回指向k对应元素的迭代器nm.count(k) -返回k在m中出现的次数n删除元素nm.erase(k) nm.erase(iter) nm.erase(b, e) 233、容器（续）n关联容器（续）nmultimap容器（续）n键可以重复n注意与map容器的操作区别nm.lower_bound(k) nm.upper_bound(k)

9、 nm.equal_range(k) k不存在，则返回指向插入位置的迭代器243、容器（续）n关联容器（续）nset容器n元素不是pair对象，而是键本身n不支持下标操作nmultiset容器n键可以重复n注意与set容器的操作区别k不存在，则返回指向插入位置的迭代器254、容器适配器n基于顺序容器实现nstacknqueuenpriority_dequen可根据基础容器创建对象并初始化nA a(c)默认用deque实现默认用vector实现基础容器对象适配器类型264、容器适配器（续）nstack典型操作npush(item)npop()ntop()nempty()nsize()274、容器

10、适配器（续）nqueue典型操作npush(item)npop()nfront()nback()nempty()nsize()284、容器适配器（续）npriority_queue典型操作npush(item)npop()ntop()nempty()nsize()29例bool palindrome(const string& text) / 功能：判断文本text是否为回文/ 后置条件：若text为回文，则返回值为true；否则返回值为false stack cstack;size_t length = text.size();for (size_t i = 0; i length/

11、2; i+) / 文本text的前半部分入栈cstack.push(texti);/ 将文本text的后半部分逐个字符与前半部分的对应字符进行比较size_t comparePos;/ 比较位置/ 设定比较起点if (length % 2 = 0)comparePos = length / 2;elsecomparePos = length / 2 + 1;while (!cstack.empty() if (textcomparePos != cstack.top() / 对应字符不相同break;cstack.pop();/ 对应字符出栈comparePos+;/ 比较位置后移一个字符if

12、 (cstack.empty()/ 所有对应字符都相同return true;elsereturn false;305、泛型算法n作用n对容器中的元素进行某些一般性处理n特点n与具体容器类型无关n一般不依赖于元素类型n要求元素类型支持比较操作315、泛型算法（续）n分类n不修改序列的算法（non-modifying sequence algorithm）n变更序列的算法（mutating-sequence algorithm） n排序及相关算法（sorting and related algorithm） n泛化算术算法（generalized numeric algorithm） 325、泛

13、型算法（续）n形参规范nalg (first, last, otherParms);nalg (first, last, result, otherParms);nalg (first, last, first2, otherParms);nalg (first, last, first2, last2, otherParms);迭代器迭代器 valuecomp(比较函数)pred(测试函数)宜使用插入迭代器335、泛型算法（续）n使用插入迭代器调用算法 n标准库插入迭代器类型ninsert_iterator 调用容器的insertnfront_insert_iterator 调用容器的pus

14、h_frontnback_insert_iterator 调用容器的push_backn创建插入迭代器的标准库函数ninserter nfront_inserter nback_inserter 接受一个容器参数和一个指向插入起始位置的迭代器 例：P406，CoustomerManager:find的实现无须考虑目标容器的容量345、泛型算法（续）n使用函数对象调用算法 n函数对象n是类对象n该类重载了函数调用操作符()n() 的形参个数与算法要求其pred形参所带的形参个数一样n需要增加的其他参数以类的数据成员的形式存在例：P403:class NoMatch及P406：CoustomerM

15、anager:find的实现突破算法对形参pred的参数限制35class BetweenCls public:BetweenCls(int ival1, int ival2): lowerBound(ival1), upperBound(ival2)bool operator() (const int& ival)/重载函数调用操作符return (ival lowerBound & ival upperBound);private:int lowerBound, upperBound;例使用形式：count_if(ivec.begin(), ivec.end(), BetweenCls(3, 5);count_if(ivec2.begin(), ivec2.end(), BetweenCls(8, 13)