常用STL容器与泛型算法

STL容器与泛型算法•常用STL基本用法•泛型算法•auto_ptrSTL简介•STL（StandardTemplateLibrary，标准模板库)是惠普实验室开发的一系列软件的统称。它是AlexanderStepanovMengLee和DavidRMusser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文件：algorithm、deque、functional、iterator、vector、list、map、memory、numeric、queue、set、stack和utility。为什么使用STL•不在为各种各样的数据类型操心•提供非常高效的算法•做事情达到事半功倍的效果•不受工作领域限制常用容器•vector•Deque•List•SetandMultiset•MapandMultimap容器共有的操作•ContTypec创建一个空的容器•ContTypec1(c2)创建一个拷贝C2内容的容器•ContTypec(beg,end)创建一个包含(BEG，END)间数据的容器•c.~ContType()删除所有数据和释放内存•c.size()返回元素的个数•c.empty()清空容器数据•c1==c2c1返回c1是否与c2相等•c1!=c2返回c1是否与c2不相等•c1c2返回C1是否小于C2•c1c2返回C1是否大于C2•c1=c2返回C1是否小于等于C2容器共有的操作•c1=c2返回C1是否大于等于C2•c1=c2赋值操作（内部元素拷贝）•c1.swap(c2)交换C1和C2的数据•swap(c1,c2)交换C1和C2的数据•c.begin()返回一个iterator指向第一个元素•c.end()返回一个iterator指向最后一个元素的后一个位置•c.rbegin()返回一个reverseiterator指向第一个元素•c.rend()返回一个reverseiterator指向最后一个元素的后一个位置•c.insert(pos,elem)插入一个元素•c.erase(beg,end)删除（beg,end）间所有元素•c.clear()删除容器所有元素vectorVector是一个动态数组，支持内存自动增长，使用需要包含#includevectorvector有如下初始化方法•vectorElemc•vectorElemc1(c2)•vectorElemc(n)•vectorElemc(n,elem)•vectorElemc(beg,end)Vector基本操作•c.insert(pos,elem)•c.insert(pos,n,elem)•c.insert(pos,beg,end)•c.push_back(elem)•c.pop_back()•c.erase(pos)•c.erase(beg,end)•c.resize(num)•c.resize(num,elem)•c.clear()用例分析•用例分析Deque(“deck”)•和VECTOR一样，也可以看成一个动态数组，不过区别在于Deque是两端开放的，也就是一个双向队列。使用该容器要包含#includedeque•与VECTOR相同点：很多基本操作都是一样的，删除容器中部的一个数据速度差不多与VECTOR的不同点•在尾端或末端插入或删除元素比较快•内部结构存在多种存取方式，因此存储元素或移动iterator会比VECTOR稍微慢•DEQUE由于分配的是多块内存，max_size()可能大些•DEQUE不支持capacity()andreserve()，也就是说不支持reserve分配内存注意•插入或删除操作都有可能造成容器的内存重新分配，因此以前指向其它元素iterators可能会无效。•例子LIST•LIST实际上就是一个双向链表•头文件#includelist•LIST不能提供随机存取，比如要存储第5个元素，由前四个元素组成的链表必须要建好，访问LIST里任意一个元素比较慢。•插入和删除元素非常快，因为不存在移动其它元素的操作•插入和删除元素不会使其它元素的指针，引用，迭代器失效•LIST每个元素都有自己的内存，所以不需要capacityorreallocation•LIST有自己的一些移动元素的算法，因为它只需要改变指针LIST操作•c.insert(pos,elem)•c.insert(pos,n,elem)•c.insert(pos,beg,end)•c.push_back(elem)•c.pop_back()•c.push_front(elem)•c.pop_front()•c.remove(val)•c.remove_if(op)•c.erase(pos)•c.erase(beg,end)•c.resize(num)•c.resize(num,elem)•c.clear()•c.unique()删除重复的连续元素•c.unique(op)删除OP为TRUE的重复的连续元素•c1.splice(pos,c2)在POS位置前插入C2（联合）•c1.splice(pos,c2,c2pos)•c1.splice(pos,c2,c2beg,c2end)•c.sort()从小到大排序•c.sort(op)根据规则排序•c1.merge(c2)合并并保证排序•c1.merge(c2,op)•c.reverse()反序SetsandMultisetsSetsandMultisets•初始化•std::setint,std::greaterintcoll;•判断两个元素不等•if(!(elem1elem2||elem2elem1))•因此SET里的数据不必要实现==•使用typedefstd::setint,std::greaterintIntSet;SetsandMultisets方法•count(elem)•find(elem)•lower_bound(elem)返回第一个大于等于elem的元素位置•upper_bound(elem)返回最后一个大于elem的元素位置•equal_range(elem)返回与ELEM相等的元素的起点和终点•lower_bound(),upper_bound(),and•equal_range()例子SetsandMultisets方法•c.insert(elem)•c.insert(pos,elem)•c.insert(beg,end)•c.erase(elem)//可能删除多个元素返回删除元素的个数•c.erase(pos)•c.erase(beg,end)•c.clear()•该类算法不要使用泛型算法，用自己内部算法例子•例子MapsandMultimapsMapsandMultimaps•MAP通过KEY值来排序，每个KEY对应一个值•初始化•std::mapfloat,std::string,std::greaterfloatcoll;MapsandMultimaps方法•count(key)•find(key)//注意找到的是KEY•lower_bound(key)•upper_bound(key)•equal_range(key)•c.insert(elem)•c.insert(pos,elem)•c.insert(beg,end)•c.erase(elem)//不要使用泛型算法•c.erase(pos)•c.erase(beg,end)•c.clear()插入元素•1.Usevalue_type•std::mapstd::string,floatcoll;•coll.insert(std::mapstd::string,float::value_type(otto,22.3));•2.Usepair•std::mapstd::string,floatcoll;•coll.insert(std::pairstd::string,float(otto,22.3));•3.Usemake_pair()•std::mapstd::string,floatcoll;•coll.insert(std::make_pair(otto,22.3));删除元素注意•for(pos=coll.begin();pos!=coll.end();++pos)•{if(pos-second==value)coll.erase(pos);//RUNTIMEERROR!!!•}•正确•for(pos=c.begin();pos!=c.end();)•{•if(pos-second==value)c.erase(pos++);•else++pos;•}例子•例子•TDbXDataMap泛型算法•头文件•numericalgorithmfunctional•选择最合适的算法来解决问题•部分算法允许用户自定义操作，传入函数或函数对象•查找小于50的元素（单个元素），从大到小排序（2个元素）两个特殊后缀•_if•不带这个后缀主要针对单一值，带这个后缀主要针对函数和函数对象。如find是找一个具有特定值的元素，而find_if则是找到满足用户传入函数或函数对象的一系列元素•_copy•带这个后缀的函数表示不仅具有前面的操作，而且将元素拷贝到另外一个区域NonmodifyingAlgorithms•for_each()对每个元素完成一次操作•count()返回元素个数•count()_if()返回满足规则的元素个数•min_element()返回最小元素•max_element()返回最大元素•find()找到对应值的第一个元素•find_if()找到满足规则的第一个元素•search_n()查找第一个满足连续N个元素满足规则•search()在容器中找到一定范围值相等的位置•find_end()在容器中找到最后一个一定范围值相等的位置•find_first_of()在容器中找到第一个一定范围值相等的位置•adjacent_find()找相邻两个元素相等的位置•equal()返回两个范围内元素是否相等•mismatch()在两个范围里面找第一不匹配的元素ModifyingAlgorithms•for_each()对每一个元素操作•copy()从第一个元素开始拷贝•copy_backward()从最后一个元素开始拷贝•transform()拷贝数据并对数据进行一些操作•merge()合并两个区域•swap_ranges()两个区域内元素交换•fill()用元素填充（填充所有元素）•fill_n()填充N个元素•generate()按照一定操作的结果替换每一个元素•generate_n()按照一定操作的结果替换N个元素•replace()将一个值替换为另外一个值•replace()_if()按照一定规则替换•replace_copy()替换后并拷贝•replace_copy_if()按规则替换后并拷贝RemovingAlgorithms•remove()删除给定值•remove_if()删除定义的给定值•remove_copy()拷贝和给定值不等的•remove_copy()_if()拷贝和给定规则不等的•unique()删除重复元素•unique_copy()删除重复元素时同时拷贝•注意删除操作只是覆盖操作，内存空间大小不变SortingAlgorithms•sort()排序（从小到大）•stable_sort()排序•partial_sort()