第1章 C++程序设计基础 网络游戏开发-C++程序设计

第9章 模板与STL 标准模板库 常用的容器 容器的概念 迭代器 映射的概念 迭代器的使用 了解标准模板库 掌握常用容器的使用

第9章 模板与STL 9.2 STL的使用 STL（Standard Temporary Library）是C++标准的一部分 提供一系列核心组件： 用以支持I/O、 字符串（strings） 容器（数据结构） 算法（排序、搜索、合并等等） 数值计算、多字符集等主题。

第9章 模板与STL 9.2 STL的使用 9.2.1 STL中的容器的概念和要求 STL中的容器（Container）是可容纳一些数据的模板类，包括 vector list set map 大大方便了程序员对程序中数据的组织和保存 具有保存和操作数据集合的能力. 提高了开发效率。

第9章 模板与STL 9.2 STL的使用 9.2.1 STL中的容器的概念和要求 容器有相同的函数接口 这些函数主要是用于进行数据比较、迭代和存储的 STL容器的特点 1）插入操作时，内部实现的是拷贝操作，置于容器内。 2）所有元素形成一个次序（order）。 3）各项操作并非绝对安全。

第9章 模板与STL 9.2 STL的使用 9.2.1 STL中的容器的概念和要求 各个容器共通的函数 操作 功能 ContType c 产生一个未含任何元素的空容器 ContType c1(c2) 产生一个同型容器 ContType c(beg, end) 复制[beg; end]区间内的元素，作为容器初值 c.~ContType() 删除所有元素，释放内存 c.size() 返回容器中的元素数量 c.empty() 判断容器是否为空（相当于size()==0,但可能更快） c.max_size() 返回元素的最大可能数量 c1 == c2 判断是否c1等于c2 c1 != c2 判断是否c1不等于c2，相当于!(c1==c2) c1 < c2 判断是否c1小于c2 c1 > c2 判断是否c1大于c2，相当于c2<c1 c1 <= c2 判断是否c1小于等于c2，相当于!(c2<c1) c1 >= c2 判断是否c1大于等于c2，相当于!(c1<c2)

第9章 模板与STL 9.2 STL的使用 9.2.1 STL中的容器的概念和要求 c1 = c2 将c2的所有元素赋值给c1 c1.swap(c2) 交换c1和c2的数据 swap(c1, c2) 同上，是个全局函数 c.begin() 返回一个迭代器，指向第一元素 c.end() 返回一个迭代器，指向最后元素的下一位置 c.rbegin() 返回一个逆向迭代器，指向逆向遍历时的第一元素 c.rend() 返回一个逆向迭代器，指向逆向遍历时的最后元素的下一位置 c.insert(pos, elem) 将elem的一份副本安插于pos处。返回值和pos的意义并不相同 c.erase(beg, end) 移除[beg; end]区间内的所有元素。某些容器会返回未被移除的第一个接续元素 c.clear() 移除所有元素，令容器为空 c.get_allocator() 返回容器的内存模型（memory model）

第9章 模板与STL 9.2 STL的使用 9.2.1 STL中的容器的概念和要求 迭代器（iterator） “能够遍历某个序列内的所有元素”的对象。 它可以通过与一般指针一致的接口来完成自已的工作。 迭代器奉行一个纯抽象概念：任何东西，只要行为类似迭代器，那么它就是一种迭代器。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 1．vector的能力和使用 namespace std { template <class T, class Allocator = allocator<T>> class vector; } 其中元素T可以是任意数据类型，只要T具有赋值和拷贝能力。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 1．vector的能力和使用 1）它是一个有序集群（ordered collection）,支持随机存取，因此只要知道位置，就可以存取这个元素； 2）在末端附加或删除元素时，vector性能很高。 3）vector的容量是可配置的。 4）可以使用reserve()配置容量。（只能用来扩大容量，但不能缩减容量） std::vector<int> v; v.reserve(80);

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 1．vector的能力和使用 vector<int> v; vector<int>::iterator iter; // 增加元素 v.reserve(20); v.push_back(5); v.push_back(10); v.push_back(20); // 插入元素 v.insert(v.begin()+2, 15); // 遍历访问 cout<<"v= "; for (iter = v.begin(); iter != v.end(); iter++) { cout<<" "<<*iter; } v.erase(v.begin() +1);

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 2. list的能力和使用 list容器可以理解为是一个双向链表。它包含在头文件<list>中 namespace std { template <class T, class Allocator = allocator<T>> class list; } 元素T可以是任意数据类型，只要T具有赋值和拷贝能力。 参数Allocator是用于定义内存模型的，在使用时采用默认参数即可。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 2. list的能力和使用 1）不支持随机存取 2）在任何位置上的插入和删除操作，性能都是很高的。 3）list没有容量的概念，所以也没有空间重新分配等操作；

第9章 模板与STL 9.2 STL的使用 函数 功能 c.unique() 如果存在若干相邻而数值相等的元素，就删除重复元素，只留一个  [fww1]什么是已序？ 第9章 模板与STL 9.2 STL的使用 函数 功能 c.unique() 如果存在若干相邻而数值相等的元素，就删除重复元素，只留一个 c.unique(op) 如果存在若干相邻元素，都使op()的结果为true，则删除重复元素，只留一个 C1.splice(pos, c2) 将c2内的所有元素转移到c1之内，迭代器pos之前 C1.splice(pos, c2, c2pos) 将c2内的c2pos的所指元素转移到c1内的pos所指位置上（c1和c2可相同） C1.splice(pos, c2, c2beg, c2end) 将c2内的[c2beg; c2end]区间内所有元素转移到c1内的pos之前（c1和c2可相同） c.sort() 以operator<为准则，对所有元素排序 c.sort(op) 以op()为准则，对所有元素排序 C1.merge(c2) 假设c1和c2容器都包含已序（sorted）元素，将c2的全部元素转移到c1，并保证合并后的list仍为已序  C1.merge(c2, op) 假设c1和c2容器都包含op()原则下的已序（sorted）元素，将c2的全部元素转移到c1，并保证合并后的list仍为已序 c.reverse() 将所有元素反序（reverse the order）

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 2. list的能力和使用 list <int> c1, c2, c3; list <int>::iterator c1_Iter, c2_Iter, c3_Iter; // 赋值 c1.push_back( 3 ); c1.push_back( 6 ); c3.push_back( 1 );   cout << "c1 ="; for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ ) cout << " " << *c1_Iter; c2.merge( c1 );

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 3. set的能力和使用 包含在头文件<set>中 namespace std { template <class T, class Compare = less<T>, class Allocator = allocator<T>> class set; } 其中元素T可以是任意数据类型，只要T具有赋值和拷贝能力。 第二个参数Compare用于确定按什么数据类型来排序，使用默认参数即可。 第三个参数Allocator是用于定义内存模型的，在使用时采用默认参数即可。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 3. set的能力和使用 set作为一个类似于平衡二叉树的容器 1）具有自动排序能力，使元素的搜索有良好性能； 2）由于二叉树的特点决定，对set容器中的元素不能直接修改。如果想修改，可以采用的办法是先删除这个元素，再插入新的元素； 3）set不提供用来直接存取元素的任何操作。通过迭代器进行元素间接存取，可视这些元素是常数。 4）set在元素搜寻方面有优化设计，所以提供了特殊的搜寻函数。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 3. set的能力和使用 函数 功能 count(elem) find(elem) 返回“元素值为elem”的第一个元素，如果找不到就返回end() lower_bound(elem) 返回elem的第一个可插入位置，也就是“元素值 >= elem”的第一个元素位置 upper_bound(elem) 返回elem的最后一个可插入位置，也就是“元素值 > elem”的第一个元素位置 equal_range(elem) 返回elem可插入的第一个和最后一个位置，也就是“元素值 == elem”的第一个元素区间

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 3. set的能力和使用 set <int> s1; set <int> :: const_iterator s1_AcIter, s1_RcIter; // 赋值 s1.insert( 10 ); s1.insert( 20 ); s1.insert( 30 ); s1_RcIter = s1.lower_bound( 20 ); cout << *s1_RcIter << "." << endl; s1_RcIter = s1.lower_bound( 40 );

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 namespace std { template < class Key, class Type, class Traits = less<Key>, class Allocator=allocator<pair <const Key, Type> > class map; } map一般译为映射，映射指的是一个范畴内的事物与另一个范畴内事物的对映关系。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 namespace std { template < class Key, class Type, class Traits = less<Key>, class Allocator=allocator<pair <const Key, Type> > class map; } 1）Key：键值； 2）Type：元素值； 3）Traits：按什么数据类型来排序，默认为以键值的数据类型来排序； 4）Allocator：内存模型，采用默认值。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 map即映射 一个范畴内的事物与另一个范畴内事物的对映关系。 在数据结构领域内： 一种数据类型与另一种数据类型的一一对应关系。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 在数据结构领域内：一种数据类型与另一种数据类型的一一对应关系。 1）可以把set看作是一类特殊的map，也就是当键值和元素值是同一对象时，就和set一样了； 2）对于键值不可以直接修改，要想实现修改的办法是先删除再插入； 3）map内的元素是“键值/元素值”成对（pair）插入的。 4）map在元素搜寻方面是通过对键值的搜寻实现的，所以提供了特殊的搜寻函数。

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 map<string, float> coll; // 运用value_type插入 coll.insert(map<string, float>::value_type("otta", 21.1)); // 运用pair<>插入 coll.insert(pair<string, float>("ottb", 22.2)); // 运用make_pair()插入 coll.insert(make_pair("ottc", 23.3));

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 函数 功能 count(key) find(key) 返回“键值等于key”的第一个元素，找不到就返回end() lower_bound(key) 返回“键值为key”的元素的第一个可插入位置，也就是“键值>=key”的第一个元素位置 upper_bound(key) 返回“键值为key”的元素的最后一个可插入位置，也就是“键值>key”的第一个元素位置 equal_range(key) 返回“键值为key”的元素的第一个可插入位置和最后一个可插入位置，也就是“键值==key”的元素区间

第9章 模板与STL 9.2 STL的使用 9.2.2 STL中容器的使用 4．map的能力和使用 map<int, int> m1; map<int, int>::const_iterator m1_AcIter, m1_RcIter; typedef pair<int, int> Int_Pair; // 成对插入元素 m1.insert(Int_Pair(1, 10)); m1.insert(Int_Pair(2, 20)); m1.insert(Int_Pair(3, 30)); m1_RcIter = m1.find(2); cout<< "键值 2 映射的元素是: " << m1_RcIter -> second << "." << endl;

第9章 模板与STL 小结 本章主要讲解STL基础知识 标准模板库 常用的容器

第9章 模板与STL 自测题 1．以下那一个不是vector的特点（ ）。 A. 支持随机存取 B. 在末端添加和删除元素，性能非常好 D. 容量是可配置的 2．迭代器就是一个指向元素的指针。（ ）

第9章 模板与STL 自测题 1．以下那一个不是vector的特点（ C ）。 A. 支持随机存取 B. 在末端添加和删除元素，性能非常好 D. 容量是可配置的 2．迭代器就是一个指向元素的指针。（ X ）

第9章 模板与STL 课后作业 【作业1】 使用容器，保存一组整数，要求能随机存取，插入和删除操作方便。 【作业2】 使用map，保存一组整数和名字，输入名字，可以找到整数。