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

Presentation on theme: "第1章 C++程序设计基础 网络游戏开发-C++程序设计."— Presentation transcript:

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

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

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

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

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

6 第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)

7 第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）

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

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

10 第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);

11 第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);

12 第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是用于定义内存模型的，在使用时采用默认参数即可。

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

14 第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）

15 第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 );

16 第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是用于定义内存模型的，在使用时采用默认参数即可。

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

18 第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”的第一个元素区间

19 第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 );

20 第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一般译为映射，映射指的是一个范畴内的事物与另一个范畴内事物的对映关系。

21 第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：内存模型，采用默认值。

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

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

24 第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));

25 第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”的元素区间

26 第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;

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

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

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

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