《达内培训内部》PPT课件.ppt
STL,STL,标准模板库(Standard Template Library)效率是STL设计的关键考虑因素STL包含很多最流行的数据结构，例如容器，并且提供了多种常用的算法来处理这些容器中的数据STL的三种关键组件容器迭代器算法类模板通常称为容器，函数模板都是通用算法类模板主要是对数据结构的设计函数模板主要是通用算法的设计,容器,标准容器序列容器关联式容器迭代器容器适配器(特殊容器),函数对象内存分配器,迭代器,迭代器在很多方面和指针类似，也是用于指向容器中的元素迭代器存有它们所指的容器的状态信息，即迭代器对每种类型的容器都有一个实现迭代器的本质是封装了的指针，支持+*-=!=运算，大部分还支持-操作容器类基本都提供成员函数begin和end,begin函数返回一个指向容器中第一个元素的迭代器，end返回一个指向容器最后一个的下一个元素的迭代器STL中，通常用两个迭代器表示一个范围，这个范围是个半开半闭区间,标准容器,序列容器的共性vector deque list关联窗口的共性set multiset map multimap特殊容器(容器适配器)stack queue priority_queue,标准容器的共性,vector,deque,list,set/map,multi.构造函数：无参构造，拷贝构造，区间构造（两个迭代器表示的两个位置）析构迭代器相关：正向.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(),.max_size(),.empty()交换：.swap(c2),swap(c1,c2)成员函数和非成员函数在使用时，优先考虑使用成员函数。运算符：=,=,=,=,!=另：标准库容器并没有严格检查错误，所以用错的后果是未知的。标准库容器共性举例。,序列式容器的共性,vector,deque,list序列式容器属于标准容器，所以具体标准容器所有的共性。除此之外，序列式有以下共性：构造函数：指定元素个数和初始值（初始值默认为零初始化）插入：.insert(pos,n,element),.insert(pos,pos_beg,pos_end)赋值：.assign(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(下标);/用下标访问，检查越界迭代器在使用时需要特别注意，在进行插入或删除后，之前获得的迭代器可能会失效。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(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(key)统计关键字等于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元素不允许重复。判断重复的标准是运算符号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对不支持方括号下标举例,特殊容器,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)copy(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,比较大小，下标,
