精华内容
下载资源
问答
  • STL详解

    千次阅读 2019-05-04 17:12:15
    C++:STL标准入门汇总 第一部分:  一、STL简介 STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所...

    C++:STL标准入门汇总

    第一部分:

     一、STL简介

    STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中,但在被引入C++之前该技术就已经存在了很长的一段时间。

    STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了模板类和模版函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中,STL被组织为下面的13个头文件:

    <algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、

    <memory>、<numeric>、<queue>、<set>、<stack>和<utility>。 

    STL(Standard Template Library),即标准模板库,是一个具有工业强度的,高效的C++程序库。它被容纳于C++标准程序库(C++ Standard Library)中,是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架,高度体现了软件的可复用性。

          从逻辑层次来看,在STL中体现了泛型化程序设计的思想(generic programming),引入了诸多新的名词,比如像需求(requirements),概念(concept),模型(model),容器(container),算法(algorithmn),迭代子(iterator)等。与OOP(object-oriented programming)中的多态(polymorphism)一样,泛型也是一种软件的复用技术;

           从实现层次看,整个STL是以一种类型参数化(type parameterized)的方式实现的,这种方式基于一个在早先C++标准中没有出现的语言特性--模板(template)。如果查阅任何一个版本的STL源代码,你就会发现,模板作为构成整个STL的基石是一件千真万确的事情。除此之外,还有许多C++的新特性为STL的实现提供了方便;

    以下为STL六大组件:

          算法(Algorithm),是用来操作容器中的数据的模板函数。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个       list中的对象,函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用;

    • 容器(Container),是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器;
    • 迭代器(Iterator),提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象;
    • 仿函数(Function object,仿函数(functor)又称之为函数对象(function object),其实就是重载了()操作符的struct,没有什么特别的地方
    • 迭代适配器(Adaptor)
    • 空间配制器(allocator)其中主要工作包括两部分1.对象的创建与销毁    2.内存的获取与释放

    二、算法

    大家都能取得的一个共识是函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说,一个求方根的函数,在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择,直到真正想使用模板或者说对模板进行特化的时候,STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类,然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。

    STL提供了大约100个实现算法的模版函数,比如算法for_each将为指定序列中的每一个元素调用指定的函数,stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来,只要我们熟悉了STL之后,许多代码可以被大大的化简,只需要通过调用一两个算法模板,就可以完成所需要的功能并大大地提升效率。

    算法部分主要由头文件<algorithm>,<numeric>和<functional>组成。

    <algorithm>是所有STL头文件中最大的一个(尽管它很好理解),它是由一大堆模版函数组成的,可以认为每个函数在很大程度上都是独立的,其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。

    <numeric>体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作。

    <functional>中则定义了一些模板类,用以声明函数对象。

    三、容器

    在实际的开发过程中,数据结构本身的重要性不会逊于操作于数据结构的算法的重要性,当程序中存在着对时间要求很高的部分时,数据结构的选择就显得更加重要。经典的数据结构数量有限,但是我们常常重复着一些为了实现向量、链表等结构而编写的代码,这些代码都十分相似,只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便,它允许我们重复利用已有的实现构造自己的特定类型下的数据结构,通过设置一些模版类,STL容器对最常用的数据结构提供了支持,这些模板的参数允许我们指定容器中元素的数据类型,可以将我们许多重复而乏味的工作简化。容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器和容器适配器(可以看作由其它容器实现的容器),可以通过下表总结一下它们和相应头文件的对应关系。

    向量(vector) 连续存储的元素<vector>

    列表(list)       由节点组成的双向链表,每个结点包含着一个元素<list>

    双队列(deque) 连续存储的指向不同元素的指针所组成的数组<deque>

    集合(set) 由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序<set>

    多重集合(multiset) 允许存在两个次序相等的元素的集合 <set>

    栈(stack) 后进先出的值的排列 <stack>

    队列(queue) 先进先出的执的排列 <queue>

    优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 <queue>

    映射(map) 由{键,值}对组成的集合,以某种作用于键对上的谓词排列 <map>

    多重映射(multimap) 允许键对有相等的次序的映射 <map>

    四、迭代器

    下面要说的迭代器从作用上来说是最基本的部分,可是理解起来比前两者都要费力一些(至少笔者是这样)。软件设计有一个基本原则,所有的问题都可以通过引进一个间接层来简化,这种简化在STL中就是用迭代器来完成的。概括来说,迭代器在STL中用来将算法和容器联系起来,起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的,每一个容器都定义了其本身所专有的迭代器,用以存取容器中的元素。 

    迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。

    <utility>是一个很小的头文件,它包括了贯穿使用在STL中的几个模板的声明,

    <iterator>中提供了迭代器使用的许多方法,而对于<memory>的描述则十分的困难,它以不同寻常的方式为容器中的元素分配存储空间,同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator,它负责产生所有容器中的默认分配器。

       对于之前不太了解STL的读者来说,上面的文字只是十分概括地描述了一下STL的框架,对您理解STL的机制乃至使用STL所起到的帮助微乎甚微,这不光是因为深入STL需要对C++的高级应用有比较全面的了解,更因为STL的三个部分算法、容器和迭代器三部分是互相牵制或者说是紧密结合的。从概念上讲最基础的部分是迭代器,可是直接学习迭代器会遇到许多抽象枯燥和繁琐的细节,然而不真正理解迭代器又是无法直接进入另两部分的学习的(至少对剖析源码来说是这样)。可以说,适应STL处理问题的方法是需要花费一定的时间的,但是以此为代价,STL取得了一种十分可贵的独立性,它通过迭代器能在尽可能少地知道某种数据结构的情况下完成对这一结构的运算,所以下决心钻研STL的朋友们千万不要被一时的困难击倒。其实STL运用的模式相对统一,只要适应了它,从一个STL工具到另一个工具,都不会有什么大的变化。

    对于STL的使用,也普遍存在着两种观点。第一种认为STL的最大作用在于充当经典的数据结构和算法教材,因为它的源代码涉及了许多具体实现方面的问题。第二种则认为STL的初衷乃是为了简化设计,避免重复劳动,提高编程效率,因此应该是“应用至上”的,对于源代码则不必深究。笔者则认为分析源代码和应用并不矛盾,通过分析源代码也能提高我们对其应用的理解,当然根据具体的目的也可以有不同的侧重。

    --------------------------------------------------------------------------------

    STL中标准容器主要vector, list, deque, string, set, multiset, map, multimay,切记:STL中只有队列,没有栈的实现。 其中set, multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看:学习STL map, STL set之数据结构基础. 因此在这些容器中,元素一直是有序的。 
    这些容器的迭代器类型并不是随机型迭代器,因此,上述的那些排序函数,对于这些容器是不可用的。上述sort函数对于下列容器是可用的:

    vector 
    string 
    deque 
    如果你自己定义的容器也支持随机型迭代器,那么使用排序算法是没有任何问题的。 
    对于list容器,list自带一个sort成员函数list::sort(). 它和算法函数中的sort差不多,但是list::sort是基于指针的方式排序,也就是说,所有的数据移动和比较都是此用指针的方式实现,因此排序后的迭代器一直保持有效(vector中sort后的迭代器会失效).


    选择合适的排序函数

    --------------------------------------------------------------------------------
    为什么要选择合适的排序函数?可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小, 因此你觉得随便用哪个函数都无关紧要。 
    其实不然,即使你不关心效率,如果你选择合适的排序函数,你会让你的代码更容易让人明白,你会让你的代码更有扩充性,逐渐养成一个良好的习惯,很重要吧  。

    如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较,那我告诉你,qsort和sort是一样的,因为他们采用的都是快速排序。从效率上看,以下几种sort算法的是一个排序,效率由高到低(耗时由小变大):

    partion 
    stable_partition 
    nth_element 
    partial_sort 
    sort 
    stable_sort 
    记得,以前翻译过Effective STL的文章,其中对如何选择排序函数总结的很好: 
    若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort; 
    若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选. 
    若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序,nth_element是最理想的; 
    若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition; 
    若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。正如上面介绍的有几种方式可以选择。 

    五、STL的组件各大组件详解

    1.STL容器

    1)序列式容器(Sequence containers),每个元素都有固定位置--取决于插入时机和地点,和元素值无关,vector、deque、list;

       Vectors:将元素置于一个动态数组中加以管理,可以随机存取元素(用索引直接存取),数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时;

       Deques:是“double-ended queue”的缩写,可以随机存取元素(用索引直接存取),数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时;

       Lists:双向链表,不提供随机存取(按顺序走到需存取的元素,O(n)),在任何位置上执行插入或删除动作都非常迅速,内部只需调整一下指针;

    2)关联式容器(Associated containers),元素位置取决于特定的排序准则,和插入顺序无关,set、multiset、map、multimap;

       Sets/Multisets:内部的元素依据其值自动排序,Set内的相同数值的元素只能出现一次,Multisets内可包含多个数值相同的元素,内部由二叉树实现(实际上基于红黑树(RB-tree)实现),便于查找;

       Maps/Multimaps:Map的元素是成对的键值/实值,内部的元素依据其值自动排序,Map内的相同数值的元素只能出现一次,Multimaps内可包含多个数值相同的元素,内部由二叉树实现(实际上基于红黑树(RB-tree)实现),便于查找;

    另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。

      容器的比较:

      Vector Deque List Set MultiSet Map MultiMap
    内部结构 dynamic array array of arrays double linked list binary tree binary tree binary tree binary tree
    随机存取 Yes Yes No No No Yes(key) No
    搜索速度 很慢
    快速插入移除 尾部 首尾 任何位置 -- -- -- --

     

    2.STL迭代器 

    Iterator(迭代器)模式又称Cursor(游标)模式,用于提供一种方法顺序访问一个聚合对象中各个元素, 
    而又不需暴露该对象的内部表示。或者这样说可能更容易理解:Iterator模式是运用于聚合对象的一种模式,通过运用该模式,使得我们可以在不知道对象内部表示的情况下,按照一定顺序(由iterator提供的方法)访问聚合对象中的各个元素。

    迭代器的作用:能够让迭代器与算法不干扰的相互发展,最后又能无间隙的粘合起来,重载了*,++,==,!=,=运算符。用以操作复杂的数据结构,容器提供迭代器,算法使用迭代器;

    常见的一些迭代器类型:iterator、const_iterator、reverse_iterator和const_reverse_iterator

    迭代器一般声明使用示例

    vector<T>::iterator it;
    list<T>::iterator it;
    deque<T>::iterator it;

     

                input         output

                  \            /  

                    forward

                         |

                    bidirectional

                         |

                   random access                                       

     



    要注意,上面这图表并不是表明它们之间的继承关系:而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如:forward迭代器不但拥有input和output迭代器的所有功能,还拥有更多的功能。

    各个迭代器的功能如下:

    迭代器类别

    说明

    输入

    从容器中读取元素。输入迭代器只能一次读入一个元素向前移动,输入迭代器只支持一遍算法,同一个输入迭代器不能两遍遍历一个序列

    输出

    向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法,统一输出迭代器不能两次遍历一个序列

    正向

    组合输入迭代器和输出迭代器的功能,并保留在容器中的位置

    双向

    组合正向迭代器和逆向迭代器的功能,支持多遍算法

    随机访问

    组合双向迭代器的功能与直接访问容器中任何元素的功能,即可向前向后跳过任意个元素

    迭代器的操作:

    每种迭代器均可进行包括表中前一种迭代器可进行的操作。

    迭代器操作

    说明

    所有迭代器

    p++

    后置自增迭代器

    ++p

    前置自增迭代器

    输入迭代器

    *p

    复引用迭代器,作为右值

    p=p1

    将一个迭代器赋给另一个迭代器

    p==p1

    比较迭代器的相等性

    p!=p1

    比较迭代器的不等性

    输出迭代器

    *p

    复引用迭代器,作为左值

    p=p1

    将一个迭代器赋给另一个迭代器

    正向迭代器

    提供输入输出迭代器的所有功能

    双向迭代器

    --p

    前置自减迭代器

    p--

    后置自减迭代器

    随机迭代器

    p+=i

    将迭代器递增i位

    p-=i

    将迭代器递减i位

    p+i

    在p位加i位后的迭代器

    p-i

    在p位减i位后的迭代器

    p[i]

    返回p位元素偏离i位的元素引用

    p<p1

    如果迭代器p的位置在p1前,返回true,否则返回false

    p<=p1

    p的位置在p1的前面或同一位置时返回true,否则返回false

    p>p1

    如果迭代器p的位置在p1后,返回true,否则返回false

    p>=p1

    p的位置在p1的后面或同一位置时返回true,否则返回false

    只有顺序容器和关联容器支持迭代器遍历,各容器支持的迭代器的类别如下:

    容器

    支持的迭代器类别

    说明

    vector

    随机访问

    一种随机访问的数组类型,提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小

    deque

    随机访问

    一种随机访问的数组类型,提供了序列两端快速进行插入和删除操作的功能。可以再需要的时候修改其自身的大小

    list

    双向

    一种不支持随机访问的数组类型,插入和删除所花费的时间是固定的,与位置无关。

    set

    双向

    一种随机存取的容器,其关键字和数据元素是同一个值。所有元素都必须具有惟一值。

    multiset

    双向

    一种随机存取的容器,其关键字和数据元素是同一个值。可以包含重复的元素。

    map

    双向

    一种包含成对数值的容器,一个值是实际数据值,另一个是用来寻找数据的关键字。一个特定的关键字只能与一个元素关联。

    multimap

    双向

    一种包含成对数值的容器,一个值是实际数据值,另一个是用来寻找数据的关键字。一个关键字可以与多个数据元素关联。

    stack

    不支持

    适配器容器类型,用vector,deque或list对象创建了一个先进后出容器

    queue

    不支持

    适配器容器类型,用deque或list对象创建了一个先进先出容器

    priority_queue

    不支持

    适配器容器类型,用vector或deque对象创建了一个排序队列

     

     3.STL算法

    STL算法部分主要由头文件<algorithm>,<numeric>,<functional>组成。要使用 STL中的算法函数必须包含头文件<algorithm>,对于数值算法须包含<numeric>,<functional>中则定义了一些模板类,用来声明函数对象。
    STL中算法大致分为四类:
    1)、非可变序列算法:指不直接修改其所操作的容器内容的算法。
    2)、可变序列算法:指可以修改它们所操作的容器内容的算法。
    3)、排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
    4)、数值算法:对容器内容进行数值计算。

     

    以下对所有算法进行细致分类并标明功能:
        <一>查找算法(13个):判断容器中是否包含某个值
        adjacent_find:            在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的ForwardIterator。否则返回last。重载版本使用输入的二元操作符代替相等的判断。
        binary_search:            在有序序列中查找value,找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。
        count:                    利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数。
        count_if:                 利用输入的操作符,对标志范围内的元素进行操作,返回结果为true的个数。
        equal_range:              功能类似equal,返回一对iterator,第一个表示lower_bound,第二个表示upper_bound。
        find:                     利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较。当匹配时,结束搜索,返回该元素的一个InputIterator。
        find_end:                 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator,否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。
        find_first_of:            在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。
        find_if:                  使用输入的函数代替等于操作符执行find。
        lower_bound:              返回一个ForwardIterator,指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。
        upper_bound:              返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置,该位置标志一个大于value的值。重载函数使用自定义比较操作。
        search:                   给出两个范围,返回一个ForwardIterator,查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置,查找失败指向last1。重载版本使用自定义的比较操作。
        search_n:                 在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。
     
        <二>排序和通用算法(14个):提供元素排序策略
        inplace_merge:            合并两个有序序列,结果序列覆盖两端范围。重载版本使用输入的操作进行排序。
        merge:                    合并两个有序序列,存放到另一个序列。重载版本使用自定义的比较。
        nth_element:              将范围内的序列重新排序,使所有小于第n个元素的元素都出现在它前面,而大于它的都出现在后面。重载版本使用自定义的比较操作。
        partial_sort:             对序列做部分排序,被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。
        partial_sort_copy:        与partial_sort类似,不过将经过排序的序列复制到另一个容器。
        partition:                对指定范围内元素重新排序,使用输入的函数,把结果为true的元素放在结果为false的元素之前。
        random_shuffle:           对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。
        reverse:                  将指定范围内元素重新反序排序。
        reverse_copy:             与reverse类似,不过将结果写入另一个容器。
        rotate:                   将指定范围内元素移到容器末尾,由middle指向的元素成为容器第一个元素。
        rotate_copy:              与rotate类似,不过将结果写入另一个容器。
        sort:                     以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。
        stable_sort:              与sort类似,不过保留相等元素之间的顺序关系。
        stable_partition:         与partition类似,不过不保证保留容器中的相对顺序。
     
        <三>删除和替换算法(15个)
        copy:                     复制序列
        copy_backward:            与copy相同,不过元素是以相反顺序被拷贝。
        iter_swap:                交换两个ForwardIterator的值。
        remove:                   删除指定范围内所有等于指定元素的元素。注意,该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数。
        remove_copy:              将所有不匹配元素复制到一个制定容器,返回OutputIterator指向被拷贝的末元素的下一个位置。
        remove_if:                删除指定范围内输入操作结果为true的所有元素。
        remove_copy_if:           将所有不匹配元素拷贝到一个指定容器。
        replace:                  将指定范围内所有等于vold的元素都用vnew代替。
        replace_copy:             与replace类似,不过将结果写入另一个容器。
        replace_if:               将指定范围内所有操作结果为true的元素用新值代替。
        replace_copy_if:          与replace_if,不过将结果写入另一个容器。
        swap:                     交换存储在两个对象中的值。
        swap_range:               将指定范围内的元素与另一个序列元素值进行交换。
        unique:                   清除序列中重复元素,和remove类似,它也不能真正删除元素。重载版本使用自定义比较操作。
        unique_copy:              与unique类似,不过把结果输出到另一个容器。
     
        <四>排列组合算法(2个):提供计算给定集合按一定顺序的所有可能排列组合
        next_permutation:         取出当前范围内的排列,并重新排序为下一个排列。重载版本使用自定义的比较操作。
        prev_permutation:         取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。
     

        <五>算术算法(4个)
        accumulate:               iterator对标识的序列段元素之和,加到一个由val指定的初始值上。重载版本不再做加法,而是传进来的二元操作符被应用到元素上。
        partial_sum:              创建一个新序列,其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法。
        inner_product:            对两个序列做内积(对应元素相乘,再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作。
        adjacent_difference:      创建一个新序列,新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。
     
        <六>生成和异变算法(6个)
        fill:                     将输入值赋给标志范围内的所有元素。
        fill_n:                   将输入值赋给first到first+n范围内的所有元素。
        for_each:                 用指定函数依次对指定范围内所有元素进行迭代访问,返回所指定的函数类型。该函数不得修改序列中的元素。
        generate:                 连续调用输入的函数来填充指定的范围。
        generate_n:               与generate函数类似,填充从指定iterator开始的n个元素。
        transform:                将输入的操作作用与指定范围内的每个元素,并产生一个新的序列。重载版本将操作作用在一对元素上,另外一个元素来自输入的另外一个序列。结果输出到指定容器。
     

        <七>关系算法(8个)
        equal:                    如果两个序列在标志范围内元素都相等,返回true。重载版本使用输入的操作符代替默认的等于操作符。
        includes:                 判断第一个指定范围内的所有元素是否都被第二个范围包含,使用底层元素的<操作符,成功返回true。重载版本使用用户输入的函数。
        lexicographical_compare:  比较两个序列。重载版本使用用户自定义比较操作。
        max:                      返回两个元素中较大一个。重载版本使用自定义比较操作。
        max_element:              返回一个ForwardIterator,指出序列中最大的元素。重载版本使用自定义比较操作。
        min:                      返回两个元素中较小一个。重载版本使用自定义比较操作。
        min_element:              返回一个ForwardIterator,指出序列中最小的元素。重载版本使用自定义比较操作。
        mismatch:                 并行比较两个序列,指出第一个不匹配的位置,返回一对iterator,标志第一个不匹配元素位置。如果都匹配,返回每个容器的last。重载版本使用自定义的比较操作。
     

        <八>集合算法(4个)
        set_union:                构造一个有序序列,包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。
        set_intersection:         构造一个有序序列,其中元素在两个序列中都存在。重载版本使用自定义的比较操作。
        set_difference:           构造一个有序序列,该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。
        set_symmetric_difference: 构造一个有序序列,该序列取两个序列的对称差集(并集-交集)。
     

       <九>堆算法(4个)
        make_heap:                把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。
        pop_heap:                 并不真正把最大元素从堆中弹出,而是重新排序堆。它把first和last-1交换,然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop_back进行真正的删除。重载版本使用自定义的比较操作。
        push_heap:                假设first到last-1是一个有效堆,要被加入到堆的元素存放在位置last-1,重新生成堆。在指向该函数前,必须先把元素插入容器后。重载版本使用指定的比较操作。
        sort_heap:                对指定范围内的序列重新排序,它假设该序列是个有序堆。重载版本使用自定义比较操作。

     

    4.适配器

    STL提供了三个容器适配器:queue、priority_queue、stack。这些适配器都是包装了vector、list、deque中某个顺序容器的包装器。注意:适配器没有提供迭代器,也不能同时插入或删除多个元素。下面对各个适配器进行概括总结。


    (1)stack用法

    #include <stack>
    template < typename T, typename Container=deque > class stack;

    可以使用三个标准顺序容器vecotr、deque(默认)、list中的任何一个作为stack的底层模型。

    bool stack<T>::empty()                               //判断堆栈是否为空
    void stack<T>::pop()                                 //弹出栈顶数据
    stack<T>::push(T x)                                  //压入一个数据
    stack<T>::size_type stack<T>::size()                 //返回堆栈长度
    T stack<T>::top()                                    //得到栈顶数据

     代码示例:

    stack<int> intDequeStack;  
    stack<int,vector<int>> intVectorStack;  
    stack<int,list<int>> intListStack; 

     


    (2)queue用法

    #include <queue>
    template<typename T, typename Container = deque<T> > class  queue;

    第一个参数指定要在queue中存储的类型,第二个参数规定queue适配的底层容器,可供选择的容器只有dequeue和list。对大多数用途使用默认的dequeue。

    复制代码
    queue<T>::push(T x)
    void queue<T>::pop()
    T queue<T>::back()
    T queue<T>::front()
    queue<T>::size_type 
    queue<T>::size()
    bool queue<T>::empty()
    复制代码

    代码示例:

    queue<int> intDequeQueue;    
    queue<int,list<int>> intListQueue;

     


    (3)priority_queue用法

    #include <queue>
    template <typename T, typename Container = vector<T>, typename Compare = less<T> > class priority_queue;

    priority_queue也是一个队列,其元素按有序顺序排列。其不采用严格的FIFO顺序,给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级,那么它们在队列中的顺序就遵循FIFO语义。默认适配的底层容器是vector,也可以使用deque,list不能用,因为priority_queue要求能对元素随机访问以便进行排序。

    复制代码
    priority_queue<T>::push(T x)
    void priority_queue<T>::pop()
    T priority_queue<T>::top()
    priority_queue<T>::size_type 
    priority_queue<T>::size()
    bool priority_queue<T>::empty()
    复制代码

    代码示例:

    priority_queue< int, vector<int>, greater<int> >
    priority_queue< int, list<int>, greater<int> >

     

    标准库默认使用元素类型的<操作符来确定它们之间的优先级关系,用法有三:(下文转自http://www.cnblogs.com/vvilp/articles/1504436.html)

    优先队列第一种用法,通过默认使用的<操作符可知在整数中元素大的优先级高。

    priority_queue<int> qi; 

    示例中输出结果为:9 6 5 3 2

    优先队列第二种用法,建立priority_queue时传入一个比较函数,使用functional.h函数对象作为比较函数。

    priority_queue<int, vector<int>, greater<int> >qi2;

    示例2中输出结果为:2 3 5 6 9

    优先队列第三种用法,是自定义优先级。

    复制代码
    struct node 
    {
         friend bool operator< (node n1, node n2)
         {
             return n1.priority < n2.priority;
         } 
         int priority;
         int value; 
    }; 
    priority_queue<node> qn; 
    复制代码

    在示例3中输出结果为:

    优先级  值

    9          5

    8          2

    6          1

    2          3

    1          4

    在该结构中,value为值,priority为优先级。通过自定义operator<操作符来比较元素中的优先级。注意:必须是自定义<操作符才行,把上述的结构中的<操作符改成>编译不通过。


    展开全文
  • 【C/C++】STL详解

    万次阅读 多人点赞 2019-08-17 08:39:13
    学校并未教授C++, 当初接触的C++的STL, 也是皮毛而已。 结合对Java的集合框架等内容的认识,回顾这部分内容,收获很大。 文章目录概述STL六大组件简介三大组件介绍1. 容器2. 算法3. 迭代器常用容器1. string容器...

    学校并未教授C++, 当初接触的C++的STL, 也是皮毛而已。

    结合对Java的集合框架等内容的认识,回顾这部分内容,收获很大。


    概述

    长久以来,软件界一直希望建立一种可重复利用的东西,以及一种得以制造出”可重复运用的东西”的方法,从函数(functions),类别(classes),函数库(function libraries),类别库(class libraries)、各种组件,从模块化设计,到面向对象(object oriented ),为的就是复用性的提升。

    复用性必须建立在某种标准之上。但是在许多环境下,就连软件开发最基本的数据结构(data structures) 和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作,竟然是为了完成前人已经完成而自己手上并未拥有的程序代码,这不仅是人力资源的浪费,也是挫折与痛苦的来源。

    为了建立数据结构和算法的一套标准,并且降低他们之间的耦合关系,以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。

    STL(Standard Template Library,标准模板库),是惠普实验室开发的一系列软件的统称。现在主要出现在 c++中,但是在引入 c++之前该技术已经存在很长时间了。

    STL 从广义上分为: 容器(container) 算法(algorithm) 迭代器(iterator)。

    容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数,这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。

    STL(Standard Template Library)标准模板库,在我们 c++标准程序库中隶属于 STL 的占到了 80%以上。


    STL六大组件简介

    STL提供了六大组件,彼此之间可以组合套用,这六大组件分别是:容器算法迭代器仿函数适配器(配接器)空间配置器

    容器:各种数据结构,如vector、list、deque、set、map等,用来存放数据,从实现角度来看,STL容器是一种class template。

    算法:各种常用的算法,如sort、find、copy、for_each。从实现的角度来看,STL算法是一种function tempalte.

    迭代器:扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

    仿函数:行为类似函数,可作为算法的某种策略。从实现角度来看,仿函数是一种重载了operator()的class 或者class template

    适配器:一种用来修饰容器或者仿函数或迭代器接口的东西。

    空间配置器:负责空间的配置与管理。从实现角度看,配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

    STL六大组件的交互关系,容器通过空间配置器取得数据存储空间,算法通过迭代器存储容器中的内容,仿函数可以协助算法完成不同的策略的变化,适配器可以修饰仿函数。


    STL的优点很明显了

    • STL 是 C++的一部分,因此不用额外安装什么,它被内建在你的编译器之内。
    • STL 的一个重要特性是将数据和操作分离。数据由容器类别加以管理,操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作
    • 程序员可以不用思考 STL 具体的实现过程,只要能够熟练使用 STL 就 OK 了。这样他们就可以把精力放在程序开发的别的方面。
    • STL 具有高可重用性,高性能,高移植性,跨平台的优点。
      • 高可重用性:STL 中几乎所有的代码都采用了模板类和模版函数的方式实现,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
      • 高性能:如 map 可以高效地从十万条记录里面查找出指定的记录,因为 map 是采用红黑树的变体实现的。
      • 高移植性:如在项目 A 上用 STL 编写的模块,可以直接移植到项目 B 上。

    三大组件介绍

    1. 容器

    几乎可以说,任何特定的数据结构都是为了实现某种特定的算法。STL容器就是将运用最广泛的一些数据结构实现出来。
    常用的数据结构:数组(array) , 链表(list), tree(),(stack), 队列(queue), 集合(set),映射表(map), 根据数据在容器中的排列特性,这些数据分为序列式容器和关联式容器两种。

    • 序列式容器强调值的排序,序列式容器中的每个元素均有固定的位置,除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。
    • 关联式容器是非线性的树结构,更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系,也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是:在值中选择一个值作为关键字key,这个关键字对值起到索引的作用,方便查找。Set/multiset容器 Map/multimap容器

    2. 算法

    算法,问题的解法,以有限的步骤,解决逻辑或数学上的问题。

    我们所编写的每个程序都是一个算法,其中的每个函数也都是一个算法,毕竟它们都是用来解决或大或小的逻辑问题或数学问题。STL收录的算法经过了数学上的效能分析与证明,是极具复用价值的,包括常用的排序,查找等等。特定的算法往往搭配特定的数据结构,算法与数据结构相辅相成。

    算法分为:质变算法和非质变算法。

    • 质变算法:是指运算过程中会更改区间内的元素的内容。例如拷贝,替换,删除等等
    • 非质变算法:是指运算过程中不会更改区间内的元素内容,例如查找、计数、遍历、寻找极值等等

    3. 迭代器

    迭代器(iterator)是一种抽象的设计概念,现实程序语言中并没有直接对应于这个概念的实物。 在<<Design Patterns>>一书中提供了23种设计模式的完整描述, 其中iterator模式定义如下:提供一种方法,使之能够依序寻访某个容器所含的各个元素,而又无需暴露该容器的内部表示方式。

    迭代器的设计思维-STL的关键所在,STL的中心思想在于将容器(container)和算法(algorithms)分开,彼此独立设计,最后再一贴胶着剂将他们撮合在一起。

    从技术角度来看,容器和算法的泛型化并不困难,c++的class template和function template可分别达到目标,如果设计出两这个之间的良好的胶着剂,才是大难题。

    迭代器的种类:

    迭代器功能描述
    输入迭代器提供对数据的只读访问只读,支持++、==、!=
    输出迭代器提供对数据的只写访问只写,支持++
    前向迭代器提供读写操作,并能向前推进迭代器读写,支持++、==、!=
    双向迭代器提供读写操作,并能向前和向后操作读写,支持++、–,
    随机访问迭代器提供读写操作,并能以跳跃的方式访问容器的任意数据,是功能最强的迭代器读写,支持++、–、[n]、-n、<、<=、>、>=

    演示

    #define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    //STL 中的容器 算法 迭代器
    void test01(){
    	vector<int> v; //STL 中的标准容器之一 :动态数组
    	v.push_back(1); //vector 容器提供的插入数据的方法
    	v.push_back(5);
    	v.push_back(3);
    	v.push_back(7);
    	//迭代器
    	vector<int>::iterator pStart = v.begin(); //vector 容器提供了 begin()方法 返回指向第一个元素的迭代器
    	vector<int>::iterator pEnd = v.end(); //vector 容器提供了 end()方法 返回指向最后一个元素下一个位置的迭代器
    	//通过迭代器遍历
    	while (pStart != pEnd){
    		cout << *pStart << " ";
    		pStart++;
    	}
    	cout << endl;
    	//算法 count 算法 用于统计元素的个数
    	int n = count(pStart, pEnd, 5);
    	cout << "n:" << n << endl;
    }
    //STL 容器不单单可以存储基础数据类型,也可以存储类对象
    class Teacher
    {
    public:
    	Teacher(int age) :age(age){};
    	~Teacher(){};
    public:
    	int age;
    };
    void test02(){
    	vector<Teacher> v; //存储 Teacher 类型数据的容器
    	Teacher t1(10), t2(20), t3(30);
    	v.push_back(t1);
    	v.push_back(t2);
    	v.push_back(t3);
    	vector<Teacher>::iterator pStart = v.begin();
    	vector<Teacher>::iterator pEnd = v.end();
    	//通过迭代器遍历
    	while (pStart != pEnd){
    		cout << pStart->age << " ";
    		pStart++;
    	}
    	cout << endl;
    }
    //存储 Teacher 类型指针
    void test03(){
    	vector<Teacher*> v; //存储 Teacher 类型指针
    	Teacher* t1 = new Teacher(10);
    	Teacher* t2 = new Teacher(20);
    	Teacher* t3 = new Teacher(30);
    	v.push_back(t1);
    	v.push_back(t2);
    	v.push_back(t3);
    	//拿到容器迭代器
    	vector<Teacher*>::iterator pStart = v.begin();
    	vector<Teacher*>::iterator pEnd = v.end();
    	//通过迭代器遍历
    	while (pStart != pEnd){
    		cout << (*pStart)->age << " ";
    		pStart++;
    	}
    	cout << endl;
    }
    //容器嵌套容器 难点
    void test04()
    {
    	vector< vector<int> > v;
    	vector<int>v1;
    	vector<int>v2;
    	vector<int>v3;
    
    	for (int i = 0; i < 5;i++)
    	{
    		v1.push_back(i);
    		v2.push_back(i * 10);
    		v3.push_back(i * 100);
    	}
    	v.push_back(v1);
    	v.push_back(v2);
    	v.push_back(v3);
    
    	for (vector< vector<int> >::iterator it = v.begin(); it != v.end();it++)
    	{
    		for (vector<int>::iterator subIt = (*it).begin(); subIt != (*it).end(); subIt ++)
    		{
    			cout << *subIt << " ";
    		}
    		cout << endl;
    	}
    } 
    int main(){
    	//test01();
    	//test02();
    	//test03();
    	test04();
    	system("pause");
    	return EXIT_SUCCESS;
    }
    

    常用容器

    1. string容器

    string容器基本概念

    C风格字符串(以空字符结尾的字符数组)太过复杂难于掌握,不适合大程序的开发,所以C++标准库定义了一种string类,定义在头文件<string>。
    String和c风格字符串对比:

    • Char*是一个指针,String是一个类
      string封装了char*,管理这个字符串,是一个char*型的容器。
    • String封装了很多实用的成员方法
      查找find,拷贝copy,删除delete 替换replace,插入insert
    • 不用考虑内存释放和越界
      string管理char*所分配的内存。每一次string的复制,取值都由string类负责维护,不用担心复制越界和取值越界等。

    string容器常用操作

    string 构造函数

    string();//创建一个空的字符串 例如: string str;      
    string(const string& str);//使用一个string对象初始化另一个string对象
    string(const char* s);//使用字符串s初始化
    string(int n, char c);//使用n个字符c初始化 
    

    string基本赋值操作

    string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
    string& operator=(const string &s);//把字符串s赋给当前的字符串
    string& operator=(char c);//字符赋值给当前的字符串
    string& assign(const char *s);//把字符串s赋给当前的字符串
    string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
    string& assign(const string &s);//把字符串s赋给当前字符串
    string& assign(int n, char c);//用n个字符c赋给当前字符串
    string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
    

    string存取字符操作

    char& operator[](int n);//通过[]方式取字符
    char& at(int n);//通过at方法获取字符
    

    string拼接操作

    string& operator+=(const string& str);//重载+=操作符
    string& operator+=(const char* str);//重载+=操作符
    string& operator+=(const char c);//重载+=操作符
    string& append(const char *s);//把字符串s连接到当前字符串结尾
    string& append(const char *s, int n);//把字符串s的前n个字符连接到当前字符串结尾
    string& append(const string &s);//同operator+=()
    string& append(const string &s, int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
    string& append(int n, char c);//在当前字符串结尾添加n个字符c
    

    string查找和替换

    int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
    int find(const char* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
    int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
    int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
    int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
    int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
    int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
    int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
    string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
    string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s
    

    string比较操作

    /*
    compare函数在>时返回 1,<时返回 -1,==时返回 0。
    比较区分大小写,比较时参考字典顺序,排越前面的越小。
    大写的A比小写的a小。
    */
    int compare(const string &s) const;//与字符串s比较
    int compare(const char *s) const;//与字符串s比较
    

    string子串

    string substr(int pos = 0, int n = npos) const;//返回由pos开始的n个字符组成的字符串
    

    string插入和删除操作

    string& insert(int pos, const char* s); //插入字符串
    string& insert(int pos, const string& str); //插入字符串
    string& insert(int pos, int n, char c);//在指定位置插入n个字符c
    string& erase(int pos, int n = npos);//删除从Pos开始的n个字符 
    

    string和c-style字符串转换

    //string 转 char*
    string str = "it";
    const char* cstr = str.c_str();
    //char* 转 string 
    char* s = "it";
    string str(s);
    

    在c++中存在一个从const char*到string的隐式类型转换,却不存在从一个string对象到C_string的自动类型转换。对于string类型的字符串,可以通过c_str()函数返回string对象对应的C_string.

    通常,程序员在整个程序中应坚持使用string类对象,直到必须将内容转化为char*时才将其转换为C_string.

    为了修改string字符串的内容,下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后,可能发生错误.

    string s = "abcdefg";
    	char& a = s[2];
    	char& b = s[3];
    
    	a = '1';
    	b = '2';
    
    	cout << s << endl;
    	cout << (int*)s.c_str() << endl;
    
    	s = "pppppppppppppppppppppppp";
    
    	//a = '1';
    	//b = '2';
    
    	cout << s << endl;
    	cout << (int*)s.c_str() << endl;
    

    2. vector容器

    vector容器基本概念

    vector的数据安排以及操作方式,与array非常相似,两者的唯一差别在于空间的运用的灵活性。

    Array是静态空间,一旦配置了就不能改变,要换大一点或者小一点的空间,可以,一切琐碎得由自己来,首先配置一块新的空间,然后将旧空间的数据搬往新空间,再释放原来的空间。

    Vector是动态空间,随着元素的加入,它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们再也不必害怕空间不足而一开始就要求一个大块头的array了。

    Vector的实现技术,关键在于其对大小的控制以及重新配置时的数据移动效率,一旦vector旧空间满了,如果客户每新增一个元素,vector内部只是扩充一个元素的空间,实为不智,因为所谓的扩充空间(不论多大),一如刚所说,是”配置新空间-数据移动-释放旧空间”的大工程,时间成本很高,应该加入某种未雨绸缪的考虑,稍后我们便可以看到vector的空间配置策略。

    在这里插入图片描述

    vector迭代器

    Vector维护一个线性空间,所以不论元素的型别如何,普通指针都可以作为vector的迭代器,因为vector迭代器所需要的操作行为,如operaroe*, operator->, operator++, operator–, operator+, operator-, operator+=, operator-=, 普通指针天生具备。

    Vector支持随机存取,而普通指针正有着这样的能力。所以vector提供的是随机访问迭代器(Random Access Iterators).

    根据上述描述,如果我们写如下的代码:

    Vector<int>::iterator it1;
    Vector<Teacher>::iterator it2;
    

    it1的型别其实就是Int*,it2的型别其实就是Teacher*.

    #define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    using namespace std;
    
    int main(){
    
    	vector<int> v;
    	for (int i = 0; i < 10;i ++){
    		v.push_back(i);
    		cout << v.capacity() << endl;  // v.capacity()容器的容量
    	}
    
    
    	system("pause");
    	return EXIT_SUCCESS;
    }
    

    vector的数据结构

    Vector所采用的数据结构非常简单,线性连续空间,它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围,并以迭代器_Myend指向整块连续内存空间的尾端。

    为了降低空间配置时的速度成本,vector实际配置的大小可能比客户端需求大一些,以备将来可能的扩充,这边是容量的概念。换句话说,一个vector的容量永远大于或等于其大小,一旦容量等于大小,便是满载,下次再有新增元素,整个vector容器就得另觅居所。

    所谓动态增加大小,并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间),而是一块更大的内存空间,然后将原数据拷贝新空间,并释放原空间。因此,对vector的任何操作,一旦引起空间的重新配置,指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误,务必小心。

    vector常用API操作

    vector构造函数

    vector<T> v; //采用模板实现类实现,默认构造函数
    vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
    vector(n, elem);//构造函数将n个elem拷贝给本身。
    vector(const vector &vec);//拷贝构造函数。
    
    //例子 使用第二个构造函数 我们可以...
    int arr[] = {2,3,4,1,9};
    vector<int> v1(arr, arr + sizeof(arr) / sizeof(int)); 
    

    vector常用赋值操作

    assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
    assign(n, elem);//将n个elem拷贝赋值给本身。
    vector& operator=(const vector  &vec);//重载等号操作符
    swap(vec);// 将vec与本身的元素互换。
    

    vector大小操作

    size();//返回容器中元素的个数
    empty();//判断容器是否为空
    resize(int num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
    resize(int num, elem);//重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长>度的元素被删除。
    capacity();//容器的容量
    reserve(int len);//容器预留len个元素长度,预留位置不初始化,元素不可访问。
    

    vector数据存取操作

    at(int idx); //返回索引idx所指的数据,如果idx越界,抛出out_of_range异常。
    operator[];//返回索引idx所指的数据,越界时,运行直接报错
    front();//返回容器中第一个数据元素
    back();//返回容器中最后一个数据元素
    

    vector插入和删除操作

    insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
    push_back(ele); //尾部插入元素ele
    pop_back();//删除最后一个元素
    erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
    erase(const_iterator pos);//删除迭代器指向的元素
    clear();//删除容器中所有元素
    

    vector 小demo: 巧用swap,收缩内存空间

    #define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    using namespace std;
    
    int main(){
    
    	vector<int> v;
    	for (int i = 0; i < 100000;i ++){
    		v.push_back(i);
    	}
    
    	cout << "capacity:" << v.capacity() << endl;
    	cout << "size:" << v.size() << endl;
    
    	//此时 通过resize改变容器大小
    	v.resize(10);
    
    	cout << "capacity:" << v.capacity() << endl;
    	cout << "size:" << v.size() << endl;
    
    	//容量没有改变
    	vector<int>(v).swap(v);
    
    	cout << "capacity:" << v.capacity() << endl;
    	cout << "size:" << v.size() << endl;
    
    
    	system("pause");
    	return EXIT_SUCCESS;
    }
    

    reserve预留空间

    #define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<vector>
    using namespace std;
    
    int main(){
    
    	vector<int> v;
    
    	//预先开辟空间
    	v.reserve(100000);
    
    	int* pStart = NULL;
    	int count = 0;
    	for (int i = 0; i < 100000;i ++){
    		v.push_back(i);
    		if (pStart != &v[0]){
    			pStart = &v[0];
    			count++;
    		}
    	}
    
    	cout << "count:" << count << endl;
    
    	system("pause");
    	return EXIT_SUCCESS;
    }
    

    3. deque容器

    deque容器基本概念

    Vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。

    所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受。

    在这里插入图片描述
    Deque容器和vector容器最大的差异,一在于deque允许使用常数项时间对头端进行元素的插入和删除操作。二在于deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像vector那样,”旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间”这样的事情在deque身上是不会发生的。也因此,deque没有必须要提供所谓的空间保留(reserve)功能.

    虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针,其复杂度和vector不是一个量级,这当然影响各个运算的层面。因此,除非有必要,我们应该尽可能的使用vector,而不是deque。对deque进行的排序操作,为了最高效率,可将deque先完整的复制到一个vector中,对vector容器进行排序,再复制回deque.

    deque容器实现原理

    Deque容器是连续的空间,至少逻辑上看来如此,连续现行空间总是令我们联想到array和vector,array无法成长,vector虽可成长,却只能向尾端成长,而且其成长其实是一个假象,事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤,如果不是vector每次配置新的空间时都留有余裕,其成长假象所带来的代价是非常昂贵的。

    Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间,便配置一段连续定量的空间,串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象,并提供随机存取的接口,避开了重新配置空间,复制,释放的轮回,代价就是复杂的迭代器架构。

    既然deque是分段连续内存空间,那么就必须有中央控制,维持整体连续的假象,数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。

    Deque采取一块所谓的map(注意,不是STL的map容器)作为主控,这里所谓的map是一小块连续的内存空间,其中每一个元素(此处成为一个结点)都是一个指针,指向另一段连续性内存空间,称作缓冲区。缓冲区才是deque的存储空间的主体。

    在这里插入图片描述

    deque常用API

    deque构造函数

    deque<T> deqT;//默认构造形式
    deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
    deque(n, elem);//构造函数将n个elem拷贝给本身。
    deque(const deque &deq);//拷贝构造函数。
    

    deque赋值操作

    assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
    assign(n, elem);//将n个elem拷贝赋值给本身。
    deque& operator=(const deque &deq); //重载等号操作符 
    swap(deq);// 将deq与本身的元素互换
    

    deque大小操作

    deque.size();//返回容器中元素的个数
    deque.empty();//判断容器是否为空
    deque.resize(num);//重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
    deque.resize(num, elem); //重新指定容器的长度为num,若容器变长,则以elem值填充新位置,如果容器变短,则末尾超出容器长度的元素被删除。
    

    deque双端插入和删除操作

    push_back(elem);//在容器尾部添加一个数据
    push_front(elem);//在容器头部插入一个数据
    pop_back();//删除容器最后一个数据
    pop_front();//删除容器第一个数据
    

    deque数据存取

    at(idx);//返回索引idx所指的数据,如果idx越界,抛出out_of_range。
    operator[];//返回索引idx所指的数据,如果idx越界,不抛出异常,直接出错。
    front();//返回第一个数据。
    back();//返回最后一个数据
    

    deque插入操作

    insert(pos,elem);//在pos位置插入一个elem元素的拷贝,返回新数据的位置。
    insert(pos,n,elem);//在pos位置插入n个elem数据,无返回值。
    insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据,无返回值。
    

    deque删除操作

    clear();//移除容器的所有数据
    erase(beg,end);//删除[beg,end)区间的数据,返回下一个数据的位置。
    erase(pos);//删除pos位置的数据,返回下一个数据的位置。
    

    4. stack容器

    stack容器基本概念

    stack是一种先进后出(First In Last Out,FILO)的数据结构,它只有一个出口,形式如图所示。stack容器允许新增元素,移除元素,取得栈顶元素,但是除了最顶端外,没有任何其他方法可以存取stack的其他元素。换言之,stack不允许有遍历行为。
    有元素推入栈的操作称为:push,将元素推出stack的操作称为pop.

    在这里插入图片描述

    stack没有迭代器

    Stack所有元素的进出都必须符合”先进后出”的条件,只有stack顶端的元素,才有机会被外界取用。Stack不提供遍历功能,也不提供迭代器。

    stack常用API

    stack构造函数

    stack<T> stkT;//stack采用模板类实现, stack对象的默认构造形式: 
    stack(const stack &stk);//拷贝构造函数
    

    stack赋值操作

    stack& operator=(const stack &stk);//重载等号操作符
    

    stack数据存取操作

    push(elem);//向栈顶添加元素
    pop();//从栈顶移除第一个元素
    top();//返回栈顶元素
    

    stack大小操作

    empty();//判断堆栈是否为空
    size();//返回堆栈的大小
    

    5. queue容器

    queue容器基本概念

    Queue是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口,queue容器允许从一端新增元素,从另一端移除元素。
    在这里插入图片描述

    queue没有迭代器

    Queue所有元素的进出都必须符合”先进先出”的条件,只有queue的顶端元素,才有机会被外界取用。Queue不提供遍历功能,也不提供迭代器。

    queue常用API

    queue构造函数

    queue<T> queT;//queue采用模板类实现,queue对象的默认构造形式:
    queue(const queue &que);//拷贝构造函数
    

    queue存取、插入和删除操作

    push(elem);//往队尾添加元素
    pop();//从队头移除第一个元素
    back();//返回最后一个元素
    front();//返回第一个元素
    

    queue赋值操作

    queue& operator=(const queue &que);//重载等号操作符
    

    queue大小操作

    empty();//判断队列是否为空
    size();//返回队列的大小
    

    6. list容器

    list容器基本概念
    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

    链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

    相较于vector的连续线性空间,list就显得负责许多,它的好处是每次插入或者删除一个元素,就是配置或者释放一个元素的空间。因此,list对于空间的运用有绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素的移除,list永远是常数时间。

    List和vector是两个最常被使用的容器。

    List容器是一个双向链表。
    在这里插入图片描述

    • 采用动态存储分配,不会造成内存浪费和溢出
    • 链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素
    • 链表灵活,但是空间和时间额外耗费较大

    list容器的迭代器

    List容器不能像vector一样以普通指针作为迭代器,因为其节点不能保证在同一块连续的内存空间上。

    List迭代器必须有能力指向list的节点,并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增,递减、取值、成员取用”是指,递增时指向下一个节点,递减时指向上一个节点,取值时取的是节点的数据值,成员取用时取的是节点的成员。

    由于list是一个双向链表,迭代器必须能够具备前移、后移的能力,所以list容器提供的是Bidirectional Iterators.

    List有一个重要的性质,插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的,因为vector的插入操作可能造成记忆体重新配置,导致原有的迭代器全部失效,甚至List元素的删除,也只有被删除的那个元素的迭代器失效,其他迭代器不受任何影响。

    list容器的数据结构

    list容器不仅是一个双向链表,而且还是一个循环的双向链表。

    #define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<list>
    using namespace std;
    
    int main(){
    
    	list<int> myList;
    	for (int i = 0; i < 10; i ++){
    		myList.push_back(i);
    	}
    
    	list<int>::_Nodeptr node =  myList._Myhead->_Next;
    
    	for (int i = 0; i < myList._Mysize * 2;i++){
    		cout << "Node:" << node->_Myval << endl;
    		node = node->_Next;
    		if (node == myList._Myhead){
    			node = node->_Next;
    		}
    	}
    
    	system("pause");
    	return EXIT_SUCCESS;
    }
    

    list常用API

    list构造函数

    list<T> lstT;//list采用采用模板类实现,对象的默认构造形式:
    list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
    list(n,elem);//构造函数将n个elem拷贝给本身。
    list(const list &lst);//拷贝构造函数。
    

    list数据元素插入和删除操作

    push_back(elem);//在容器尾部加入一个元素
    pop_back();//删除容器中最后一个元素
    push_front(elem);//在容器开头插入一个元素
    pop_front();//从容器开头移除第一个元素
    insert(pos,elem);//在pos位置插elem元素的拷贝,返回新数据的位置。
    insert(pos,n,elem);//在pos位置插入n个elem数据,无返回值。
    insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据,无返回值。
    clear();//移除容器的所有数据
    erase(beg,end);//删除[beg,end)区间的数据,返回下一个数据的位置。
    erase(pos);//删除pos位置的数据,返回下一个数据的位置。
    remove(elem);//删除容器中所有与elem值匹配的元素。
    

    list大小操作

    size();//返回容器中元素的个数
    empty();//判断容器是否为空
    resize(num);//重新指定容器的长度为num,
    若容器变长,则以默认值填充新位置。
    如果容器变短,则末尾超出容器长度的元素被删除。
    resize(num, elem);//重新指定容器的长度为num,
    若容器变长,则以elem值填充新位置。
    如果容器变短,则末尾超出容器长度的元素被删除。
    

    list赋值操作

    assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
    assign(n, elem);//将n个elem拷贝赋值给本身。
    list& operator=(const list &lst);//重载等号操作符
    swap(lst);//将lst与本身的元素互换。
    

    list数据的存取

    front();//返回第一个元素。
    back();//返回最后一个元素。
    

    list反转排序

    reverse();//反转链表,比如lst包含1,3,5元素,运行此方法后,lst就包含5,3,1元素。
    sort(); //list排序
    

    7. set/multiset容器

    set容器基本概念

    Set的特性是。所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值,set的元素即是键值又是实值。Set不允许两个元素有相同的键值。

    我们不可以通过set的迭代器改变set元素的值,因为set元素值就是其键值,关系到set元素的排序规则。如果任意改变set元素值,会严重破坏set组织。换句话说,set的iterator是一种const_iterator.

    set拥有和list某些相同的性质,当对容器中的元素进行插入操作或者删除操作的时候,操作之前所有的迭代器,在操作完成之后依然有效,被删除的那个元素的迭代器必然是一个例外。

    multiset容器基本概念

    multiset特性及用法和set完全相同,唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树.

    set常用API

    set构造函数

    set<T> st;//set默认构造函数:
    mulitset<T> mst; //multiset默认构造函数: 
    set(const set &st);//拷贝构造函数
    

    set赋值操作

    set& operator=(const set &st);//重载等号操作符
    swap(st);//交换两个集合容器
    

    set大小操作

    size();//返回容器中元素的数目
    empty();//判断容器是否为空
    

    set插入和删除操作

    insert(elem);//在容器中插入元素。
    clear();//清除所有元素
    erase(pos);//删除pos迭代器所指的元素,返回下一个元素的迭代器。
    erase(beg, end);//删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。
    erase(elem);//删除容器中值为elem的元素。
    

    set查找操作

    find(key);//查找键key是否存在,若存在,返回该键的元素的迭代器;若不存在,返回set.end();
    count(key);//查找键key的元素个数
    lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
    

    set的返回值 指定set排序规则举例:

    //插入操作返回值
    void test01(){
    
    	set<int> s;
    	pair<set<int>::iterator,bool> ret = s.insert(10);
    	if (ret.second){
    		cout << "插入成功:" << *ret.first << endl;
    	}
    	else{
    		cout << "插入失败:" << *ret.first << endl;
    	}
    	
    	ret = s.insert(10);
    	if(ret.second){
    		cout << "插入成功:" << *ret.first << endl;
    	}
    	else{
    		cout << "插入失败:" << *ret.first << endl;
    	}
    
    }
    
    struct MyCompare02{
    	bool operator()(int v1,int v2){
    		return v1 > v2;
    	}
    };
    
    //set从大到小
    void test02(){
    
    	srand((unsigned int)time(NULL));
    	//我们发现set容器的第二个模板参数可以设置排序规则,默认规则是less<_Kty>
    	set<int, MyCompare02> s;
    	for (int i = 0; i < 10;i++){
    		s.insert(rand() % 100);
    	}
    	
    	for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it ++){
    		cout << *it << " ";
    	}
    	cout << endl;
    }
    
    //set容器中存放对象
    class Person{
    public:
    	Person(string name,int age){
    		this->mName = name;
    		this->mAge = age;
    	}
    public:
    	string mName;
    	int mAge;
    };
    
    
    struct MyCompare03{
    	bool operator()(const Person& p1,const Person& p2){
    		return p1.mAge > p2.mAge;
    	}
    };
    
    void test03(){
    
    	set<Person, MyCompare03> s;
    
    	Person p1("aaa", 20);
    	Person p2("bbb", 30);
    	Person p3("ccc", 40);
    	Person p4("ddd", 50);
    
    	s.insert(p1);
    	s.insert(p2);
    	s.insert(p3);
    	s.insert(p4);
    
    	for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){
    		cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
    	}
    
    }
    

    对组(pair)

    对组(pair)将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可以分别用pair的两个公有属性first和second访问。
    类模板:template <class T1, class T2> struct pair.
    创建对组:

    //第一种方法创建一个对组
    pair<string, int> pair1(string("name"), 20);
    cout << pair1.first << endl; //访问pair第一个值
    cout << pair1.second << endl;//访问pair第二个值
    //第二种
    pair<string, int> pair2 = make_pair("name", 30);
    cout << pair2.first << endl;
    cout << pair2.second << endl;
    //pair=赋值
    pair<string, int> pair3 = pair2;
    cout << pair3.first << endl;
    cout << pair3.second << endl;
    

    8. map/multimap容器

    map/multimap基本概念

    Map的特性是,所有元素都会根据元素的键值自动排序。

    Map所有的元素都是pair,同时拥有实值和键值,pair的第一元素被视为键值,第二元素被视为实值,map不允许两个元素有相同的键值。

    我们不可以通过map的迭代器改变map的键值, 因为map的键值关系到map元素的排列规则,任意改变map键值将会严重破坏map组织。如果想要修改元素的实值,那么是可以的。

    Map和list拥有相同的某些性质,当对它的容器元素进行新增操作或者删除操作时,操作之前的所有迭代器,在操作完成之后依然有效,当然被删除的那个元素的迭代器必然是个例外。

    Multimap和map的操作类似,唯一区别multimap键值可重复。

    Map和multimap都是以红黑树为底层实现机制。

    map/multimap常用API

    map构造函数

    map<T1, T2> mapTT;//map默认构造函数: 
    map(const map &mp);//拷贝构造函数
    

    map赋值操作

    map& operator=(const map &mp);//重载等号操作符
    swap(mp);//交换两个集合容器
    

    map大小操作

    size();//返回容器中元素的数目
    empty();//判断容器是否为空
    

    map插入数据元素操作

    map.insert(...); //往容器插入元素,返回pair<iterator,bool>
    map<int, string> mapStu;
    // 第一种 通过pair的方式插入对象
    mapStu.insert(pair<int, string>(3, "小张"));
    // 第二种 通过pair的方式插入对象
    mapStu.inset(make_pair(-1, "校长"));
    // 第三种 通过value_type的方式插入对象
    mapStu.insert(map<int, string>::value_type(1, "小李"));
    // 第四种 通过数组的方式插入值
    mapStu[3] = "小刘";
    mapStu[5] = "小王";
    

    map删除操作

    clear();//删除所有元素
    erase(pos);//删除pos迭代器所指的元素,返回下一个元素的迭代器。
    erase(beg,end);//删除区间[beg,end)的所有元素 ,返回下一个元素的迭代器。
    erase(keyElem);//删除容器中key为keyElem的对组。
    

    map查找操作

    find(key);//查找键key是否存在,若存在,返回该键的元素的迭代器;/若不存在,返回map.end();
    count(keyElem);//返回容器中key为keyElem的对组个数。对map来说,要么是0,要么是1。对multimap来说,值可能大于1。
    lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
    

    multimap案例

    //公司今天招聘了5个员工,5名员工进入公司之后,需要指派员工在那个部门工作
    //人员信息有: 姓名 年龄 电话 工资等组成
    //通过Multimap进行信息的插入 保存 显示
    //分部门显示员工信息 显示全部员工信息
    
    #define _CRT_SECURE_NO_WARNINGS
    
    #include<iostream>
    #include<map>
    #include<string>
    #include<vector>
    using namespace std;
    
    //multimap 案例
    //公司今天招聘了 5 个员工,5 名员工进入公司之后,需要指派员工在那个部门工作
    //人员信息有: 姓名 年龄 电话 工资等组成
    //通过 Multimap 进行信息的插入 保存 显示
    //分部门显示员工信息 显示全部员工信息
    
    
    #define SALE_DEPATMENT 1 //销售部门
    #define DEVELOP_DEPATMENT 2 //研发部门
    #define FINACIAL_DEPATMENT 3 //财务部门
    #define ALL_DEPATMENT 4 //所有部门
    
    //员工类
    class person{
    public:
    	string name; //员工姓名
    	int age; //员工年龄
    	double salary; //员工工资
    	string tele; //员工电话
    };
    
    //创建5个员工
    void CreatePerson(vector<person>& vlist){
    
    	string seed = "ABCDE";
    	for (int i = 0; i < 5; i++){
    		person p;
    		p.name = "员工";
    		p.name += seed[i];
    		p.age = rand() % 30 + 20;
    		p.salary = rand() % 20000 + 10000;
    		p.tele = "010-8888888";
    		vlist.push_back(p);
    	}
    
    }
    
    //5名员工分配到不同的部门
    void PersonByGroup(vector<person>& vlist, multimap<int, person>& plist){
    
    
    	int operate = -1; //用户的操作
    
    	for (vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){
    
    		cout << "当前员工信息:" << endl;
    		cout << "姓名:" << it->name << " 年龄:" << it->age << " 工资:" << it->salary << " 电话:" << it->tele << endl;
    		cout << "请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务部门):" << endl;
    		scanf("%d", &operate);
    
    		while (true){
    
    			if (operate == SALE_DEPATMENT){  //将该员工加入到销售部门
    				plist.insert(make_pair(SALE_DEPATMENT, *it));
    				break;
    			}
    			else if (operate == DEVELOP_DEPATMENT){
    				plist.insert(make_pair(DEVELOP_DEPATMENT, *it));
    				break;
    			}
    			else if (operate == FINACIAL_DEPATMENT){
    				plist.insert(make_pair(FINACIAL_DEPATMENT, *it));
    				break;
    			}
    			else{
    				cout << "您的输入有误,请重新输入(1 销售部门, 2 研发部门, 3 财务部门):" << endl;
    				scanf("%d", &operate);
    			}
    
    		}
    
    	}
    	cout << "员工部门分配完毕!" << endl;
    	cout << "***********************************************************" << endl;
    
    }
    
    //打印员工信息
    void printList(multimap<int, person>& plist, int myoperate){
    
    	if (myoperate == ALL_DEPATMENT){
    		for (multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){
    			cout << "姓名:" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话:" << it->second.tele << endl;
    		}
    		return;
    	}
    
    	multimap<int, person>::iterator it = plist.find(myoperate);
    	int depatCount = plist.count(myoperate);
    	int num = 0;
    	if (it != plist.end()){
    		while (it != plist.end() && num < depatCount){
    			cout << "姓名:" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话:" << it->second.tele << endl;
    			it++;
    			num++;
    		}
    	}
    }
    
    //根据用户操作显示不同部门的人员列表
    void ShowPersonList(multimap<int, person>& plist, int myoperate){
    
    	switch (myoperate)
    	{
    	case SALE_DEPATMENT:
    		printList(plist, SALE_DEPATMENT);
    		break;
    	case DEVELOP_DEPATMENT:
    		printList(plist, DEVELOP_DEPATMENT);
    		break;
    	case FINACIAL_DEPATMENT:
    		printList(plist, FINACIAL_DEPATMENT);
    		break;
    	case ALL_DEPATMENT:
    		printList(plist, ALL_DEPATMENT);
    		break;
    	}
    }
    
    //用户操作菜单
    void PersonMenue(multimap<int, person>& plist){
    
    	int flag = -1;
    	int isexit = 0;
    	while (true){
    		cout << "请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4 所有部门, 0退出):" << endl;
    		scanf("%d", &flag);
    
    		switch (flag)
    		{
    		case SALE_DEPATMENT:
    			ShowPersonList(plist, SALE_DEPATMENT);
    			break;
    		case DEVELOP_DEPATMENT:
    			ShowPersonList(plist, DEVELOP_DEPATMENT);
    			break;
    		case FINACIAL_DEPATMENT:
    			ShowPersonList(plist, FINACIAL_DEPATMENT);
    			break;
    		case ALL_DEPATMENT:
    			ShowPersonList(plist, ALL_DEPATMENT);
    			break;
    		case 0:
    			isexit = 1;
    			break;
    		default:
    			cout << "您的输入有误,请重新输入!" << endl;
    			break;
    		}
    
    		if (isexit == 1){
    			break;
    		}
    	}
    
    }
    
    int main(){
    
    	vector<person>  vlist; //创建的5个员工 未分组
    	multimap<int, person> plist; //保存分组后员工信息
    
    	//创建5个员工
    	CreatePerson(vlist);
    	//5名员工分配到不同的部门
    	PersonByGroup(vlist, plist);
    	//根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表
    	PersonMenue(plist);
    
    	system("pause");
    	return EXIT_SUCCESS;
    }
    

    STL容器使用时机

    .vectordequelistsetmultisetmapmultimap
    典型内存结构单端数组双端数组双向链表二叉树二叉树二叉树二叉树
    可随机存取对key而言:不是
    元素搜寻速度非常慢对key而言:快对key而言:快
    元素安插移除尾端头尾两端任何位置----

    vector的使用场景:比如软件历史操作记录的存储,我们经常要查看历史记录,比如上一次的记录,上上次的记录,但却不会去删除记录,因为记录是事实的描述。

    deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。

    vector与deque的比较:
    一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置 却是不固定的。
    二:如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
    三:deque支持头部的快速插入与快速移除,这是deque的优点。

    list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。

    set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。

    map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。

    常用算法

    1. 函数对象

    重载函数调用操作符的类,其对象常称为函数对象(function object),即它们是行为类似函数的对象,也叫仿函数(functor),其实就是重载“()”操作符,使得类对象可以像函数那样调用。

    注意:

    1. 函数对象(仿函数)是一个类,不是一个函数。
    2. 函数对象(仿函数)重载了”() ”操作符使得它可以像函数一样调用。

    分类:假定某个类有一个重载的operator(),而且重载的operator()要求获取一个参数,我们就将这个类称为“一元仿函数”(unary functor);相反,如果重载的operator()要求获取两个参数,就将这个类称为“二元仿函数”(binary functor)。

    函数对象的作用:
    STL提供的算法往往都有两个版本,其中一个版本表现出最常用的某种运算,另一版本则允许用户通过template参数的形式来指定所要采取的策略。

    //函数对象是重载了函数调用符号的类
    class MyPrint
    {
    public:
    	MyPrint()
    	{
    		m_Num = 0;
    	}
    	int m_Num;
    
    public:
    	void operator() (int num)
    	{
    		cout << num << endl;
    		m_Num++;
    	}
    };
    
    //函数对象
    //重载了()操作符的类实例化的对象,可以像普通函数那样调用,可以有参数 ,可以有返回值
    void test01()
    {
    	MyPrint myPrint;
    	myPrint(20);
    
    }
    // 函数对象超出了普通函数的概念,可以保存函数的调用状态
    void test02()
    {
    	MyPrint myPrint;
    	myPrint(20);
    	myPrint(20);
    	myPrint(20);
    	cout << myPrint.m_Num << endl;
    }
    
    void doBusiness(MyPrint print,int num)
    {
    	print(num);
    }
    
    //函数对象作为参数
    void test03()
    {
    	//参数1:匿名函数对象
    	doBusiness(MyPrint(),30);
    }
    

    总结:
    1、函数对象通常不定义构造函数和析构函数,所以在构造和析构时不会发生任何问题,避免了函数调用的运行时问题。
    2、函数对象超出普通函数的概念,函数对象可以有自己的状态
    3、函数对象可内联编译,性能好。用函数指针几乎不可能
    4、模版函数对象使函数对象具有通用性,这也是它的优势之一

    2. 谓词

    谓词是指普通函数或重载的operator()返回值是bool类型的函数对象(仿函数)。如果operator接受一个参数,那么叫做一元谓词,如果接受两个参数,那么叫做二元谓词,谓词可作为一个判断式。

    class GreaterThenFive
    {
    public:
    	bool operator()(int num)
    	{
    		return num > 5;
    	}
    
    };
    //一元谓词
    void test01()
    {
    	vector<int> v;
    	for (int i = 0; i < 10;i ++)
    	{
    		v.push_back(i);
    	}
    	
    	 vector<int>::iterator it =  find_if(v.begin(), v.end(), GreaterThenFive());
    	 if (it == v.end())
    	 {
    		 cout << "没有找到" << endl;
    	 }
    	 else
    	 {
    		 cout << "找到了: " << *it << endl;
    	 }
    }
    
    //二元谓词
    class MyCompare
    {
    public:
    	bool operator()(int num1, int num2)
    	{
    		return num1 > num2;
    	}
    };
    
    void test02()
    {
    	vector<int> v;
    	v.push_back(10);
    	v.push_back(40);
    	v.push_back(20);
    	v.push_back(90);
    	v.push_back(60);
    
    	//默认从小到大
    	sort(v.begin(), v.end());
    	for (vector<int>::iterator it = v.begin(); it != v.end();it++)
    	{
    		cout << *it << " ";
    	}
    	cout << endl;
    	cout << "----------------------------" << endl;
    	//使用函数对象改变算法策略,排序从大到小
    	sort(v.begin(), v.end(),MyCompare());
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    	{
    		cout << *it << " ";
    	}
    	cout << endl;
    }
    

    3.内建函数对象

    STL内建了一些函数对象。分为:算数类函数对象,关系运算类函数对象,逻辑运算类仿函数。这些仿函数所产生的对象,用法和一般函数完全相同,当然我们还可以产生无名的临时对象来履行函数功能。使用内建函数对象,需要引入头文件

    #include<functional>
    

    6个算数类函数对象,除了negate是一元运算,其他都是二元运算。

    template<class T> T plus<T>//加法仿函数
    template<class T> T minus<T>//减法仿函数
    template<class T> T multiplies<T>//乘法仿函数
    template<class T> T divides<T>//除法仿函数
    template<class T> T modulus<T>//取模仿函数
    template<class T> T negate<T>//取反仿函数
    

    6个关系运算类函数对象,每一种都是二元运算。

    template<class T> bool equal_to<T>//等于
    template<class T> bool not_equal_to<T>//不等于
    template<class T> bool greater<T>//大于
    template<class T> bool greater_equal<T>//大于等于
    template<class T> bool less<T>//小于
    template<class T> bool less_equal<T>//小于等于
    

    逻辑运算类运算函数,not为一元运算,其余为二元运算。

    template<class T> bool logical_and<T>//逻辑与
    template<class T> bool logical_or<T>//逻辑或
    template<class T> bool logical_not<T>//逻辑非
    

    内建函数对象举例:

    //取反仿函数
    void test01()
    {
    	negate<int> n;
    	cout << n(50) << endl;
    }
    
    //加法仿函数
    void test02()
    {
    	plus<int> p;
    	cout << p(10, 20) << endl;
    }
    
    //大于仿函数
    void test03()
    {
    	vector<int> v;
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 10; i++){
    		v.push_back(rand() % 100);
    	}
    
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
    		cout << *it << " ";
    	}
    	cout << endl;
    	sort(v.begin(), v.end(), greater<int>());
    
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++){
    		cout << *it << " ";
    	}
    	cout << endl;
    
    }
    

    4. 函数对象适配器

    //函数适配器bind1st bind2nd
    //现在我有这个需求 在遍历容器的时候,我希望将容器中的值全部加上100之后显示出来,怎么做?
    //我们直接给函数对象绑定参数 编译阶段就会报错
    //for_each(v.begin(), v.end(), bind2nd(myprint(),100));
    //如果我们想使用绑定适配器,需要我们自己的函数对象继承binary_function 或者 unary_function
    //根据我们函数对象是一元函数对象 还是二元函数对象
    class MyPrint :public binary_function<int,int,void>
    {
    public:
    	void operator()(int v1,int v2) const
    	{
    		cout << "v1 = : " << v1 << " v2 = :" <<v2  << " v1+v2 = :" << (v1 + v2) << endl;	
    	}
    };
    //1、函数适配器
    void test01()
    {
    	vector<int>v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    	cout << "请输入起始值:" << endl;
    	int x;
    	cin >> x;
    
    	for_each(v.begin(), v.end(), bind1st(MyPrint(), x));
    	//for_each(v.begin(), v.end(), bind2nd( MyPrint(),x ));
    }
    //总结:  bind1st和bind2nd区别?
    //bind1st : 将参数绑定为函数对象的第一个参数
    //bind2nd : 将参数绑定为函数对象的第二个参数
    //bind1st bind2nd将二元函数对象转为一元函数对象
    
    
    class GreaterThenFive:public unary_function<int,bool>
    {
    public:
    	bool operator ()(int v) const
    	{
    		return v > 5;
    	}
    };
    
    //2、取反适配器
    void test02()
    {
    	vector <int> v;
    	for (int i = 0; i < 10;i++)
    	{
    		v.push_back(i);
    	}
    	
    // 	vector<int>::iterator it =  find_if(v.begin(), v.end(), GreaterThenFive()); //返回第一个大于5的迭代器
    //	vector<int>::iterator it = find_if(v.begin(), v.end(),  not1(GreaterThenFive())); //返回第一个小于5迭代器
    	//自定义输入
    	vector<int>::iterator it = find_if(v.begin(), v.end(), not1 ( bind2nd(greater<int>(),5)));
    	if (it == v.end())
    	{
    		cout << "没找到" << endl;
    	}
    	else
    	{
    		cout << "找到" << *it << endl;
    	}
    
    	//排序  二元函数对象
    	sort(v.begin(), v.end(), not2(less<int>()));
    	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
    
    }
    //not1 对一元函数对象取反
    //not2 对二元函数对象取反
    
    void MyPrint03(int v,int v2)
    {
    	cout << v + v2<< " ";
    }
    
    //3、函数指针适配器   ptr_fun
    void test03()
    {
    	vector <int> v;
    	for (int i = 0; i < 10; i++)
    	{
    		v.push_back(i);
    	}
    	// ptr_fun( )把一个普通的函数指针适配成函数对象
    	for_each(v.begin(), v.end(), bind2nd( ptr_fun( MyPrint03 ), 100));
    }
    
    
    //4、成员函数适配器
    class Person
    {
    public:
    	Person(string name, int age)
    	{
    		m_Name = name;
    		m_Age = age;
    	}
    
    	//打印函数
    	void ShowPerson(){
    		cout << "成员函数:" << "Name:" << m_Name << " Age:" << m_Age << endl;
    	}
    	void Plus100()
    	{
    		m_Age += 100;
    	}
    public:
    	string m_Name;
    	int m_Age;
    };
    
    void MyPrint04(Person &p)
    {
    	cout << "姓名:" <<  p.m_Name << " 年龄:" << p.m_Age << endl;
    
    };
    
    void test04()
    {
    	vector <Person>v;
    	Person p1("aaa", 10);
    	Person p2("bbb", 20);
    	Person p3("ccc", 30);
    	Person p4("ddd", 40);
    	v.push_back(p1);
    	v.push_back(p2);
    	v.push_back(p3);
    	v.push_back(p4);
    
    	//for_each(v.begin(), v.end(), MyPrint04);
    	//利用 mem_fun_ref 将Person内部成员函数适配
    	for_each(v.begin(), v.end(), mem_fun_ref(&Person::ShowPerson));
    // 	for_each(v.begin(), v.end(), mem_fun_ref(&Person::Plus100));
    // 	for_each(v.begin(), v.end(), mem_fun_ref(&Person::ShowPerson));
    }
    
    void test05(){
    
    	vector<Person*> v1;
    	//创建数据
    	Person p1("aaa", 10);
    	Person p2("bbb", 20);
    	Person p3("ccc", 30);
    	Person p4("ddd", 40);
    
    	v1.push_back(&p1);
    	v1.push_back(&p2);
    	v1.push_back(&p3);
    	v1.push_back(&p4);
    
    	for_each(v1.begin(), v1.end(), mem_fun(&Person::ShowPerson));
    }
    
    //如果容器存放的是对象指针,  那么用mem_fun
    //如果容器中存放的是对象实体,那么用mem_fun_ref
    

    算法概述

    算法主要是由头文件<algorithm><functional> <numeric>组成。
    <algorithm>是所有STL头文件中最大的一个,其中常用的功能涉及到比较,交换,查找,遍历,复制,修改,反转,排序,合并等…
    <numeric>体积很小,只包括在几个序列容器上进行的简单运算的模板函数.
    <functional> 定义了一些模板类,用以声明函数对象。

    1. 常用遍历算法

    /*
        遍历算法 遍历容器元素
    	@param beg 开始迭代器
    	@param end 结束迭代器
    	@param _callback  函数回调或者函数对象
    	@return 函数对象
    */
    for_each(iterator beg, iterator end, _callback);
    /*
    	transform算法 将指定容器区间元素搬运到另一容器中
    	注意 : transform 不会给目标容器分配内存,所以需要我们提前分配好内存
    	@param beg1 源容器开始迭代器
    	@param end1 源容器结束迭代器
    	@param beg2 目标容器开始迭代器
    	@param _cakkback 回调函数或者函数对象
    	@return 返回目标容器迭代器
    */
    transform(iterator beg1, iterator end1, iterator beg2, _callbakc)
    
    
    for_each:
    /*
    
    template<class _InIt,class _Fn1> inline
    void for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
    {
    	for (; _First != _Last; ++_First)
    		_Func(*_First);
    }
    
    */
    
    //普通函数
    void print01(int val){
    	cout << val << " ";
    }
    //函数对象
    struct print001{
    	void operator()(int val){
    		cout << val << " ";
    	}
    };
    
    //for_each算法基本用法
    void test01(){
    	
    	vector<int> v;
    	for (int i = 0; i < 10;i++){
    		v.push_back(i);
    	}
    
    	//遍历算法
    	for_each(v.begin(), v.end(), print01);
    	cout << endl;
    
    	for_each(v.begin(), v.end(), print001());
    	cout << endl;
    
    }
    
    struct print02{
    	print02(){
    		mCount = 0;
    	}
    	void operator()(int val){
    		cout << val << " ";
    		mCount++;
    	}
    	int mCount;
    };
    
    //for_each返回值
    void test02(){
    
    	vector<int> v;
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);
    	}
    
    	print02 p = for_each(v.begin(), v.end(), print02());
    	cout << endl;
    	cout << p.mCount << endl;
    }
    
    struct print03 : public binary_function<int, int, void>{
    	void operator()(int val,int bindParam) const{
    		cout << val + bindParam << " ";
    	}
    };
    
    //for_each绑定参数输出
    void test03(){
    	
    	vector<int> v;
    	for (int i = 0; i < 10; i++){
    		v.push_back(i);
    	}
    
    	for_each(v.begin(), v.end(), bind2nd(print03(),100));
    }
    
    
    transform:
    //transform 将一个容器中的值搬运到另一个容器中
    /*
    	template<class _InIt, class _OutIt, class _Fn1> inline 
    	_OutIt _Transform(_InIt _First, _InIt _Last,_OutIt _Dest, _Fn1 _Func)
    	{	
    
    		for (; _First != _Last; ++_First, ++_Dest)
    			*_Dest = _Func(*_First);
    		return (_Dest);
    	}
    
    	template<class _InIt1,class _InIt2,class _OutIt,class _Fn2> inline
    	_OutIt _Transform(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
    	{	
    		for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest)
    			*_Dest = _Func(*_First1, *_First2);
    		return (_Dest);
    	}
    */
    
    struct transformTest01{
    	int operator()(int val){
    		return val + 100;
    	}
    };
    struct print01{
    	void operator()(int val){
    		cout << val << " ";
    	}
    };
    void test01(){
    
    	vector<int> vSource;
    	for (int i = 0; i < 10;i ++){
    		vSource.push_back(i + 1);
    	}
    
    	//目标容器
    	vector<int> vTarget;
    	//给vTarget开辟空间
    	vTarget.resize(vSource.size());
    	//将vSource中的元素搬运到vTarget
    	vector<int>::iterator it = transform(vSource.begin(), vSource.end(), vTarget.begin(), transformTest01());
    	//打印
    	for_each(vTarget.begin(), vTarget.end(), print01()); cout << endl;
    	
    }
    
    //将容器1和容器2中的元素相加放入到第三个容器中
    struct transformTest02{
    	int operator()(int v1,int v2){
    		return v1 + v2;
    	}
    };
    void test02(){
    
    	vector<int> vSource1;
    	vector<int> vSource2;
    	for (int i = 0; i < 10; i++){
    		vSource1.push_back(i + 1);	
    	}
    
    	//目标容器
    	vector<int> vTarget;
    	//给vTarget开辟空间
    	vTarget.resize(vSource1.size());
    	transform(vSource1.begin(), vSource1.end(), vSource2.begin(),vTarget.begin(), transformTest02());
    	//打印
    	for_each(vTarget.begin(), vTarget.end(), print01()); cout << endl;
    }
    

    2. 常用查找算法

    /*
    	find算法 查找元素
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param value 查找的元素
    	@return 返回查找元素的位置
    */
    find(iterator beg, iterator end, value)
    /*
    	find_if算法 条件查找
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param  callback 回调函数或者谓词(返回bool类型的函数对象)
    	@return bool 查找返回true 否则false
    */
    find_if(iterator beg, iterator end, _callback);
    
    /*
    	adjacent_find算法 查找相邻重复元素
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param  _callback 回调函数或者谓词(返回bool类型的函数对象)
    	@return 返回相邻元素的第一个位置的迭代器
    */
    adjacent_find(iterator beg, iterator end, _callback);
    /*
    	binary_search算法 二分查找法
    	注意: 在无序序列中不可用
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param value 查找的元素
    	@return bool 查找返回true 否则false
    */
    bool binary_search(iterator beg, iterator end, value);
    /*
    	count算法 统计元素出现次数
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param  value回调函数或者谓词(返回bool类型的函数对象)
    	@return int返回元素个数
    */
    count(iterator beg, iterator end, value);
    /*
    	count算法 统计元素出现次数
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param  callback 回调函数或者谓词(返回bool类型的函数对象)
    	@return int返回元素个数
    */
    count_if(iterator beg, iterator end, _callback);
    

    3. 常用排序算法

    /*
    	merge算法 容器元素合并,并存储到另一容器中
    	@param beg1 容器1开始迭代器
    	@param end1 容器1结束迭代器
    	@param beg2 容器2开始迭代器
    	@param end2 容器2结束迭代器
    	@param dest  目标容器开始迭代器
    */
    merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
    /*
    	sort算法 容器元素排序
    	注意:两个容器必须是有序的
    	@param beg 容器1开始迭代器
    	@param end 容器1结束迭代器
    	@param _callback 回调函数或者谓词(返回bool类型的函数对象)
    */
    sort(iterator beg, iterator end, _callback)
    /*
    	sort算法 对指定范围内的元素随机调整次序
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    */
    random_shuffle(iterator beg, iterator end)
    /*
    	reverse算法 反转指定范围的元素
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    */
    reverse(iterator beg, iterator end)
    

    4. 常用拷贝和替换算法

    /*
    	copy算法 将容器内指定范围的元素拷贝到另一容器中
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param dest 目标起始迭代器
    */
    copy(iterator beg, iterator end, iterator dest)
    /*
    	replace算法 将容器内指定范围的旧元素修改为新元素
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param oldvalue 旧元素
    	@param oldvalue 新元素
    */
    replace(iterator beg, iterator end, oldvalue, newvalue)
    /*
    	replace_if算法 将容器内指定范围满足条件的元素替换为新元素
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param callback函数回调或者谓词(返回Bool类型的函数对象)
    	@param oldvalue 新元素
    */
    replace_if(iterator beg, iterator end, _callback, newvalue)
    /*
    	swap算法 互换两个容器的元素
    	@param c1容器1
    	@param c2容器2
    */
    swap(container c1, container c2)
    

    5. 常用算数生成算法

    /*
    	accumulate算法 计算容器元素累计总和
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param value累加值
    */
    accumulate(iterator beg, iterator end, value)
    /*
    	fill算法 向容器中添加元素
    	@param beg 容器开始迭代器
    	@param end 容器结束迭代器
    	@param value t填充元素
    */
    fill(iterator beg, iterator end, value)
    

    6. 常用集合算法

    /*
    	set_intersection算法 求两个set集合的交集
    	注意:两个集合必须是有序序列
    	@param beg1 容器1开始迭代器
    	@param end1 容器1结束迭代器
    	@param beg2 容器2开始迭代器
    	@param end2 容器2结束迭代器
    	@param dest  目标容器开始迭代器
    	@return 目标容器的最后一个元素的迭代器地址
    */
    set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
    /*
    	set_union算法 求两个set集合的并集
    	注意:两个集合必须是有序序列
    	@param beg1 容器1开始迭代器
    	@param end1 容器1结束迭代器
    	@param beg2 容器2开始迭代器
    	@param end2 容器2结束迭代器
    	@param dest  目标容器开始迭代器
    	@return 目标容器的最后一个元素的迭代器地址
    */
    set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
    /*
    	set_difference算法 求两个set集合的差集
    	注意:两个集合必须是有序序列
    	@param beg1 容器1开始迭代器
    	@param end1 容器1结束迭代器
    	@param beg2 容器2开始迭代器
    	@param end2 容器2结束迭代器
    	@param dest  目标容器开始迭代器
    	@return 目标容器的最后一个元素的迭代器地址
    */
    set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
    

    可能你觉得不够深入,想要深入的话, 看源码呗!

    展开全文
  • C++STL详解(MarkDown)

    2021-08-02 10:27:46
    C++STL详解(MarkDown)
  • C++ STL详解(建议收藏!!!) 本蒟蒻写这篇分享的目的一个是为了写一个归纳总结方便自己以后随时能够复习还有就是给那些对STL还不是很了解的萌新介绍一下什么是STL以及如何使用STL更高效偷懒地解题。本篇文章将会...

    本蒟蒻写这篇分享的目的一个是为了写一个归纳总结方便自己以后随时能够复习还有就是给那些对STL还不是很了解的萌新介绍一下什么是STL以及如何使用STL更高效偷懒地解题。本篇文章将会长期更新,欢迎大家一起监督学习,有错误的地方或者需要补充的欢迎在评论区留言哦~跳转至AcWing~

    一、什么是STL?

    STL(Standard Template Library,标准模板库),是惠普实验室开发的一系列软件的统称。现主要出现在C++中,STL从广义上分为:容器(container)、算法(algorithm)和迭代器(iterator)。STL几乎所有的代码都采用了模板类或者模板函数,这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。

    二、STL六大组件是什么?

    STL提供了六大组件,彼此之间可以组合套用,这六大组件分别是容器、算法、迭代器、仿函数、适配器、空间配置器。其中,在算法竞赛中用到最多的为容器、算法与迭代器

    • 容器(Container):STL容器为各种数据结构,如vectorstackqueuemapset等,用来存放数据,从实现角度来看,STL容器是一种class template
    • 算法(Algorithm):STL的算法多数定义在<algorithm>头文件中,其中包括了各种常用的算法,如sortfindcopyreverse等,从实现角度来看,STL算法是一种function template
    • 迭代器(Iterator):STL迭代器扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将opetator*opetator->operator++等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。
    • 仿函数(Functor):行为类似函数,可作为算法的某种策略,从实现角度来看,仿函数是一种重载了operator()class或者class template
    • 适配器(Adaptor):一种用来修饰容器或仿函数或迭代器接口的东西。
    • 空间配置器(Allocator):负责空间的配置与管理。从实现角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的class template

    三、STL容器详解

    相信很多人学习STL就是为了在比赛中能够更好地装B运用各种数据结构和算法,提高解题速度。确实,使用STL中的容器能够不需要自己手写定义各种数据结构,使用STL中的算法能够不需要自己手写实现各种基本算法,因此本部分对于算法巨巨们是最为重要的一部分,那么STL容器究竟有哪些呢?在做题中该如何使用呢?

    vector:又称变长数组,定义在<vector>头文件中,vector容器是动态空间,随着元素的加入,它的内部机制会自动扩充空间以容纳新的元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助。

    • vector的定义方式
    	vector<int> v;//定义一个vector,其中的元素为int类型
    	vector<int> v[N];//定义一个vector数组,其中有N个vector
    	vector<int> v(len);//定义一个长度为len的vector
    	vector<int> v(len, x);//定义一个长度为len的vector,初始化每个元素为x
    	vector<int> v2(v1);//用v1给v2赋值,v1的类型为vector
    	vector<int> v2(v1.begin(), v1.begin() + 3);//将v1中第0~2三个元素赋值给v2
    
    • vector的常用内置函数
        //vector中的常用内置函数
    	vector<int> v = { 1, 2, 3 };//初始化vector,v:{1, 2, 3}
    	vector<int>::iterator it = v.begin();//定义vector的迭代器,指向begin()
    
    	v.push_back(4);//在vector的尾部插入元素4,v:{1, 2, 3, 4}
    	v.pop_back();//删除vector的最后一个元素,v:{1, 2, 3}
    	v.size();//返回vector中元素的个数
    	v.empty();//返回vector是否为空,若为空则返回true否则返回false
    	v.front();//返回vector中的第一个元素
    	v.back();//返回vector中的最后一个元素
    	v.begin();//返回vector第一个元素的迭代器
    	v.end();//返回vector最后一个元素后一个位置的迭代器
    	v.clear();//清空vector
    	v.erase(v.begin());//删除迭代器it所指向的元素
    	v.insert(v.begin(), 1);//在迭代器it所指向的位置前插入元素1,返回插入元素的迭代器
    
    	//根据下标进行遍历
    	for (int i = 0; i < v.size(); i++)
    		cout << v[i] << ' ';
    	//使用迭代器遍历
    	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    		cout << *it << ' ';
    	//for_each遍历(C++11)
    	for (auto x : v)
    		cout << x << ' ';
    

    stack:又称,是一种后进先出(Last In First Out,LIFO)的数据结构,定义在<stack>头文件中,stack容器允许新增元素、移除元素、取得栈顶元素,但是除了最顶端以外,没有任何方法可以存取stack的其它元素,换言之,stack不允许有遍历行为

    • stack的定义方式
        stack<int> stk;//定义一个stack,其中元素的类型为int
        stack<int> stk[N];//定义一个stack数组,其中有N个stack
    
    • stack的常用内置函数
        //stack中的常用内置函数
        stack<int> stk;
    	stk.push(x);//在stack中插入元素x
    	stk.pop();//弹出stack的栈顶元素
    	stk.top();//返回stack的栈顶元素
    	stk.size();//返回stack中元素的个数
    	stk.empty();//返回stack是否为空,若为空则返回true否则返回false
    

    string:又称字符串,定义在<string>头文件中。C风格的字符串(以空字符结尾的字符数组)太过复杂难于掌握,因此C++标准库定义了一种string类。string玩得好,天梯和蓝桥拿个国奖真的有手就行,去年我刚大二的时候从零开始学算法,两个星期没学多少只学了string,校选拔就进前几了,后来的国赛也拿了点小奖然后ACM就被打爆(哭)。因此熟练地运用string还是很重要滴~

    • string的定义方式
    	string str;//定义一个空的字符串
    	string str[N];//定义一个string数组,其中有N个string
    	string str(5, 'a');//使用5个字符'a'初始化
    	string str("abc");//使用字符串初始化
    
    • string的常用内置函数
        //string中的常用内置函数
        string str("abcabc");
    	str.push_back('d');//在string尾部插入字符,"abcabcd"
    	str.pop_back();//删除string尾部的字符,"abcabc"
    	str.length();//返回string中字符的个数
    	str.size();//作用与length()相同
    	str.empty();//返回string是否为空,若为空返回true否则返回false
    	str.substr(1);//返回string中从下标为1开始至末尾的子串,"bc"
    	str.substr(0, 2);//返回string中从下标为0开始长度为2的子串,"ab"
    	str.insert(1, 2, 'x');//在下标为1的字符前插入2个字符'x',"axxbcabc"
    	str.insert(1, "yy");//在下标为1的字符前插入字符串"yy","ayyxxbcabc"
    	str.erase(1, 4);//删除从位置1开始的4个字符,"abcabc"
    	str.find('b');//返回字符'b'在string中第一次出现的位置,返回1
    	str.find('b', 2);//返回从位置2开始字符'b'在string中第一次出现的位置,返回4
    	str.find("bc");//同上,返回字符串第一次出现的位置,返回1
    	str.find("bc", 2);//返回4
    	str.rfind('b');//反向查找,原理同上,返回4
    	str.rfind('b', 3);//返回1
    	str.rfind("bc");//返回4
    	str.rfind("bc", 3);//返回1
    	str[0];//用下标访问string中的字符
    	cout << (str == str) << endl;//string可比较大小,按字典序
    
    • stringerase()remove()函数的用法
        //string中erase()与remove()的用法
    	string str1, str2, str3, str4, str5;
    	str1 = str2 = str3 = str4 = str5 = "I love AcWing! It's very funny!";
    	str1.erase(15);//删除[15,end())的所有元素,"I love AcWing!"
    	str2.erase(6, 11);//从第6个元素(包括)开始往后删除11个元素,"I love's very funny!"
    	str3.erase(str3.begin() + 2);//删除迭代器所指的元素,"I ove AcWing! It's very funny!"
    	str4.erase(str4.begin() + 7, str4.end() - 11);//删除[str4.begin()+7,str4.end()-11)的所有元素,"I love very funny!"
    	str5.erase(remove(str5.begin(), str5.end(), 'n'), str5.end());//删除[str5.begin(),str5.end())中所有字符'n',"I love AcWig! It's very fuy!"
    

    queue:又称队列,是一种先进先出(First In First Out,FIFO)的数据结构,定义在<queue>头文件中,queue容器允许从一端(称为队尾)新增元素(入队),从另一端(称为队头)移除元素(出队)。
    priority_queue:又称优先队列,同样定义在<queue>头文件中,与queue不同的地方在于我们可以自定义其中数据的优先级,优先级高的排在队列前面,优先出队。priority_queue具有queue的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它的本质是用实现的,因此可分为小根堆大根堆小根堆中较小的元素排在前面,大根堆中较大的元素排在前面。注意:创建priority_queue时默认是大根堆

    • queue的定义方式
    	queue<int> que;//定义一个queue,其中元素的类型为int
    	queue<int> que[N];//定义一个queue数组,其中有N个queue
    	priority_queue<int> bigHeap;//定义一个大根堆
    	priority_queue<int, vector<int>, greater<int> > smallHeap;//定义一个小根堆
    
    • queue的常用内置函数
        //queue中的常用内置函数
        queue<int> que;
        que.push(x);//在queue的队尾插入元素x
    	que.pop();//出队queue的队头元素
    	que.front();//返回queue的队头元素
    	que.back();//返回queue的队尾元素
    	que.size();//返回stack中元素的个数
    	que.empty();//返回stack是否为空,若为空则返回true否则返回false
    

    deque:又称双端队列,定义在<deque>头文件中,vector容器是单向开口的连续内存空间,deque则是一种双向开口的连续线性空间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然,vector也可以在头尾两端插入元素,但是在其头部进行插入操作效率奇差,无法被接受。dequevector最大的差异一是在于deque允许使用常数项时间在头部进行元素的插入和删除操作,二是在于deque没有容量的概念,因为它是动态的以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。

    • deque的定义方式
    	deque<int> deq;//定义一个deque,其中的元素为int类型
    	deque<int> deq[N];//定义一个deque数组,其中有N个deque
    	deque<int> deq(len);//定义一个长度为len的deque
    	deque<int> deq(len, x);//定义一个长度为len的deque,初始化每个元素为x
    	deque<int> deq2(deq1);//用deq1给v2赋值,deq2的类型为deque
    	deque<int> deq2(deq1.begin(), deq1.begin() + 3);//将deq1中第0~2三个元素赋值给deq2
    
    • deque的常用内置函数
        //deque中的常用内置函数
        deque<int> deq = { 1, 2, 3 };//初始化vector,v:{1, 2, 3}
    	deque<int>::iterator it = deq.begin();//定义vector的迭代器,指向begin()
    
    	deq.push_back(4);//在deque的尾部插入元素4,v:{1, 2, 3, 4}
    	deq.pop_back();//删除deque的尾部元素,v:{1, 2, 3}
    	deq.push_front(4);//在deque的头部插入元素4,v:{4, 1, 2, 3}
    	deq.pop_front();//删除deque的头部元素,v:{1, 2, 3}
    	deq.size();//返回vector中元素的个数
    	deq.empty();//返回vector是否为空,若为空则返回true否则返回false
    	deq.front();//返回vector中的第一个元素
    	deq.back();//返回vector中的最后一个元素
    	deq.begin();//返回vector第一个元素的迭代器
    	deq.end();//返回vector最后一个元素后一个位置的迭代器
    	deq.clear();//清空vector
    	deq.erase(deq.begin());//删除迭代器it所指向的元素
    	deq.insert(deq.begin(), 1);//在迭代器it所指向的位置前插入元素1,返回插入元素的迭代器
    
    	//根据下标进行遍历
    	for (int i = 0; i < deq.size(); i++)
    		cout << deq[i] << ' ';
    	//使用迭代器遍历
    	for (deque<int>::iterator it = deq.begin(); it != deq.end(); it++)
    		cout << *it << ' ';
    	//for_each遍历(C++11)
    	for (auto x : deq)
    		cout << x << ' ';
    

    map/multimap:又称映射,定义在<map>头文件中,mapmultimap的底层实现机制都是红黑树。map的功能是能够将任意类型的元素映射到另一个任意类型的元素上,并且所有的元素都会根据元素的键值自动排序。map所有的元素都是pair,同时拥有实值键值pair的第一元素被视为键值,第二元素被视为实值map不允许两个元素有相同的键值。multimapmap的操作类似,唯一区别是multimap的键值允许重复。

    • map/multimap的定义方式
    	map<string, int> mp;//定义一个将string映射成int的map
    	map<string, int> mp[N];//定义一个map数组,其中有N个map
    	multimap<string, int> mulmp;//定义一个将string映射成int的multimap
    	multimap<string, int> mulmp[N];//定义一个multimap数组,其中有N个multimap
    
    • map/multimap的常用内置函数
        //map/multimap中的常用内置函数
        map<string, int> mp;
    	mp["abc"] = 3;//将"abc"映射到3
    	mp["ab"]++;//将"ab"所映射的整数++
    	mp.insert(make_pair("cd", 2));//插入元素
    	mp.insert({ "ef", 5 });//同上
    	mp.size();//返回map中元素的个数
    	mp.empty();//返回map是否为空,若为空返回true否则返回false
    	//mp.clear();//清空map
    	mp.erase("ef");//清除元素{"ef", 5}
    	mp["abc"];//返回"abc"映射的值
    	mp.begin();//返回map第一个元素的迭代器
    	mp.end();//返回map最后一个元素后一个位置的迭代器
    	mp.lower_bound("abc");//返回第一个键值大于等于"abc"的元素的迭代器,{"abc", 3}
    	mp.upper_bound("abc");//返回第一个键值大于"abc"的元素的迭代器,{"cd", 2}
    
    	//使用迭代器遍历
    	for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++)
    		cout << (*it).first << ' ' << (*it).second << endl;
    	//for_each遍历(C++11)
    	for (auto x : mp)
    		cout << x.first << ' ' << x.second << endl;
    	//扩展推断范围的for_each遍历(C++17)
    	for (auto &[k, v] : mp)
    		cout << k << ' ' << v << endl;
    

    set/multiset:又称集合,定义在<set>头文件中。set的特性是所有元素都会根据元素的键值自动被排序,set的元素不像map那样可以同时拥有实值键值set的元素既是键值又是实值set不允许两个元素有相同的键值,因此总结来说就是set中的元素是有序且不重复的multiset的特性和用法和set完全相同,唯一的区别在于multiset允许有重复元素,setmultiset的底层实现都是红黑树。

    • set/multiset的定义方式
    	set<int> st;//定义一个set,其中的元素类型为int
    	set<int> st[N];//定义一个set数组,其中有N个set
    	multiset<int> mulst;//定义一个multiset
    	multiset<int> mulst[N];//定义一个multiset数组,其中有N个multiset
    
    • set/multiset的常用内置函数
        //set/multiset中的常用内置函数
    	set<int> st;
    	st.insert(5);//插入元素5
    	st.insert(6);//同上
    	st.insert(7);//同上
    	st.size();//返回set中元素的个数
    	st.empty();//返回set是否为空,若为空返回true否则返回false
    	st.erase(6);//清除元素6
    	st.begin();//返回set第一个元素的迭代器
    	st.end();//返回set最后一个元素后一个位置的迭代器
    	st.clear();//清空set
    	st.lower_bound(5);//返回第一个键值大于等于5的元素的迭代器,返回元素5的迭代器
    	st.upper_bound(5);//返回第一个键值大于5的元素的迭代器,返回元素7的迭代器
    
    	//使用迭代器遍历
    	for (set<int>::iterator it = st.begin(); it != st.end(); it++)
    		cout << (*it) << ' ';
    	//for_each遍历(C++11)
    	for (auto x : st)
    		cout << x << ' ';
    

    unordered_map/unordered_set:分别定义在<unordered_map><unordered_set>头文件中,内部采用的是hash表结构,拥有快速检索的功能。与map/set相比最大的区别在于unordered_map/unordered_set中的元素是无序的,增删改查的时间复杂度为O(1)(map/set增删改查的时间复杂度为O(logn)),但是不支持lower_bound()/upper_bound()函数。

    • unordered_map/unordered_set的定义方式
    	unordered_set<int> st;//定义一个unordered_set,其中的元素类型为int
    	unordered_set<int> st[N];//定义一个unordered_set数组,其中有N个unordered_set
    	unordered_map<int, int> mp;//定义一个unordered_map
    	unordered_map<int, int> mp[N];//定义一个unordered_map数组,其中有N个unordered_map
    
    • unordered_map/unordered_set的常用内置函数
        //unordered_map/unordered_set中的常用内置函数
        unordered_set<int> st;
    	unordered_map<int, int> mp;
    	st.insert(5);//插入元素5
    	st.insert(6);//同上
    	st.insert(7);//同上
    	st.size();//返回unordered_set中元素的个数
    	st.empty();//返回unordered_set是否为空,若为空返回true否则返回false
    	st.erase(6);//清除元素6
    	st.begin();//返回unordered_set第一个元素的迭代器
    	st.end();//返回unordered_set最后一个元素后一个位置的迭代器
    	st.clear();//清空unordered_set
    	mp.insert(make_pair(1, 2));//插入元素{1, 2}
    	mp.insert({ 3, 4 });//同上
    	mp.size();//返回unordered_map中元素的个数
    	mp.empty();//返回unordered_map是否为空,若为空返回true否则返回false
    	mp.erase(3);//清除元素{3, 4}
    	mp.begin();//返回unordered_map第一个元素的迭代器
    	mp.end();//返回unordered_map最后一个元素后一个位置的迭代器
    	mp.clear();//清空unordered_map
    
    	//使用迭代器遍历
    	for (unordered_set<int>::iterator it = st.begin(); it != st.end(); it++)
    		cout << (*it) << ' ';
    	//for_each遍历(C++11)
    	for (auto x : st)
    		cout << x << ' ';
    
    	//使用迭代器遍历
    	for (unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
    		cout << (*it).first << ' ' << (*it).second << endl;
    	//for_each遍历(C++11)
    	for (auto x : mp)
    		cout << x.first << ' ' << x.second << endl;
    	//扩展推断范围的for_each遍历(C++17)
    	for (auto &[k, v] : mp)
    		cout << k << ' ' << v << endl;
    

    四、STL算法详解

    C++标准库定义了一组泛型算法,之所以称为泛型指的是它们可以操作在多种容器上,不但可以作用于标准库类型,还可以用在内置数组类型甚至其它类型的序列上。泛型算法定义在<algorithm>头文件中,标准库还定义了一组泛化的算术算法(Generalized Numeric Algorithm),定义在<numeric>头文件中。

    #include <iostream>
    #include <algorithm>
    #include <numeric>
    using namespace std;
    
    int main()
    {
    	//使用STL容器时将数组地址改为迭代器即可
    
    	int a[5] = { 1, 2, 3, 4, 5 };
    
    	//排序算法
    	sort(a, a + 5);//将区间[0, 5)内元素按字典序从小到大排序
    	sort(a, a + 5, greater<int>());//将区间[0, 5)内元素按字典序从大到小排序
    	reverse(a, a + 5);//将区间[0, 5)内元素翻转
    	nth_element(a, a + 3, a + 5);//将区间[0, 5)中第a + 3个数归位,即将第3大的元素放到正确的位置上,该元素前后的元素不一定有序
    
    	//查找与统计算法
    	find(a, a + 5, 3);//在区间[0, 5)内查找等于3的元素,返回迭代器,若不存在则返回end()
    	binary_search(a, a + 5, 2);//二分查找区间[0, 5)内是否存在元素2,若存在返回true否则返回false
    	count(a, a + 5, 3);//返回区间[0, 5)内元素3的个数
    
    	//可变序列算法
    	copy(a, a + 2, a + 3);//将区间[0, 2)的元素复制到以a+3开始的区间,即[3, 5)
    	replace(a, a + 5, 3, 4);//将区间[0, 5)内等于3的元素替换为4
    	fill(a, a + 5, 1);//将1写入区间[0, 5)中(初始化数组函数)
    	unique(a, a + 5);//将相邻元素间的重复元素全部移动至末端,返回去重之后数组最后一个元素之后的地址
    	remove(a, a + 5, 3);//将区间[0, 5)中的元素3移至末端,返回新数组最后一个元素之后的地址
    
    	//排列算法
    	next_permutation(a, a + 5);//产生下一个排列{ 1, 2, 3, 5, 4 }
    	prev_permutation(a, a + 5);//产生上一个排列{ 1, 2, 3, 4, 5 }
    
    	//前缀和算法
    	partial_sum(a, a + 5, a);//计算数组a在区间[0, 5)内的前缀和并将结果保存至数组a中
    
    	return 0;
    }
    
    展开全文
  • [转] C++ STL详解

    万次阅读 多人点赞 2018-08-30 20:12:32
    C++合理运用STL标准库是非常方便的,对数据结构和一些算法的学习也大有裨益。 事实上转载处也是转载自他处,但是感觉总结的很好,当然也同时感谢原创者。 互联网就是这么神奇的分享平台…… 目录  一、STL简介...

    转载自:https://www.cnblogs.com/CnZyy/p/3317999.html

    C++合理运用STL标准库是非常方便的,对数据结构和一些算法的学习也大有裨益。

    事实上转载处也是转载自他处,但是感觉总结的很好,当然也同时感谢原创者。

    互联网就是这么神奇的分享平台……

    目录

     一、STL简介

     二、算法

    三、容器

    四、迭代器

    C++STL框架中常用函数

    迭代器(iterator)

    求和( accumulate)

    vector(动态数组)

    数组转置 ( reverse)

    排序( sort)

     字符串()

     输入

        删除 (erase clear)

     查找(find)

        数字化处理(string)

        string与char *

        sscanf()

        string与数值相互转换( sprintf )


     一、STL简介

    STL(Standard Template Library,标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中,但在被引入C++之前该技术就已经存在了很长的一段时间。

    STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了模板类和模版函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

    在C++标准中,STL被组织为下面的13个头文件:<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。 

     二、算法

    大家都能取得的一个共识是函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说,一个求方根的函数,在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择,直到真正想使用模板或者说对模板进行特化的时候,STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——你可以将所有的类型划分为少数的几类,然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。

    STL提供了大约100个实现算法的模版函数,比如算法for_each将为指定序列中的每一个元素调用指定的函数,stable_sort以你所指定的规则对序列进行稳定性排序等等。这样一来,只要我们熟悉了STL之后,许多代码可以被大大的化简,只需要通过调用一两个算法模板,就可以完成所需要的功能并大大地提升效率。

    算法部分主要由头文件<algorithm>,<numeric>和<functional>组成。

    <algorithm>是所有STL头文件中最大的一个(尽管它很好理解),它是由一大堆模版函数组成的,可以认为每个函数在很大程度上都是独立的,其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。

     <numeric>体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作。

     <functional>中则定义了一些模板类,用以声明函数对象。

    三、容器

    在实际的开发过程中,数据结构本身的重要性不会逊于操作于数据结构的算法的重要性,当程序中存在着对时间要求很高的部分时,数据结构的选择就显得更加重要。

    经典的数据结构数量有限,但是我们常常重复着一些为了实现向量、链表等结构而编写的代码,这些代码都十分相似,只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便,它允许我们重复利用已有的实现构造自己的特定类型下的数据结构,通过设置一些模版类,STL容器对最常用的数据结构提供了支持,这些模板的参数允许我们指定容器中元素的数据类型,可以将我们许多重复而乏味的工作简化。

    容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>组成。对于常用的一些容器和容器适配器(可以看作由其它容器实现的容器),可以通过下表总结一下它们和相应头文件的对应关系。

    向量(vector) 连续存储的元素<vector>

    列表(list)       由节点组成的双向链表,每个结点包含着一个元素<list>

    双队列(deque) 连续存储的指向不同元素的指针所组成的数组<deque>

    集合(set) 由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序 <set>

    多重集合(multiset) 允许存在两个次序相等的元素的集合 <set>

    栈(stack) 后进先出的值的排列 <stack>

    队列(queue) 先进先出的执的排列 <queue>

    优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 <queue>

    映射(map) 由{键,值}对组成的集合,以某种作用于键对上的谓词排列 <map>

    多重映射(multimap) 允许键对有相等的次序的映射 <map>

    四、迭代器

    下面要说的迭代器从作用上来说是最基本的部分,可是理解起来比前两者都要费力一些(至少笔者是这样)。软件设计有一个基本原则,所有的问题都可以通过引进一个间接层来简化,这种简化在STL中就是用迭代器来完成的。

    概括来说,迭代器在STL中用来将算法和容器联系起来,起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的,每一个容器都定义了其本身所专有的迭代器,用以存取容器中的元素。

    迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。

    <utility>是一个很小的头文件,它包括了贯穿使用在STL中的几个模板的声明,

    <iterator>中提供了迭代器使用的许多方法,而对于<memory>的描述则十分的困难,它以不同寻常的方式为容器中的元素分配存储空间,同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator,它负责产生所有容器中的默认分配器


    C++STL框架中常用函数

    以下转自:http://www.cnblogs.com/duoduo369/archive/2012/04/12/2439118.html 

    代码均重新编译运行了一遍,个别冗杂之处也适当进行了删减

    学完c++快一年了,感觉很有遗憾,因为一直没有感觉到c++的强大之处,当时最大的感觉就是这个东西的输入输出比C语言要简单好写。后来我发现了qt,opencv,opengl,原来,c++好玩的狠。

    在这些图形库之外,最常用的可能就是STL,这个东西由于当时学c++的时候迷迷糊糊,完全是一头雾水,上学期数据结构之后开始有点儿开窍了,现在把才c++STL中常用的函数,用法贴一下,也是记录一下,希望能给一样迷糊的盆友们一些帮助。

    整理自《ACM程序设计》  

    迭代器(iterator)

      个人理解就是把所有和迭代有关的东西给抽象出来的,不管是数组的下标,指针,for里面的、list里面的、vector里面的,抽象一下变成了iterator

    #include <iostream>
    #include <vector>
      
    using namespace std;
      
    int main()
    {
        vector<int> v;
        for(int i = 0; i < 10; ++i )
        {
        	v.push_back(i);
        }
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    	{
        	cout << *it << " ";
        }
        cout << endl;
        return 0;
    }

    以上运行结果:

    求和(<numeric> accumulate)

    accumulate(v.begin(),v.end(),0),把从 v.begin() 开始到 v.end()结束所有的元素加到 0上面去

    #include <iostream>
    #include <vector>
    #include <numeric>
    
    using namespace std;
    
    int main()
    {
        vector<int> v;
        for(int i = 0; i < 10; ++i )
        {
            v.push_back(i);
        }
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
        cout << accumulate(v.begin(),v.end(),0) << endl;
        return 0;
    }

     

    以上运行结果:

    vector(动态数组)

    vector有内存管理的机制,也就是说对于插入和删除,vector可以动态调整所占用的内存空间。  

    #include<vector> //导入vector
    
    vector<int> v; //定义int 类型的 vector
    
    v.push_back(3); //向vector数组尾部插入3 相当于v[0] = 3;
    v.push_back(2); //尾部插入2  相当于v[1] = 2;
    
    
    v.insert(v.begin(),111);//在第一个元素之前插入111  
    
    v.insert(v.end(),222);//在最后一个元素之后插入222 
    
    v.insert(v.end()-1,333);//在倒数第二个元素之后插入333
    
    v.insert(v.begin()+1,444);//在第二个元素之前插入444
    
    
    
    v.erase(arr.begin());//删除用法 同insert 表示删除第一个元素
    
    v.erase(arr.begin(),arr.begin()+5); //删除开头第1-5的元素

     

    主要用法即上述函数。

    数组转置 (<algorithm> reverse)

    reverse(v.begin(),v.end()),顾名思义,就是相当于原来是正着排列,现在是倒着排列

    #include<iostream>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    int main()
    {
        vector<int> v;
        for(int i = 0; i < 10; ++i)
        {
            v.push_back(i);
        }
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
    
        reverse(v.begin(),v.end()); //数组转置
    
    
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
        return 0;
    }

     

    上述运行结果为:

    排序(<algorithm> sort)

    sort(v.begin(),v.end()),默认是从小到大排序,如果要进行从大到小排序,需要添加一个比较函数

    #include<iostream>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    bool Comp(const int &a,const int &b)
    {
        return a>b;
    }
    
    int main()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(3);
        v.push_back(2);
        v.push_back(55);
        v.push_back(-1);
        v.push_back(0);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
    
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
    
        //默认升序
        sort(v.begin(),v.end());
    
    
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
    
        //用降序 需要自定义一个降序函数
        sort(v.begin(),v.end(),Comp);
    
    
        for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        {
            cout << *it << " ";
        }
        cout << endl;
    
        return 0;
    }

     

    以上运行结果为:

     字符串(<string>)

      输入

    #include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main()
    {
        string s1;
        s1 = "hello";
    
        string s2;
        char s[1024];
        //scanf 输入速度比cin快的多
        //scanf 是C函数,不可以输入string
        scanf("%s",s);
        s2 = s;
    
        cout << s1 << endl;
        cout << s2 << endl;
    
        return 0;
    }

     

    上述运行展示:

    尾部添加字符字符串直接用+号 例如: s += 'a'; s += "abc",或者使用append方法,s.append(“123”)

        删除 (erase clear)

    s.erase(it + 1,it + 4); //删除s[1]-s[3]

    clear()//删除全部

    #include<iostream>
    #include<string>
    
    using namespace std;
    
    int main()
    {
        string s;
        s = "0123456789";
        cout << s << endl;
    
        string::iterator it = s.begin();
    
        //删除s[3]
        s.erase(it+3);
        cout << s << endl;
    
        //删除s[1]~s[3]
        s = "0123456789";
        s.erase(it + 1,it + 4);
        cout << s << endl;
    
        //全部删除
        s.clear();
        cout << "clear : " << s << endl;
    
        return 0;
    }

    运行结果为:

     查找(find)

    用find找到string里面第一个要找到元素(char或者串),找到返回数组下标,找不到返回-1

    #include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main()
    {
        string s1;
        s1 = "hello";
        int n = s1.find('e');
        int m = s1.find('a');
    	cout << n <<endl<< m <<endl;
        n = s1.find('h',2); //从第二元素开始找
        cout << n <<endl;
        return 0;
    }

    上述运行结果:

    string和vector有很多相同的东西,比如length(),size(),empty()等,相对也容易。统一展示如下:

    #include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main()
    {
        string s1;
        s1 = "hello";
        cout << s1.length() <<endl;
        
        cout << s1.size() <<endl;
        
        cout << s1.empty() <<endl;
        
        return 0;
    }

    上述结果为:

         数字化处理(string)

    经常会遇到这样一种情况,有一个数字,需要把每一位给提取出来,如果用取余数的方法,花费的时间就会很长,所以可以当成字符串来处理,方便、省时。

      例子:求一个整数各位数的和

    #include<iostream>
    #include<string>
    
    using namespace std;
    
    int main()
    {
        string s;
        s = "123456789";
        int sum = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            switch(s[i])
            {
                case '1': sum += 1;break;
                case '2': sum += 2;break;
                case '3': sum += 3;break;
                case '4': sum += 4;break;
                case '5': sum += 5;break;
                case '6': sum += 6;break;
                case '7': sum += 7;break;
                case '8': sum += 8;break;
                case '9': sum += 9;break;
            }
        }
        
        cout << sum << endl;
        
        return 0;
    }

        string与char *

    #include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main()
    {
        string s_string;
        char s_char[1000];
        scanf("%s",s_char);
    
        s_string = s_char;
    
        //printf输出char* 时用c_str处理
        printf(s_string.c_str());
        cout << endl;
    
        printf("%s",s_char);
        cout << endl;
    
        cout << s_char << endl;
        cout << s_string << endl;
        return 0;
    }

    sscanf()

    #include<iostream>
    #include<string>
    #include<cstdio>
    
    using namespace std;
    
    int main()
    {
        string s1,s2,s3;
        char sa[100],sb[100],sc[100];
        sscanf("abc 123 wcd","%s%s%s",sa,sb,sc);
        s1 = sa;
        s2 = sb;
        s3 = sc;
        cout << s1 << " " << s2 << " " << s3 << endl;
    
        //将字符串分离成数字,分隔符为',''$'
        int a,b,c;
        sscanf("4,5$6","%d,%d$%d",&a,&b,&c);
        cout << a << " " << b << " " << c << endl;
        return 0;
    }

    以上结果为:

    string与数值相互转换( sprintf <sstream> )

    #include<iostream>
    #include<string>
    #include<sstream>
    #include<cstdio>
    
    using namespace std;
    
    //c++ 方法 把数转换为string
    string converToString(double x)
    {
        ostringstream o;
        if( o << x)
        {
            // str()没有'\0' c_str有
            return o.str();
        }
        return "error";
    }
    
    double converFromString(const string &s)
    {
        istringstream i(s);
        double x;
        if( i >> x)
        {
            return x;
        }
        //if error
        return 0.0;
    }
    int main()
    {
        char b[100];
        string s1;
    
        //c语言方法
        sprintf(b,"%d",1987);
        s1 = b;
        cout << s1 << endl;
    
        string s2 = converToString(1954);
        cout << s2 << endl;
    
        string s3 = "202";
        int c = converFromString(s3);
        cout << c << endl;
    
        string s4 = "casacsa6";
        int d = converFromString(s4);
        cout << d << endl;
    
        string s5 = "21abf4";
        int f = converFromString(s5);
        cout << f << endl;
    
        return 0;
    }

    上述代码运行结果为:

    后续还包括set容器,map,queue,stack等等内容,由于之后和原文完全一致,有兴趣的可以直接前往围观:

    https://www.cnblogs.com/CnZyy/p/3317999.html

    展开全文
  • c++ stl详解

    2018-04-27 12:38:00
    本书对C++ STL进行了全面而深入的阐述。STL(标准模板库)是在惠普实验室中开发的,已纳入ANSI/ISO C++标准。其中的代码采用模板类及模板函数的方式,可以极大地提高编程效率。本书由P.J. Plauger等四位对C++ STL的...
  • C++_STL详解;主要内容;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL概述;STL容器;STL容器;STL容器;STL容器;STL容器;STL容器;STL容器;STL容器;STL...
  • STL 详解

    2021-11-12 00:10:11
    C++ STL 是什么 STL,英文全称 standard template library,中文可译为标准模板库或者泛型库,其包含有大量的模板类和模板函数,是 C++ 提供的一个基础模板的集合,用于完成诸如输入/输出、数学计算等功能。 STL ...
  • STL基础详解

    2016-01-07 16:00:19
    STL基础详解,其中包含了String的用法等
  • C++_STL详解.ppt

    2013-03-07 20:21:22
    西安电子科技大学课堂教学用C++ 标准模板库的ppt。非常适合基础薄弱或者没有基础的人循序渐进了解和学习STL
  • STL的课件详细讲解适合新学者,包含STL组件和各个数据结构的详细讲解,初学者必备知识,课堂讲解课件适合需要进行讲解的老师必备知识
  • 内含oj部分习题
  • STL容器 priority_queue 实例priority_queue 以某种排序准则默认为less管理队列中的元素 #include <queue> 核心接口 push(e)根据元素的优先级将元素置入队列 top)返回优先队列头部最大的元素的引用但不移除 pop)从栈...
  • C++ STL详解超全总结(快速入门STL)

    千次阅读 多人点赞 2021-02-24 16:12:25
    一、 c++ STL常用内容总结 文章目录一、 c++ STL常用内容总结1.vector(数组)1.1 介绍1.2 方法函数1.3 注意点1.3.a 排序1.3.b 访问2.stack(栈)2.1 介绍2.2 方法函数2.3 注意点2.3.a.栈遍历2.3.b.模拟栈3.queue...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,850
精华内容 6,340
关键字:

stl详解