达内培训内部--STL.ppt

1、STL,STL,标准模板库(Standard Template Library) 效率是STL设计的关键考虑因素 STL包含很多最流行的数据结构，例如容器，并且提供了多种常用的算法来处理这些容器中的数据 STL的三种关键组件 容器 迭代器 算法 类模板通常称为容器，函数模板都是通用算法 类模板主要是对数据结构的设计 函数模板主要是通用算法的设计,容器,标准容器 序列容器 关联式容器 迭代器 容器适配器(特殊容器), 函数对象 内存分配器 ,迭代器,迭代器在很多方面和指针类似，也是用于指向容器中的元素 迭代器存有它们所指的容器的状态信息，即迭代器对每种类型的容器都有一个实现 迭代器的本质是封装了

2、的指针，支持+ * - = !=运算，大部分还支持-操作 容器类基本都提供成员函数begin和end,begin函数返回一个指向容器中第一个元素的迭代器，end返回一个指向容器最后一个的下一个元素的迭代器 STL中，通常用两个迭代器表示一个范围，这个范围是个半开半闭区间,标准容器,序列容器的共性 vector deque list 关联窗口的共性 set multiset map multimap 特殊容器(容器适配器) stack queue priority_queue,标准容器的共性,vector,deque,list,set/map,multi. 构造函数：无参构造，拷贝构造，区间构造

3、（两个迭代器表示的两个位置） 析构 迭代器相关：正向.begin()，.end()反向.rbegin()，.rend() iterator,reverse_iterator,const_iterator,const_reverse_iterator *,-,=,+,=,!= - 插入：.insert(pos,element)，其中pos表示插入位置，是个迭代器,标准容器的共性,插入：.insert(pos,element)，其中pos表示插入位置，是个迭代器 删除：.erase(pos), .erase(pos_beg, pos_end) 清除：.clear() 大小：.size(), .ma

4、x_size(), .empty() 交换：.swap(c2), swap(c1,c2) 成员函数和非成员函数在使用时，优先考虑使用成员函数。 运算符：=, , =, =, =, != 另：标准库容器并没有严格检查错误，所以用错的后果是未知的。 标准库容器共性举例。,序列式容器的共性,vector,deque,list 序列式容器属于标准容器，所以具体标准容器所有的共性。除此之外，序列式有以下共性： 构造函数：指定元素个数和初始值（初始值默认为零初始化） 插入：.insert(pos, n, element), .insert(pos, pos_beg, pos_end) 赋值：.assign

5、(n, element), .assign(pos_beg, pos_end) 调整：.resize(n, element=零初始化) 首尾：.front(), .back() 注：返回的是首尾元素的引用 增删：.push_back(element), .pop_back()只删除，返回void 序列式容器共性举例。,序列式容器的个性介绍,vector .capacity();/取得当前分配了多少容量 .reserve(n);/约定容量 下标;/如同数组，支持下标操作，operator(i)即使越界也不检查 .at(下标);/用下标访问，检查越界 迭代器在使用时需要特别注意，在进行插入或删除后

6、，之前获得的迭代器可能会失效。 vector使用举例,deque,deque (double_ended_queue) 由数组实现，支持下标操作，如vector .at(i)会做越界检查。 没有capacity reserve操作 可从头增删：.push_front(element) .pop_front(); deque举例,list,list (双向链表实现) 增删.push_front(element), .pop_front(), .remove(element)/删除等于指定值的所有元素，需要支持=运算符 不支持下标 除重：.unique()相邻的重复元素只保留一个 排序：.sort

7、(compare_func=less)默认用小于符号比较，从小到大排序 greater为从大到小排序函数 倒置：.reverse()颠倒链表中元素顺序 转移.splice(pos,list2), .splice(pos,list2,pos2), .splice(pos,list2,pos_beg,pos_end) 归并：.merge(list2) list举例,关联式容器共性,二叉树实现，会根据关键字自动排序。 个性少。 set, multiset, map, multimapK,V) 查找：.find(key)返回一个迭代器指向找到的第一个元素，失败返回.end() 统计：.count(ke

8、y)统计关键字等于key的元素的个数 删除：.erase(key)删除关键字等于key的所有元素 区间： .lower_bound(key)取得关键字为key的第一个元素的位置, .upper_bound(key)取得关键字为key的最后一个元素之后的位置， .equal_range(key)一次取得关键字为key的元素的区间，返回一个pair 插入：.insert(element) 所在关联容器插入都不会指定位置：insert(element) 构造函数：可以用比较函数作为参数bool(*compare)(K a,K b),关联式容器的个性,set 元素不允许重复。判断重复的标准是运算符号

9、set举例 multiset 元素允许重复。 multiset举例,map/multimap,map 不允许key重复,元素是key/value对 支持以key为下标访问对应的value的引用，如果key不存在就新增一个元素以这个为key。 mis.insert(map:value_type(8,P(“aaa“,20); mis.insert(pair(5,P(“bbb“,22); mis.insert(make_pair(4,P(“ccc“,21); mis3 = P(“ddd“,20); 举例 multimap 允许重复key 元素是key/value对 不支持方括号下标 举例,特殊容器,

10、stack，queue，priority_queue .push(element), .pop(), .empty() stack:.top(), queue:.front(),.back() priority_queue:.top() 没有迭代器 优先队列举例，说明优先队列的实现原理：堆调整,通用算法,1)for_each(pos_beg, pos_end, func(数据元素); 2)iterator find(pos_beg, pos_end, 数据元素); 3)sort(pos_beg, pos_end); sort(pos_beg, pos_end, func(数据元素); 4)co

11、py(pos_beg, pos_end, pos_target); copy_if(pos_beg, pos_end, pos_target, func(数据元素); 5)find_if(pos_beg, pos_end, func(); count(pos_beg, pos_end, x); count(pos_beg, pos_end, func();,迭代器分类,迭代器分类（it）：+,*,-,=,!= 输入迭代器：可读*it的值，但不一定能修改（设置）*it的值 输出迭代器：可以设置*it的值，但不一定能读取*it的值 前向迭代器：可以读取也可以设置*it的值 双向迭代器：支持- 随机迭代器：几乎跟指针一样，支持-,+n,-n,比较大小，下标,