精华内容
下载资源
问答
  • STL六大组件

    2020-03-14 18:13:58
    1.容器(containers):各种数据结构,如vector, list, deque, set, map等,用来存放数据,从实现的角度来看,STL是一种class template。 2.算法(algorithms):常用算法如sort, search, copy, erase等,从实现的...

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

    2.算法(algorithms):常用算法如sort, search, copy, erase等,从实现的角度来看,STL算法是一种function template。

    3.迭代器(iterators):扮演容器和算法之间的胶合剂,是所谓的“泛型指针”。从实现的角度看,迭代器是一种将operator*, operator->, operator++, operator--等指针相关操作予以重载的class template。

    4.仿函数(functors):行为类似函数,可作为算法的某种策略。从实现的角度看,仿函数是一种重载了operator()的class或class template,一般函数指针可视为狭义的仿函数。

    5.配接器(adapters):一种用来修饰容器或仿函数或迭代器接口的东西。

    6.配置器(allocators):负责空间配置与管理。从实现的角度来讲,配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

    总结:容器通过配置器取得数据储存空间,算法通过迭代器存取容器内容,仿函数可以协助算法完成不同的策略变化,配接器可以修饰或套接仿函数。

    展开全文
  • 六大组件 1、容器:各种数据结构 2、算法:各种常用算法 3、迭代器:容器与算法之间的胶合剂,即泛型指针 4、仿函数:算法策略,重载了operator()的class或class template 5、配接器:用来修饰容器或仿函数或...

    六大组件

    1、容器:各种数据结构

    2、算法:各种常用算法

    3、迭代器:容器与算法之间的胶合剂,即泛型指针

    4、仿函数:算法策略,重载了operator()的class或class template

    5、配接器:用来修饰容器或仿函数或迭代器接口

    6、配置器:负责空间配置与管理,实现了动态空间配置、空间管理、空间释放的class template

    相互关系

    容器通过配置器取得数据存储空间,算法通过迭代器获取容器内容,仿函数可以协助算法完成不同的策略变化,配接器可以修饰或套接仿函数。

    展开全文
  • C++ STL六大组件-简介

    2020-08-18 11:25:40
    STL(Standard Template Library),即标准模板库,是一个高效的C++程序库。包含了诸多在计算机科学领域里常用的...STL六大组件如下: Container(容器) Adapter(适配器) Algorithm(算法) Iterator(迭代器) Fu...

    STL(Standard Template Library),即标准模板库,是一个高效的C++程序库。包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。从逻辑层次来看,在STL中体现了泛型化程序设计的思想(generic programming)。从实现层次看,整个STL是以一种类型参数化(type parameterized)的方式实现的。

    STL的六大组件如下:

    1. Container(容器) 
    2. Adapter(适配器) 
    3. Algorithm(算法) 
    4. Iterator(迭代器) 
    5. Function object(函数对象) 
    6. Allocator(分配器)

    六大组件的基本作用:

    1. Container(容器)    各种数据结构,如Vector,List,Deque,Set,Map,用来存放数据,STL容器是一种Class Template,就体积而言,这一部分很像冰山载海面的比率。
    2. Adapter(适配器)    一种用来修饰容器(Containers)仿函数(Functors)迭代器(Iterators)接口的东西,例如:STL提供的Queue和Stack,虽然看似容器,其实只能算是一种容器配接器,因为 它们的底部完全借助Deque,所有操作有底层的Deque供应。改变Functor接口者,称为Function Adapter;改变Container接口者,称为Container Adapter;改变Iterator接口者,称为Iterator Adapter。配接器的实现技术很难一言蔽之,必须逐一分析。
    3. Algorithm(算法)  各种常用算法如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templates。
    4. Iterator(迭代器)   扮演容器与算法之间的胶合剂,是所谓的“泛型指针”,共有五种类型,以及其它衍生变化,从实现的角度来看,迭代器是一种将:Operators*,Operator->,Operator++,Operator--等相关操作予以重载的Class Template。所有STL容器都附带有自己专属的迭代器——是的,只有容器设计者才知道如何遍历自己的元素,原生指针(Native pointer)也是一种迭代器。
    5. Function object(函数对象)   行为类似函数,可作为算法的某种策略(Policy),从实现的角度来看,仿函数是一种重载了Operator()的Class 或 Class Template。一般函数指针可视为狭义的仿函数。
    6. Allocator(分配器)  负责空间配置与管理,从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的Class Template。

    六大组件的原理简析和使用如下:

    C++ STL六大组件-1-Container(容器) 

    C++ STL六大组件-2-Adapter(适配器) 

    C++ STL六大组件-3-Algorithm(算法) 

    C++ STL六大组件-4-Iterator(迭代器) 

    C++ STL六大组件-5-Function object(函数对象) 

    C++ STL六大组件-6-Allocator(分配器)

     

     

    参考文档:

    https://blog.csdn.net/qq_31108501/article/details/55049937

    https://blog.csdn.net/jnu_simba/article/details/9410459

    展开全文
  • STL 六大组件

    2021-05-27 16:25:42
    6、配置器(allocators):负责空间配置与管理,是一个实现了动态空间配置、空间管理、空间释放的class template 六大组件的交互关系:container通过allocator取得数据存储空间,algorithm通过iterator存取container...

    1、容器(containers):各种数据结构:vector,list,deque,set,map...

    2、算法(algorithm):各种常用算法:sort、search、copy、erase...

    3、迭代器(iterators):从实现角度看,迭代器是一种将指针 操作予以重载的class template

    4、仿函数(functors):行为类似函数,可以作为算法的某种策略(policy)

    5、配接器(adapters):用来修饰容器、仿函数或迭代器的东西

    6、配置器(allocators):负责空间配置与管理,是一个实现了动态空间配置、空间管理、空间释放的class template

    六大组件的交互关系:container通过allocator取得数据存储空间,algorithm通过iterator存取container内容,functor可以协助algorithm完成不同的策略变化,adapter可以修饰或套接functor

    一、容器(containers)

    //序列式容器:Sequence Containers
    //	array、vector、heap、priority-queue、list、slist、deque、stack、queue
    // a.元素都可序(ordered),但未必有序(sorted)
    // b.array是C++本身内建的序列式容器 ,其他由STL另外提供
    // 1、vector
    //	  1.1、vector的数据安排以及操作方式与array相似。array是静态空间,初始化以后就不能再改变;vector是动态空间。
    //    1.2、为了降低空间配置时的速度成本,vector实际配置的大小可能比客户端需求量更大一些,以备将来可能的扩充。这便是容量的概念。
    //    1.3、vector的容量永远大于或等于其大小。一旦容量等于大小,便是满载,下次再有新增元素,容量就会扩充至两倍。如果两倍容量
    //		   仍不足,就扩张至足够大的容量。
    //	  1.4、容量扩张需要经历“重新配置、元素移动、释放原空间”等过程,工程浩大。
    //	  1.5、所谓动态增加大小,并不是在原空间之后接续新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块
    //		   较大的空间,将原内容拷贝过来,然后才开始在原内容后面构造新的元素,并释放原空间。因此,对vector的任何操作一旦引起空间的重新
    //         配置,只想原vector的迭代器就失效了。
    // 2、list
    //    2.1、每次插入或删除一个元素,就配置或释放一个元素空间。对空间运用有绝对的精准
    //    2.2、对任何位置的元素插入或移除,永远时常数时间
    //    2.3、list本身和list节点是不同的结构,需要分开设计
    //    2.3、STL list是一个双向链表,且是一个环状双向链表
    //    2.3、插入操作(insert)和接合(splice)都不会造成原有list迭代器的失效,这在vector中不成立
    // 3、deque
    //	  3.1、vector是单向开口的连续线性空间,deque是一种双向开口的连续线性空间。
    //	  3.2、所谓双向开口,意思是可以在头尾两端分别做元素插入和删除操作。vector也可以在头尾两端进行操作,但是效率奇差。
    //    3.3、deque允许常数时间内对起头端进行元素的插入和移除操作
    //    3.4、deque没有所谓容量(capacity)观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。
    //	  3.5、deque的迭代器远比vector复杂很多,这影响了各个运算层面。因此除非必要,我们尽可能选择vector而非deque。对deque的排序,可以先将deque
    //			完整的复制到一个vector中,将vector排序后,再复制回dqeue中,提高效率
    //	  3.6 deque是由一段一段的定量连续空间构成。deque需要在这些分段的连续空间上维护其整体连续的假象,并提供随机存取的接口,避开了“重新配置、复制、释放”
    //		  的轮回,代价则是复杂的迭代器架构
    // 4、stack
    //	  4.1、先进后出(FILO)的数据结构
    //	  4.2、允许新增元素,移除元素,取得最顶端元素;不允许遍历
    //	  4.3、将元素推入stack的操作称为push,将元素推出stack的操作称为pop
    //	  4.4、不提供走访功能,也不提供迭代器
    // 5、queue
    //	  5.1、先进先出(FIFO)的数据结构
    //    5.2、允许新增元素、移除元素、从最底端加入元素、取得最顶端元素
    //	  5.3、不提供迭代器,不允许遍历
    //	  5.4、将元素推入queue的操作称为push,将元素推出queue的操作称为pop
    // 6、heap(隐式表述,implicit representation)
    // 7、priority_queue(优先队列)
    //	  7.1、一个拥有权值的queue
    //	  7.2、内部元素按照权值排列,权值最高者排在最前面
    //	  7.3、没有迭代器,不允许遍历
    // 8、slist
    //	  8.1、单向链表(single linked list)
    //    8.2、相对于list,slist的迭代器是单向的
    //    8.3、插入(insert)、移除(erase)、接合(splice)等操作并不会造成迭代器失效。
    //    8.4、根据STL的习惯,插入操作会将新元素插入于指定位置之前,而非之后。但对于slit,没有办法回头定位头一个元素的位置,它必须从头开始找。
    //		   也就是说,除了起点附近区域之外,在其他位置上采用insert或erase操作函数,都属不智之举。这便是slist相较于list最大的缺点。
    //	  8.5、slist提供了insert_after()和erase_after()供灵活运用
    //    8.6、基同样的考虑,slist不提供push_back(),只提供push_front()
    
    //关联式容器:Associative Containers
    //	RB-tree、set、map、multiset、multimap、hashtable、hash_set、hash_map、hash_multimap
    //a.STL关联式容器分为两大类:set(集合)和map(映射表)
    //b.两大类的衍生体multiset(多键集合)和multimap(多键映射表)
    //c.这些容器的底层机制均以RB-tree(红黑树)完成。RB-tree也是一个独立的容器,但不开放给外界使用
    //d.hash_table(散列表),以及以hashtable为底层机制完成的hash_set(散列集合)、hash_multiset(散列多键集合)、hash_map(散列映射表)、hash_multimap(散列映射表)
    //e.每个元素都有一个键值(key)和一个实值(value);set的键值就是实值
    //f.元素被插入时,容器内部结构(RB-tree或hash-table)便依照其键值大小,以某种特定规则将元素放置于适当位置
    //g.没有所谓头尾(只有最大元素和最小元素),不存在push_back()、push_front()、pop_back()、pop_front()、begin()、end()的操作行为
    //h.RB-tree是一棵平衡二叉树
    //std::map和std::unordered_map都是一种存储{key, value}的容器,并提供成员函数来高效地插入、搜索和删除键值对。 顾名思义,std::map是有序的,std::unordered_map是无序的。std::map底层为红黑树,std::unordered_map底层为哈希表。
    // 1、set
    //	   1.1 键值就是实值,所有元素根据键值自动排序
    //	   1.2 不能通过迭代器修改set的元素值,会破坏set的组织
    //	   1.3 新增和删除操作不会使原来的迭代器失效
    //	   1.4 提供包括交集(set_intersection)、联集(set_union)、差集(set_difference)、对称差集(set_asymmetric_difference)算法
    //     1.5 几乎所有的set操作行为,都是调用RB-tree的操作行为
    //	   1.6 对于关联式容器,使用其本身提供的find函数来搜寻元素,会比STL算法find()更有效率。STL算法find()只是循环搜寻。
    //	   1.7 不允许有相同的元素(键值)
    // 2、map
    //	   2.1 所有元素根据键值自动排序
    //	   2.2 所有元素都是pair,同时拥有实值(value)和键值(key)
    //	   2.3 不允许元素有相同的键值
    //	   2.3 不能通过迭代器修改元素的键值,但可以修改元素的实值
    //	   2.4 新增和删除操作不会使原来的迭代器失效
    //	   2.5 几乎所有的map操作行为,都是调用RB-tree的操作行为
    //3.multiset
    //	  3.1 用法与set完全相同,唯一的差别在于它的键值可以重复
    //	  3.2 它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()
    //4.multimap
    //	  4.1 用法与map完全相同,唯一的差别在于它允许键值重复
    //	  4.2 它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()
    //5.hashtable
    //	  5.1 提供对任何有名项(named item)的存取操作和删除操作,被视为一种字典结构(dictionary)
    //	  5.2 hash函数(散列函数)
    //	  5.3 碰撞问题:hash函数会有可能将不同的元素映射到相同的位置(即具有相同的索引)
    //	  5.4 解决碰撞问题的方法包括:线性探测(linear probing)、二次探测(quadratic probing)、开链(separate chaining)...
    //	  5.5 开链:在每一个表格元素的中维护一个list; SGI STL便是采用这种做法
    //    5.6 hash_table表格内的元素称为桶(bucket)
    //    5.7 bucket所维护的linked list,并不采用STL的list或sliet,而是自行维护
    //    5.8 bucket的聚合体,以vector完成,以便具有动态扩充能力
    //	  5.9 hash_table迭代器必须永远维系与整个"buckets vector"的关系,并记录目前所指的节点。利用节点的next指针
    //		  可以轻易完成前进操作。如果当前节点正好是list的尾端,就跳至下一个bucket身上,也就是下一个list的头部节点。
    //    5.10 hash_table迭代器没有后退操作(operator--()),也没有所谓的逆向迭代器(reverse iterator)
    //    5.11 hash_table的模板参数:
    //          Value: 节点的实值类型
    //			Key:  节点的键值类型
    //          HashFcn: hash function的函数型别
    //			ExtractKey: 从节点中取出键值的方法(函数或仿函数)
    //          EqualKey:   判断键值相同与否的方法(函数或仿函数)
    //			Alloc:	空间配置器,缺省使用std::alloc
    //6.hash_set
    //    6.1 STL set大多以RB-tree为底层机制,hash_set以hashtable为底层机制
    //    6.2 几乎所有的hashhash_set操作行为,都是转向调用hashtable的操作
    //    6.3 运用set是为了快速搜寻元素。这一点无论底层是RB-tree或是hashtable,都能满足需要
    //    6.4 但是RB-tree具有自动排序功能,而hashtable没有,反应出来的结果就是,set的元素有自动排序功能,而hash_set没有
    //    6.5 hash_set的使用方式与set完全相同,hashset的实值就是键值
    //    6.6 凡是hashtable无法处理的型别(除非用户为它们撰写hash_function),hash_set也无法处理
    //7.hash_map
    //	  7.1 hash_map以hashtable为底层机制。
    //    7.2 几乎所有的hash_map行为都是转向调用hashtable的操作
    //    7.3 基于同样的原因,map的元素有自动排序功能而hash_map没有
    //    7.4 hash_map的使用方式与map完全相同,hash_map每一个元素都同时拥有一个实值和一个键值
    //    7.5 凡是hashtable无法处理的型别(除非用户为它们撰写hash_function),hash_map也无法处理
    //8.hash_multiset
    //    8.1 hash_multiset以hashtable为底层机制
    //    8.2 hash_multiset元素不会被自动排序
    //    8.3 hash_multiset的使用方式与hash_set完全相同
    //    8.4 hash_multiset和hash_set在实现上唯一的差别是,前者的元素插入操作采用的是底层机制hashtable的insert_equal(),后者采用insert_unqiue()
    //    8.5 凡是hashtable无法处理的型别(除非用户为它们撰写hash_function),hash_multiset也无法处理
    //8.hash_multimap
    //    8.1 hash_multimap以hashtable为底层机制
    //    8.2 hash_multimap元素不会被自动排序
    //    8.3 hash_multimap的使用方式与hash_map完全相同
    //    8.4 hash_multimap和hash_map在实现上唯一的差别是,前者的元素插入操作采用的是底层机制hashtable的insert_equal(),后者采用insert_unqiue()
    //    8.5 凡是hashtable无法处理的型别(除非用户为它们撰写hash_function),hash_multimap也无法处理

    二、算法

    //再好的编程技巧,也无法让一个笨拙的算法起死回生
    //特定的算法往往搭配特定的数据结构,例如
    //binary search tree(二叉搜索树)和RB-tree(红黑树): 解决查找问题
    //hashtable: 拥有快速查找能力
    //max-heap(或min-heap): 完成heap sort(堆排序)
    //1、算法分析与算法复杂度表示O()
    //    1.1 一般而言,算法的执行时间和其所要处理的数据量有幻术关系,可能是一次(线性,linear)、二次(quadratic)、三次(cubic)或对数(logarithm)
    //    1.2 当数据量很小时,多项式函数的每一项都可能对结果带来相当程度的影响,但当数据量足够大时,只有最高次方的项目才具有主导地位
    //	  1.3 如果有任何正值常数c和N0,使得当N>=N0时,T(N)<=cF(N),那么我们便可将T(N)的复杂度表示为O(F(N))^3
    //2、STL算法总览
    //	  算法名称                          算法用途									 是否会改变操作对象
    //    accumulate                        元素累计									 否
    //    adjacent_difference               相邻元素差额								 是
    //    adjacent_find                     查找相邻而重复的元素						 否
    //    binary_search                     二分查找									 否
    //    copy                              复制										 是
    //    copy_backward                     逆向复制									 是
    //    copy_n							复制n个元素									 是
    //    count                             计数										 否
    //    count_if                          在特定条件下计数							 否
    //    equal                             判断两个区间相等与否						 否
    //    equal_range                       试图在有序区间中寻找某值					 否
    //    fill                              改填元素值									 是
    //    fill_n                            改填元素值n次								 是
    //    find                              循环查找									 否
    //    find_if                           循环查找符合特定条件者						 否
    //    find_end                          查找某个子序列的最后出现点					 否
    //    find_first_of                     查找某些元素首次出现的点					 否
    //    for_each                          对区间内的每一个元素施行某操作				 否
    //    generate                          以特定操作的运算结果填充特定区间内元素		 是
    //    generate_n                        以特定操作的运算结果填充n个元素内容		     是
    //    includes                          是否涵盖于某个序列之中    		             是
    //    inneer_product                    内积    									 否
    //    inplace_merge                     合并并就地替换(覆写上去)    			     是
    //    iota                              以顺序递增的值赋值指定范围内的元素           是
    //    is_heap                           判断区间是否为一个heap                       否
    //    is_sorted                         判断区间是否已排序                           否
    //    iter_swap                         元素互换                                     是
    //    lexicographical_compare           以字典序进行比较                             否
    //    lower_bound                       返回指向不小于key值的第一个值的位置          否
    //    max                               最大值                                       否
    //    max_element                       最大值所在位置                               否
    //    merge                             合并两个序列                                 是
    //    min                               最小值                                       否
    //    min_element                       最小值所在位置                               否
    //    mismatch                          找出不匹配点                                 否
    //    next_permutation                  获得下一个排列组合                           是
    //    nth_element                       重新安排序列中第n个元素的左右两端            是
    //    partial_sort                      局部排序                                     是
    //    partial_sort_copy                 局部排序并复制到他处                         是
    //    partial_sum                       局部求和                                     是
    //    partition                         分割                                         是
    //    pre_permutation                   获得前一个排列组合                           是
    //    power                             幂次方                                       否
    //    random_shuffle                    随机重排元素                                 是
    //    random_sample                     随机取样                                     是
    //    random_sample_n                   随机取样                                     是
    //    remove                            删除某类元素                                 是
    //    remove_copy                       删除某类元素并将结果复制到另一容器           是
    //    replace                           替换某类元素                                 是
    //    replace_copy                      替换某类元素并将结果复制到另一容器           是
    //    replace_if                        有条件替换                                   是
    //    replace_copy_if                   有条件替换并将结果复制到另一容器             是
    //    reverse                           反转元素次序                                 是
    //    reverse_copy                      反转元素次序并将结果复制到另一容器           是
    //    rotate                            旋转                                         是
    //    rotate_copy                       旋转并将结果复制到另一容器                   是
    //    search                            查找某个子序列                               否
    //    search_n                          查找"连续发生n次"的子序列                    否
    //    set_difference                    差集                                         是
    //    set_intersection                  交集                                         是
    //    set_symmetric_difference          对称差集                                     是
    //    set_union                         并集                                         是
    //    sort                              排序                                         是
    //    stable_partition                  分割并保持元素相对次序                       是
    //    stable_sort                       排序并保持等值元素的相对次序                 是
    //    swap                              交换(对调)                                 是
    //    swap_ranges                       交换(指定区间)                             是
    //    transform                         两个序列交互作用产生第三个序列               是
    //    unique                            将相邻重复元素折叠缩编,使成唯一              是
    //    unique_copy                       将相邻重复元素折叠缩编,使成唯一并复制到他处  是
    //    upper_bound                       返回指向比key大的第一个值的位置              是
    //    make_heap                         制造一个heap                                 是
    //    pop_heap                          从heap中取出一个元素                         是
    //    push_heap                         将一个元素推入heap                           是
    //    sort_heap                         对heap进行排序                               是
    
    //3.STL算法的一般形式
    //   3.1 所有泛型算法的前两个参数都是一对迭代器(iterators),通常称为first和last,标识算法的操作区间
    //   3.2 STL习惯采用前闭后开区间(或称左涵盖区间),当first==last时,表现的便是一个空区间
    
    #include "stdafx.h"
    #include <iostream>
    #include <fstream>
    #include <memory>
    #include <streambuf>
    #include <numeric>
    #include <vector>
    #include <iterator>
    using namespace std;
    
    //1.质变算法:指运算过程中会改变操作对象的值
    //2.非质变算法:指运算过程中不会改变操作对象的值
    
    //C++一个极大的优点便是,几乎所有的东西都可以改写为程序员自定义的形式或行为
    
    //一、数值算法
    //	   1.1 包含头文件<numeric>
    //	   1.2 accumulate: 1.将每个元素的值累加到初值身上;2.对每一个元素进行二元操作
    //	   1.3 adjacent_difference: 用来计算容器中相邻元素的差额(存储第一个元素值,然后存储后继元素之差值)
    //		   等价操作:*(d_first)= *first
    //                   *(d_first+1)= *(first+1)-*(first)
    //                   *(d_first+2)= *(first+2)-*(first+1)
    //                   *(d_first+3)= *(first+3)-*(first+2)
    //                   *(d_first+4)= *(first+4)-*(first+3)
    //					 ......
    //	   1.3 inner_product: 用来计算两个向量的一般内积(generalized inner product)。当极端两个vector的内积时,应该将init设置为0
    //			内积: 又称数量积、点积(dot product, scalar product),是指接受在实数集R上的两个向量并返回一个实数值标量的二元运算。它是欧几里得空间的标准内积。
    //				  两个向量a=[a1,a2,...,an]和b=[b1,b2,...,bn]的点积定义为:
    //				  a·b=a1b1+a2b2+...+anbn
    //     1.4 partial_sum: 用来计算局部总和
    //		   等价操作:*(d_first) = *first
    //                   *(d_first+1) = *(first)+*(first+1)
    //                   *(d_first+2) = *(first)+*(first+1)+*(first+2)
    //                   *(d_first+3) = *(first)+*(first+1)+*(first+2)+*(first+3)
    //                   *(d_first+4) = *(first)+*(first+1)+*(first+2)+*(first+3)+*(first+4)
    //					 ......
    //     1.5 power: 用来计算某数的n幂次方
    //			这里的n幂次方是指自己对自己进行n次某种运算。运算类型有外界指定,如果指定为乘法,那就是乘幂
    //	   1.6 iota: 用顺序递增的值复制指定范围的元素
    
    int myFunction(int x, int y)
    {
    	//x 可以理解成上一次运算的结果
    	//y 可以理解成容器中的每一个元素
    	cout << "2*" << x << "+" << y << "=" << 2 * x + y << endl;
    	return 2 * x + y;
    }
    
    int myPower(int x, int y)
    {
    	cout << x << "+" << y << "*" << y << "=" << x + y*y << endl;
    	return x + y*y;
    }
    
    int main()
    {
    	int ia[5] = { 1,2,3,4,5 };
    	vector<int> iv(ia, ia + 5);
    
    	//版本1:1+2+3+4+5 = 15
    	cout << accumulate(iv.begin(), iv.end(), 0) << std::endl;		//求和
    	//1+1+2+3+4+5 = 16
    	cout << accumulate(iv.begin(), iv.end(), 1) << endl;			//求和的基础上累积初值
    	//版本2:0-1-2-3-4-5 = -15
    	cout << accumulate(iv.begin(), iv.end(), 0, minus<int>()) << endl;
    	//1*1*2*3*4*5 = 120
    	cout << accumulate(iv.begin(), iv.end(), 1, multiplies<int>()) << endl;
    	//求和
    	cout << accumulate(iv.begin(), iv.end(), 0, plus<int>()) << endl;
    	//2*(2*(2*(2*(2*0+1)+2)+3)+4)+5 = 57
    	cout << accumulate(iv.begin(), iv.end(), 0, myFunction) << endl;
    	//1^2+2^2+3^2+4^2+5^2 = 1+4+9+16+25 = 55
    	cout << accumulate(iv.begin(), iv.end(), 0, myPower) << endl;
    
    	vector<int> vTest(ia, ia + 5);
    	adjacent_difference(vTest.begin(), vTest.end(), vTest.begin());
    	for (auto item : vTest)
    	{
    		cout << item << " ";	//1 1 1 1 1
    	}
    	cout << endl;
    	partial_sum(vTest.begin(), vTest.end(), vTest.begin());		//adjacent_difference 的逆运算
    	for (auto item : vTest)
    	{
    		cout << item << " ";	//1 2 3 4 5
    	}
    	cout << endl;
    
    	partial_sum(vTest.begin(), vTest.end(), vTest.begin());		//adjacent_difference 的逆运算
    	for (auto item : vTest)
    	{
    		cout << item << " ";	//1 3 6 10 15
    	}
    	cout << endl;
    
    	vector<int> v(10);
    	v[0] = 1;
    	adjacent_difference(v.begin(), v.end() - 1, v.begin() + 1, std::plus<int>());	//差值通过仿函数运算可以变成正值
    	cout << "斐波拉契数列: ";
    	for (auto item : v)
    	{
    		cout << item << " ";
    	}
    	cout << endl;
    
    	//计算两个向量的内积
    	cout << inner_product(vTest.begin(), vTest.end(), v.begin(), 0) << endl;
    
    	vector<int> vv(10);
    	iota(vv.begin(), vv.end(), 5);		//从5开始递增赋值给vv
    	for (auto item : vv)
    	{
    		cout << item << " ";
    	}
    	cout << endl;
    
    	system("pause");
        return 0;
    }
    // Porject1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <iterator>
    
    using namespace std;
    
    //二、基本算法
    //     2.1 std::mismatch():查找两个序列中第一对不匹配的元素
    //     2.2 std::equal(): 判断两个序列在[first, last)区间内是否相等。如果元素不一样多,则会产生未定义的结果。
    //          因此,如果我们希望保证两个序列完全相等,必须先判断其元素个数是否相同
    //     2.3 std::fill(): 将[first,last)内所有的元素改填新值
    //     2.4 std::fill_n(): 将[first,last)内前n个元素改填新值
    //     2.5 std::swap(): 用来交换两个对象的内容
    //     2.6 std::copy(): 这个效率非常高
    //     2.7 std::copy_backward(): 不要被 copy_backward() 算法的名称所误导,它不会逆转元素的顺序。
    //          它只会像 copy() 那样复制元素,但是从最后一个元素开始直到第一个元素。
    //     2.8 std::count(): 用于统计某一值在区间内出现的次数
    //     2.9 std::count_if(): 对区间内符合条件的项进行计数
    //     2.10 std::find(): 在区间内查找第一个匹配"等同条件"者
    //     2.10 std::find_end(): 在序列一[first1,last1)所涵盖的区间中,查找序列二[first2,last2)的最后一次出现点
    //     2.11 std::for_each(): 将仿函数f执行于区间内每一个元素身上. f不可以改变元素内容。如果需要改变内容使用std::transform()
    //     2.12 std::max_element(): 返回一个迭代器,指向序列中数值最大的元素
    //     2.13 std::merge(): 将两个有序的序列合并为一个有序的序列
    //     2.14 std::min_element(): 返回一个迭代器,指向序列中数值最小的元素
    //     2.15 std::partition(): std::partition会将区间[first,last)中的元素重新排列,满足判断条件pred的元素会被放在区间的前段,
    //          不满足pred的元素会被放在区间的后段。该算法不能保证元素的初始相对位置,如果需要保证初始相对位置,应该使用stable_partition.
    //     2.16 std::remove(): 移除区间内所有与value值相等的元素,这一算法并不真正从容器中删除那些元素(容器大小未改变),
    //          而是将每一个不与value相等的元素轮番赋值给first之后的空间. 返回值ForwardIterator标出重新整理后的最后元素的下一位置.
    //          例如序列{0,1,0,2,0,3,0,4}, 如果我们执行remove(),希望移除所有0值元素,执行结果将是{1,2,3,4,0,3,0,4}. 每一个与0不相等的元素,
    //          1,2,3,4, 分别被拷贝到第一、二、三、四位置上,第四个位置以后不动。换句话说,第四个位置之后是这一算法留下的残余数据. 返回值
    //          ForwardIterator指向第五个位置. 通过容器的erase()成员函数可以删除这些残余数据.
    //          array不适合使用remove()和remove_if(), 因为array的尺寸无法缩小,导致残余数据永远存在。使用remove_copy()和remove_copy_if().
    //     2.17 std::remove_copy(): 将remove()后的结果复制到另一容器. 返回值OutputIterator指出被复制的最后元素的下一位置
    //     2.18 std::remove_if(): 移除区间内所有被仿函数pred核定为true的元素(并不真正删除). 每一个不符合pred条件的元素都会被轮番赋值给first之后的空间.
    //          返回值ForwardIterator标识出重新整理后的最后元素的下一个位置。可以使用erase()删除残余数据. 对array而言使用std::remove_copy_if().
    //     2.19 std::replace(): 将区间内所有old_value都以new_value取代.
    //     2.20 std::replace_copy(): 将区间内所有old_value都以new_value取代.新序列被复制到指定容器中.原序列没有任何改变.
    //     2.21 std::replace_if(): 将区间内所有被仿函数运算为true的元素,都以new_value取代.
    //     2.22 std::replace_copy_if(): 将区间内所有被仿函数运算为true的元素,都以new_value取代. 新序列被复制到指定的容器中. 原序列没有任何改变.
    //     2.23 std::reverse(): 将区间内元素在原容器中颠倒重排.
    //     2.24 std::reverse_copy(): 将颠倒重排的元素序列存放到指定的容器中. 原序列没有任何改变.
    //     2.25 std::search(): 在序列一[first1,last1)中,查找序列二[first2,last2)的首次出现点.
    //     2.26 std::search_n(): 在序列[first,last)中,查找"连续count个符合条件的元素"所形成的子序列,并返回指向该序列起始处的迭代器。
    //     2.27 std::transform(): 将仿函数作用于区间中每一个元素身上,并以其结果产生新序列
    //     2.28 std::unique(): 移除重复元素。只能移除相邻的重复元素群,如果想要移除所有的重复元素,必须先将序列排序,使所有重复元素相邻。
    //           事实上unique并不改变区间元素个数,会有一些数据残留下来。使用erase()清除残余元素
    //     2.29 std::unique_copy(): 将区间内的元素复制到指定容器中,如果遇到相邻重复元素群,只会复制其中第一个元素。返回的迭代器指向目的容器区间的尾端
    //     2.30 std::sort(): 接收两个RandomAccessIterators(随机存取迭代器),将区间内的元素以渐增的方式重新排列;也允许用户指定一个仿函数(functor), 作为排序标准
    //           STL的所有关系型容器(associative container)都有自动排序功能(底层结构采用RB-tree),不需要sort算法;
    //           序列式容器(sequence container)中的stack、queue和priority-queue都有特别的入口,不允许用户对元素进行排序;
    //           vector、deque的迭代器属于RandomAccessIterators,适用sort算法。
    //           list的迭代器属于BidirectionalIterator,都不适用sort算法。应该使用list的成员函数sort()进行排序
    //           STL的sort算法,数据量大时采用Quick Sort, 分段递归排序。一旦分段的数据量小于某个,门槛,为避免Quick Sort的递归调用带来过大的额外负荷,
    //           就改用Insertion Sort. 如果递归层次过深,还会改用Heap Sort.
    
    int main()
    {
        vector<int> v1{ 1,2,3,4 };
        vector<int> v2{ 2,3,4,5 };
        vector<int> v3{ 1,2,3,4 };
        if (v1.size() == v2.size() && equal(v1.begin(), v1.end(), v2.begin()))
        {
            cout << "v1与v2相同" << endl;
        }
        else
        {
            cout << "v1与v2不相同" << endl;
        }
    
        if (v1.size() == v3.size() && equal(v1.begin(), v1.end(), v3.begin()))
        {
            cout << "v1与v3相同" << endl;
        }
        else
        {
            cout << "v1与v3不相同" << endl;
        }
    
        fill(v3.begin(), v3.end(), 5);
        for (auto item : v3)
        {
            cout << item << " ";
        }
        cout << endl;
    
        merge(v1.begin(), v1.end(), v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));    //1 2 2 3 3 4 4 5
        getchar();
        return 0;
    }

    三、仿函数(functors)和配接器(adapters)

    1、仿函数(functors)
         1.1 就实现而言,仿函数其实就是一个"行为类似函数"的对象。
         1.2 STL仿函数的分类:以操作数(operand)的个数划分:一元仿函数、二元仿函数(STL不支持三元仿函数)
                              以功能划分:算术运算、关系运算、逻辑运算
         1.3 STL内建的仿函数包含在<functional>中
         1.4 STL仿函数的可配接性:有能力被函数配接器修饰,使STL算法更灵活
         1.5 unary_function:用来呈现一元函数的参数型别和返回值型别
         1.6 binary_function:用来呈现二元函数的第一参数型别、第二参数型别
         1.7 算术类仿函数:STL内建的算术类仿函数,支持:
              加法:plus<T>
              减法:minus<T>
              乘法:multiplies<T>
              除法:divides<T>
              取模(余数, modulus):modulus<T>
              否定(negation):negate<T>
         1.8 关系运算类(Relational)仿函数
              等于(equality):equal_to<T>
              不等于(inequality):not_equal_to<T>
              大于(greater than):greater<T>
              大于或等于(greater than or equal):greater_equal<T>
              小于(less than):less<T>
              小于或等于(less than or equal):less_equal<T>
        1.9 逻辑运算类(Relational)仿函数
              And:logicl_and<T>
              Or:logic_or<T>
              Not:logical_not<T>

    2、配接器(adapters)
         2.1 Adapter概念实际上是一种设计模式:将一个class接口转换为另一个class的接口,使原本因接口不兼容而不能合作的classes可以一起运作
         2.2 STL各种配接器:
              function adapter:改变仿函数(functors)的接口
              container adapter:改变容器(containers)的接口;queue和stack都是一种配接器,修饰deque的接口
              iterator adapter:改变迭代器(iterators)的接口;insert_iterators, reverse_iterators, iostream_iterators...

    四、配置器(allocator)

    // Porject1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    #include <vector>
    
    
    #include <new>              //for placement new
    //ptrdiff_t是C / C++标准库中定义的一个与机器相关的数据类型。ptrdiff_t类型变量通常用来保存两个指针减法操作的结果
    //size_t 类型用于指明数组长度, 它必须是一个正数;
    //ptrdiff_t 类型则应保证足以存放同一数组中两个指针之间的差距,它有可能是负数
    #include <cstddef>          //for ptrdiff_t, size_t
    #include <cstdlib>          //for exit()
    #include <climits>          //for UINT_MAX
    
    using namespace std;
    
    //实现一个简单的allocator
    //根据stl规范,allocator必须实现以下必要接口
    // 1)allocator::value_type
    // 2)allocator::pointer
    // 3)allocator::const_pointer
    // 4)allocator::reference
    // 5)allocator::const_reference
    // 6)allocator::size_type
    // 7)allocator::difference_type
    // 8)allocator::rebind
    //      一个嵌套的class template. class rebind<U>拥有唯一成员other, 那是一个typdef, 代表allocator<U>
    // 9) allocator::alloctaor()
    //      缺省构造函数
    // 10) allocator::alloctaor(const allocator&)
    //      拷贝构造函数
    // 11) typelate <class U>
    //     allocator::alloctaor(const allocator<U>&)
    //      泛华拷贝构造函数
    // 12) allocator::~allocator()
    //      缺省析构函数
    // 13) pointer allocator::address(reference x) const
    //      返回某个const对象的地址。算式a.address(x)等同于&x
    // 14) pointer allocator::allocate(size_type n, const void* = 0)
    //      配置空间,足以存储n个T对象。第二个参数是提示。实现上可能会用它来增进区域性,或者完全忽略
    // 15) pointer allocator::deallocate(pointer p, size_type n)
    //      归还先前配置的空间
    // 16) size_type allocator::max_size() const
    //      返回可成功配置的最大量
    // 17) void allocator::construct(pointer p, const T& x)
    //      等同于new((const void*)p) T(x)
    // 18)void allocator::destroy(pointer p)
    //      等同于p->~T()
    namespace JJ
    {
        template <class T>
        inline T* _allocate(ptrdiff_t size, T*)
        {
            //当operator new无法满足某一个内存分配的需求的时候,它会抛出一个异常,
            //在这之前,它会先调用一个客户制定的错误处理函数new_handler。
            //为了指定这个来处理内存不足的函数,使用者需要调用标准库程序函数set_new_handler
            set_new_handler(0);
            T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
            if (tmp == 0)
            {
                cerr << "out of memory" << endl;
                exit(1);
            }
            return tmp;
        }
    
        template <class T>
        inline void _deallocate(T* buff)
        {
            ::operator delete(buff);
        }
    
        template <class T1, class T2>
        inline void _construct(T1* p, const T2& value)
        {
            new(p) T1(value);               //placement new. invoke ctor of T1
        }
    
        template <class T>
        inline void _destroy(T* ptr)
        {
            ptr->~T();
        }
    
        template <class T>
        class allocator
        {
        public:
            typedef T           value_type;
            typedef T*          pointer;
            typedef const T*    const_pointer;
            typedef T&          reference;
            typedef const T&    const_reference;
            typedef size_t      size_type;
            typedef ptrdiff_t   difference_type;
    
            //rebind allocator of type U
            template <class U>
            struct rebind
            {
                using other = allocator<U>;
            };
    
            pointer address(reference x) { return (pointer)&x; }
            const_pointer const_address(const_reference x)
            {
                return (const_pointer)&x;
            }
    
            constexpr allocator() noexcept {}
            constexpr allocator(const allocator&) noexcept = default;
            template <class U>
            constexpr allocator(const allocator<U>&) noexcept {}
    
            void deallocate(pointer p, size_type n) { _deallocate(p); }
            pointer allocate(size_type n, const void* hint = 0)
            {
                return _allocate((difference_type)n, (pointer)0);
            }
    
            void construct(pointer p, const T& value)
            {
                _construct(p, value);
            }
    
            void destroy(pointer p)
            {
                _destroy(p);
            }
    
            size_type max_szie() const
            {
                return size_type(UINT_MAX / sizeof(T));
            }
        };
    }
    
    int main()
    {
        //C++中using的用法
        //1、using申明:using+限定名称(包含名称空间的名称)
        //  例:using std::cout
        //2、using编译指令:
        //  例:using namespce std;
        //  using编译指令可以传递
        //3、C++11取代typedef:
        //  using intvec = std::vector<int>
    
        int ia[5] = { 0, 1, 2, 3, 4 };
        vector<int, JJ::allocator<int>> iv(ia, ia + 5);
    
        //采用标准空间配置器
        //vector<int, std::allocator<int>> iv(ia, ia + 5);
        //C++标准禁止将const元素的容器,因为分配器会失败。
        //vector<const int> vec{ 1, 2, 3 };
       
        //一般我们习惯的C++内存配置和释放操作是这样的:
        //  class Foo {};
        //  Foo* pf = new Foo;     //配置内存,然后构造对象
        //  delete pf;             //将对象析构,然后释放内存
        //这其中new算式内包含两阶段操作:
        //  (1).调用::operator new 配置内存;
        //  (2).调用Foo::Foo()构造对象内容。
        //delete算式也内含两个阶段操作:
        //  (1).调用Foo::~Foo将对象析构
        //  (2).调用::operator delete释放内存
        //STL allocator将这两个操作分开。
        //内存配置由alloc::allocate()负责
        //内存释放有alloc::deallocate()负责
        //对象构造由::construct()负责
        //对象析构由::destroy()负责
    
        for (size_t i = 0; i < iv.size(); i++)
        {
            cout << iv[i] << ' ';
        }
        cout << endl;
    
        return 0;
    


     

    展开全文
  • c++STL六大组件

    2017-04-02 22:52:18
    C++的模板为泛型程序设计奠定了关键的基础(二)、什么是STL 1、STL(Standard Template Library),即标准模板库,是一个高效的C++程序库。2、包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大...
  • STL 提供了六大组件,彼此组合套用协同工作。这六大组件分别是: 容器(Containers):各种数据结构,如 vector、list、deque、set、map 等。从实现的角度来看,容器是一种 class template。 算法(Algorithms):...
  • 2、STL六大组件

    2019-07-10 18:28:01
    具体:六大组件 容器(常见的数据结构,作用:存放数据) 迭代器: 算法: 适配器 : 容器适配器 (对容器的再次封装) :stack和queue priority_queue 仿函数:可以向函数一样操作的对象,作用:可以让一个...
  • STL学习—STL六大组件

    2016-07-18 00:03:38
    STL六大组件 STL主要提供6大组件: 1、容器(container):各种数据结构,如map、vector、list、deque、set等,用来存放数据; 2、算法(algorithm):各种常用算法,如sort、search、copy等; 3、迭代器...
  • STL的目的是标准化组件,所以在STL中使用了泛型编程的思想,对我们常用的数据结构:顺序表、链表、树、哈希以及常用的查找、排序等算法使用模板进行了封装,而且从运行效率以及内存使用上都基本达到了最优。引入STL...
  • 一、STL简介 (一)、泛型程序设计 泛型编程(generic programming) 将程序写得尽可能通用 将算法从数据结构中抽象出来,成为通用的 C++的模板为泛型程序设计奠定了关键的基础 (二)、...
  • STL六大组件简介

    2018-05-09 23:25:49
    STL中的六大组件包括:容器、容器适配器、算法、迭代器、仿函数、空间配置器。 下面我们总解容器这个组件。 1.vector 优点是访问元素效率高,因为是连续空间,所以内存使用率高,缓存使用率也高。缺点是中间...
  • C++ STL 六大组件概览

    2019-07-12 14:23:16
    STL六大组件 容器(container):在实现上,是类模板(class template) 序列容器:vector、list、deque 关联容器:set、map、 迭代器(iterator):一套访问容器的接口,行为类似于指针。他为不同算法提供的...
  • STL六大组件示例

    2019-02-14 10:58:08
    STL六大组件包括容器,算法,迭代器,分配器,函数式,适配器。 核心是容器+算法,迭代器是连接容器和算法的桥梁。分配器是为容器分配存储空间。函数式是辅助算法的工具。适配器有三种,容器适配器,迭代器适配器和...
  • STL 六大组件 容器: 各种数据结构, 如 vector, list, deque, set, map, 用来存放数据 算法: 各种常用算法, 如 sort, search, copy, erase等,从实现的角度来看是一种function template 迭代器: 容器和算法之间的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,295
精华内容 1,718
关键字:

stl六大组件

友情链接: tsl2x7x.rar