第 8 章 标准模板库STL 陈哲 副教授 南京航空航天大学 计算机科学与技术学院

8.1 标准模板库简介 重要性：学好本章将为“数据结构” 打下坚实的基础。 8.1 标准模板库简介 STL（Standard Template Library）标准模板库是一个高效的C++程序库，它是C++标准中极具特色的一部分。 为广大程序员们提供了一个可扩展的应用框架，体现了软件的可复用性。体现了泛型程序设计的思想。 重要性：学好本章将为“数据结构” 打下坚实的基础。

8.2 The C++ string Class C++ provides two ways of storing and working with strings. One method is to store them as C strings in character array variables. Another way is to store them in string class object.

8.2 The C++ string Class (continued ) Using the string Class The first step : #include <string> Notice : There is no ".h“. The next step : using namespace std;

奇怪的语句 #include <iostream> #include <string> using namespace std; void main(void) { string movieTitle; movieTitle = "Wheels of Fury"; cout << movieTitle << endl; cin >> movieTitle ; cin.ignore(); getline(cin,movieTitle); } 奇怪的语句

8.2 The C++ string Class (continued ) Comparing string Objects : use the <, >, <=, >=, ==, and != relational operators. For example: string set1 = "ABC"; string set2 = "XYZ"; if ( set1 < set2 ) cout << "set1 is less than set2.\n";

8.2 The C++ string Class (continued ) Other Ways to Declare string Objects: 1. string address; Declares an empty string object. 2. string name("Zhang San"); 3. string personl(person2); person2 : a string object or character array.

8.2 The C++ string Class (continued ) 4. string setl(set2, 5); 采用set2的前5个字符初始化set1. 5. string lineFull( 'z', 10); initialized with 10 ' z' characters. 6. string firstName(fullName,0,7); 用fullName 从位置0开始的7个字符，初始化firstName.

8.2 The C++ string Class (continued ) The string class supports several operators： >>、<<、= 、+=、+ [ ] Implements array-subscript notation, as in name [x]. Relational operators <,>,>=,<=, == ,!= 例如：

#include <iostream> #include <string> using namespace std; void main(void) { string strl="ABC", str2="DEF", str3; str3 = strl + str2; for (int x = 0; x < str3.size( ); x++) cout << str3[x]; cout << endl; if (strl < str2) cout << "strl is less than str2\n"; else cout << "strl is not less than str2\n"; }

8.2 The C++ string Class (continued ) Some member functions: 1. s1.append(str); 2. s1.assign(str); 3. s1.at(x); 4. s1.clear( ); 5. s1.compare(str); // like strcmp(s1, str)

8.2 The C++ string Class (continued ) 6. s1.data( ); // returns a character array. 7. s1.empty( ); 8. s1.length( ); 9. s1.size( ); 10. s1.substr(x, n); 11. s1.swap(str); //swaps the contents of s1 with str.

A Case Study assume a string object contains a value such as 1084567.89  ￥1,084,567.89 例如：Program 1-47

#include <iostream> #include <string> using namespace std; void RMBFormat( string & ); void main(void) { string input; cout << "Enter a RMB amount (nnnnn.nn): "; cin >> input; RMBFormat(input); // function call cout << "Here is the amount formatted: "; cout << input << endl; }

//******************************************* // function formats the number // as a RMB amount with commas and a ￥symbol. void RMBFormat(string & currency) { int dp; dp = currency.find('.'); // Find decimal point if (dp > 3) { // Insert commas for (int x = dp - 3; x > 0; x -= 3) currency.insert(x, ","); } currency.insert(0, “￥"); // Insert RMB sign

8.3 迭代器类 C++标准库中对普通类型迭代器按照基本访问功能分类，有5种4级（输入/输出为同一级）预定义迭代器，其功能最强、最灵活的是随机访问迭代器。

迭代器类型 说 明 输入 InputIterator   输出 OutputIterator 正向 ForwardIterator 双向BidirectionalIterator 随机访问 RandomAccessIterator 从容器中读取元素。只能一次一个元素地向前移动。要重读必须从头开始。 向容器写入元素。只能一次一个元素地向前移动。如果重写，必须从头开始。 组合输入和输出迭代器的功能，并保留在容器中的位置，所以重新读/写不必从头开始。 组合正向迭代器功能与逆向移动功能（即从容器序列末尾到容器序列开头）。 能直接访问容器中的任意元素，即可向前或向后跳过任意多个元素。

标准库定义的各种迭代器可执行的操作如下表8-6。 迭代操作 说 明 说 明 所有迭代器 ++p p++ 前置自增迭代器，先++后执行。 后置自增迭代器，执行后再++。 输入迭代器 *p p=q p==q p!=q 间接引用迭代器，作为表达式的右值。 将一个迭代器赋给另一个迭代器。 比较迭代器的相等性。 比较迭代器的不等性。 输出迭代器 间接引用迭代器，作为表达式的左值。 正向迭代器 提供输入和输出迭代器的所有功能 双向迭代器 --p p-- 包含正向迭代器所有功能，又增加了： 先--后执行，称为前置自减迭代器。 先执行后-- ，称为后置自减迭代器。

迭代操作 说 明 随机访问迭代器 p+=i p-=i p+i p-i p[i] p<q p<=q p>=q p>q 说 明 随机访问迭代器 p+=i p-=i p+i p-i p[i] p<q p<=q p>=q p>q 包含双向迭代器所有功能，又增加了： 迭代器p递增i位（后移i位）（p本身变）。 迭代器p递减i位（前移i位）（p本身变）。 在p所在位置后移i位后的迭代器（迭代器p本身不变）。 在p所在位置前移i位后的迭代器（迭代器p本身不变）。 返回与p所在位置后移i位的元素引用。 如迭代器p小于q，返回true，否则返回false。小的含义是：p在q之前。 如迭代器p小于等于q，返回true，否则返回false。 如迭代器p大于等于q，返回true，否则返回false。大的含义是：p在q之后。 如迭代器p大于迭代器q，返回true，否则返回false。

P231【例8-2】 #include <algorithm> #include <iostream> using namespace std; int main() { int value, *presult, a[ ] = {33, 26, 16, 37, 3, 88}; cout<<"请输入要查找的值："; cin>>value; presult = find(a, a + 6, value); if(presult == a + 6) cout<<value<<"不存在！"<<endl; else cout<< value<<"存在，下标是："<< presult - a <<endl; return 0; }

P231【例8-2】 其中的find泛型函数的内部定义如下，在写程序时不要给出，仅仅便于读者的理解而给出： template<typename InputIterator,typename T> InputIterator find( InputIterator first, InputIterator last, const T value ) { for( ; first != last ; ++first ) if( value == *first ) return first; return last; }

8.4 顺序容器 STL提供了3种顺序容器：vector、list和deque。表8-7给出顺序容器中的共同函数。 8.4 顺序容器 STL提供了3种顺序容器：vector、list和deque。表8-7给出顺序容器中的共同函数。 assign（n, elem） 将指定元素elem的n个拷贝，添加到容器中。 assign(beg, end) 复制迭代器beg到end之间的元素。 push_back(elem) 将元素elem添加到容器。 pop_back() 删除容器尾元素。 front() 返回容器首元素。 back() 返回容器尾元素。 insert(position, elem) 将元素elem插入到容器指定的位置position处。

8.4.1 矢量类 STL提供了3种顺序容器：vector、list和deque。表8-7给出顺序容器中的共同函数。 8.4.1 矢量类 STL提供了3种顺序容器：vector、list和deque。表8-7给出顺序容器中的共同函数。 assign（n, elem） 将指定元素elem的n个拷贝，添加到容器中。 assign(beg, end) 复制迭代器beg到end之间的元素。 push_back(elem) 将元素elem添加到容器。 pop_back() 删除容器尾元素。 front() 返回容器首元素。 back() 返回容器尾元素。 insert(position, elem) 将元素elem插入到容器指定的位置position处。

【例8-3】演示vector类的应用。 #include <iostream> #include <vector> using namespace std; int main( ) { double values[] = {1, 2, 3, 4, 5, 6, 7}; int i; // values, values + 7分别指向数组第一个和最后一个元素 vector<double> dVector(values, values + 7); cout << "1. dVector中的初始内容: "; for( i = 0; i < dVector.size(); i++) cout << dVector[i] << "\t"; cout << endl;

dVector.assign(4, 1.8); //将1.8拷贝份 cout << "2. 执行assign函数后，dVector内容: "; for(i = 0; i < dVector.size(); i++) cout << dVector[i] << "\t"; cout << endl; dVector.at(0) = 64.4; //赋值向量的第一个元素为64.4 cout << "3. 执行at函数后，dVector内容: "; vector<double>::iterator itr = dVector.begin(); //将元素55和66，依次插入到首元素后的第一个位置 dVector.insert(itr + 1, 55); dVector.insert(itr + 1, 66);

cout << "4. 执行insert函数后，dVector内容: "; for(i = 0; i < dVector.size(); i++) cout << dVector[i] << "\t"; cout << endl; dVector.erase(itr + 2, itr + 4); //将itr+2到itr+4之间的个元素删除 cout << "5. 执行erase函数后，dVector内容: "; dVector.clear(); //将容器清空 return 0; }

【P237, 例8-4】vector类的高级应用。 cout<<"请输入一组整数，以Ctrl+Z结束："; istream_iterator<int> inputIterator(cin); istream_iterator<int> end_of_stream; vector<int> intVector; copy( inputIterator,end_of_stream, inserter(intVector,intVector.begin())); //输入数字 sort(intVector.begin(),intVector.end(),greater<int>());//降序 ostream_iterator<int>outputIterator(cout,"\t"); cout<<"结果为："; unique_copy(intVector.begin(),intVector.end(),outputIterator); cout<<endl;

8.4.2 列表类 list可作为双向链表实现。高效地在任意位置插入和删除。有两个指针，可以前/后移，不支持随机访问。 p238, 例8-5 8.4.2 列表类 list可作为双向链表实现。高效地在任意位置插入和删除。有两个指针，可以前/后移，不支持随机访问。 p238, 例8-5 #include <iostream> #include <list> using namespace std; int main() { int vals[] = {10, 20, 30, 40, 50 }; // 用vals至vals + 4之间元素初始化列表 list<int> intList(vals, vals + 4);

cout << "intList中的初始元素: "; list<int>::iterator p; for(p = intList.begin(); p != intList.end(); p++) cout << *p << " "; cout << endl << endl; intList.assign(2, 11); //将元素11拷贝2份加入到容器中 cout << "执行assign后，intList中内容: "; cout << endl ;

list<int>::iterator itr = intList.begin(); //插入元素55 intList.insert(itr, 55); cout << "执行insert后，intList中内容: "; for(p = intList.begin(); p != intList.end(); p++) cout << *p << " "; cout << endl ;

list<int>::iterator beg = intList.begin(); itr++; intList.erase(beg, itr); //将beg到itr之间的元素删除 cout << "执行erase后, intList中的内容: "; for(p = intList.begin(); p != intList.end(); p++) cout << *p << " "; cout << endl ; intList.clear(); //清空容器

//将元素10、20插入到列表头 intList.push_front(10); intList.push_front(20); cout << "执行插入操作后, intList中的内容: "; for(p = intList.begin(); p != intList.end(); p++) cout << *p << " "; cout << endl ; intList.pop_front(); //删除列表头元素 intList.pop_back(); //删除列尾元素 cout << "执行删除操作后, intList中的内容: ";

int val1[] = {7, 3, 1, 2}; list<int> list1(val1, val1 + 4); list1.sort(); //将列表按升序排列 cout << "按升序排列后, list1: "; for(p = list1.begin(); p != list1.end(); p++) cout << *p << " "; cout << endl ;

list<int> list2(list1); list1.merge(list2); //将列表list1、list2合并，list2变为空 cout << "合并后, list1: "; for(p = list1.begin(); p != list1.end(); p++) cout << *p << " "; cout << endl ; cout << "list2元素个数为: " << list2.size() << endl ; list1.reverse(); //将list1反转 cout << "将list1反转, list1: ";

//在列表尾部插入元素100 list1.push_back(100); cout << "在list1表尾插入元素, list1: "; for(p = list1.begin(); p != list1.end(); p++) cout << *p << " "; cout << endl ; list1.remove(7); //将列表中值为7的删除 cout << "删除值为7的元素, list1: ";

list2.assign(3, 2); //将元素2拷贝3份加入到列表list2中 cout << "执行assign后, list2: "; for(p = list2.begin(); p != list2.end(); p++) cout << *p << " "; cout << endl ; p = list2.begin(); p++; list2.splice(p, list1); //将list1的元素移到list2首元素之前，list1变为空 cout << "将列表list1中元素移到list2, list2变为: "; cout << endl; cout << "移动之后, list1中元素个数: " << list1.size() << endl;

8.4.3双端队列类 双端队列有高度的灵活性，对象既可从队首进队，也可以从队尾进队，同样也可从任一端出队，还支持通过使用下标操作符“[ ]”进行访问，即随机访问。 能实现的各种数据结构更加灵活、方便。 使用双端队列时必须包含头文件<deque>。 p241, 例8-6（见源码）

8.5 函数对象与泛型算法 STL中的算法表现为一系列的函数模板，定义在STL头文件中。 8.5 函数对象与泛型算法 STL中的算法表现为一系列的函数模板，定义在STL头文件中。 程序员可以用来实例化每一个模板函数，从而提高它们的通用性。 这些函数模板一般都使用迭代器作为它的参数和返回值。

8.5.1 函数对象 函数对象是一个类，通常仅有一个成员函数，该函数重载了函数调用操作符operator( )。该操作符封装了可实现为一个函数的所有操作。 函数对象的英文是“function object”，有人也称其为仿函数或函子，是通过对象来模仿函数。

【例8-7】函数对象的基本使用。 #include <algorithm> #include <iostream> using namespace std; struct Point { int x, y; }; //定义函数对象lessPointX用来比较两个点的X坐标值 struct lessPointX //重载函数调用操作符“()” inline bool operator()(Point a, Point b) { return(a.x < b.x); } } structLessPointX;

//定义函数fungreatPointY用来比较两个点的Y坐标值 bool fungreatPointY(Point a, Point b) { return(a.y > b.y); } int main() Point pointArray[] = {{3,4}, {1,7}, {5,4}, {2,2}, {6,6}}; int i; cout<<"初始化pointArray数组为："<<endl; for( i = 0; i < 5; i++) cout<<"{"<<pointArray[i].x<<","<<pointArray[i].y<<"}"<<"\t"; cout << endl;

//函数对象lessPointX的实例做第3个参数 sort(pointArray, pointArray + 5, structLessPointX); cout<<"按X坐标从小到大排序后的结果为："<<endl; for( i = 0; i < 5; i++) cout<<"{"<<pointArray[i].x<<","<<pointArray[i].y<<"}"<<"\t"; cout << endl; //函数fungreatPointY做第3个参数 sort(pointArray, pointArray + 5, fungreatPointY); cout<<"按Y坐标从大到小排序后的结果为："<<endl; return 0; }

自学：【例8-8】预定义函数对象的应用举例。

8.5.2 泛型算法 思想：将一些通用函数实现为能适用于不同容器乃至数组的通用算法，如STL 的做法。 8.5.2 泛型算法 思想：将一些通用函数实现为能适用于不同容器乃至数组的通用算法，如STL 的做法。 _if后缀：表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如find_if算法表示查找一些值满足函数指定条件的元素，而find查找特定的值。 _copy后缀：表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。例如replace算法将序列中等于特定值的所有元素的值改为另一特定值，而replace_copy算法同时把结果复制到目标范围中。 应用举例：P249, 【例8-9】

8.6.1 集合和多重集合类 集合和多重集合提供了控制数值集合的操作，其中数值就是关键字，即不必另有一组值与每个关键字相关联。 8.6.1 集合和多重集合类 集合和多重集合提供了控制数值集合的操作，其中数值就是关键字，即不必另有一组值与每个关键字相关联。 集合与多重集合的主要区别在于多重集合允许重复的关键字，而集合不允许有重复的关键字，它们都在头文件<set>中定义。 例：P251，【例8-10】

8.6.2 映射和多重映射类 映射和多重映射类提供了操作与关键字相关联的映射值的方法。 8.6.2 映射和多重映射类 映射和多重映射类提供了操作与关键字相关联的映射值的方法。 映射和多重映射的主要区别：多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的关键字，它们都定义在<map>头文件中。 映射和多重映射关联容器类用于快速存储和读取关键字与关键值，按关键字排序。 例：P253，【例8-11】

8.7 容器适配器 STL提供了三个容器适配器（Container Adapter）：栈（Stack）、队列（Queue）和优先级队列（Priority_Queue）。 使用时要用头文件<stack>，队列使用时要用头文件<queue>。适配器依附在一个顺序容器上，并同步独立。

8.7.1 栈容器适配器 模板类stack实现为先进后出。一般选择vector、deque或list构造stack对象。 8.7.1 栈容器适配器 模板类stack实现为先进后出。一般选择vector、deque或list构造stack对象。 template <class T, class C = deque<T> > class stack; 参数T指定栈中所存储的元素类型；参数C指定用来控制元素的序列容器类型。 默认的模板参数，可以：stack<int>。否则就必须指定容器的类型。【例8-12】

8.7.2 队列容器适配器 模板类queue是先进先出，可以选择deque或list来构造一个队列容器对象。 8.7.2 队列容器适配器 模板类queue是先进先出，可以选择deque或list来构造一个队列容器对象。 默认情况下，queue由deque实现。 【例8-13】

8.7.3 优先级队列容器适配器 在优先级队列中，每个元素都被赋予一个优先级，优先级最高的元素首先被访问。 8.7.3 优先级队列容器适配器 在优先级队列中，每个元素都被赋予一个优先级，优先级最高的元素首先被访问。 可以选择vector或deque来构造一个优先级队列priority_queue对象，默认是使用vector实现。 【例8-14】