"STL源码解析"

  "STL源码"

Posted by Xu on May 28, 2018

STL源码剖析

第一章.STL概论

STL六大组件:

  1. 容器containers:各种数据结构,如vector,list,deque,set,map用来存放数据,STL容器是一种class template
  2. 算法algorithms:STL算法是一种function template
  3. 迭代器iterators:扮演容器和算法之间的胶合剂,是所谓的”泛型指针”。共有五种类型,及其衍生变化,从实现的角度来看,迭代器是一种将operator*,operator->,operator++,operator–等指针相关操作予以重载的class template。所有容器都有附带自己专属的迭代器-因为只有容器设计者才知道如何遍历自己的元素,原生指针也是一种迭代器
  4. 仿函数functors:行为类似函数,可作为算法的某种策略,从实现的角度来看,仿函数是一种重载了operator()的class或class template。一般函数指针可以视为狭义的仿函数
  5. 适配器adapters:一种用来修饰容器或仿函数或迭代器接口的东西。底层实现可以有所区别,但接口是统一标准的
  6. 配置器allocators:负责空间配置与管理,从实现角度来看,配置器提供了一个实现动态空间配置、空间管理、空间释放的class template

六大组件的交互关系:

stl_pic_1.png

第二章.空间配置器

2.1空间配置器的标准接口

allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
//rebind是一个嵌套的class template,class rebind<U> 拥有唯一成员other,是一个typedef,代表allocator<U>
allocator::rebind
//构造函数
allocator::allocator()
//拷贝构造函数
allocator::allocator(const allocator&) 
//泛化的拷贝构造函数
template <class U> allocator::allocator(const allocator<U>&)
//析构函数
allocator::~allocator()
//返回某个对象的地址,算式 a.address(x) 等同于&x
pointer allocator::address(reference x) const 
//返回某个const对象的地址,算式 a.address(x) 等同于&x
const_pointer allocator::address(const_reference x) const
//配置空间,足以容纳n个T对象
//第2个参数是提示,实现上可能会利用它来增进区域性,或完全忽略
pointer allocator::allocate(size_type n,const void* = 0)
//归还之前配置的空间
void allocator::deallocate(pointer p,size_type n)
//返回可成功配置的最大量
size_type allocator::max_size() const
//根据x(调用p所指向类型的构造函数),在p指向的地址构造一个T对象。相当于new((void*)p) T(x)
void allocator::construct(pointer p,const T& x)
//等同于p->~T(),析构地址p的对象
void allocator::destroy(pointer p)

这些标准完全无法应用于SGI STL因为SGI STL在这个项目上摆脱了STL标准规格,使用了一个专属的、拥有次层配置能力、效率优越的特殊配置器。事实上SGI STL仍然提供了一个标准的配置器接口,只是把它做了一层隐藏。

2.2具备次配置力的SGI空间配置器

  • 配置器名称:alloc
  • 不接受任何参数

如:

vector <int,std::allocator<int>> iv;

//必须写成

vector <int ,std::alloc> iv;//不接受参数

SGI STL的每一个容器都已经指定其缺省的空间配置器为alloc

2.2.1 SGI标准的空间配置器,std::allocator

虽然SGI也定义有一个符合部分标准、名为allocator的配置器,但SGI自己从未用过它,也不建议我们使用,主要原因是因为效率不佳,只是把C++的**::operator new和::operator delete **做一层薄薄的包装而已

2.2.2 SGI特殊的空间配置器,std::alloc

一般而言,我们所习惯的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()
  • 对象构造:::construct()

内存的析构和释放对应以下两部操作:

  • 内存析构:::destroy()
  • 内存释放:alloc::deallocate()
#include<stl_alloc.h> //负责内存的配置和释放
#include<stl_construct.h>//负责对内容的构造与析构

stl_pic_2.png

2.2.3 构造和析构基本工具:construct()和destroy()

stl_pic_3.png

  • construct()接受一个指针p和一个初值value,该函数的用途就是将该初值在所给指针所指的空间上构造,C++的定位new运算符可以实现这一任务。
  • destroy有两个版本
    • 一个版本接受一个指针,准备将该指针所指对象析构掉,直接调用其析构函数即可。
    • 第二个版本是接受first,last两个迭代器,准备将[first,last)范围内的所有对象析构掉。
      • 我们需要考虑的是,该范围内的对象的析构函数是否是non-trivial(无关痛痒)的,多次调用这些non-trivial析构函数也是对效率的一种伤害。
      • 因此我们首先利用 value_type()获取迭代器所指对象的型别,再利用 **__type_traits** 判断该型别的析构函数是否无关痛痒。若是(__true_type),则什么都不做,若不是(\__false_type),这才循环析构范围内的对象。

2.2.4 空间的配置与释放,std::alloc

对象构造前的空间配置和对象析构后的空间释放,由负责,SGI对此的设计哲学如下:

  • 向system heap要求空间
  • 考虑多线程(multi-threads)状态(暂时不考虑)
  • 考虑内存不足时的应变措施
  • 考虑过多“小型区块”可能导致的内存碎片问题

C++内存配置的基本操作是::operator new(),内存释放的基本操作是::operator delete()。这两个全局函数相当于C的malloc和free。

考虑到小型区块可能造成的内存破碎问题,SGI设计了双层配置器:

  • 第一级配置器直接使用malloc和free
  • 第二级配置器采用不同的策略:当配置区块超过128bytes时,视之为”足够大”,便调用第一级配置器;当配置器区块小于128bytes时,视之为”过小”“,为了降低额外负担,采用内存池“memory pool整理方式”

整个设计究竟只开放第一级配置器还是同时开放第二级配置器。取决于__USE_malloc是否被定义。

为了屏蔽使用过程中对一级二级配置器的调用区别,SGI将配置器封装成统一的接口:simple_alloc,该接口其实就是单纯的转调用,SGI容器全部使用这个simple_alloc接口:

stl_pic_4.png

容器通过该接口使用配置器: stl_pic_5.png

一二级配置器之间的关系:

stl_pic_6.png

一二级配置器的封装接口和调用方式: stl_pic_7.png

2.2.5 第一级配置器__malloc_alloc_template解析

第一级配置器通过malloc和free来直接配置内存,当内存不足时,调用相应处理函数。

默认处理例程如下:

stl_pic_8.png

配置器模版类结构实现如下:

stl_pic_9.png

配置器内存不足时调用的处理函数如下:

stl_pic_10.png

第一级配置器以malloc,free,realloc等C函数执行实际的内存配、释放、重配置操作,并实现类似C++ new-handler的机制。它并不能直接运用C++ new-handler机制,因为它没有使用::operator new来配置内存。

C++ new-handler机制就是当你的内存配置需求无法满足时,可以要求系统调用一个你所指定的函数。也就是一旦::operator new无法完成任务,在丢出std::bad_alloc异常状态之前,可以调用指定的处理例程。所以SGI也仿真出了一套类似new-handler机制

SGI第一级配置器的allocate()和realloc()都是在调用malloc和realloc不成功后,该调用oom_malloc()和oom_realloc(),后两者都有内循环,不断调用“内存不足处理例程”,期望释放部分内存后再次重新分配。如果该例程没有被客端指定,则调用默认的处理过程__THROW_BAD_ALLOC,丢出bad_alloc异常或利用exit(1)硬生生终止程序。

2.2.6 第二级配置器__default_alloc_template解析

第二级配置器多了一些机制,避免太多小额区块造成内存的碎片。

  • 如果区块够大,超过128bytes时,就移交第一级配置器处理
  • 当区块小于128bytes时,则以内存池管理,该方法称为次层配置:每次配置一大块内存(默认20个区块),并维护该大小的区块链表(free-list)。
    • 需要配置内存时从该链表取出一块使用,但取出后就不在该链表结构中
    • 回收内存时,则将回收的区块添加到该链表头位置

为了方便管理,SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数,并维护16条(8,16,24…128)链表在一个数组中freelists[16],每一条的链表节点结构为:

union obj{
    union obj *free_list_link;
    char client_data[1];
}

从第一个字段来查看是一个指向下一个obj节点的指针,从第二个字段来看则是指向实际数据块的指针。

第二级配置器的实现:

stl_pic_11.png

stl_pic_12.png

stl_pic_13.png

2.2.7 空间配置函数allocate()

第二级配置器分配内存的规则是:

  • 先判断区块的大小,大于128bytes的就调用第一级配置器
  • 小于128bytes就检查对应的free list如果free list之内有可用的区块,就从链表中直接分配
  • 没有可用的区块,就将区块大小对齐为8的倍数,然后调用refill来新开辟20个区块添加到可用链表

实现如下: stl_pic_14.png

stl_pic_15.png

2.2.8 空间释放函数deallocate()

第二级配置器释放内存规则:

  • 大于128bytes时调用第一级配置器释放
  • 小于128bytes时,找到对应的可用区块链表,添加到该链表的头节点部分。

代码实现:

stl_pic_16.png

stl_pic_17.png

2.2.9 重新填充free lists -refill()

当分配内存时发现,没有可用区块用于分配时,调用refill,缺省取得20个新区块,但万一内存出不足,获得的节点数可能小于20

stl_pic_18.png

2.2.10 内存池(memory pool)

首先我们先解释一下内存池分配内存的机制:

  1. 一般我们从内存池分配内存,都是分配指定区块大小的内存块(默认为20个
  2. 如果内存池中内存无法分配20个区块的内存,则力所能及分配少于20个区块的内存块
  3. 如果内存池中连一个指定大小的区块都无法分配时:
    • 3.1 首先将内存池中剩余的内存添加到合适的区块链表中,防止浪费
    • 3.2 从heap结构中调用malloc分配内存
    • 3.3 如果堆结构中内存不够时,在从所有大于我们指定的区块的区块链表中,搜索是否有可用区块,只要有一个则释放到内存池中,然后从内存池再次分配该指定大小的区块
    • 3.4 如果所有大于该指定大小区块的链表中也没有可用区块时,则调用第一级配置器分配内存,若还是不够,则报bad_alloc异常

stl_pic_19.png stl_pic_20.png stl_pic_21.png

2.3 内存基本处理工具

SGI定义了五个全局函数,作用于未初始化的空间上:

  • construct()
  • destroy()
  • uninitialized_copy():对应于高层次函数copy()
  • uninitialized_fill():对应于高层次函数fill()
  • uninitialized_fill_n():对应于高层次函数fill_n()

这三个函数可以有效将内存的配置与对象的构造行为分离开来。一个容器全区间的构造函数通常以两个步骤完成:

  • 配置合适大小的内存区块
  • 使用uninitialized_copy,uninitialized_fill或uninitialized_fill_n三个函数对这些未初始化的内存空间进行构造

在一块内存中构造元素的过程中,有两点:

  • 在内存中的元素构造过程中,必须具备“commit or rollback”语意,也就是要么全部构造完成,要么一个都不构造,不能只构造部分元素。
  • 如果构造的对象满足POD类型要求,则可以通过采取最有效的初值填写手法,一般是调用对应的stl算法中的高层函数。如果不满足POD类型,则需要一个一个元素调用construct进行构造。

举例解释,uninitialized_copy()的实现:

uninitialized_fill,uninitialized_fiil_n和uninitialized_copy的区别在于,当是POD类型时,调用的stl算法高层函数不同,分别为fill()和fill_n()

函数逻辑:

  1. 先获取拷贝对象的value_type
  2. 根据value_type获取判断是否是POD类型的函数
  3. 是POD类型,调用高层函数进行批量拷贝
  4. 不是POD类型调用construct一个个构造
----------------------------------------------------------------------------
//uninitialized_copy主要是将__uninitialized_copy进行封装调用,获取要拷贝对象的value_type
template<class InputIterator,class ForwardIterator> 
inline ForwardIterator
    uninitialized_copy(InputIterator first,InputIterator last,ForwardIterator result){

    return __unitialized_copy(first,last,result,value_type(result));
}

----------------------------------------------------------------------------
//__uninitialized_copy获取了拷贝对象的value_type之后再,获取该对象类型是否是POD类型,然后调用__unitialized_copy_aux进行对应的操作

template<class InputIterator,class ForwardIteratorclass T> 
inline ForwardIterator
    uninitialized_copy(InputIterator first,InputIterator last,ForwardIterator result,T*){
    typedef typename __type_traits<T> ::is_POD_type  is_POD;
    return __unitialized_copy_aux(first,last,result,result,is_POD());
}
----------------------------------------------------------------------------
//__unitialized_copy_aux的POD拷贝版本,is_POD返回__true_type
template<class InputIterator,class ForwardIterator> 
inline ForwardIterator
    uninitialized_copy_aux(InputIterator first,InputIterator last,ForwardIterator result,__true_type){

    return copy(first,last,result);//是POD类型,则调用高层stl算法函数
}
----------------------------------------------------------------------------
//__unitialized_copy_aux的非POD拷贝版本,is_POD返回__false_type
template<class InputIterator,class ForwardIterator> 
inline ForwardIterator
    uninitialized_copy_aux(InputIterator first,InputIterator last,ForwardIterator result,__false_type){
    ForwardIterator cur = result;
    for(;first!=last;++first,++cur)
        construct(&*cur,*first)//不是是POD类型,则调用construct一个个构造
    return cur;
}

对于char和wchar_t两种类型,可以采用最具效率的做法:memmove来执行复制行为,因此为这个类型设计一份特化版本的uninitialized_copy()函数: stl_pic_22.png

总结这三个对未初始化内存的操作函数如下图: stl_pic_23.png

3.迭代器概念与traits编程技法

  • 迭代器所指对象的型别,称为该迭代器的value_type
  • 模版的参数推导机制只能针对参数进行推导,而不能根据执行期的返回类型进行推导获取返回类型
  • 所以我们需要指明返回的类型,但当指明的返回值涉及到模版迭代器参数类所指向的对象类型时,我们需要使用合适的声明来告知编译器,我们返回的是该迭代器所指的类型。

stl_pic_24.png

  • 但是并不是所有的迭代器都是一个类类型,只有类类型才能给出value_type字段的定义。但当迭代器是原生指针时,我们就无法根据value_type字段获取该指针所指向的多对象。
  • 所以我们要统一一个接口获取所有迭代器(类类型迭代器,原生指针等)所指对象的型别。则需要在中间层添加一层萃取器类模版,并对原生指针进行偏特例化处理

对于一般类类型迭代器,该萃取器实例类中value_type的定义如下:

template <class I>
struct iterator_traits{
    typedef typename I::value_type value_type;//类类型迭代器所指对象的型别value_type可以直接从迭代器类型中成员value_type获取
}

对于原生指针迭代器,该萃取器实例类中value_type定义如下:

template<class T> 
struct iterator_traits<T*>{
    typedef T value_type;//偏特例化版本,根据指针及模版参数推导机制直接获取指针所指对象类型
}

针对指向常量对象的原生指针“const int *”,用原生指针的特例化版本萃取器会返回const int常量对象,而我们一般使用所指对象的value_type用于生命一个暂时变量如果是一个常量时,不能修改,并没有什么作用,所以我们针对指向常量对象的指针类型也有一个特例化版本萃取器。

template <class T>
struct iterator_traits<const T*>{//针对指向常量对象指针的特例化版本
    typedef T value_type;
}

萃取器的工作就是获取一个迭代器所有的特性,而value_type只是其中的一个特性,萃取器可以获取迭代器一共五个特性,其它四个特性我们也将分别介绍:

  1. value_type:迭代器所指对象类型
  2. difference_type:迭代器之间的距离度量类型
  3. pointer:指针类型,指向该迭代器所指的对象类型
  4. reference:引用类型(左值引用,右值引用),引用该迭代器所指对象
  5. iterator_category:该迭代器类型,一共有五类:
    • Input Iterator:只读
    • Output Iterator:只写
    • Forward Iterator:允许读写
    • Bidirectional Iterator:可以双向移动
    • Random Acess Iterator:涵盖前四种所有迭代器能力

stl_pic_25.png

3.2 迭代器相应型别:difference_type

difference_type:用来声明表示两个迭代器之间的距离的变量

对于类类型迭代器,有成员diffrence_type来直接获取,对于原生指针和原生常量指针之间的距离用ptrdiff_t类型来度量(萃取器模版特例化实现)。

typename iterator_traits::difference_type diff;//可以用于声明表示两个I类型迭代器之间的距离变量

3.3 迭代器相应型别: reference type(用于解引用操作*)

从“迭代器所指之物的内容是否可以改变”的角度来看,迭代器可以分为两种:

  • 可以改变:reference传回的是左值引用
  • 不能改变:迭代器指向常量,reference传回的是右值引用

reference用于返回一个迭代器指向对象的引用类型,所以若迭代器指向常量对象,返回的引用也是指向该常量对象,实现见下一小节

3.4 迭代器型别:pointer type

上一节reference是用于返回指向某迭代器指向对象的引用,这部分则是返回指向对象的原生指针。无论是指针还是引用都有针对原生指针和常量原生指针的特例化版本:

stl_pic_26.png

3.5迭代器型别:iterator_category

该型别指示该迭代器的类型,一共有五个类型(上面有提到),并且这五个类型之间具有一定继承关系:

stl_pic_27.png

根据不同类型的迭代器,操作的方式也有所区别,为了根据各类型迭代器的特点,采用对应的迭代器操作,来提高效率。我们需要利用函数的重载来实现这一特点。

实例,advanced()函数实现:该函数有两个参数,迭代器p和数值n,函数的功能就是将迭代器p累进n次,下面有三个函数版本,针对三个不同类型的迭代器具体实现: stl_pic_28.png

然后advanced函数先判断迭代器类型再调用各类型的函数: stl_pic_29.png

这个版本的advanced实现需要在执行期才能确定使用哪一个版本,影响程序效率,所以我们采用重载函数机制来实现,根据参数中迭代器类型标签来区分调用哪一个重载函数。

五个标签: stl_pic_30.png

五个类型的函数的重载版本: stl_pic_31.png

将这五个重载模版函数封装为上层接口:

stl_pic_32.png

所以萃取器iterator_traits中需要添加一个新的型别:

template<class I>
struct iterator_traits{
    ...//其它迭代器特性
    typedef typename I::iterator_category  iterator_category;//直接从迭代器类型中获取该成员值
}

同样萃取器需要针对原生指针和常量指针实现特例化版本,原生指针和常量指针其实也属于一种Random Acess Iterator(最强化版迭代器)

template<class I>
struct iterator_traits<T*>{
    ...//其它迭代器特性
    typedef random_access_iterator_tag  iterator_category;//直接定义为Random Acess Iterator类型的迭代器标签
}

template<class I>
struct iterator_traits<const T*>{
    ...//其它迭代器特性
    typedef random_access_iterator_tag  iterator_category;//直接定义为Random Acess Iterator类型的迭代器标签
}

STL算法命名规则:如advanced本来可以接受各种类型的迭代器,但在模版参数的命名上依然为InputIterator,这是因为要以算法所能接受的最低阶迭代器来为迭代器型别的参数命名

消除“单纯传递调用的函数”

用class来定义迭代器类型的标签,并用继承来实现类型之间的从属关系不仅可以实现重载的机制

  • 还一个好处是,通过继承我们可以避免再写“单纯只做传递调用的”函数。
  • 如上述advanced函数中五个迭代器类型的重载函数实现中,对于ForwardIterator类型迭代器的函数实现,完全只是调用InputIterator版本的函数。
  • 所以我们完全不用书写ForwardIteratorh的函数实现,因为参数转化过程会自动调用InputIterator的函数版本

3.5 std::iterator的保证

  • 为了符合规范,任何迭代器都应该提供 五个内嵌的相应型别(迭代器的五个特性),利于traits萃取,否则便是自别于整个STL架构,可能无法与其它STL组件顺利搭配
  • 为了然后新设计的迭代器来和STL组件顺利兼容,STL提供了一个iterators class如下,只要新设计的迭代器继承自它,就可以保证符合STL所需要的规范标准。

其实这个std::iterator类就是包含了这五个特性的成员:

stl_pic_33.png

当我们继承该类,设计新迭代器时:

template <class Item>
struct ListIter:public std::iterator<std::forward_iterator_tag,Item>{//继承std::Iterator类并提供前两个特性参数
    ...
}

3.6 新迭代器的实现过程总结

要实现新的迭代器要实现如下几个部分:

  1. 五个迭代器类型的标签类
  2. 要继承的std::iterator,来和STL组件兼容。
  3. 萃取器iterator的实现,其中包括迭代器五个特性的萃取,及对原生指针和原生常量指针偏特例化实现。
  4. 实现一个算法针对不同类型的迭代器的重载函数版本如__distance,再为这些重载函数封装一个访问入口的接口函数,如distance.

3.7 SGI STL的私房菜:__type_triats

上面所提及的iterator_traits只是针对迭代器的五个特性进行萃取,这一节将对所有 型别(类,或基本类型等)的对象的相关特性进行萃取,__type_traits就是该执行特性萃取的萃取器。

对于一个型别(type)的特性包括:

  • 构造、析构、拷贝、赋值这些函数是否是有用的(non-trivial)函数,根据这些特性就可以采用最有效率的措施。对于那些没用的函数,可以采用内存直接处理操作如malloc,memcpy等等获得最高效率。
  • 一个型别是否为POD类型

所以萃取器中需要有这些成员来代表是否具有这些特性:

__type_traits<T>::has_trivial_defualt_constructor
__type_traits<T>::has_trivial_copy_constructor
__type_traits<T>::has_trivial_assignment_operator
__type_traits<T>::has_trivial_destructor
__type_traits<T>::is_POD_type

这些式子会响应我们“真”或“假”,但其结果不应该只是一个bool值,应该是个有着真/假性质的“对象”,因为我们希望利用其响应结果来进行参数推导(为什么bool值不能进行参数推导?),为此,对应真和假有如下两个对象:

//这两个空白classes没有任何成员不会带来额外负担,却又能标示真假。
struct __true_type{};
struct __false_type{};

萃取器模版的定义: stl_pic_34.png

中有对C++基本型别char,signed char,unsighed char,short,unsigned short,int,unsigned int,long,unsigned long,float,double,long double还有**原生指针**提供了萃取器__type_traits的特化版本,所有成员均设置为__true_type

实例:uninitialized_fill_n(),首先获取对象型别value_type T1,在根据型别获取POD特性,在根据POD特性调用对应的重载函数:

stl_pic_35.png

stl_pic_36.png

当我们新设计一个类时,很有有编译器会根据你的构造函数,析构函数等特性信息自动进行萃取,通常我们需要为新设计的类型设计一个特化版的萃取器__type_traits。否则默认这些特性都是__false_type,即使你具有这些特性。

4 序列式容器

4.2 vector

这一节内容见幕布中STL容器的底层实现有介绍。

4.3 list

相比与vector的连续线性空间,list就显得复杂许多,它的好处就是每次插入或删除一个元素,就配置和释放一个元素空间,因此list绝对不浪费空间

4.3.2 list的节点结构

lists是一个双向链表

stl_pic_37.png

4.3.3 list迭代器

  • list的迭代器不能想vector一样使用普通的迭代器,因为不能保证所有的节点保存在连续的存储空间,所以迭代器的前进后退都需要进行重载设置。
  • 所谓list迭代器正确的递增,递减、取值,成员存取等操作是指:
    • 递增时指向下一个节点
    • 递减时指向上一个节点
    • 取值时取得是节点的数据值
    • 成员取用时取用的是节点的成员
  • list的迭代器要能前进后退双向移动,所以其迭代器类型为Bidirectional Iterators
  • list的插入操作和接合操作不会使原有迭代器失效,因为原有迭代器所指节点位置并没有改变,甚至删除操作也不会影响到原有迭代器,除非是指向被删除节点的迭代器

stl_pic_38.png

list迭代器代码:

stl_pic_39.png stl_pic_40.png

4.3.4 list的数据结构

SGI list不仅是一个双向链表,而且还是一个环状双向链表。所以它只需要一个指针就可以表现整个链表:

template<class T, class Alloc = alloc>
class list{
    protected:
        typedef __list_node<T> list_node;
    public:
        typedef list_node* link_type;
    protected:
        link_type node;//只要一个指针指向链表中的任意一个节点,我们就能够表示整个环状双向链表
        ...
}

但双向链表如何符合STL对于“前闭后开”的区间要求,对应一个begin迭代器和last迭代器?

  • 我们只要让node指向刻意至于尾端的一个”空白节点”即可。所有双向列表的首尾相连的部分都会多出一个空白节点,拥有该空白节点,以下几个函数都可以轻易完成:
iterator begin(){
    return (link_type)((*node).next);//空白节点的下一个节点为链表的起始节点迭代器
}

iterator end(){
    return node;//空白节点即为last迭代器
}

bool empty() const{
    return node->next == node;//当空白节点首尾相连时为空链表
}

size_type size() const{
    size_type result = 0;
    distance(begin(),end(),result);//全局算法函数,计算两个迭代器之间节点的个数
    return result;
}

reference front(){
    return *begin();//返回起始节点的数据值的引用
}

reference back(){
    return *(--end());//返回最后一个节点的数据值引用
}

stl_pic_41.png

4.3.5 list 的构造和内存管理(constructor,push_back,insert)

  • list的默认构造函数是构造一条空的链表,只有一个空白节点。
  • list的内存管理包括对一个节点的内存配置,释放,构造和销毁操作

首先我们看一下list的空间配置器,list默认使用alloc作为空间配置器,并使用统一的空间配置器接口simple_alloc模版,来分配内存:

template <class T,class Alloc = alloc>
class list{
    protected:
        typedef __list_node<T> list_node;//定义一个节点模版类,确定节点所存储的数据类型
        typedef simple_alloc<list_node,Alloc> list_node_allocator;//该配置器是以list_node为内存单位来实现统一的内存分配接口simple_alloc模版
        ...

}

以下四个list类成员函数分别用于配置、释放、构造和销毁一个节点:

stl_pic_42.png

push_back,insert

push_back只是对insert函数的调用而已,相当于在尾部插入元素。

void push_back(const T& x){
    insert(end(),x);//在尾部插入元素
}
//insert函数

// 将元素插入到指定的位置
iterator insert(iterator position,const T& x){
    link_type tmp = create_node(x);//想创建一个节点并构造
    tmp->next = position.node;
    tmp->prev = positon.prev;
    (link_type(positon.node->prev))->next = tmp;
    position.node->prev = tmp;//设置插入操作相关的指针设置
    return tmp;

}


4.3.6 list的元素操作总结

  1. push_front:在起始迭代器处插入
  2. push_back:在last迭代器处插入
  3. erase:擦除迭代器所指元素,通过指针操作
  4. pop_front():用erase移除头节点
  5. pop_back():移除尾节点
  6. clear():清楚所有节点
  7. remove():移除指定value的节点
  8. unique():移除数值相同的连续元素
  9. transfer():迁移操作,将某个连续范围的元素迁移到某个特定位置之前,以下几个函数都是在tansfer的基础上实现的。
    • splice():将某元素或某范围内元素结合到迭代器指定元素之前
    • merge(): 将两个递增链表合并
    • reverse():将一个链表进行反转
    • sort():将链表进行排序(list不能使用STL算法sort(),因为STL算法sort只接收RandomAcessIterator)

4.4 deque

deque是一种双向开口的连续线性空间,deque和vector之间的最大差异在于:

  1. deque允许于常数时间内对起头端进行元素的插入或移除操作
  2. deque没有所谓的容量的概念,它是以动态地以分段连续空间组合而成,随时可以增加一段新的空间并连接起来

4.4.2 deque的中控器

  • deque是由一段一段的定量连续空间构成的,deque的最大任务就是在这些分段的定量连续空间上,维护其整体连续的假象。
  • 实现:deque是用一块所谓的map作为主控器,其实map就是一个映射数组,数组中存放的是指向一块块连续空间缓冲区的指针。默认值0表示该连续空间缓冲区的大小为512bytes:
template <class T,class Alloc = alloc,size_type Bufsize = 0>//Buf_size为每个缓冲区的大小
class deque{
    public:
        typedef T value_type;
        typedef value_type* pointer;
        ...
    protected:
        typedef pointer * map_pointer;
    //数据成员
    protected:
        map_pointer map;//指针数组,指针指向缓冲区
        size_type map_size;//指针数组中可容纳的指针数
        ...
}

stl_pic_43.png

4.4.3 deque的迭代器

deque是分段连续空间,为了维持“其整体连续”的假象的任务,落在迭代器的 operator++和operator–两个运算子上。这两个运算子必须能够指出分段连续空间在哪里,其次要能够判断自己 是否已经处于其所在缓冲区的边缘

控制一个缓冲区的边界信息及当前迭代器所指位置信息主要靠迭代器中的三个成员:

  • cur;//当前迭代器的具体指针
  • first;//当前迭代器所在的缓冲区的首部
  • last;//当前迭代器所在缓冲区的尾部

stl_pic_44.png

上述buffer_size()中返回缓冲区的大小

  • 若Bufsize为0,表示缓冲区大小使用默认值
    • 若元素大小sz<512则传回512/sz
    • 若元素大小sz>512,则传回1
  • 若Bufsize 不为0,则直接返回Bufsize
inline size_t __deque_buf_size(size_t,size_t sz){
    return n! = 0 ? n : (sz < 512  ?  size_t ( 512 / sz  :  size_t ( 1 ) ) );
}

stl_pic_45.png

  • 假设我们产生一个元素为int,缓冲区大小为8个元素的deque,经过一系列操作,deque拥有20个元素
  • 那么begin()和end()所传回的两个迭代器应该如下图所示,这两个迭代器一直保存在deque内,成员名为start,finish。
  • 由于有20个元素所以需要三个缓冲区,map数组需要三个node节点

stl_pic_46.png

接下来将就deque的一些关键操作进行分析,operator++,opertor–等

因为可能涉及到 多个缓冲区之间的跳转 ** ,实现函数为 **set_node(),该函数主要用来合理的对三个迭代器关键成员: node,last,first 进行设置:

void set_node(map_pointer new_node)//先找到合适的缓冲区对应的map数组中的节点new_node,传入函数set_node
{
    //设置三个成员
    node = new_node;
    first = *new_node;
    last = first + difference_type(buffer_size());
}

reference operator*() const{
    return *cur;//返回迭代器当前所指对象的引用
}

reference operator->() const{
    return &(operator*());//返回迭代器当前所指对象的指针
}

stl_pic_47.png stl_pic_48.png

4.4.4 deque的数据结构

上一节介绍完deque的迭代器之后,现在介绍 deque自身的数据结构:

  • 维护一个指向中控器map的指针
  • 维护缓冲区的起始和尾后迭代器start,finish
  • 维护map的大小,当map所提供的大小不足时,需要*重新配置**一块新的大小

stl_pic_49.png

有了上面这些成员,如下几个deque的操作便可以轻易完成:

stl_pic_50.png

4.4.5 deque的构造和内存管理

首先我们先了解一下当初始化一个deque结构时,内存是如何进行分配和构造的

deque <int,alloc,8> ideq(20,9);//创建一个队列,并保留20个元素,均初始化为9,每个缓冲区的大小为8

deque自行定义了两个专属的空间配置器:

  • 一个是map数组的节点内存配置器
  • 一个是缓冲区的内存配置器
protected:
    typedef simple_alloc<value_type,Alloc> data_allocator;
    typedef simple_alloc<pointer,Alloc> map_allocator;

    //并提供一个构造函数:
    deque(int n , const value_type& value):
    start(),finish(),map(0),map_size(0){
        fill_initialize(n,value);//向缓冲区填充n个元素value
    }

接下来我们看看是如何分配内存并填充元素的fill_initialze的:

stl_pic_51.png

map结构的创建和缓冲区的分配:

  1. 创建map数组结构
  2. 为map结构中的所有节点配置缓冲区
  3. 为deque设置队首和队尾(下一个位置)元素迭代器

stl_pic_52.png

向队尾插入元素时:

  • 若缓冲区还有剩余空间,则直接插入后构造,并设置好尾后迭代器finish
  • 若最后只剩下最后一个可用空间,插入后需要新创建一个map中的节点,指向新创建的一个缓冲区,尾后迭代器finish指向该缓冲区的第一个元素

stl_pic_53.png

stl_pic_54.png

向队首插入元素时:

  • 若缓冲区还有剩余空间,则直接插入后 构造,并设置好 队首迭代器finish
  • 没有(和队尾插入元素的区别)可用空间,插入后需要新 创建一个map中的节点,指向新创建的一个缓冲区,队首迭代器指向该缓冲区的 最后一个元素。
void push_front(const value_type& t){
    if(start.cur != start.first){
        construct(start.cur-1,t);
        --start.cur;
    }else
        push_front_aux(t);//没有可用空间时
}

stl_pic_55.png stl_pic_56.png

检测map 数组是否需要扩充:

  1. 当map数组尾端的节点备用空间不足时,需要重新配置reserve_map_at_back
  2. 当map数组的首端的节点备用空间不足时,需要重新配置reserve_map_at_front
  3. 重新配置map的函数为reallocate_map()函数:
    • 首先判断当前map的大小是否为所有节点数的两倍以上
      • 是,则只需要在本数组中调整所有节点的位置到中间即可
      • 不是,需要重新分配更大的map数组,将原数组中的节点拷贝到合适的位置,然后回收原map数组的内存
    • 最后重新设置deque的队首迭代器和尾后迭代器start,finish
void reserve_map_at_back(size_type nodes_to_add = 1)//要添加的节点个数{
    if(nodes_to_add + 1 >map_size-(finish.node -map))//map尾段的可用空间不足
        reallocate_map(nodes_to_add,false);//重新分配map
}

void reserve_map_at_front(size_type nodes_to_add = 1)//要添加的节点个数{
    if(nodes_to_add >start.node -map)//map首端的可用空间不足
        reallocate_map(nodes_to_add,true);//重新分配map
}

对map的重新分配操作:

stl_pic_57.png

4.4.6 deque的元素操作(pop_back,pop_front,clear,erase,insert)

队列的的迭代器可用于各类STL算法,因为该迭代器为RandomAccessIterator类型

队尾删除元素,队首删除元素

和添加元素一样,我们需要考虑缓冲区的边界问题,但这里是释放缓冲区,不是新分配缓冲区,原理我就不再赘述了,直接上代码:

stl_pic_58.png

clear():清楚所有节点

  • 如果有多个缓冲区:

    1. 先将除头尾两个缓冲区的所有缓冲区全部析构后释放内存,因为这些缓冲区肯定都是饱满
    2. 在分别析构头缓冲区和尾部缓冲区的对象,但只释放尾部缓冲区,头部缓冲区保留
  • 如果只有一个缓冲区:根据start和finish直接析构,不释放缓冲区
  • 最后设置deque的 finish = start

stl_pic_59.png

erase:擦除迭代器所指元素,通过指针操作

擦除迭代器指定的元素:

  1. 如果擦除元素的前面的元素个数较少,则将前面所有的元素向后面拷贝一个距离,然后将队首的元素pop_front()
  2. 如果擦除元素的后面的元素个数较少,则将前面所有的元素向前面拷贝一个距离,然后将队尾的元素pop_back()

stl_pic_60.png

擦除一定范围内的元素,思路和上面擦出一个元素差不多,只不过最后处理不是调用pop_front和pop_back,而是直接调用destroy和deallocate进行析构后释放处理。

stl_pic_61.png

insert:插入一个元素

思路其实和erase操作如出一辙,主要是做尽可能少的数据移动

  1. 当在队首前插入元素时,则直接调用push_front()
  2. 在队尾插入元素时,直接调用push_back()
  3. 在队中插入元素时:
    • 若插入位置的前面元素少,将前面的所有元素向前移动一个距离(调用copy函数)
    • 若插入元素的后面元素较少,将后面的所有元素向后移动一个距离(调用copy_backward函数)
iterator insert(iterator position,const value_type& x){
    if(position.cur == start.cur){
        push_front(x);
        return start;
    }else if(position.cur == finish.cur){
        iterator tmp = finish;
        --tmp;
        return tmp;
    }else{
        insert_aux(position,x);//插入队列中间
    }
}

队列中间部分的插入操作: stl_pic_62.png

4.5 stack

stack是一种先进后出的数据结构,只有一个出口,除了顶端以外,没有任何其他方法可以存取 stack的其他元素,换言之,stack不允许有遍历行为,也就没有迭代器

  • deque是双向开口的数据结构,若以deque为底部结构,并封闭其头端开口,便可以轻易地形成一个stack。因此SGI STL便以deque作为缺省情况下的stack底部结构。
  • 由于stack系以底部容器完成其所有工作,而具有这种“修改某物接口,形成另一种风貌者”称为adapter(配接器),因此STL stack往往不被归类为容器,而被归类为container adapter

stl_pic_63.png

我们也可以用list来做底层容器实现stack:

stack<int,list> isstack;

4.6 queue

queue是一种先进后出的数据结构,同stack一样,queue也是一种适配器,默认使用deque作为底层容器来实现,同样可以用list做底层容器实现: stl_pic_64.png

list做底层容器:

queue< int ,list< int » iqueue;

4.7 heap

4.7.2 heap算法

堆的性质和结构不再赘述,详见排序算法博客:http://blog.xbblfz.site/2018/03/06/排序算法/

主要介绍一下堆的上溯操作(添加数据)和下沉操作(删除数据)的代码实现:

上溯

stl_pic_65.png

当向堆中添加数据时,由于堆是由数组实现的,数组中第一个元素保留,这样可以满足父节点为i时,他的左右孩子节点分别为2i和2i+1,随后在数组的末端添加一个空洞元素,进行上溯操作。

由于堆中的数组结构要求能够动态扩展,所以我们底层的实现容器采用vector容器:

stl_pic_66.png

下沉

将节点的元素删除后会放到数组堆的最后一个节点处。

stl_pic_67.png

stl_pic_68.png

stl_pic_69.png

sort_heap算法

堆排序,就是从堆中逐个获取最大(或最小)的元素,放在数组堆的末端,循环调用pop_heap()即可。:

stl_pic_70.png

stl_pic_71.png

make_heap算法

堆创建算法:给一个数组,元素个数为N,从右至左(防止冗余的比较,从底部逐渐将大的元素向上浮动)对前N/2个元素进行下沉操作即可,因为只有前N/2个元素为根节点需要下沉。

stl_pic_72.png

4.7.3 heap没有迭代器

heap的一系列操作都是一套算法,作用于vector实现堆的一些性质。

4.8 priority_queue

priority_queue也是一个容器适配器,默认情况是使用max_heap完成的,后者是一个结合vector表现的完全二叉树结构,所以相当于priority_queue以底部容器为基础,结合heap算法的处理规则,实现的优先级队列。 stl_pic_73.png

priority_queue不提供遍历功能,没有迭代器

4.9 slist

4.9.1 slist 概述

  • list是一个双向链表,slist则是一个单向链表,主要差别在于list的迭代器为 BidirectionalIterator(双向迭代器),slist使用的是 ForwardIterator(单向迭代器)

  • STL的习惯是在一个元素之前插入元素,但这对于slist是不适用的,因为slist中的任何节点都无法知道它的上一个节点的元素和位置,所以对slist有单独的插入操作:insert_after()和erase_after()

  • 基于效率的考虑,slist不提供 push_back(),只提供 push_front(),因此slist的元素次序和元素插入进来的次序相反

4.9.2 slist的节点和迭代器

slist的节点和迭代器的设计比list复杂许多,运用的继承关系。

stl_pic_74.png

节点

结构实现如下:

stl_pic_75.png

迭代器

迭代器的基本结构:实现对节点基本结上构的操作 stl_pic_76.png

单向链表节点的迭代器结构: stl_pic_77.png

4.9.4 slist的数据结构

主要内容为:

  • create_node
  • destroy_node
  • swap
  • front
  • push_front
  • pop_front

stl_pic_78.png stl_pic_79.png

5.关联式容器

标准的STL关联式容器为set和map两大类,以及这两大类的衍生体multiset和multimap。这些容器的底层机制均由RB-tree(红黑树)完成,RB-tree也是一个独立容器,但并不开放给外界使用。

SGI STL还提供了一个不在标准规格之列的关联式容器:hash table(散列表),以及以此hashtable为底层机制而完成的hash_set,hash_map,hash_multiset,hash_multimap

关联式容器没有所谓的头和尾结构,一般而言,关联式容器的内部结构是一个平衡二叉树,STL中使用的是RB-tree

stl_pic_80.png

5.1 红黑树相关的概念

红黑树相关的概念在幕布中的 STL容器机制的底层实现中有具体介绍,概念上的内容不做过多介绍,这里主要从源码的角度来进行介绍

5.2.3 RB-tree的节点设计

红黑树节点的基本结构设计:

stl_pic_81.png

红黑树节点设计(包含存储对象数据):

stl_pic_82.png

5.2.4 RB-tree的迭代器

红黑树的迭代器结构也分为两层,上层为迭代器的基本结构,指向红黑树节点的基本结构,下层才为红黑树的迭代器,指向红黑树的节点。和slist中的迭代器设计类似。

stl_pic_83.png

红黑树的基础迭代器结构:

我们主要关注increment()和decrement()两个操作:

我们要先了解红黑树的一些特殊设计:

stl_pic_86.png

  • increment():该函数就是找到将该红黑树进行中序遍历后获取的链表的下一个节点,也就是比该节点的元素中最小的那一个
    • 状况1:该节点有右子树,找到该右子树的最左节点
    • 状况2:没有右子树,找到第一个该节点在其左子树上的父节点
    • 状况3,状况4:该节点正好为根节点,且没有右子树的情况,其parent为header,而header的parent也为根节点
  • decrement():该函数就是找到将该红黑树进行中序遍历后获取的链表的上一个节点,也就是比该节点的元素中最大的那一个
    • 状况1:该节点为header节点时
    • 状况2:该节点有左子树,找到左子树的最右节点
    • 状况3:没有左子树,找到第一个该节点在其右子树上的父节点

stl_pic_84.png

红黑树正规迭代器

红黑树正规迭代器中涉及到一些和节点保存的数据对象相关的操作:其中++和–都是利用基础迭代器中的increment()和decrement()函数实现的:

stl_pic_85.png

5.2.5 红黑树的数据结构

红黑树的数据结构我们主要关注三个成员,以这三个成员为基础我们就可以获取整棵树的数据,和存放方式:

  • node_count:该树有多少个节点
  • header:访问红黑树的入口,left保存最小值节点,right保存最大值节点,parent保存根节点
  • key_compare:节点间的比较准则,一般为函数指针对象

红黑树的初始化操作:

init():主要是创建一个header节点。

红黑树的插入操作:

  • insert_unique:将元素插入到红黑树中,且保证红黑树中的元素不重复
  • insert_equal:将元素插入到红黑树中,允许节点值重复

红黑树结构源码:

stl_pic_87.png stl_pic_88.png stl_pic_89.png stl_pic_90.png

5.2.7 RB-tree的元素操作

上一节我们提到了红黑树的插入操作,insert_equal,insert_unique

insert_equal(可重复插入)
  1. 遇到大节点值,往左寻找
  2. 遇到比该值小或相等的节点值,往右寻找
  3. 找到可插入点后(x==0),直接插入

stl_pic_91.png

insert_unique(不可重复插入)
  • 同insert_equal的插入规则一样,但是找到插入点后,还要检测是否存在重复元素
  • 一般往一棵树(没有重复数)中插入一个重复的值x’(对应树中的x),肯定会插入到x节点的右子树的最左节点

stl_pic_92.png

__insert(真正的插入操作)

插入时需要考虑下面几个问题:

  • 是否在header的孩子节点上插入,需要设置header的相关指针
  • 正常插入,需要考虑header的left和right的指针变动情况
  • 设置新节点的left,right,parent指针
  • 红黑树的颜色调整
  • 红黑树的节点计数增加

stl_pic_93.png

红黑树的颜色调整:单旋转,双旋转,左旋转,右旋转

这部分内容了解概念即可,源码部分见书P225面的实现。

5.3 set

  • set的特性是,所有的元素都会根据元素的键值自动排序,set的元素不像map那样可以同时拥有实值和键值,set元素的实值就是键值

  • 我们不能通过set的迭代器修改其元素值,set的迭代器为const_iterator,键值是无法被修改的

  • set和list有相同的性质,客户端对它进行元素的新增操作时或删除操作时,原有的迭代器都不会失效,其实set就是一棵红黑树,红黑树就是通过链表来实现的。

  • STL为set提供了一组算法:
    • set_insersection(交集)
    • set_union(并集)
    • set_difference(差集)
    • set_symmetric_diffrence(对称差集)
  • STL的set是以RB-tree为底层机制,又由于set所开放的各种操作接口,RB-tree也都提供了,所以几乎所有的set操作行为,都只是转调用RB-tree的操作行为而已

  • set的实现主要是根据其成员 rep_type t;红黑树结构调用相应的操作实现,在插入操作上红黑树转调用的是 insert_unique操作。源码这里不做展示,可见书P235。
template<class Key,class Compare = less<Key>, class Alloc = alloc>//默认递增排序
class set{
    ...
}
//set模版参数传入键值即可

5.4 map

map和set类似都是对RB_tree 操作的转调用,区别在于map模版参数传入键值和实值,实值可以修改,键值不能修改

  • key_type :键值型别
  • data_type: 实值型别
  • value_type: 节点值类型:pair

map中的插入操作也是转调用RB_tree的insert_unique函数,源码见书P239

template<class Key,class T, class Compare = less<Key>,class Alloc = alloc>
class map{
    ...
}

5.5 multiset,multimap

  • multiset的特性和用法和set完全相同,唯一的差别在于它允许键值重复,因为它的插入操作采用的是底层机制RB-tree的insert_equal()实现的

  • multimap的特性和用法和map完全相同,唯一的差别在于它允许键值重复,因为它的插入操作采用的是底层机制RB-tree的insert_equal()实现的

5.7 hashtable

hashtable的原理在 幕布的STL容器底层实现中有简单介绍,这里直接进入hashtable的源码实现部分。在STL的hash table表格内的元素为桶子bucket,表格内的每个单元不仅仅包含一个节点,而是一桶节点。

哈希表的节点定义:

template<class Value>
struct __hashtable_node{
    __hashtable_node * next;
    Value val;
};

5.7.3 hashtable的迭代器

  • hashtable的迭代器属于单向迭代器
  • 每一个迭代器除了拥有指向自身节点的指针cur
  • 还要有一根指针维护和hashtable的关系ht,因为在operator++操作时可能出现从一个bucket跳到下一个bucket

stl_pic_94.png

stl_pic_95.png

5.7.4 hashtable的数据结构

hashtable的数据结构模版中需要传入6个参数:

  1. Value: 实值型别
  2. Key: 键值型别
  3. HashFcn: 哈希散列函数型别
  4. ExtractKey: 从节点中取出键值的方法(函数或仿函数)
  5. EqualKey: 判断两个键值是否相同的方法(函数或仿函数)
  6. Allc: 空间配置器

hashtable的五个成员:

  1. hash: 散列函数
  2. equals: 判断两个键值相等的函数
  3. get_key: 从一个节点获取键值的函数
  4. buckets:hashtable的实体结构,实际上就是存储对象为node* 的vector结构
  5. num_elements: 所有节点的数量

stl_pic_96.png

  • 虽然开链法并不要求表格的大小必须为质数,但SGI STL仍然以质数来设计表格大小
  • 并且预先将28个质数(逐渐呈现大约两倍的关系)计算好,以便随时访问
  • 同时提供一个函数,用来查询这28个质数中“最接近某数并大于某数”的质数。

stl_pic_97.png

5.7.5 hashtable的构造和内存管理

hashtable的节点配置和释放函数:

stl_pic_98.png

hashtable的构造函数:

stl_pic_99.png stl_pic_100.png

hashtable的插入操作和表格重整
//不可重复插入
pair<iterator,bool> insert_unique(const value_type & obj){
    resize(num_elements + 1);//判断是否需要表格重整
    return insert_unique_noresize(obj);//插入表格
}

//可重复插入
pair<iterator,bool> insert_equal(const value_type & obj){
    resize(num_elements + 1);//判断是否需要表格重整
    return insert_equal_noresize(obj);//插入表格
}

表格重整:

  • 表格是否重建的判断原则是拿元素的个数和bucket的个数进行比较,如果前者大于后者,则需要重整,否则不需要 stl_pic_101.png

将旧桶中的节点添加到新桶中的过程:

stl_pic_102.png

插入操作:(不允许键值重复)

先遍历要插入桶中的所有元素,是否有相等的节点,没有则将该节点插入到链表头部:

stl_pic_103.png

插入操作:(允许键值重复)

先遍历要插入桶中的所有元素,是否有相等的节点,有则插入到相等节点位置之后,没有则插入到链表头,这样是为了将所有相等的节点保存在一起

stl_pic_104.png

复制(copy_from)和整体删除(clear):这两个函数没什么特别的,只需要知道有这两个函数存在即可

5.7.7 hash散列函数

SGI STL默认使用的散列函数针对char,int,long等整数型别的型别,什么也没做,只是返回其原值。而对于字符串(const char *),设计了一个转换函数:

inline size_t __stl_hash_string(const char * s){
    unsigned long h = 0;
    for(;*s;s++){
        h = 5*h + *s;
    }
    return size_t(h);
}

SGI的hashtable可以为

  • char*
  • const char*
  • char
  • unsigned char
  • signed char
  • short
  • unsigned short
  • int
  • unsigned int
  • long
  • unsigned long

为这些型别都有对应的hash函数来进行散列,这些型别以外的类型则不能使用默认的hash散列函数,需要我们自己定义后提供给hashtable模版。比如string ,double,float都需要自定义hash散列函数

5.8 hash_set,hash_multiset,hash_map,hash_multimap

  • 这四个关联容器同标准的set,multiset,map,multimap的区别在于前者是使用hashtable(无序)为底层机制来实现的,后者使用RB_tree(有序)来实现的
  • 这四个关联容器的实现都是通过转调用hashtable的操作实现的
  • 同样的,hash_set和hash_map是建立在hashtable的insert_unique来实现的插入操作,所以没有重复的元素,hash_multiset和hash_multimap是建立在hashtable的insert_equal来实现的插入操作,允许存在重复的元素

6. 算法

STL算法总览:

stl_pic_105.png stl_pic_106.png stl_pic_107.png stl_pic_108.png

6.1.3 质变算法 - 会改变操作对象之值

质变算法是指运算过程中会更改区间内的元素内容:

  • copy: 拷贝
  • swap:互换
  • replace:替换
  • fill:填写
  • remove:删除
  • permutation:排列组合
  • partition:分割
  • random shuffling:随机重拍
  • sort:排序

6.1.4 非质变算法

  • find:查找
  • search:匹配搜索
  • count:计数
  • for_each:遍历
  • equal,mismatch:比较
  • max,min:寻找极值

6.1.5 STL算法的一般形式

所有泛型算法的前两个参数都是一对迭代器,通常称为first和last,用以标示算法的操作区间,STL习惯才用前闭后开区间表示法,写成[first,last)。

每一个迭代器可分为5类,每一个STL算法的声明都表现出它所需要的最低程度的迭代器类型。

许多STL算法不只支持一个版本:

  • 这一类算法的某个版本采用缺省行为
  • 另一个版本提供额外的参数,接受外界传入的一个仿函数。
  • 如unique()缺省情况使用equality操作符,用户也可以调用另一个版本传入自定义的equality操作符

质变算法通常提供两个版本:

  1. in-place(就地进行)版,直接改变操作对象
  2. copy版,将操作对象复制一份副本,然后在副本上进行修改并返回该副本,copy版总是以__copy作为函数名称后缀。不是所有的质变算法都有copy版,如 sort()就没有

数值算法:实现于,必须先包含上层头文件

  • adjacent_difference()
  • accumulate()
  • inner_product()
  • partial_sum

其它算法都实现于SGI的文件中,必须先包含上层头文件

6.2 算法的泛化过程

将算法独立于其所处理的数据结构之外,不受数据结构的羁绊为算法的泛化过程,我们使用迭代器的观念(注意是观念,不是特殊的类,只要可以按次序访问数据结构即为迭代器,所以指针也是一种迭代器)来完成算法的泛化过程。

6.3 数值算法(每个算法都有两个版本,一个使用默认操作符,一个使用自定义操作符)

6.3.2 累加算法accumulate

//版本1
template<class InputIterator,class T>
T accumulate(InputIterator first,InputIterator last,T init){//init防止迭代器区间为空时,要有正确的值返回
    ...
}

//版本2:自定义操作符
template<class InputIterator,class T>
T accumulate(InputIterator first,InputIterator last,T init){
    ...
}

6.3.3 相邻元素的差值计算:adjacent_difference

partial_sum和adjacent_difference互为逆运算

//将迭代器范围中的第一个元素和每两个相临之间的差值从result指示的位置开始记录
template<class InputIterator,class OutputIterator>
OutputIterator adjacent_difference(InputIterator first,InputIterator last,OutputIterator result){
    ...
}

//版本2:自定义减号运算符
template<class InputIterator,class OutputIterator,class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first,InputIterator last,OutputIterator result,BinaryOperation binary_op){
    ...
}

6.3.4 内积计算inner_product

内积的概念:(1,2,3)X(4,5,6) = 14+24+3*6 = 30

//将first1到last1内的元素与从first2开始相同数量的元素做内积后返回,如果区间为空,返回init
template<class InputIterator1,class InputIterator2,class T>
T inner_product(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,T init){
    ...
}

//版本2:自定义+和*
template<class InputIterator1,class InputIterator2,class T,class BinaryOperation1,class BinaryOperation2>
T inner_product(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,T init,BinaryOperation1 binary_op1,BinaryOperation2 binary_op2){
    ...
}

6.3.5 相邻元素求和partial_sum

和adjacent_difference互为逆运算。不再赘述

6.3.6 power(非STL标准)

求幂运算,可以自定义乘法运算符

6.3.7 iota(非STL标准)

设定某个区间的内容,是其内部每一个元素从指定的value值开始,增递增状态

6.4 基本算法

6.4.2 euqal,fill,fill_n,iter_swap,lexicographical_compare,max,min,mismatch,swap

equal:

//版本1:比较first1到last1区间的元素和从first2开始相同数量的元素是否相等
template<class InputIterator1,class InputIterator2>
inline bool equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2){
    ...
}

//提供自定义相等操作符
template<class InputIterator1,class InputIterator2,class BinaryPredicate>
inline bool equal(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,BinaryPredicate binary_pred){
    ...
}

fill

//将first到last区间所有的元素都设置为value
template<class ForwardIterator,class T>
void fill(ForwardIterator first,ForwardIterator last,const T& value){
    for(;first!=last;++first)
        *first = value;
}

fill_n

//将first开始后面n哥元素的值设置为value
template<class OutputIterator,class Size,class T>
OutputIterator fill_n(OutputIterator first,Size n,const T& value){
    for(;n>0;--n,++first)
        *first = value;
    return first;
}

当n超过容器的现有大小,会导致一些不可预期的错误。

解决办法:利用inserter()产生一个具有插入而非覆写能力的迭代器。

iter_swap

将两个迭代器所指的元素进行交换

lexicographical_compare

以字典排序对两个序列[first1,last1)和[first2,last2)的元素进行比较,类似于字符串比较

当序列1中的元素小于序列2中的元素时返回true,大于等于返回false。

max,min

返回两个对象的较大者,或较小者,可以自定义比较操作符。

mismatch

用来平行比较两个序列之间第一个不匹配点

swap

交换两个对象的内容

6.4.2 copy

首先拷贝copy函数有三个版本,一个泛化版本,两个全特化版本

  • 泛化版本:传入参数都是迭代器
    • 全泛化版本
      • __copy: InputIterator迭代器类型普通版本,速度慢
      • __copy => __copy_d:RandomAccessIterator迭代器类型强化版本
    • 偏特化版本(判断指针所指对象T的赋值操作函数是否为trivial)
      • __copy_t:原生指针类型T*(trivial:调用memmove,否则调用 __copy_d)
      • __copy_t:常量原生指针类型const T*(trivial:调用memmove,否则调用 __copy_d)
  • 特化版本:传入的参数是char * 或wchar_t*,直接使用memmove函数进行拷贝

关系如下图:

stl_pic_109.png

  • 如果输出区间的起点位于输入区间,copy算法便(可能)会在输入期间的(某些)元素尚未被复制之前就覆盖其值,导致错误的结果。

stl_pic_110.png

  • 为什么是可能?因为copy算法会根据其所接受的 迭代器的特性决定来调用 memmove()来执行任务,memmove()会先将整个输入区间的内容复制下来,就没有被覆盖的危险。

stl_pic_111.png

stl_pic_112.png

  • 上述这个deque换成vector时,就不会出现错误,因为vector的迭代器就是原生指针

三个版本:泛化版和两个特化版

stl_pic_113.png

四个迭代器版本:

stl_pic_114.png

分别根据迭代器类型的两个重载函数版本和赋值函数是否为trivial的两个重载函数版本

__copy的两个版本(根据迭代器类型重载): stl_pic_115.png

__copy_t的两个版本(根据赋值函数是否trivial重载):

stl_pic_116.png

6.4.4 copy_backward

实现方式和copy类似,只不过不同于copy的时,输出区间是先确定区间的前闭后开区间的终点,然后用逆向拷贝的方式进行拷贝,同样该终点(就正向区间而言)若落在输入区间内部就可能出现问题

6.5 set相关

STL一共提供了四种与set(集合相关)的算法,分别是并集,交集,差集,对称差集。SGI STL虽然提供有hash_set/hash_multiset两种容器,以hashtable为底层机制,其内的元素并未呈现排序状态,所以不可以使用这四种算法。

每一个算法提供两个版本:一个版本默认”<”操作符,另一个版本用户自定义”<”操作符。

例子:

stl_pic_117.png

这些算法都有考虑到重复元素出现的情况,接下来会具体介绍

6.5.1 set_union并集

当有重复元素出现时,结果集中该重复元素重复出现的次数和这两个集合中该元素出现次数的最多次

stl_pic_118.png

6.5.2 set_insersection交集

交集,遇到重复的元素时,结果集中该重复元素出现的次数和这两个集合中该元素出现次数的最少次数

stl_pic_119.png

6.5.3 set_difference差集

差集,遇到重复元素时,结果集中只包含集合中多出来的重复元素

stl_pic_120.png

6.5.3 set_symmetric_difference对称差集

stl_pic_121.png

6.7 其它算法

6.7.1 简单算法

  • adjacent_find:找出第一组满足条件的相邻元素,这里所谓的条件在版本1是指“两元素相等”,版本2中可以自定义相等二元运算**
  • count: 运用equality操作符,返回[first,last)区间内和指定value相等的元素的个数
  • count_if:和count的区别在于,提供了预测函数predict,预测为真代表相等,否则不相等
  • find:根据equality 操作符,返回[first,last)相等的第一个元素的迭代器,否则返回last
  • find_if:和find的区别在于提供预测函数
  • find_end:在序列1[first1,last1)中寻找匹配(完全匹配)序列2[first2,last2)的最后一个子序列的起始迭代器,如果没有完全匹配的序列则返回last1
    • 区间迭代器类型是单向迭代器和双向迭代器的处理办法不同,双向迭代器利用reverser_iterator会处理的快
    • 主要是通过search函数找到匹配的子序列首次出现的点
  • find_first_of:本算法以[first2,last2)区间内任意一个元素为查找目标,查找在[first1,last1)区间内[first2,last2)的任意元素第一次出现的点,和find_end不同的是序列不用完全匹配
  • for_each:将仿函数f,执行在[first,last)区间的每一个元素身上
  • generate:将gen()函数的运算结果赋值到[first,last)每一个元素上
  • generate_N将gen()函数的运算结果赋值到first开始后面n个元素上
  • includes:判断序列S2是否涵盖序列S1,S1和S2必须要是有序序列
    • stl_pic_122.png
  • max_element:返回[first,last)区间数值最大的元素,有一个版本可以提供比较函数
  • merge:将两个经过排序的集合S1和S2合并起来置于另一段空间result,依然有序。
  • min_element:获取区间[first,last)数值最小的元素,有一个版本可以提供比较函数
  • partition:(不稳定版)partition会将区间[first,last)中的元素重新排列,所有被一元条件预测函数pred判断为true的元素都会被放到区间的前段,被判断为false的元素放到区段后面。这个不保证元素原始的相对位置,若要保证,则需要使用stable_partition
  • remove:将所有不等于value的值都拷贝到[first,last)的前端,后段不需要变动。这样得到的结果就是[first,last)的前面部分为不等于value的值,返回值为前端不等于value区间的尾后迭代器
    • stl_pic_123.png
  • remove_copy:将[first,last)移除后的结果拷贝到一个新的容器result中区间
  • remove_if,remove_copy_if:对应remove,remove_copy,提供预测函数pred
  • replace:将[first,last)区间内的所有old_value 都以new_value取代
    • replace_copy,replace_if,replace_copy_if
  • reverse:将迭代器区间[first,last)元素倒序
    • reverse_copy
  • rotate:将[first,middle)和[middle,last)内的元素互换,和swap_ranges()类似,但rotate可以互换两个不同长度的区间,swap_ranges()只能互换长度相同的区间
    • stl_pic_124.png
    • rotate根据迭代器类型的不同分为三类来进行处理
      • 单向迭代器
      • stl_pic_125.png
      • 双向迭代器(三次调用reverse)
      • stl_pic_126.png
      • 随机迭代器
      • stl_pic_127.png
  • rotate_copy:
  • search:在序列1[first1,last1)所涵盖的区间中,查找[first2,last2)的首次出现的点,有一个可以提供二元运算相等符的版本
  • search_n:在序列[first,last)所涵盖的区间中,查找“连续count个符合条件之元素”的子序列
    • stl_pic_128.png
  • swap_ranges:将[first1,last1)区间内的元素与“从first2开始个数相同的”元素互相交换
    • stl_pic_129.png
  • transform:和for_each类似,只不过将用仿函数op作用于[first,last)中的每一个元素的结果存放到result指定的新序列中。还有一个版本是提供一个二元运算仿函数,函数的参数为两个区间[first1,last1]和first2开始的区间内的元素
    • stl_pic_130.png
  • unique():同remove,这里是将重复的元素“移除”
    • unique_copy()

6.7.2 复杂算法

  • lower_bound:利用二分查找的原理,试图在已排序的[first,last)中寻找元素value,如果有和value相等的元素应该,返回一个迭代器指向其中第一个元素,如果没有,则返回一个迭代器指向value应该插入的位置
  • upper_bound:利用”二分查找”的原理,求value元素可以插入的最后一个位置
  • binary_search:二分查找,在已排序[first,last)区间寻找元素value,有返回true,没有返回false,有一个版本可以提供比较函数
  • next_permutation():返回[first,last)区间所标示的序列的下一个排列组合,如[a,b,c]有排列组合{abc,acb,bac,bca,cab,cba}这些组合按字符串比较就是从小到大的排序,当[first,last)中的序列为acb时,则下一个排列组合就是bac。该函数有两个版本,有一个版本可以提供比较函数
  • prev_permutation:对应next_permutation,返回前一个排列组合
  • random_shuffle:这个算法将[first,last)中的元素次序随机重排,random_shuffle会产生一个均匀分布,使得任何一个排列被选中的几率都为(1/N!)
    • 实现原理就是通过遍历一遍该数组,遍历到一个元素时,随机和序列中的该元素前面的一个元素进行交换
    • stl_pic_131.png
  • partial_sort/partial_sort_copy:为了找出middle-first 个最小的元素,本算法接收一个middle迭代器器,然后重新排列[first,last),使得序列中middle-first个最小元素按递增顺序排列到[first,middle)区间,其余的元素排列到[middle,last),不保证有任何特定顺序。
    • 原理就是利用堆排序,先构建堆,然后逐个找出最小元素,且只接收RandomIterator
    • stl_pic_132.png

6.7.9 排序算法sort()

STL所提供的各式各样的算法中,sort()是最复杂最庞大的一个,这个算法接收两个RandomIterator,然后将区间内的所有元素由小到大重新排列,第二个版本则允许用户指定一个仿函数作为排序标准

  • 关系型容器都拥有自动排序的功能,所以不需要sort算法
  • stack,queue,priority_queue有特定的出入口,所以不能使用sort算法
  • vector,deque和list:前两个迭代器为RandomIterator适合使用sort算法,list迭代器属于forward_iterator,不适合sort算法,对于list和slist使用排序算法,应该使用自己提供的成员函数sort()

  • sort排序思路:
    • STL的sort算法,数据量大时采用QuickSort,分段递归排序
    • 一旦分段后的数据量小于某个门槛,为避免QuickSort的递归调用带来过大的额外负担就改用InsertionSort。
    • 如果递归层次过深,还会改用Heap Sort
  • 快排的三点中值枢纽选取法
  • 阈值thredhold
    • 何时改用插入排序来替代快排(当元素个数小于16时)
    • 何时改用堆排序:当递归次数超过限制的次数(该次数随着元素的个数变化)

stl_pic_133.png stl_pic_134.png

6.7.10 equal_range(应用于有序区间)

找到和value相等的区间,先用二分法找到一个元素和value相等,再确定lower_bound和upper_bound,在LeetCode有看到这一题:搜索一个数字在一个递增数组(允许数字重复)中出现的范围

6.7.11 inplace_merge(就地合并)

如果两个连接在一起的序列[first,middle)和[middle,last)都已经排好序,那么inplace_merge可以将这两个序列合并为一整个排好序的序列[first,last)

inplace_merge有两个版本,有一个版本可以提供自定义的比较操作函数

inplace_merge在有额外的内存辅助,效率会好许多,但在没缓冲区或缓冲区不足的情况下也可以运作:

stl_pic_135.png

有缓冲区下的实现方式:

stl_pic_136.png

6.7.12 nth_element

快排中所经历的过程,重排[first,last),确定第n大(或小)的元素在第n个位置上,且前面的元素全部小于该元素,后面的元素全部大于该元素。但不保证这些元素之间的顺序。

  • 先使用三分中值切割法,确定一个值的正确位置
  • 若该位置小于n,则对右部分进行三分中值切割重排
  • 若该位置大于n,则对左部分进行三分中值切割重排
  • 不断缩小切割重排的范围即可。

stl_pic_137.png

6.7.13 mergesort归并排序

分而治之的归并排序:

stl_pic_138.png

7.仿函数

仿函数是C++中的函数对象,一种具有函数特质的对象。

仿函数的作用主要用于满足STL对抽象性的要求,就实现观点而言,仿函数其实就是一个“行为类似函数”的对象,其类别定义中必须自定义function call运算符。

#include <functional>
#include <iostream>
using namespace std;

//两种调用方式
int main(){
    greater<int> ig;
    cout << boolalpha <<ig(4,6);//false
    cout << greater<int>()(6,4);//true,实例化一个临时对象后调用函数
}

下图表示STL仿函数与STL算法的关系: stl_pic_139.png

  • STL以操作数划分,可分为一元和二元仿函数,若以功能划分,可分为算术运算,关系运算和逻辑运算三大类。
  • STL 仿函数应该有能力被函数配接器修饰,彼此像积木一样串接,为了拥有配接能力,每一个仿函数必须定义自己的相应型别,就像迭代器的五个型别来适应STL规范。
  • 仿函数的相应型别主要用于表现参数型别和传回值型别。为了方便起见,定义了两个classes分别代表一元仿函数和二元仿函数

7.2.1 unary_function 一元函数

unary_function用来呈现一元函数的参数型别和返回值类型:

template <class Arg,class Result>
struct unary_function{
    typedef Arg argument_type;//参数类型
    typedef Result result_type;//返回值类型
};

stl_pic_140.png

7.2.2 binary_function二元函数

binary_function用来呈现二元函数的第一个参数型别,第二参数型别以及返回值型别

template<class Arg1,class Arg2,class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argumrnt_type;
    typedef Result result_type;
}

stl_pic_141.png

7.3 算术类仿函数

STL内建的“算术类仿函数”,支持加法,减法,乘法,除法,模数(余数)和否定运算,除了否定运算是一元运算,其余都是二元运算。

  • plus
  • minus
  • multiplies
  • divides
  • modulus
  • negate

stl_pic_142.png

证同元素

所谓op的证同元素,意思是数值A与该元素做op运算,会得到A自己。加法的证同元素为0,因为任何元素加上0仍然为自己,乘法的证同元素为1.`

7.4 关系运算类仿函数

均为二元运算符

  • 等于:equal_to
  • 不等于:not_equal_to
  • 大于:greater
  • 大于或等于:greater_equal
  • 小于:less
  • 小于或等于:less_equal

7.5 逻辑运算类仿函数

逻辑类仿函数包括And,or,not三种运算,其中And,or为二元运算,Not为一元运算

  • And:logical_and
  • Or:logical_or
  • Not:logical_not

7.6 证同,选择,投射

这部分的仿函数都只是将其参数原封不动地传回,其中某些仿函数对传回的参数有刻意的选择,或者刻意的忽略。设计这些仿函数的目的在于是想划分一层,实现间接性。

stl_pic_143.png

8.配接器adapters

配接器在STL组件的灵活组合运用的功能上,扮演着轴承、转换器的角色。配接器用于讲一个对象的借口转换成另一个对象的接口。

配接器就是一种具有接口标准的对象。可以用其他的对象来实现。配接的过程则要么通过类的实例化实现,要么通过辅助函数实现。

8.1 配接器分类

  • 仿函数配接器
  • 容器配接器
  • 迭代器配接器

8.1.1 容器配接器

STL提供的两个容器queue和stack其实都只不过是一种配接器,他们修饰deque的接口而成就出另一种容器风貌。

8.1.2 迭代器配接器

STL提供的迭代器适配器:包括insert adapter,reverse iterator,iostream iterator。

Insert Iterators

插入迭代器,将一般迭代器的赋值操作转变为插入操作,包括

  • 尾端插入迭代器:back_insert_iterator
  • 头端插入迭代器:front_insert_iterator
  • 任意位置插入迭代器:insert_iterator

stl_pic_144.png

Reverse Iterators

可以将一般迭代器的行进方向逆转,使原本operator++的操作变成后退操作,使原本operator–的操作变成前进操作,这种迭代器特别适合用于“从尾端开始进行的算法上”。

IOstream Iterators

可以将迭代器绑定在某个iostream对象身上,对该迭代器进行操作就是执行对应的输入输出操作

stl_pic_145.png

8.1.3 应用于仿函数

仿函数配接器是所有配接器中数量最庞大的一个族群,其配接灵活度也是前两者所不能及,它可以不断嵌套配接,这些配接操作包括系结(bind),否定(negate),组合(compose)以及对一般函数或成员函数的修饰,使其成为一个仿函数。

仿函数配接器可以实现各种各样的表达式:

f(g(elem));

其中f,g都是数学函数,那么可以写成:

compose1(f(x),g(y));//组合操作,生成一个组合操作配接器的实例化对象

例如,我们希望对容器内的每一个元素v进行(v+2)3的操作,我们可以令f(x)=x3,g(y)=y+2;

compose1(bind2nd(multiplies<int>(),3),bind2nd(plus<int>(),2));

这个算式会改变参数的值,所以不能用于for_each算法,因为该算法是非质变算法,但可以用于transform来输出到新的容器中去。

兼容一般函数指针和成员函数指针

为了让一般函数指针和成员函数也能使用配接器适配,所以我们需要通过修饰将一般函数和成员函数修饰为对应的仿函数对象:

修饰一般函数的配接器:ptr_fun(func) 修饰成员函数的配接器:mem_fun_ptr(&class::func)

stl_pic_146.png

8.2 container adapters

stack,deque的源码不做重复的介绍,之前有介绍

8.3 iterator adapters

8.3.1 insert iterator

将对迭代器做赋值操作的时候,就在insert iterator中被转为对该容器的迭代器做插入操作:

  • 也就是说在insert iterators的operator=操作符中调用底层的push_front,push_back或insert操作。
  • 至于其它的迭代器惯常行为如operator++,operator–,operator*都被关闭功能
  • 也就是说对insert iterator的前进,后退,取值,成员取用等操作都是没有意义的,甚至是不被允许的
back_insert_iterator

stl_pic_147.png

front_insert_iterator

不适用于不支持push_front的容器迭代器,如vector

stl_pic_148.png

insert iterator

和前两个迭代器类似,只不过转调用的操作为insert函数

8.3.2 reverse iterators

每一个容器都有rbegin(),rend()操作,且每一个容器都有reverse_iterator的型别定义。所以其实调用rbegin和rend操作中,适配器reverse_iterator也已经被实例化了:

typedef __list(deque)_iterator iterator;
typedef reverse_iterator<iterator> reverse_iterator;

reverse_iterator rbegin(){
    return reverse_iterator(finish);
}
reverse_iterator rend(){
    return reverse_iterator(start);
}

stl_pic_149.png

  • 前进变成后退,涉及到++,+,+=
  • 后退变成前进,涉及到–,-,-=
  • 提领操作 *,去迭代器前面的值。

stl_pic_150.png stl_pic_151.png

8.3.4 stream iterators

将一个流迭代器绑定到一个stream(数据流)对象身上。若绑定到istream则拥有输入能力,绑定到一个ostream身上则拥有数处2能力。

istream_iterator

输入能力的实现主要就是通过调用operator++实现,该操作符会转调用stream的operator»(输入)。流迭代器是一个InputIterator所以不具有operator–操作

stl_pic_152.png

只要客户端定义一个istream iterator并绑定到某个istream上,程序会阻塞到read()函数,等待输入。因此,我们只有在必要的时候定义所需要的istream iterator

拷贝函数copy,和流迭代器istream_iterator合作的例子:

stl_pic_153.png

ostream_iterator

ostream_iterator在内部维护一个ostream member,客户端对这个迭代器所做的 operator=就会转调用ostream对象的 operator«操作。这个迭代器是一个OutputIteartor

stl_pic_154.png

ostream_iterator和copy函数的合作使用:

stl_pic_155.png

8.4 function adapter仿函数迭代器

  • 仿函数是一种将operate()重载的class template
  • 迭代器是一种将指针相关的操作++,*等操作符重载的class template
  • 应用在容器和迭代器身上的配接器都是一种class template
  • 应用在仿函数身上的配接器,通过传入仿函数对象,然后“事先”对一个函数的参数的绑定(多个参数转换为一个参数),执行结果的否定,多方函数的组合,

8.4.1 对返回值进行逻辑否定:not1,not2

  • 构造传入一个预测仿函数对象
  • 调用时,根据调用传入的参数来调用构造时传入的仿函数并执行逻辑非!操作
  • 辅助函数对该适配器进行实例化操作

stl_pic_156.png

8.4.2 对参数进行事先绑定:bind1st,bind2nd

二元仿函数转化成一元仿函数配接器

  • 构造时传入一个二元仿函数,和事先配置好的参数,bind1st事先配置好第一个参数,bind2nd事先配置好第二个参数。
  • 调用该一元仿函数配接器时,再传入还没有配置另一个参数,然后根据这两个参数调用二元仿函数
  • 辅助函数实现该一元仿函数配接器的实例化

stl_pic_157.png

8.4.3 用于函数合成:compose1,compose2

  • 构造时传入要合成的两个仿函数对象(合成二元仿函数compose2需要传入三个仿函数)
  • 调用的时候,根据一定规则组合这些函数的调用组合方式。
  • 辅助函数实例化该配接器

stl_pic_158.png

8.4.3 用于函数指针修饰为仿函数辅助函数:ptr_fun

  • 传入指针作为模版参数,模版对指针进行参数分析,得到函数的相关信息:返回值,参数
  • 继承自unary_function一元仿函数或二元仿函数binary_function,通过膜拜分析的信息,实例化这两个父类对象
  • 调用该仿函数时,就是调用该指针指向的函数
  • ptr_fun为辅助函数,用于实例化配接器pointer_to_unary_function或pointer_to_binary_function

stl_pic_159.png

8.4.4 用于成员函数修饰为仿函数的辅助函数:mem_fun,mem_fun_ref

可以完成泛型到多态之间的重要接合步骤:

  • 也是通过构造函数中传入成员函数的指针,然后模版参数推导得到返回结果信息S,类信息T,成员函数偏移(指针)信息pf
  • 根据这些信息调用每个元素类的成员函数
  • 其中还有区别在于
    • 成员函数是否有一个参数
    • 通过引用,还是通过指针调用
    • 是否为const成员函数

stl_pic_160.png stl_pic_161.png stl_pic_162.png