《标准模板库分析课件》由会员分享，可在线阅读，更多相关《标准模板库分析课件（37页珍藏版）》请在金锄头文库上搜索。
1、标准模板库标准模板库vectorbegin()end()sort()containerscontainersalgorithmsalgorithmsiteratorsiterators(STL)class librariesclass librariesfunction librariesfunction librariesclassclasstemplatestemplatesclassesclassesfunctionfunctiontemplatestemplatesdata typesdata typesuser-defineduser-defined(enums, structs,
2、etc.)(enums, structs, etc.) Data Data + + Algorithms Algorithms = = Programs Programsoverloadedoverloadedfunctionsfunctionsspecific functionsspecific functionsinline Codeinline CodeFig 1 The Evolution of Reusability/GenericityFig 1 The Evolution of Reusability/Genericity主要内容标准模板库（STL）容器顺序容器：vector,
3、list, deque关联容器：set， map迭代器iteratorconst_iterator算法排序算法：sort()等查找对象算法：find() , count()等等STL简介STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C+程序库。它被容纳于C+标准程序库（C+ Standard Library）中，是ANSI/ISO C+标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C+程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。C+标准库STL的三个关键组件一
4、个STL容器是对象的集合，STL容器包括vector、deque、list、set 、map 、 stack和queue等。一个STL容器是一个数据结构。STL算法是对容器进行处理的函数，例如copy、sort、search、merge等。一个STL算法是处理数据结构的函数。STL迭代器是访问容器中对象的一种机制，一次访问一个对象。在任何情况下，STL算法都用迭代器来处理STL容器。迭代器迭代器容器容器算法算法容器概览顺序容器 sequence containersvector： 从后面快速的插入与删除，直接访问任何元素deque ：从前面或后面快速的插入与删除，直接访问任何元素 list ：
5、双链表，从任何地方快速插入与删除 关联容器 associative containersset ：快速查找，不允许重复值multiset： 快速查找，允许重复值 map ：一对一映射，基于关键字快速查找，不允许重复值multimap ：一对多映射，基于关键字快速查找，允许重复值 容器适配器 container adaptersstack： 后进先出 queue：先进先出 priority_queue ：最高优先级元素总是第一个出列标准库容器的头文件这些头文件的内容都在std名字空间域中，程序中必须加以说明。 头文件头文件说明说明两端队两端队deque的头文件的头文件表表list的头文件的头文件
6、映射映射map和多重映射和多重映射multimap的头文件的头文件集合集合set和多重集合和多重集合multimap的头文件的头文件队队queue和优先级队列和优先级队列priority_queue的头文件的头文件栈栈stack的头文件的头文件向量向量vector的头文件的头文件容器内定义的类型别名 所有容器内部都提供了下列类型别名：size_type 无符号类型，足以存储此容器类型的最大可能容器长度 iterator 此容器类型的迭代器类型 value_type 元素类型 容器小结初始化C c；创建一个名为c的空容器C c(c2); 创建c2的副本cC c(b,e); 创建c，其元素是迭代器
7、b和e标示范围内元素的副本C c(n,t); 用n个值为t的元素创建容器c，只适用于顺序容器C c(n); 创建有n个值初始化元素的容器c，只适用于顺序容器容器元素类型必须满足以下两个约束：元素类型必须支持赋值运算；元素类型的对象必须可以复制；VECTOR顺序容器vector类提供了具有连续内存地址的数据结构。通过下标运算符 直接有效地访问vector的任何元素。与数组不同， vector的内存用尽时， vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是 vector 类的优点。在这里内存分配是由分配子（allocator）完成。 vector可以用来实
8、现堆栈等其他更复杂的结构。vector支持随机访问迭代器所有的STL算法都可以用于vector。vector的迭代器通常实现为一个指向vector元素的指针。OperationsConstructors: vector v, / empty vector v1(100), / contains 100 elements of type T v2(100, val), / contains 100 copies of val v3(fptr,lptr); / contains copies of elements in / memory locations fptr up to lptrCopy
9、 constructorDestructorv.size()Number of elements v actually containsv.empty()Check if v is emptyv.push_back(val)Add val at end vi, , v.at(i)i-th value without / with range checking(at throws out-of-range exception )Relational operatorsLexicographic order is usedAssignment (=)e.g., v1 = v2;v.swap(v1)
10、Swap contents with those of vector v1 练习：使用VECTOR作为STACK的数据成员#include using namespace std;templateclass Stack/* Function Members */public: Stack() ; / let vectors constructor do the work bool empty() const; void push(const StackElement & value); void display(ostream & out) const; StackElement top()
11、const; void pop();/* Data Members */private: vector myVector; / vector to store elements / dont need myTop - back of vector is top of stack; / end of class declaration迭代器/迭代子（ITERATOR）概览迭代器是面向对象版本的指针。迭代器保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代器。迭代器用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代器来对这些
12、模板实例化。迭代器可以包括指针，但又不仅是一个指针。迭代器是一种检查容器内元素并遍历元素的数据类型每种标准容器都定义了迭代器类型现代C+程序更倾向于使用迭代器而不是下标访问容器元素迭代器操作迭代器操作定义 vector:iterator iter;begin和end操作 vector:iterator iter=ivec.begin();迭代器指向第一个元素end操作返回的迭代器指向末端元素的下一个vector迭代器的自增和解引用运算：iter+, *iter比较：=, !=迭代器举例要求：using iteraotrs to seset all the elements in ivec to
13、 0for (vector:iterator iter = ivec.begin(); iter != ivec.end(); +iter) *iter = 0;const_iterator上面的代码vector:iterator改变vector中的元素值每种容器类型还定义了一种名为const_iterator的类型，该类型只能用于读取容器内元素，不能改变其值。举例：for (vector:const_iterator iter = text.begin(); iter != text.end(); +iter) cout*iter endl;练习：Read words from the st
14、andard input and store as elements in a vector #include #include#includeusing namespace std;int main(int argc, const char * argv) vector svec; string data; vector:iterator it; while (cindata) svec.push_back(data); for (it=svec.begin(); it!=svec.end(); it+) cout*itendl; return 0;顺序容器小结BEGIN和ENDc.begi
15、n() 返回一个迭代器，指向容器c的第一个元素c.end() 返回一个迭代器，指向容器c的最后一个元素的下一位置c.rbegin() 返回一个逆序迭代器，指向容器c的最后一个元素c.rend() 返回一个逆序迭代器，指向容器c的第一个元素前面的位置顺序容器小结添加元素c.push_back(t) 在容器c的尾部添加值为t的元素，返回void 类型c.push_front(t)在容器c的前端添加值为t的元素，返回void类型只适用于list和deque容器类型c.insert(p,t)在迭代器p所指的元素前插入值为t的新元素，返回指向新添加元素的迭代器c.insert(p,n,t)在迭代器p所指
16、向的元素前面插入n个值为t的新元素，返回void类型c.insert(p,b,e)在迭代器p所指向的元素前面插入由迭代器b和e标记的范围内的元素，返回void顺序容器小结容器大小的操作c.size() 返回容器c中的元素个数，类型为c:size_typec.max_size()返回容器c可容纳的最多元素个数c.empty()返回容器大小是否为0的布尔值c.resize(n)调整容器c的大小，使其能容纳n个元素c.resize(n,t)调整容器c的大小，使其能容纳n个元素，所有新添加元素值为t顺序容器小结访问元素c.back()返回容器c最后一个元素的引用c.front()返回容器c第一个元素的
17、引用cn返回下标为n的元素引用只适用于vector和deque容器c.at(n)返回下标为n的元素的引用只适用于vector和deque容器顺序容器小结删除元素c.erase(p)删除迭代器p所指向的元素，返回一个迭代器，指向被删除元素后面的元素。c.erase(b,e)删除迭代器b和e所标记的范围内所有元素c.clear()删除容器c内的所有元素，返回voidc.pop_back()删除容器c的最后一个元素，返回void。c.pop_front()删除容器c的第一个元素，返回void。只适用于list和deque容器顺序容器小结赋值与SWAPc1=c2删除容器c1的所有元素，然后将c2的元素
18、复制给c1。c1和c2的类型（包括容器类型和元素类型）必须相同。c1.swap(c2)交换容器c1和c2内容。c.assign(b,e)重新设置c的元素：将迭代器b和e标记范围内的所有元素复制到c中。b和e不是指向c中元素的迭代器c.assign(n,t)将容器c重新设置为存储n个值为t的元素容器的选择选择容器类型的法则：1.如果程序要求随机访问元素，使用vector或deque容器2.如果程序必须在容器中间位置插入删除元素，采用list容器3.如果程序不在容器中间位置，而是在容器首部或尾部插入或删除元素，使用deque容器。4.如果需要读取输入时在容器中间位置插入元素，然后要求随机访问元素。
19、可以在输入时读入到一个list容器，然后对其排序，再复制到一个vector容器。提示：通常来说，除非找到选择使用其他容器的更好理由，否则vector容器都是最佳选择容器适配器适配器(adaptor) 是标准库中通用的概念容器适配器：让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。举例：stack适配器可使任何一种顺序容器以栈的方式工作三种顺序容器适配器：queue, priority_queue , stack使用适配器时，包含相关头文件#include , #include容器适配器的基础容器类型stack栈可以建立在vector,list或deque容器上，默认是deque容
20、器。queue适配器要求关联的容器提供push_front运算，不能建立在vector 容器上，默认是基于deque容器实现priority_queue要求提供随机访问功能，可建立在vector和deque容器上，默认基于vector 容器实现适配器的初始化stack stk; / 空对象stack stk2(deq); /用参数容器的副本初始化栈stackstring,vector str_stk; / empty stack implemented on top of vectorstackstring, vector str_stk2(svec); /str_stk2 is implem
21、ented on top of vector and holds a copy of svec栈适配器举例栈支持的操作int main() const stack:size_type stk_size=10; stack intStack; int ix=0; while(intStack.size()!= stk_size) intStack.push(ix+); int error_cnt = 0; while(intStack.empty()=false) int value=intStack.top(); if(value!= -ix) cerroops!expected ix rec
22、eived valueendl; +error_cnt; else coutvalue ; intStack.pop(); coutOur program ran with error_cnt errors!endl;9 8 7 6 5 4 3 2 1 0 Our program ran with 0 errors!关联容器pair类型简单标准库类型，在utility头文件中定义关联容器：通过键key存储和读取元素map类型适合存储每个键所关联的值例如：字典，单词本身是键，它的解释说明是值set类型：存储不同值的集合例如：做文本处理时，用set保存要忽略的单词PAIR类型提供的操作pair p
23、1 创建一个空的pair对象，两个元素分别是T1和T2类型，采用初始化值pair p1(v1,v2) 其中first成员初始化为v1,second成员初始化为v2make_pair(v1,v2) 以v1和v2值创建一个新的pair对象p1p2 两个pair对象之间的小于运算，遵循字典次序p1=p2 若两个pair对象的first和second成员依次相等，则两对象相等p.first 返回p中名为first的（公有）数据成员p.second 返回p中名为second的（公有）数据成员关联容器关联容器操作关联容器共享大部分顺序容器的操作但不提供front ,push_front ,pop_fron
24、t , back , push_back , pop_back操作关联容器特点 关联容器根据键排列元素 即在迭代遍历关联容器时，确保按键的顺序访问元素，而与元素在容器中存放位置完全无关。MAP类型键值对集合map定义的类型map:key_type 用作索引的键的类型map:mapped_type 键所关联的值的类型map: value_type 一个pair类型，它的first元素具有const map:key_type类型，而second元素则为map:mapped_type类型程序举例：“单词转换”map对象问题：给出一个string对象，把它转换为另一个string对象程序输入：两个文件
25、，第一个文件是单词转换集合，第二个文件提供了需要转换的文本程序举例如果单词转换内容为：am them cuz because gratz grateful iI nahno possupposed sez said tanxthanks wuz was要转换的文本是 nah i sez tanx cuz i wuz pos to not cuz i wuz gratz程序产生的输出结果 no I said thanks because I was supposed to not because I was grateful单词转换程序解决方案：将单词转换文件的内容存储在一个map容器中，将被替
26、换的单词作为键，而用作替换的单词作为相应的值。接着读取输入，查找输入的每个单词是否对应有转换。若有，则转换，输出转换后的值，否则，输出原词。步骤1: 读入文件，单词转换文件及需要转换的文件int main(int argc, char *argv) map trans_map;/map to hold the word transformation pairs string key,value; if(argc!=3) cerrwrong number of arguments”; exit(0); ifstream map_file; if(!open_file(map_file,argv1
27、) cerrkeyvalue) trans_map.insert(make_pair(key,value); ifstream input; if(!open_file(input,argv2) cerrword) /the actual mapwork ,this part is the heart of the program map:const_iterator map_it=trans_map.find(word); /if this word is in the transformation map if(map_it!=trans_map.end() word=map_it-sec
28、ond;/replace it by the transformation value in the map if(firstword) firstword=false; else cout ;/print space between words coutword; coutendl; return 0 ;相关头文件及文件打开函数#include#include#include#include#includeusing namespace std;ifstream& open_file(ifstream &in, const string &file) in.close(); in.clear
29、(); in.open(file.c_str(); return in;算法概览STL最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。STL提供70种左右的标准算法。算法只是间接通过迭代子操作容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（generic algorithm）。算法分为：修改容器的算法，即变化序列算法（mutating-sequence algorithm），如copy()、remove()、replace()、swap()等。不修改容器的算法，即非变化序列算法（non-mutating-sequence algorithm），如count()、find()等。数字型算法。
