全世界所有的STL实现版本,都源于Alexander Stepanov和Meng Lee完成的原始版本,这份原始版本有Hewlett-Packard Compant(惠普公司)拥有。每一个头文件都有一份声明,允许任何人任意运用、拷贝、修改、传播、贩卖这些代码,无需付费,唯一的条件是必须将声明置于使用者新开发的文件内
这份开放源代码的精神,一般统称为open source
GNU(音译为“革奴”),代码GUN is Not Unix。当时Unix是计算机界主流操作系统,由AT&T Bell实验室的Ken Thompson和Dennis Ritchie创造。原本只是学术上的一个练习产品,AT&T将它分享给许多研究人员。但是当所有研究与分享使这个产品越来越美好时,AT&T开始思考是否应该追加投资,从中获利。于是开始要求大学校园内的相关研究人员签约,要求他们不得公开或透露UNIX源代码,并赞助Berkeley大学继续强化UNIX,导致后来发展出BSD(Berkeley Software Distribution)版本,以及更后来的FreeBSD、OpenBSD、NetBSD...,Stallman将AT&T的这种行为视为思想禁锢,以及一种伟大传统的沦丧,于是进行了他的反奴役计划,称之为GNU:GUN is Not Unix,GNU计划中,早期最著名的软件包括Emacs和GCC,晚期最著名的是Linux操作系统
GNU以所谓的GPL(General Public License,广泛开放授权)来保护(或说控制)其成员:使用者可以自由阅读与修改GPL软件的源码,但如果使用者要传播借助GPL软件而完成的软件,必须也同意GPL规范。这种精神主要是强迫人们分享并回馈他们对GPL软件的改善。得之于人,舍于人
Cygnus是一家商业公司,包装并出售自由软件基金会所构造的软件工具,并贩卖各种服务。他们协助芯片厂商调整GCC,在GPL的精神和规范下将GCC源代码的修正公布于世;他们提供GCC运作信息,提升其运行效率,并因此成为GCC技术领域的最佳咨询对象。Cygnus公司之于GCC,地位就像Red Hat公司之于Linux
- HP实现版本(HP STL)
- 所有STL实现版本的始祖
- 运行任何人免费使用、拷贝、修改、传播、贩卖这份软件及其说明文件
- 唯一需要遵守的是:必须在所有文件中加上HP的版本声明和运用权限声明
- 这种授权不属于GNU GPL范畴,但属于open source范畴
- P.J. Plauger实现版本(PJ STL)
- 继承自HP版本,所有每一个头文件都有HP的版本说明
- 此外还加上P.J. Plauger的个人版权声明
- 不属于GNU GPL范畴,也不属于open source范畴
- 被Visual C++采用
- 符号命名不讲究、可读性较低
- Rouge Wave实现版本(RW STL)
- 继承自HP版本,所以每一个头文件都有HP的版本说明
- 此外还加上Rouge Wave的公司版权声明
- 不属于GNU GPL范畴,也不属于open source范畴
- 被C++Builder采用(C++Builder对C++语言特性支持不错,连带给予了RW版本正面的影响)
- 可读性不错
- STLport实现版本
- 以SGI STL为蓝本的高度可移植性实现版本
- SGI STL实现版本
- 继承自HP版本,所以每一个头文件都有HP的版本说明
- 此外还加上SGI的公司版权声明
- 不属于GNU GPL范畴,但属于open source范畴
- 被GCC采用(GCC对C++语言特性支持很好,连带给予了SGI STL正面影响)
- 可读性很高
- 为了具有高度移植性,考虑了不同编译器的不同编译能力
- C++标准规范下的C头文件:cstdio,csyflib,cstring,...
- C++标准程序库中不属于STL范畴者:stream,string,...
- STL标准头文件(无扩展名):vector,deque,list,map,...
- C++标准定案前,HP所规范的STL头文件:vector.h,deque.h,list.h,...
- SGI STL内部文件(STL真正实现与此):stl_vector.h,stl_deque.h,stl_algo.h,...
不同的编译器对C++语言的支持程度不尽相同。作为一个希望具备广泛移植能力的程序库,SGI STL准备了一个环境组态文件<stl_config.h>,其中定义了许多常量,标示某些组态的成立与否,所有STL头文件都会直接或间接包含这个组态文件,并以条件式写法,让预处理器根据各个常量决定取舍哪一段程序代码,例如:
组态测试程序:
- 编译器对组态的支持
- 组态3:__STL_STATIC_TEMPLATE_MEMBER_BUG
- 组态5:__STL_CLASS_PARTIAL_SPECIALIZATION
- 组态6:__STL_FUNCTION_TMPL_PARTIAL_ORDER
- 组态7:__STL_EXPLICIT_FUNCTION_TMPL_ARGS(整个SGI STL内都没有用到这一常量定义)
- 组态8:__STL_MEMBER_TEMPLATES
- 组态10:__STL_LIMITED_DEFAULT_TEMPLATES
- 组态11:__STL_NON_TYPE_TMPL_PARAM_BUG
- 组态:__STL_EXPLICIT_FUNCTION_TMPL_ARGS(bound friend templates)
- 组态:__STL_TEMPLATE_NULL(class template explicit specialization)
最重要的2个是容器与算法
- 容器(container)
- 分配器(Allocator)
- 算法(Algorithms)
- 迭代器(Iterrators)
- 适配器(Adaptors)
- 仿函数(Functors)
在运用层面,不需要关注空间分配器。但是在容器背后,空间分配器负责容器中元素空间的分配
不称作”内存分配器“,是因为分配的空间不一定是内存,可以是磁盘或其它辅助存储介质。可以实现一个获取磁盘空间的allocator。不过这里介绍的空间分配器获取的空间是内存
通常,C++内存分配和释放的操作如下:
class Foo {...};
Foo *pf = new Foo;
delete pf;
- new内含2阶段操作:
- 调用::operator new分配内存
- 调用构造函数构造对象
- delete也含2阶段操作:
- 调用析构函数析构对象
- 调用::operator delete释放内存
STL allocator将new和delete的2阶段操作进行了分离:
- 内存分配:由alloc::allocate()负责
- 内存释放:由alloc::deallocate()负责
- 对象构造:由alloc::construct()负责
- 对象析构:由alloc::destroy负责
根据STL的规范,以下是allocator的必要接口:
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
//一个嵌套的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
//返回某个对象的地址,等同于&x
pointer allocator::address(reference x) const
const_pointer allocator::address(const_reference x) const
//分配空间,足以容纳n个元素
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指向的地址构造一个对象。相当于new((void*)p) T(x)
void allocator::construct(pointer p,const T& x)
//析构地址p的对象
void allocator::destroy(pointer p)
- 只能有限度搭配PJ STL,因为PJ STL未完全遵循STL规格,其所供应的许多容器都需要一个非标准的空间分配器接口
- 只能有限度地搭配RW STL,因为RW STL在很多容器身上运用了缓冲区,情况复杂很多
- 完全无法应用于SGI STL,因为SGI STL在这个项目上根本就脱离了STL标准规格,使用一个专属的、拥有次层配置能力的、效率优越的特殊分配器。但提供了一个对其进行了封装的名为simple_alloc的分配器,符合部分标准
虽然SGI也定义有一个符合”部分“标准、名为allocator的分配器,但SGI自己从未用过它,也不建议我们使用。主要原因是效率不佳,只把C++的::operator new和::operator delete做一层薄薄的包装而已
STL标准规定分配器定义于<memory>
中,SGI<memory>
内含两个文件,负责分离的2阶段操作
真正在SGI STL中大显身手的分配器(即SGI特殊的空间分配器std::alloc)或为第一级分配器,或为第二级分配器
STL规定分配器必须拥有名为construct()和destroy()的两个成员函数,然而SGI特殊的空间分配器std::alloc并未遵守这一规则,所以实际上这部分属于STL allocator,但不属于std::alloc。换句话说,SGI特殊的空间分配器std::alloc不包含”3.1 对象构造与析构“,只包含”3.2 内存分配与释放“
SGI对内存分配与释放的设计哲学如下:
- 向system heap申请空间
- 考虑多线程状态
- 考虑内存不足时的应变措施
- 考虑过多“小型区块”可能造成的内存碎片问题(SGI设计了双层级分配器)
C++的内存分配基本操作是::operator new(),内存释放基本操作是::operator delete()。这两个全局函数相当于C的malloc()和free()函数。SGI正是以malloc和free()完成内存的分配与释放
考虑到小型区块所可能造成的内存碎片问题,SGI设计了双层级分配器:
- 第一级分配器
- 直接使用malloc()和free()
- 第二级分配器
- 当分配区块超过128bytes时,视为“足够大”,调用第一级分配器
- 当分配区块小于128bytes时,视为“过小”,为了降低额外负担,采用复杂的memory pool整理方式,不再求助于第一级分配器
无论alloc被定义为第一级或第二级分配器,SGI还为它再包装一个接口,使分配器的接口能够符合STL规格:
template<class T, class Alloc>
class simple_alloc {
public:
static T *allocate(size_t n)
{ return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
static T *allocate(void)
{ return (T*) Alloc::allocate(sizeof (T)); }
static void deallocate(T *p, size_t n)
{ if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T)); }
};
内部4个函数都是转调用分配器的成员函数。这个接口使分配器的分配单位从bytes转为个别元素的大小
上图中Alloc=alloc中的缺省alloc可以是第一级分配器,也可以是第二级分配器。SGI STL已经把它设为第二级分配器
两级分配器都定义在头文件<stl_alloc.h>中
//一般而言是线程安全,并且对于空间的运用比较高效
//无“template型别参数”,至于”非型别参数“inst,则完全没派上用场
template <int inst>
class __malloc_alloc_template {
private:
//oom:out of memory ,用来处理内存不足的情况
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (* __malloc_alloc_oom_handler)();
#endif
public:
static void * allocate(size_t n)
{
void *result = malloc(n);//第一级分配器直接使用malloc()
//以下无法满足需求时,改用oom_malloc()
if (0 == result) result = oom_malloc(n);
return result;
}
static void deallocate(void *p, size_t /* n */)
{
free(p);//第一级分配器直接使用free()
}
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
void * result = realloc(p, new_sz);//第一级分配器直接使用realloc()
//以下无法满足需求时,改用oom_realloc()
if (0 == result) result = oom_realloc(p, new_sz);
return result;
}
//以下仿真C++的set_new_handler()。可以通过它指定自己的
//out-of-memory handler
//不能直接运用C++ new-handler机制,因为它并非使用::operator new来分配内存
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
// malloc_alloc out-of-memory handling
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
//初值为0,有待客户设定
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
#endif
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
void (* my_malloc_handler)();
void *result;
for (;;) {//不断尝试释放、分配、再释放、再分配...
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)(); //调用处理例程,企图释放内存
result = malloc(n); //再次尝试分配内存
if (result) return(result);
}
}
template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
{
void (* my_malloc_handler)();
void *result;
for (;;) {//不断尝试释放、分配、再释放、再分配...
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)(); //调用处理例程,企图释放内存
result = realloc(p, n); //再次尝试分配内存
if (result) return(result);
}
}
- 以malloc()、free()、realloc()等C函数执行实际的内存分配、释放、重分配操作
- 实现出类似C++ new-handler的机制(C++ new-handler机制是,可以要求系统在内存分配需求无法被满足时,调用一个你所指定的函数。换句话说,一旦::operator new无法完成任务,在丢出std::bad_alloc异常状态之前,会先调用由客户指定的处理例程,该处理例程通常即被称为new-handler),不能直接运用C++ new-handler机制,因为它并非使用::operator new来分配内存(operator new的实现)
第二级分配器多了一些机制,避免太多小额区块造成内存的碎片,小额区块存在下列问题:
- 产生内存碎片
- 额外负担。额外负担是一些区块信息,用以管理内存。区块越小,额外负担所占的比例就越大,越显浪费
- 当区块大于128bytes时,视为大区块
- 转交第一级分配器处理
- 当区块小于128bytes时,视为小额区块
- 以内存池管理(也称为次层分配):每次分配一大块内存,并维护对应的自由链表(free-list),下次若载有相同大小的内存需求,就直接从free-list中拨出。如果客户释放小额区块,就由分配器回收到free-list中。维护有16个free-list,各自管理大小分别为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128bytes的小额区块
- SGI第二级分配器会主动将任何小额区块的内存需求量上调至8的倍数
free-list使用如下结构表示:
//使用union解决free-list带来的额外负担:维护链表所必须的指针而造成内存的另一种浪费
union obj{
union obj * free_list_link; //系统视角
char client_data[1]; //用户视角
}
下图是free-list的实现技巧:
第二级分配器__default_alloc_template也定义在头文件<stl_alloc.h>中,以下为部分实现:
#ifdef __SUNPRO_CC
// breaks if we make these template class members:
enum {__ALIGN = 8}; //小型区块的上调边界
enum {__MAX_BYTES = 128}; //小型区块的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; //free-list的个数
#endif
//第二级分配器的定义
//无”template型别参数“,第一个参数用于多线程环境,第二参数完全没派上用场
template <bool threads, int inst>
class __default_alloc_template {
private:
//将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}
private:
//free-list
union obj {
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
private:
//16个free-list
static obj * volatile free_list[__NFREELISTS];
//根据区块大小,决定使用第n号free-list。n从0算起
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}
//返回一个大小为n的对象,并可能加入大小为n的其它区块到free-list
static void *refill(size_t n);
//分配一大块空间,可容纳nobjs个大小为”size“的区块
//如果分配nobjs个区块有所不便,nobjs可能会降低
static char *chunk_alloc(size_t size, int &nobjs);
// Chunk allocation state.
static char *start_free; //内存池起始位置。只在chunk_alloc()中变化
static char *end_free; //内存池结束位置。只在chunk_alloc()中变化
static size_t heap_size;
public:
static void * allocate(size_t n){ /*详述于后*/ }
static void deallocate(void *p, size_t n){ /*详述于后*/ }
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
};
/*以下是static data member的定义与初始值*/
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;
template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj * volatile
__default_alloc_template<threads, inst> ::free_list[__NFREELISTS] =
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
- 空间分配函数allocate()
- 若区块大于128bytes,就调用第一级分配器
- 若区块小于128bytes,检查对应的free-list
- 若free-list之内有可用的区块,则直接使用
- 若free-list之内没有可用区块,将区块大小调至8倍数边界,调用refill(),准备为free-list重新填充空间
- 空间释放函数deallocate()
- 若区块大于128bytes,就调用第一级分配器
- 若区块小于128bytes,找出对应的free-list,将区块回收
-
重新填充free-list的函数refill()
- 若free-list中没有可用区块时,会调用chunk_alloc从内存池中申请空间重新填充free-list。缺省申请20个新节点(新区块),如果内存池空间不足,获得的节点数可能小于20
-
chunk_alloc()函数从内存池申请空间,根据end_free-start_free判断内存池中剩余的空间
- 如果剩余空间充足
- 直接调出20个区块返回给free-list
- 如果剩余空间不足以提供20个区块,但足够供应至少1个区块
- 拨出这不足20个区块的空间
- 如果剩余空间连一个区块都无法供应
- 利用malloc()从heap中分配内存(大小为需求量的2倍,加上一个随着分配次数增加而越来越大的附加量),为内存池注入新的可用空间(详细例子见下图)
- 如果malloc()获取失败,chunk_alloc()就四处寻找有无”尚有未用且区块足够大“的free-list。找到了就挖出一块交出
- 如果上一步仍未成功,那么就调用第一级分配器,第一级分配器有out-of-memory处理机制,或许有机会释放其它的内存拿来此处使用。如果可以,就成功,否则抛出bad_alloc异常
上图中,一开始就调用chunk_alloc(32,20),于是malloc()分配40个32bytes区块,其中第1个交出,另19个交给free-list[3]维护,余20个留给内存池;接下来客户调用chunk_alloc(64,20),此时free_list[7]空空如也,必须向内存池申请。内存池只能供应(32*20)/64=10个64bytes区块,就把这10个区块返回,第1个交给客户,余9个由free_list[7]维护。此时内存池全空。接下来再调用chunk_alloc(96,20),此时free-list[11]空空如也,必须向内存池申请。而内存池此时也为空,于是以malloc()分配40+n(附加量)个96bytes区块,其中第1个交出,另19个交给free-list[11]维护,余20+n(附加量)个区块留给内存池...
- 如果剩余空间充足
STL定义了5个全局函数,作用于未初始化空间上,有助于容器的实现:
- 作用于单个对象(见3.1 对象构造与析构,SGI STL定义在头文件<stl_construct.h>中)
- construct()函数(构造单个对象)
- destroy()函数(析构单个对象)
- 作用于容器的区间(本节,SGI STL定义在头文件<stl_uninitialized.h>中,是高层copy()、fill()、fill_n()的底层函数)
容器的全区间构造函数通常分2步:
- 分配内存区块,足以包含范围内的所有元素
- 调用上述3个函数在全区间范围内构造对象(因此,这3个函数使我们能够将内存的分配与对象的构造行为分离;并且3个函数都具有”commit or rollback“语意,要么所有对象都构造成功,要么一个都没有构造)
在算法中运用迭代器时,很可能会用到其相应类型。所谓相应类型,迭代器所指之物的类型便是其中之一,算法可以在函数体中使用迭代器所指之物的类型来定义变量,也可能将迭代器所指之物的类型作为算法的返回值:
- 在函数体中使用迭代器所指之物的类型
- C++支持sizeof(),但并未支持typeof()。即便动用RTTI性质中的typeid(),获得的也只是类型名称,不能拿来做变量声明
- 这里利用函数模板的参数推导机制解决。算法func()作为对外接口,算法的所有逻辑另外封装在一个实现函数func_impl()中,由于它是一个函数模板,一旦被调用,编译器就会自动进行参数推导,导出类型T
- 迭代器所指之物的类型作为算法的返回类型
- 函数模板的参数推导机制推导的是参数,无法推导函数的返回类型
- 这里使用嵌套类型声明解决。但是,对于类类型的迭代器,可以正常工作,但是非类类型的原生指针无法处理
通过上图,可以了解到在算法中对迭代器相应类型的需求。除了迭代器所指之物的类型(value type),迭代器相应类型还包括另外4种,在traits编程技法中将会介绍,并且会提到如何使用traits来解决上面的问题(这也是STL中实际使用的方法)
上一节所使用的方法,在value type作为返回类型时,无法处理非类类型的原生指针。下图使用traits来解决,使用了模板偏特化来处理非类类型的原生指针:
现在,不论面对的是迭代器MyIter,或是原生指针int*或const int*,都可以通过traits取出正确的value type
当然,若要“特性萃取机”traits能够有效运作,每一个迭代器必须遵循约定,自行以内嵌类型定义的方式定义出相应类型。这是一个约定,谁不遵守这个约定,谁就不能兼容于STL这个大家庭
根据经验,最常用到的迭代器相应类型有5种:
-
value type:指迭代器所指对象的类型
-
difference type:用以表示两个迭代器之间的距离
-
pointer:如果value type是T,那么pointer就是指向T的指针
-
reference:如果value type是T,那么reference就是T的引用
-
iterator category:迭代器的类型(详见)
如果希望开发的容器能与STL相容,一定要为容器定义这5种相应类型。“特性萃取机”traits会很忠实地将特性萃取出来:
template <class Iterator>
struct iterator_traits{
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
iterator_traits必须针对传入的类型为pointer及pointer-to-const者设计偏特化版本:
//以C++内建的ptrdiff_t(定义于<cstddef>头文件)作为原生指针的difference type
//针对原生指针的偏特化版本
template <class T>
struct iterator_traits<T*>{
//原生指针是一种Random Access Iterator
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
//针对原生pointer-to-const的偏特化版本
template <class T>
struct iterator_traits<const T*>{
//原生指针是一种Random Access Iterator
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T* pointer;
typedef const T& reference;
};
STL提供以下函数,简化迭代器相应类型的萃取:
//这个函数可以很方便地萃取category
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
typedef typename iterator_traits<Iterator>::iterator_category category;
return category();
}
//这个函数可以很方便地萃取distance type
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&) {
return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}
//这个函数可以很方便地萃取value type
template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&) {
return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}
设计算法时,如果可能,尽量针对某种迭代器提供一个明确定义,并针对更强化的某种迭代器提供另一种定义,这样才能在不同情况下提供最大效率,如下图的advanced()函数,用于移动迭代器:
在上图中,每个__advance()的最后一个参数都只声明类型,并未指定参数名称,因为它纯粹只是用来激活重载机制,函数之中根本不使用该参数。如果加上参数名称也没有错,但是没必要
将advance()中的iterator_category(i)展开得到iterator_traits<InputIterator>::iterator_category(),这会产生一个临时对象,其类型隶属于几种迭代器中的一种。然后,根据这个类型,编译器才决定调用哪一个__advance()重载函数
上图以class来定义迭代器的各种分类标签,有下列好处:
- 可以促成重载机制的成功运作
- 通过继承,可以不必再写“单纯只做传递调用”的函数(如__advance()的Forward Iterator版只是单纯的调用Input Iterator版,因此可以省略),可以通过这个例子来模拟证实
为了符合规范,任何迭代器都应该提供5个内嵌相应类型,以便于traits萃取,否则便是自别于整个STL架构,可能无法与其它STL组件顺利搭配。然而,写代码难免会有遗漏。因此,STL提供了一个iterators class如下,如果每个新设计的迭代器都继承自它,就可保证符合STL所需的规范;
template <class Category,
class T,
class Distance = ptrdiff_t,
class Pointer = T*,
class Reference = T&>
struct iterator{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
iterator class不含任何成员,存粹只是类型定义,所以继承它不会导致任何额外负担。由于后3个参数皆有默认值,故新的迭代器只需提供前2个参数即可。以下为一个继承示例:
template <class Item>
struct ListIter : public std::iterator<std::forword_iterator_tag, Item>{
...
};
SGI将STL的traits进一步扩大到迭代器以外,于是有了所谓的__type_traits,它属于SGI STL,不属于STL标准规范
- iterator_traits:负责萃取迭代器的特性
- __type_traits:负责萃取类型的特性,包括:
- 该类型是否具备non-trivial default ctor
- 该类型是否具备non-trivial copy ctor
- 该类型是否具备non-trivial assignment operator
- 该类型是否具备non-trivial dtor
通过使用__type_traits,在对某个类型进行构造、析构、拷贝、赋值等操作时,就可以采用最有效率的措施。这对于大规模而操作频繁的容器,有着显著的效率提升
萃取类型的特性时,我们希望得到一个”真“或”假“(以便决定采取什么策略),但其结果不应该只是个bool值,应该是个有着真/假性质的”对象”,因为我们希望利用响应的结果来进行参数推导,而编译器只有面对class object形式的参数,才会做参数推导,所以萃取类型的特性时,返回__true_type或__false_type:
struct __true_type { };
struct __false_type { };
模板类__type_traits的泛化与特化/偏特化见下图:
上图中的“衍生”并非“派生”,而是内含关系。例如heap内含一个vector,priority-queue内含一个heap,stack和queue都含一个deque,set/map/multiset/multimap都内含一个RB-tree,has_x都内含一个hashtable
array是静态空间,一旦配置了就不能改变;vector与array非常相似,但是vector是动态空间,随着元素的加入,内部机制会自动扩充以容纳新元素
SGI STL中vector的定义
vector维护的是一个连续线性空间,所以不论其元素类型为何,普通指针都可以作为vector的迭代器而满足所有必要条件,因为vector迭代器所需要的操作行为,如operator*,operator->,operator++,operator--,operator+,operator-,operator+=,operator-=,普通指针天生就具备。vector支持随机存取,而普通指针正有着这样的能力。所以,vector提供的是Random Access Iterators:
template <class T,class Alloc = alloc>
class vector{
public:
typedef T value_type;
typedef value_type* iterator; //vector的迭代器时普通指针
...
};
vector缺省使用alloc作为空间分配器,并据此另外定义了一个data_allocator,为的是更方便以元素大小为配置单位:
template<class T,class Alloc = alloc>
class vector{
protected:
typedef simple_alloc<value_type,Alloc> data_allocator;
...
};
因此,data_allocator::allocate(n)表示分配n个元素空间
常见的vector操作包括:
- vector(size_type n,const T &value)
- push_back(const T &x)
- pop_back()
- erase(iterator first, iterator last)
- erase(iterator position)
- insert(iterator position, size_type n, const T& x)
插入操作可能造成vector的3个指针重新配置,导致原有的迭代器全部失效
SGI STL中list的定义
template <class T>
struct __list_node{
typedef void* void_pointer;
void_pointer prev; //类型为void*
void_pointer next;
T data;
};
list不再能够像vector一样以普通指针作为迭代器,因为其节点不保证在存储空间中连续存在
list迭代器必须有能力指向list的节点,并有能力进行正确的递增、递减、取值、成员存取等操作。list中,迭代器与节点的关系见下图:
由于STL list是一个双向链表,迭代器必须具备前移、后移的能力,所以list提供的是Bidirectional Iterators
list的插入和接合操作都不会造成原有的list迭代器失效,对于删除操作,也只有”指向被删除元素“的那个迭代器失效,其它迭代器不受任何影响
template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;//节点指针类型link_type
typedef size_t size_type;
typedef ptrdiff_t difference_type;
link_type node;//迭代器内部的指针,指向list的节点
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
//对迭代器取值,取的是节点的数据值
reference operator*() const { return (*node).data; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
//以下是迭代器的成员存取运算子的标准做法
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//对迭代器累加1,就是前进一个节点
self& operator++() {
node = (link_type)((*node).next);
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
//对迭代器递减1,就是后退一个节点
self& operator--() {
node = (link_type)((*node).prev);
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
};
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; //只要一个指针,便可表示整个环状双向链表
};
iterator begin() { return (link_type)((*node).next); }
iterator end() { return node; }
size_type size() const {
size_type result = 0;
distance(begin(), end(), result);
return result;
}
list缺省使用alloc作为空间分配器,并据此另外定义了一个list_node_allocator,为的是更方便以节点大小为配置单位:
template <class T, class Alloc = alloc>
class list {
protected:
typedef simple_alloc<list_node, Alloc> list_node_allocator;
...
};
因此,list_node_allocator::allocate(n)表示分配n个节点空间
-
节点操作
- 分配一个节点:get_node
- 释放一个节点:put_node
- 生成(分配并构造)一个节点:create_node
- 销毁(析构并释放)一个节点:destroy_node
- 节点插入:push_back和push_front
- 节点移除:erase,pop_front和pop_back
- 移除某一数值的所有节点:remove
- 移除数值相同的连续节点:unique
-
链表操作
-
链表拼接:splice
- 将[first,last)内的元素移动到position之前:transfer([first,last)区间可以在同一个list之中,transfer并非公开接口,公开的是splice)
deque是一种双向开口的连续线性空间
deque和vector最大的差异:
- deque允许于常数时间内对起头端进行元素的插入或移除操作
- deque没有所谓容量观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来(deque没有必要提供所谓的空间保留功能)
deque是分段连续空间。维持其”整体连续“假象的任务,落在了迭代器的operator++和operator--两个运算子身上
deque迭代器必须能够指出分段连续空间(即缓冲区)在哪;必须能够判断自己是否已经处于其所在缓冲器的边缘。为了能够正确跳跃,迭代器必须随时掌握中控器map
template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator { //未继承std::iterator
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
//为继承std::iterator,所以必须自行撰写5个必要的迭代器相应类型
typedef random_access_iterator_tag iterator_category; // (1)
typedef T value_type; // (2)
typedef Ptr pointer; // (3)
typedef Ref reference; // (4)
typedef size_t size_type;
typedef ptrdiff_t difference_type; // (5)
typedef T** map_pointer;
typedef __deque_iterator self;
//保持与容器的联结
T* cur; //此迭代器所指缓冲区中的当前元素
T* first; //此迭代器所指缓冲区的头
T* last; //此迭代器所指缓冲区的尾(含备用空间)
map_pointer node; //指向中控器map
...
};
迭代器操作:
deque采用一块所谓的map作为主控(中控器)。这里所谓的map是指一小块连续空间,其中每个元素都是一个指针,指向另一段(较大的)连续线性空间,称为缓冲区。缓冲区才是deque的存储空间主体。SGI STL允许我们指定缓冲区大小,默认值0表示使用512bytes缓冲区
deque除了维护一个指向map的指针外,也维护start,finish两个迭代器。分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一位置)。此外,也必须记住目前的map大小。因为一旦map所提供的节点不足,就必须重新配置更大的一块map
temlate <class T,class Alloc = alloc,size_t BufSiz = 0>
class deque{
public: //Basic types
typedef T value_type;
typedef value_type* pointer;
typedef size_t size_type;
...
public:
typedef __deque_iterator<T,T&.T*,BufSiz> iterator; //迭代器类型
protected: //Internal typedefs
//元素的指针的指针
typedef pointer* map_pointer;
protected: //Data members
iterator start; //第一个节点的迭代器
iterator finish; //最后一个节点的迭代器
map_pointer map; //指向map,map是块连续空间
//其每个元素都是个指针,指向一个节点(缓冲区)
size_type map_size; //map的大小,即内有多少个指针
...
};
deque的中控器、缓冲区、迭代器的关系如下图:
deque自行定义了2个专属的空间配置器:
protected:
//专属的空间分配器,每次分配一个元素大小
typedef simple_alloc<value_type,Alloc> data_allocator;
//专属的空间分配器,每次分配一个指针大小
typedef simple_alloc<pointer,Alloc> map_allocator;
- deque构造与初始化:deque
- 元素初始化fill_initialize
- 空间分配与成员设定create_map_and_nodes
- 元素初始化fill_initialize
- 插入操作:
- 在队列末尾插入:push_back
- 最后缓冲区只有1个可用空间时:push_back_aux
- 在队列首部插入:push_front
- 第一个缓冲区没有可用空间时:push_front_aux
- 指定位置插入一个元素:insert
- 在首部插入:push_front
- 在尾部插入:push_back
- 在中间插入:insert_aux
- 在队列末尾插入:push_back
- 弹出操作:
- 弹出队列末尾元素:pop_back
- 最后缓冲区没有元素时:pop_back_aux
- 弹出队列首部元素:pop_front
- 第一个缓冲区仅有一个元素时:pop_front_aux
- 弹出队列末尾元素:pop_back
- 清除所有元素:clear
- 清除某个区间的元素:erase
具有”修改某物接口,形成另一种风貌“的性质者,称为适配器。因此,STL stack往往不被归类为容器,而被归类为容器适配器
SGI STL以deque作为缺省情况下的stack底部结构,定义如下:
template <class T, class Sequence = deque<T> >
class stack {
//以下__STL_NULL_TMPL_ARGS会展开为 <>
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
public:
//以下完全利用Sequence c的操作,完成stack的操作
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
//deque是两头可进出,stack是后进后出
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
return x.c < y.c;
}
只有stack顶端的元素有机会被外界取用,stack不提供遍历功能,也不提供迭代器
指定其它容器作为stack的底层容器的方法:
stack<int,list<int> > istack;
queue(队列)是一种先进先出的数据结构,尾端插入,首部移出
SGI STL以deque作为缺省情况下的queue底部结构,定义如下:
template <class T, class Sequence = deque<T> >
class queue {
//以下__STL_NULL_TMPL_ARGS会展开为 <>
friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
public:
//以下完全利用Sequence c的操作,完成stack的操作
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
//deque是两头可进出,queue是尾端进、首部出
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
return x.c < y.c;
}
只有首部元素才有机会被外界取用,queue不提供遍历功能,也不提供迭代器
指定其它容器作为queue的底层容器的方法:
queue<int,list<int> > iqueue;
heap并不归属与STL容器组件,它是个幕后英雄,扮演priority queue的助手
heap是一颗完全二叉树,完全二叉树使用数组实现,因此使用一个vector作为heap的结构,然后通过一组xxx_heap算法,使其符合heap的性质
顾名思义,priority_queue就是具有优先级的queue,允许首部移出,尾端插入。缺省情况下利用一个max-heap完成,因此首部元素优先级最高
以下为SGI STL中priority_queue的定义:
template <class T, class Sequence = vector<T>,
class Compare = less<typename Sequence::value_type> >
class priority_queue {
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c; //底层容器
Compare comp; //元素大小比较标准
public:
priority_queue() : c() {}
explicit priority_queue(const Compare& x) : c(), comp(x) {}
//以下用到的make_heap()、push_heap()、pop_heap()都是泛型算法
//构造一个priority queue,首先根据传入的迭代器区间初始化底层容器c,然后调用
//make_heap()使用底层容器建堆
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Compare& x)
: c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: c(first, last) { make_heap(c.begin(), c.end(), comp); }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
void push(const value_type& x) {
//先利用底层容器的push_back()将新元素推入末端,再重排heap
__STL_TRY {
c.push_back(x);
push_heap(c.begin(), c.end(), comp);
}
__STL_UNWIND(c.clear());
}
void pop() {
//从heap内取出一个元素。但不是真正弹出,而是重排heap,然后以底层容器的pop_back()
//取得被弹出的元素
__STL_TRY {
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};
和queue一样,priority queue只有首部的元素有机会被外界取用。不提供遍历功能,也不提供迭代器
slist并不在标准规格之内,由SGI STL提供,slist和list不同的是slist是单链表
单链表每个节点的消耗更小,但是只支持单向遍历,所以功能会受到许多限制
SGI STL中slist的定义
节点相关的结构:
//单向链表的节点基本结构
struct __slist_node_base
{
__slist_node_base *next;
};
//单向链表的节点结构
template <class T>
struct __slist_node : public __slist_node_base
{
T data;
}
节点相关的全局函数:
//已知某一节点prev_node,将新节点new_node插入其后
inline __slist_node_base* __slist_make_link(
__slist_node_base *prev_node,
__slist_node_base *new_node)
{
//令new节点的下一节点为prev节点的下一节点
new_node->next = prev_node->next;
prev_node->next = new_node; //令prev节点的下一节点指向new节点
return new_node;
}
//单向链表的大小(元素个数)
inline size_t __slist_size(__slist_node_base *node)
{
size_t result = 0;
for(;node != 0;node = node->next)
++result; //一个个累计
return result;
}
迭代器的定义如下:
//单向链表的迭代器基本结构
struct __slist_iterator_base
{
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category; //单向
__slist_node_base* node; //指向节点基本结构
__slist_iterator_base(__slist_node_base* x) : node(x) {}
void incr() { node = node->next; } //前进一个节点
bool operator==(const __slist_iterator_base& x) const {
return node == x.node;
}
bool operator!=(const __slist_iterator_base& x) const {
return node != x.node;
}
};
//单向链表的迭代器结构
template <class T, class Ref, class Ptr>
struct __slist_iterator : public __slist_iterator_base
{
typedef __slist_iterator<T, T&, T*> iterator;
typedef __slist_iterator<T, const T&, const T*> const_iterator;
typedef __slist_iterator<T, Ref, Ptr> self;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __slist_node<T> list_node;
__slist_iterator(list_node* x) : __slist_iterator_base(x) {}
__slist_iterator() : __slist_iterator_base(0) {}
__slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {}
reference operator*() const { return ((list_node*) node)->data; }
pointer operator->() const { return &(operator*()); }
self& operator++()
{
incr(); //前进一个节点
return *this;
}
self operator++(int)
{
self tmp = *this;
incr(); //前进一个节点
return tmp;
}
};
标准的STL关联容器分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)。这些容器的底层机制均以RB-tree(红黑树)完成。RB-tree也是一个独立容器,但并不开放给外界使用
此外,SGI STL还提供了一个不在标准规格之列的关联容器:hash table,以及以此hash table为底层机制而完成的hash_set(散列集合)、hash_map(散列映射表)、hash_multiset(散列多键集合)、hash_multimap(散列多键映射表)
typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false; //红色为0
const __rb_tree_color_type __rb_tree_black = true; //黑色为1
//RB-tree节点的基类
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color; //颜色
base_ptr parent; //指向父节点的指针
base_ptr left; //指向左子节点的指针
base_ptr right; //指向右子节点的指针
//静态函数,获取以x为根节点的RB-tree最小节点的指针
static base_ptr minimum(base_ptr x)
{
while (x->left != 0) x = x->left;
return x;
}
//静态函数,获取以x为根节点的RB-tree最大节点的指针
static base_ptr maximum(base_ptr x)
{
while (x->right != 0) x = x->right;
return x;
}
};
//RB-tree节点类
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field; //RB-tree节点的value
};
键和值都包含在value_field中
SGI将RB-tree迭代器实现为两层:
RB-tree迭代器属于双向迭代器,但不具备随机定位能力。前进操作operator++()调用了基类迭代器的increment(),后退操作operator--()调用了基类迭代器的decrement()。前进或后退的举止行为完全依据二叉搜索树的节点排列法则
//迭代器基类
struct __rb_tree_base_iterator
{
typedef __rb_tree_node_base::base_ptr base_ptr;
typedef bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
base_ptr node; //节点基类类型的指针,将迭代器连接到RB-tree的节点
void increment()
{
if (node->right != 0) {//如果node右子树不为空,则找到右子树的最左子节点
node = node->right;
while (node->left != 0)
node = node->left;
}
else {//如果node右子树为空,则找到第一个“该节点位于其左子树”的节点
base_ptr y = node->parent;
while (node == y->right) {
node = y;
y = y->parent;
}
if (node->right != y)
node = y;
}
}
void decrement()
{
if (node->color == __rb_tree_red &&
node->parent->parent == node)//这种情况发生于node为header时(亦即node为
node = node->right; //end()时)header右子节点即mostright,指向max节点
else if (node->left != 0) {//如果左子树不为空,则找到左子树的最右子节点
base_ptr y = node->left;
while (y->right != 0)
y = y->right;
node = y;
}
else {//如果左子树为空,则找到第一个“该节点位于其右子树”的节点
base_ptr y = node->parent;
while (node == y->left) {
node = y;
y = y->parent;
}
node = y;
}
}
};
//迭代器类
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
typedef Value value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
typedef __rb_tree_iterator<Value, Ref, Ptr> self;
typedef __rb_tree_node<Value>* link_type; //指向RB-tree节点的指针类型
__rb_tree_iterator() {}
__rb_tree_iterator(link_type x) { node = x; }
__rb_tree_iterator(const iterator& it) { node = it.node; }
//解引用操作为获取所指RB-tree节点的value
reference operator*() const { return link_type(node)->value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
//调用父类的increment(),函数会修改node成员,使其指向后一个RB-tree节点
self& operator++() { increment(); return *this; }
self operator++(int) {
self tmp = *this;
increment();
return tmp;
}
//调用父类的decrement(),函数会修改node成员,使其指向前一个RB-tree节点
self& operator--() { decrement(); return *this; }
self operator--(int) {
self tmp = *this;
decrement();
return tmp;
}
};
SGI STL中RB-tree的定义
- 节点操作:
- 涉及内存管理的操作
- 分配节点:get_node
- 释放节点:put_node
- 创建节点:create_node
- 拷贝节点:clone_node
- 销毁节点:destroy_node
- 获取节点成员:
- left
- right
- parent
- value
- key
- color
- 涉及内存管理的操作
- RB-tree操作
SGI STL中set的定义
set的所有元素都会根据元素的键值自动被排序。元素的键值就是实值,实值就是键值、set不允许两个元素具有相同的键值
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
...
//键值和实值类型相同,比较函数也是同一个
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
...
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 内含一棵RB-tree,使用RB-tree来表现set
public:
...
//iterator定义为RB-tree的const_iterator,表示set的迭代器无法执行写操作
typedef typename rep_type::const_iterator iterator;
...
};
set的元素值就是键值,关系到set元素的排列规则。因此不能通过set的迭代器改变set的元素值。set将其迭代器定义为RB-tree的const_iterator以防止修改
set所开放的各种操作接口,RB-tree也提供了,所以几乎所有的set操作行为,都只是转调用RB-tree的操作行为而已
SGI STL中map的定义
map的所有元素会根据元素的键值自动被排序。所有元素都是pair,同时拥有键值和实值,第一个元素被视为键值,第二个元素被视为实值。map不允许两个元素拥有相同的键值
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key key_type; //键值类型
typedef T data_type; //实值类型
typedef T mapped_type;
typedef pair<const Key, T> value_type; //键值对,RB-tree节点中的value类型
typedef Compare key_compare; //键值比较函数
...
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 内含一棵RB-tree,使用RB-tree来表现map
public:
...
//迭代器和set不同,允许修改实值
typedef typename rep_type::iterator iterator;
...
//下标操作
T& operator[](const key_type& k) {
return (*((insert(value_type(k, T()))).first)).second;
}
//插入操作
pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }
...
};
可以通过map的迭代器修改元素的实值,不能修改元素的键值
map所开放的各种操作接口,RB-tree也都提供了,所以几乎所有的map操作行为,都只是转调用RB-tree的操作行为而已
SGI STL中set的定义
multiset的特性及用法和set完全相同,唯一的差别在于它允许键值重复,插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()
SGI STL中map的定义
multimap的特性及用法和map完全相同,唯一的差别在于它允许键值重复,插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()
SGI STL中以开哈希实现hash table,hash table表格中的元素为桶,每个桶中包含了哈希到这个桶中的节点,节点定义如下:
template <class Value>
struct __hashtable_node
{
__hashtable_node *next;
Value val;
};
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc>
struct __hashtable_iterator {
typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
hashtable;
typedef __hashtable_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
iterator;
typedef __hashtable_const_iterator<Value, Key, HashFcn,
ExtractKey, EqualKey, Alloc>
const_iterator;
typedef __hashtable_node<Value> node;
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef Value& reference;
typedef Value* pointer;
node* cur; //迭代器目前所指的节点
hashtable* ht; //指向相应的hashtable
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
pointer operator->() const { return &(operator*()); }
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
前进操作首先尝试从目前所指的节点出发,前进一个位置(节点),由于节点被安置于list内,所以利用节点的next指针即可轻易完成。如果目前节点正好是list的尾端,就跳至下一个bucket身,它正好指向下一个list的头部节点:
template <class V, class K, class HF, class ExK, class EqK, class A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>&
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
{
const node* old = cur;
cur = cur->next; //如果存在,就是它。否则进入以下if流程
if (!cur) {
//根据元素值,定位出下一个bucket,其起头处就是我们的目的地
size_type bucket = ht->bkt_num(old->val);
while (!cur && ++bucket < ht->buckets.size())
cur = ht->buckets[bucket];
}
return *this;
}
template <class V, class K, class HF, class ExK, class EqK, class A>
inline __hashtable_iterator<V, K, HF, ExK, EqK, A>
__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
{
iterator tmp = *this;
++*this;
return tmp;
}
hashtable的迭代器没有后退操作,hashtable也没有定义所谓的逆向迭代器
SGI STL中hashtable的定义
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey, class Alloc = alloc>
class hashtable;
...
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc> //先前声明时,已给出Alloc默认值alloc
class hashtable {
public:
typedef HashFcn hasher;
typedef EqualKey key_equal;
...
private:
//以下3者都是function objects
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node; //hashtable节点类型
typedef simple_alloc<node, Alloc> node_allocator;
vector<node*,Alloc> buckets; //hashtable的桶数组,以vector完成
size_type num_elements; //元素个数
...
};
SGI STL以质数来设计表格大小,并且先将28个质数(逐渐呈现大约2倍的关系)计算好,以备随时访问,同时提供一个函数,用来查询在这28个质数中,“最接近某数并大于某数”的质数:
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473ul, 4294967291ul
};
//该函数被next_size()所调用
inline unsigned long __stl_next_prime(unsigned long n)
{
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
- 节点操作
- 涉及内存管理
- 创建节点:new_node
- 销毁节点:delete_node
- 涉及内存管理
- hashtable操作
- 创建满足n个bucket的hashtable:hashtable
- 插入节点
- 不允许键值重复: insert_unique
- 判断和重新分配bucket:resize
- insert_unique_noresize
- 允许键值重复:insert_equal
- 判断和重新分配bucket:resize(同上)
- insert_equal_noresize
- 不允许键值重复: insert_unique
- 哈希映射寻找bucket
- 接受实值和buckets个数:bkt_num
- 只接受实值:bkt_num
- 只接受键值:bkt_num_key
- 接受键值和buckets个数:bkt_num_key
- 清除:clear
- 复制:copy_from
- 查找元素:find
- 统计元素个数:count
hash function是计算元素位置的函数,SGI将这项任务赋予了bkt_num(),再由它来调用这里提供的hash function,取得一个可以对hashtable进行模运算的值。针对char,int,long等整数类型,大部分的hash functions什么也没做,只是忠实返回原值
inline size_t __stl_hash_string(const char* s)
{
unsigned long h = 0;
for ( ; *s; ++s)
h = 5*h + *s;
return size_t(h);
}
__STL_TEMPLATE_NULL struct hash<char*>
{
size_t operator()(const char* s) const { return __stl_hash_string(s); }
};
__STL_TEMPLATE_NULL struct hash<const char*>
{
size_t operator()(const char* s) const { return __stl_hash_string(s); }
};
__STL_TEMPLATE_NULL struct hash<char> {
size_t operator()(char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned char> {
size_t operator()(unsigned char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<signed char> {
size_t operator()(unsigned char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
size_t operator()(short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
size_t operator()(unsigned short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
size_t operator()(int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
size_t operator()(unsigned int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
size_t operator()(long x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
size_t operator()(unsigned long x) const { return x; }
};
SGI STL中hash_set的定义
hash_set以hashtable为底层机制,由于hash_set所供应的操作接口hashtable都提供了,所以几乎所有的hash_set操作行为,都只是转调用hashtable的操作行为而已
SGI STL中hash_map的定义
hash_map以hashtable为底层机制,由于hash_map所供应的操作接口hashtable都提供了,所以几乎所有的hash_map操作行为,都只是转调用hashtable的操作行为而已
SGI STL中hash_multiset的定义
hash_multiset和hash_set实现上的唯一差别在于,前者的元素插入操作采用底层机制hashtable的insert_equal(),后者则是采用insert_unique()
SGI STL中hash_multimap的定义
hash_multimap和hash_map实现上的唯一差别在于,前者的元素插入操作采用底层机制hashtable的insert_equal(),后者则是采用insert_unique()
SGI STL的copy算法用尽各种办法,包括函数重载、类型特性、偏特化等编程技巧来尽可能地加强效率
-
泛化版本
- copy
- 泛化版本:__copy_dispatch
- 偏特化版本:__copy_dispatch
- 偏特化版本:__copy_dispatch
- __copy_t(同上)
- copy
-
特化版本
copy将输入区间[first,last)
内的元素复制到输出区间[result,result+(last-first))
内,也就是说,它会执行赋值操作*result = *first,*(result+1) = *(first+1),...
依次类推。返回一个迭代器:result+(last-first)
。copy对其template参数所要求的条件非常宽松。其输入区间只需由inputIterators构成即可,输出区间只需要由OutputIterator构成即可。这意味着可以使用copy算法,将任何容器的任何一段区间的内容,复制到任何容器的任何一段区间上
由于拷贝的顺序,对于没有使用memmove()的版本,要特别注意目的区间与源区间重合的情况。memmove()能处理区间重合的情况
copy会为输出区间内的元素赋予新值,而不是产生新的元素。它不能改变输出区间的迭代器个数。换句话说,copy不能直接用来将元素插入空容器中。如果想将元素插入序列之内,要么使用序列容器的insert成员函数,要么使用copy算法并搭配insert_iterator
copy_backward将[first,last)
区间的每一个元素,以逆行的方向复制到以result-1为起点,方向亦为逆行的区间上。换句话说,copy_backward算法会执行赋值操作*(result-1) = *(last - 1),*(result-2) = *(last - 2),...
以此类推,返回一个迭代器:result-(last-first)
copy_backward所接受的迭代器必须是BidirectionalIterators,才能够“倒行逆施”
这部分介绍的4个算法所接受的set,必须是有序区间,元素可能重复。换句话说,它们可以接受STL的set/multiset容器作为输入区间。hash_set/hash_multiset两种容器,以hashtable为底层机制,其内的元素并未呈现排序状态,所以虽然名称中也有set字样,却不可应用于这里的4个算法
这个函数求集合s1和s2的并集。s1和s2及其并集都是以排序区间表示。函数返回一个迭代器,指向输出区间的尾端
s1和s2内的每个元素都不需要唯一,因此,如果某个值在s1出现n此,在s2出现m次,那么该值在输出区间中会出现max(m,n)次
SGI SLT中set_union的实现,操作示例如下:
这个函数求集合s1和s2的交集。s1和s2及其交集都是以排序区间表示。函数返回一个迭代器,指向输出区间的尾端
SGI SLT中set_intersection的实现,操作示例如下:
该函数计算两个集合的差集,即当s1为第一个参数,s2为第二个参数时,计算s1-s2。内含“出现于s1但不出现于s2”的每一个元素。s1和s2及其差集都是以排序区间表示。函数返回一个迭代器,指向输出区间的尾端
SGI SLT中set_difference的实现,操作示例如下:
这个函数求集合s1和s2的对称差集,也就是说,它能构造出集合s1-s2与集合s2-s1的并集,内含“出现于s1但不出现于s2”以及“出现于s2但不出现于s1”的每一个元素。s1、s2及其对称差集都是以排序区间表示,返回值是一个迭代器,指向输出区间的尾端
由于s1和s2内的每个元素不需要唯一,因此如果某个值在s1出现n此,在s2出现m次,那么该值在输出区间中会出现|n-m|次
SGI SLT中set_symmetric_difference的实现,操作示例如下:
sort要求传入的迭代器为随机迭代器,因此只能对vector和deque进行排序
STL的sort算法,数据量大时采用Quick Sort,分段递归排序。一旦分段后的数据量小于某个门槛,为避免Quick Sort的递归调用带来过大的额外负荷,就改用Insertion Sort。如果递归层次过深,还会改用Heap Sort
以下为SGI SLT的sort实现:
- sort
- __lg
- __introsort_loop
- 当子区间大于__stl_threshold(16)时才运行,否则直接返回
- 当深度限制为0时,使用堆排序
- 当深度限制大于0时,继续递归排序
- 当子区间大于__stl_threshold(16)时才运行,否则直接返回
- __final_insertion_sort(此时,已经基本有序)
- 当数组区间大于__stl_threshold(16)时
- 当数组区间小于等于__stl_threshold(16)时
- 调用:__insertion_sort(同上)
相对简单的算法:
-
查找
- adjacent_find(查找第一对满足条件的相邻元素,返回第一个元素的迭代器)
- find
- find_if(可以指定操作)
- find_end(在区间一中查找区间二最后一次出现的位置)
- 版本一
- 单向迭代器版:__find_end
- 双向迭代器版:__find_end
- 版本二(可以指定操作)
- 单向迭代器版:__find_end
- 双向迭代器版:__find_end
- 版本一
- find_first_of(在区间一中查找区间二中任一元素第一次出现点)
- max_element
- min_element
- search(在序列一的区间中查找序列二的首次出现点)
- search_n(在序列一中查找连续n个满足条件的元素的起点)
-
统计
-
单区间操作
- for_each(将仿函数f施行于指定区间,f不允许修改元素,因为迭代器类型是InputIterators)
- generate(将仿函数gen的运算结果赋值到指定区间的所有元素上)
- generate_n(将仿函数gen的运算结果赋值到迭代器first开始的n个元素上)
- partition(不保证元素的原始相对位置)
- stable_partition(保留元素的原始相对位置)
- remove(区间大小并不发送变化,需要移除的元素会被后面的覆盖,区间尾部会有残余,返回指向第一个残余元素的迭代器)
- remove_if
-
rotate(将[first,middle)和[middle,last)的元素互换,middle所指元素将成为容器第一个元素)
- 迭代器为向前迭代器:__rotate
- 迭代器为双向迭代器:__rotate
- 迭代器为随机迭代器:__rotate
-
transform
-
unique(移除相邻的重复元素,必须相邻,所以要先排序。和remove一样,会有残余)
-
- 迭代器为向前迭代器:__unique_copy
- 迭代器为输出迭代器(不能读):__unique_copy
-
双区间操作
- swap_ranges(将区间一的元素与first2开始等个数的元素互换)
较为复杂的算法:
-
查找
- lower_bound(查找等于value的第一个元素的位置,不存在则返回第一个插入点)
- 版本一
- 迭代器是向前迭代器:__lower_bound
- 迭代器是随机迭代器:__lower_bound
- 版本二(允许指定比较操作)
- 版本一
- upper_bound(查找value的最后一个插入点,即如果存在元素等于value,那么插入最后一个等于value的元素之后)
- 版本一
- 迭代器是向前迭代器:__upper_bound
- 迭代器是随机迭代器:__upper_bound
- 版本二(允许指定比较操作)
- 版本一
- binary_search
- equal_range(返回一对迭代器i和j,i是lower_bound的结果,j是upper_bound的结果)
- 版本一
- 迭代器是向前迭代器:__equal_range
- 迭代器是随机迭代器:__equal_range
- 版本一
- lower_bound(查找等于value的第一个元素的位置,不存在则返回第一个插入点)
-
单区间操作
-
next_permutation(按字典序计算下一个排列组合。算法思想:从最尾端开始往前寻找两个相邻元素,令第一个元素为*i,第二个元素为*ii,且满足*i<*ii。找到这样一组相邻元素后,再从最尾端开始往前检验,找到第一个大于*i的元素,设为*j,将i,j元素对调,再将ii之后的所有元素颠倒排列。就是下一个排列组合)
-
prev_permutation(按字典序计算上一个排列组合。算法思想:从最尾端开始往前寻找两个相邻元素,令第一个元素为*i,第二个元素为*ii,且满足*i>*ii。找到这样一组相邻元素后,再从最尾端开始往前检验,找到第一个小于*i的元素,设为*j,将i,j元素对调,再将ii之后的所有元素颠倒排列。就是下一个排列组合)
-
random_shuffle
- 版本一(使用内部随机数产生器) __random_shuffle
- 版本二(使用一个会产生随机数的仿函数)
-
partial_sort(将middle-first个最小元素排序并置于[first,middle),其余元素放在middle开始的后半部)
-
partial_sort_copy
-
- inplace_merge_aux
-
有额外的缓冲区辅助:__merge_adaptive
- 当序列1较小,且缓冲区足够容纳序列1
- 当序列2较小,且缓冲区足够容纳序列2
- 当缓冲区不足以容纳序列1和序列2 __rotate_adaptive
-
- inplace_merge_aux
-
在STL标准规格定案后,仿函数采用函数对象作为新名称
函数指针的缺点在于:不能满足STL对抽象性的要求,也不能满足软件积木的要求——函数指针无法和STL其它组件(如适配器)搭配,产生更灵活的变化
就实现而言,仿函数其实就是一个“行为类似函数”的对象,为了能够“行为类似函数”,其类别定义中必须自定义function call运算子。拥有这样的运算子后,就可以在仿函数的对象后面加上一对小括号,以此调用仿函数所定义的operator()
STL仿函数的分类,若以操作数的个数划分,可分为一元和二元仿函数,若以功能划分,可分为算术运算,关系运算,逻辑运算三大类
任何应用程序欲使用STL內建的仿函数,都必须含入头文件,SGI则将它们实际定义于<stl_function.h>头文件
STL仿函数应该有能力被函数适配器修饰,彼此像积木一样地串接。为了拥有适配能力,每一个仿函数必须定义自己的相应类型。就像迭代器如果要融入整个STL大家庭,也必须依照规定定义自己的5个相应类型一样。这些相应类型是为了让适配器能够取出,获得仿函数的某些信息
仿函数的相应类型主要用来表现函数参数类型和传回值类型
为方便起见,<stl_function.h>定义了两个classes,分别代表一元仿函数和二元仿函数(STL不支持三元仿函数),其中没有任何data members或member functions,唯有一些类型定义。任何仿函数只要依据需求选择继承其中一个class,就自动拥有了那些相应类型,也就拥有了适配能力
unary_function用来呈现一元函数的参数类型和返回值类型:
template <class Arg, class Result>
struct unary_function {
typedef Arg argument_type;
typedef Result result_type;
};
binary_function用来呈现二元函数的第一参数类型,第二参数类型,以及返回值类型:
template <class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
以下为STL内建的“算术类仿函数”,除了“否定”运算为一元运算,其它都是二元运算:
- 加法:plus<T>
- 减法:minus<T>
- 乘法:multiplies<T>
- 除法:divides<T>
- 取模:modulus<T>
- 否定:negate<T>
template <class T>
struct plus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x + y; }
};
template <class T>
struct minus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x - y; }
};
template <class T>
struct multiplies : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x * y; }
};
template <class T>
struct divides : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x / y; }
};
template <class T>
struct modulus : public binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x % y; }
};
template <class T>
struct negate : public unary_function<T, T> {
T operator()(const T& x) const { return -x; }
};
以下为STL内建的“关系运算类仿函数”,每一个都是二元运算:
- 等于:equal_to<T>
- 不等于:not_equal_to<T>
- 大于:greater<T>
- 大于或等于:greater_equal<T>
- 小于:less<T>
- 小于或等于:less_equal<T>
template <class T>
struct equal_to : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x == y; }
};
template <class T>
struct not_equal_to : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x != y; }
};
template <class T>
struct greater : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x > y; }
};
template <class T>
struct less : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x < y; }
};
template <class T>
struct greater_equal : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x >= y; }
};
template <class T>
struct less_equal : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x <= y; }
};
以下为STL内建的“逻辑运算类仿函数”,其中And和Or是二元运算,Not为一元运算:
- 逻辑运算 And:logical_and<T>
- 逻辑运算 Or:logical_or<T>
- 逻辑运算 Not:logical_not<T>
template <class T>
struct logical_and : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x && y; }
};
template <class T>
struct logical_or : public binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x || y; }
};
template <class T>
struct logical_not : public unary_function<T, bool> {
bool operator()(const T& x) const { return !x; }
};
C++标准并未涵盖这里介绍的任何一个仿函数,不过它们常常存在于各个实现品中作为内部运用。在SGI STL中的实现如下:
//证同函数。任何数值通过此函数后,不会有任何改变
//此函数运用于<stl_set.h>,用来指定RB-tree所需的KeyOfValue op
//那是因为set元素的键值即实值,所以采用identity
template <class T>
struct identity : public unary_function<T, T> {
const T& operator()(const T& x) const { return x; }
};
//选择函数:接受一个pair,传回其第一元素
//此函数运用于<stl_map.h>,用来指定RB-tree所需的KeyOfValue op
//由于map系以pair元素的第一元素为其键值,所以采用select1st
template <class Pair>
struct select1st : public unary_function<Pair, typename Pair::first_type> {
const typename Pair::first_type& operator()(const Pair& x) const
{
return x.first;
}
};
//选择函数:接受一个pair,传回其第二元素
//SGI STL并未运用此函数
template <class Pair>
struct select2nd : public unary_function<Pair, typename Pair::second_type> {
const typename Pair::second_type& operator()(const Pair& x) const
{
return x.second;
}
};
//投射函数:传回其第一参数,忽略第二参数
template <class Arg1, class Arg2>
struct project1st : public binary_function<Arg1, Arg2, Arg1> {
Arg1 operator()(const Arg1& x, const Arg2&) const { return x; }
};
//投射函数:传回第二参数,忽略第一参数
template <class Arg1, class Arg2>
struct project2nd : public binary_function<Arg1, Arg2, Arg2> {
Arg2 operator()(const Arg1&, const Arg2& y) const { return y; }
};
适配器在STL组件的灵活组合运用功能上,扮演着轴承、转换器的角色
STL所提供的各种适配器中:1)改变仿函数接口者,称为函数适配器;2)改变容器接口者,称为容器适配器;3)改变迭代器接口者,称为迭代器适配器
STL提供两个容器适配器:queue和stack,它们修饰deque的接口而生成新的容器风貌
stack的底层由deque构成。stack封锁住了所有的deque对外接口,只开放符合stack原则的几个函数
queue的底层也由deque构成。queue封锁住了所有的deque对外接口,只开放符合queue原则的几个函数
stack和queue的具体详见第四章
STL提供了许多应用于迭代器身上的适配器,包括:
-
insert iterators:可以将一般迭代的赋值操作转变为插入操作,可以分为下面几个
- back_insert_iterator:专门负责尾端的插入操作
- front_insert_iterator:专门负责首部的插入操作
- insert_iterator:可以从任意位置执行插入操作
由于上面3个迭代器的使用接口不是十分直观,因此,STL提供了三个相应函数用以获取相应迭代器:
-
reverse iterators:可以将一般迭代器的行进方向反转
-
iostream iterators:可以将迭代器绑定到某个iostream对象身上
- 绑定到istream对象身上的,称为istream_iterator,拥有输入功能
- 绑定到ostream对象身上的,称为ostream_iterator,拥有输出功能
C++ Standard规定它们的接口可以藉由获得,SGI STL将它们实际定义于<stl_iterator.h>
insert iterators实现的主要观念是:每一个insert iterators内部都维护有一个容器(必须由用户指定);容器当然有自己的迭代器,于是,当客户端对insert iterators做赋值操作时,就在insert iterators中被转为对该容器的迭代器做插入操作(也就是说,调用底层容器的push_front()或push_back()或insert())
其它迭代器惯常的行为如:operator++、operator++(int)、operator*都被关闭,更没有提供operator--或operator--(int)或operator->等功能,因此类型被定义为output_iterator_tag
template <class Container>
class back_insert_iterator {
protected:
Container* container; //底层容器
public:
typedef output_iterator_tag iterator_category; //迭代器类型
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
//构造函数。传入一个容器,使back_insert_iterator与容器绑定起来
explicit back_insert_iterator(Container& x) : container(&x) {}
//赋值操作
back_insert_iterator<Container>&
operator=(const typename Container::value_type& value) {
container->push_back(value); //赋值操作的关键是转调用容器的push_back()
return *this;
}
//以下3个操作对back_insert_iterator不起作用(关闭功能)
//三个操作符返回的都是back_insert_iterator自己
back_insert_iterator<Container>& operator*() { return *this; }
back_insert_iterator<Container>& operator++() { return *this; }
back_insert_iterator<Container>& operator++(int) { return *this; }
};
//这是一个辅助函数,帮助我们方便使用back_insert_iterator
template <class Container>
inline back_insert_iterator<Container> back_inserter(Container& x) {
return back_insert_iterator<Container>(x);
}
template <class Container>
class front_insert_iterator {
protected:
Container* container; //底层容器
public:
typedef output_iterator_tag iterator_category; //迭代器类型
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
//构造函数。传入一个容器,使front_insert_iterator与容器绑定起来
explicit front_insert_iterator(Container& x) : container(&x) {}
//赋值操作
front_insert_iterator<Container>&
operator=(const typename Container::value_type& value) {
container->push_front(value); //赋值操作的关键是转调用容器的push_front()
return *this;
}
//以下3个操作对front_insert_iterator不起作用(关闭功能)
//三个操作符返回的都是front_insert_iterator自己
front_insert_iterator<Container>& operator*() { return *this; }
front_insert_iterator<Container>& operator++() { return *this; }
front_insert_iterator<Container>& operator++(int) { return *this; }
};
//这是一个辅助函数,帮助我们方便使用front_insert_iterator
template <class Container>
inline front_insert_iterator<Container> front_inserter(Container& x) {
return front_insert_iterator<Container>(x);
}
template <class Container>
class insert_iterator {
protected:
Container* container; //底层容器
typename Container::iterator iter; //底层容器的迭代器(前2个插入迭代器没有)
public:
typedef output_iterator_tag iterator_category; //迭代器类型
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
//构造函数。传入一个容器,使insert_iterator与容器和容器迭代器绑定起来
insert_iterator(Container& x, typename Container::iterator i)
: container(&x), iter(i) {}
//赋值操作
insert_iterator<Container>&
operator=(const typename Container::value_type& value) {
iter = container->insert(iter, value); //赋值操作的关键是转调用容器的insert()
++iter; //使insert iterator永远随其目标贴身移动
return *this;
}
//以下3个操作对insert_iterator不起作用(关闭功能)
//三个操作符返回的都是insert_iterator自己
insert_iterator<Container>& operator*() { return *this; }
insert_iterator<Container>& operator++() { return *this; }
insert_iterator<Container>& operator++(int) { return *this; }
};
//这是一个辅助函数,帮助我们方便使用insert_iterator
//和前2个插入迭代器不容,这里还需额外传入一个底层容器的迭代器
template <class Container, class Iterator>
inline insert_iterator<Container> inserter(Container& x, Iterator i) {
typedef typename Container::iterator iter;
return insert_iterator<Container>(x, iter(i));
}
可以通过一个双向顺序容器调用rbegin(),和rend()来获取相应的逆向迭代器。只要双向顺序容器提供了begin(),end(),它的rbegin()和rend()就如同下面的形式。单向顺序容器slist不可使用reserve iterators。有些容器如stack、queue、priority_queue并不提供begin(),end(),当然也就没有rbegin()和rend():
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; //容器迭代器类型
typedef reverse_iterator<iterator> reverse_iterator; //逆向迭代器类型
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
...
};
template <class T, class Alloc = alloc>
class list {
public:
typedef __list_iterator<T, T&, T*> iterator; //容器迭代器类型
typedef reverse_iterator<iterator> reverse_iterator; //逆向迭代器类型
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
...
};
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public:
typedef __deque_iterator<T, T&, T*, BufSiz> iterator; //容器迭代器类型
typedef reverse_iterator<iterator> reverse_iterator; //逆向迭代器类型
iterator begin() { return start; }
iterator end() { return finish; }
reverse_iterator rbegin() { return reverse_iterator(finish); }
reverse_iterator rend() { return reverse_iterator(start); }
正向迭代器和逆向迭代器的逻辑位置如下图:
具有这样的逻辑位置关系,当我们将一个正向迭代器区间转换为一个逆向迭代器区间后,不必再有任何额外处理,就可以让接受这个逆向迭代器区间的算法,以相反的元素次序处理区间中的每一个元素
reverse_iterator实现如下:
template <class Iterator>
class reverse_iterator
{
protected:
Iterator current; //对应的正向迭代器
public:
//迭代器的5种相应类型都和其对应的正向迭代器相同
typedef typename iterator_traits<Iterator>::iterator_category
iterator_category;
typedef typename iterator_traits<Iterator>::value_type
value_type;
typedef typename iterator_traits<Iterator>::difference_type
difference_type;
typedef typename iterator_traits<Iterator>::pointer
pointer;
typedef typename iterator_traits<Iterator>::reference
reference;
typedef Iterator iterator_type; //代表正向迭代器
typedef reverse_iterator<Iterator> self; //代表逆向迭代器
public:
reverse_iterator() {}
//下面这个构造函数将逆向迭代器与正向迭代器x关联起来
explicit reverse_iterator(iterator_type x) : current(x) {}
reverse_iterator(const self& x) : current(x.current) {}
//base()成员函数返回相应的正向迭代器
iterator_type base() const { return current; }
//对逆向迭代器取值,就是将“对应的正向迭代器”后退一步后取值ßßßß
reference operator*() const {
Iterator tmp = current;
return *--tmp;
}
//前置++,++变为--
self& operator++() {
--current;
return *this;
}
//后置++,++变--
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
//前置--,--变++
self& operator--() {
++current;
return *this;
}
//后置--,--变++
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
//前进与后退方向完全逆转
self operator+(difference_type n) const {
return self(current - n);
}
self& operator+=(difference_type n) {
current -= n;
return *this;
}
self operator-(difference_type n) const {
return self(current + n);
}
self& operator-=(difference_type n) {
current += n;
return *this;
}
//第一个*会调用本类的operator*,第二个不会
reference operator[](difference_type n) const { return *(*this + n); }
};
所谓绑定一个istream object,其实就是在istream iterator内部维护一个istream member,客户端对于这个迭代器所做的operator++操作,会被引导调用迭代器内部所含的那个istream member的输入操作(operator>>)。这个迭代器是个input iterator,不具备operator--
//此版本是旧有的HP规格,未符合标准接口:istream_iterator<T,charT,traits,Distance>
//然而一般使用input iterators时都只使用第一个template参数、此时以下仍适用
//SGI STL 3.3已实现出符合标准接口的istream_iterator,做法与本版大同小异
template <class T, class Distance = ptrdiff_t>
class istream_iterator {
friend bool
operator== __STL_NULL_TMPL_ARGS (const istream_iterator<T, Distance>& x,
const istream_iterator<T, Distance>& y);
protected:
istream* stream;
T value;
bool end_marker;
void read() {
end_marker = (*stream) ? true : false;
if (end_marker) *stream >> value; //关键
//输入后,stream的状态可能改变,所以下面再判断一次以决定end_marker
//当读到eof或读到类型不符的数据,stream即处于false状态
end_marker = (*stream) ? true : false;
}
public:
typedef input_iterator_tag iterator_category; //迭代器类型
typedef T value_type;
typedef Distance difference_type;
typedef const T* pointer;
typedef const T& reference;
istream_iterator() : stream(&cin), end_marker(false) {}
istream_iterator(istream& s) : stream(&s) { read(); }
//以上两行的用法:
// istream_iterator<int> eos; 造成end_marker为false
// istream_iterator<int> initer(cin) 引发read(),程序至此会等待输入
reference operator*() const { return value; }
pointer operator->() const { return &(operator*()); }
//迭代器前进一个位置,就代表要读取一次数据
istream_iterator<T, Distance>& operator++() {
read();
return *this;
}
istream_iterator<T, Distance> operator++(int) {
istream_iterator<T, Distance> tmp = *this;
read();
return tmp;
}
};
下图展示了copy()和istream_iterator共同合作的例子:
所谓绑定一个ostream object,其实就是在oßstream iterator内部维护一个ostream member,客户端对于这个迭代器所做的operator=操作,会被引导调用迭代器内部所含的那个ostream member的输出操作(operator<<)。这个迭代器是个Onput iterator
//此版本是旧有的HP规格,未符合标准接口:istream_iterator<T,charT,traits>
//然而一般使用onput iterators时都只使用第一个template参数、此时以下仍适用
//SGI STL 3.3已实现出符合标准接口的ostream_iterator,做法与本版大同小异
template <class T>
class ostream_iterator {
protected:
ostream* stream;
const char* string; //每次输出后的间隔符号
public:
typedef output_iterator_tag iterator_category; //迭代器类型
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
ostream_iterator(ostream& s) : stream(&s), string(0) {}
ostream_iterator(ostream& s, const char* c) : stream(&s), string(c) {}
//对迭代器做赋值操作,就代表要输出一笔数据
ostream_iterator<T>& operator=(const T& value) {
*stream << value; //关键,输出数值
if (string) *stream << string; //如果间隔符号不为空,输出间隔符号
return *this;
}
ostream_iterator<T>& operator*() { return *this; }
ostream_iterator<T>& operator++() { return *this; }
ostream_iterator<T>& operator++(int) { return *this; }
};
下图展示了copy()和ostream_iterator共同合作的例子:
函数适配器(functor adapters,亦即function adapters)是所有适配器中数量最庞大的一个族群,其适配灵活度也是前2者所不能及,可以适配、适配、再适配
函数适配器的价值:通过它们之间的绑定、组合、修饰能力,几乎可以无限制地创造出各种可能的表达式,搭配STL算法一起演出。下表是STL函数适配器一览表:
适配操作包括:
- bind、negate、compose
- 对一般函数或成员函数的修饰
C++标准规定,这些适配器的接口可由<functional>获得,SGI STL将它们定义于<stl_function.h>
注意,所有期望获得适配能力的组件,本身都必须是可适配的。换句话说,1)一元仿函数必须继承自unary_function;2)二元仿函数必须继承自binary_function;3)成员函数必须以mem_fun处理过;4)一般函数必须以ptr_fun处理过。一个未经ptr_fun处理过的一般函数,虽然也能以函数指针的形式传给STL算法使用,却无法拥有任何适配能力
下图是count_if()和bind2nd(less(),12)的搭配实例;
//以下适配器用来表示某个 "可适配 predicate" 的逻辑负值
template <class Predicate>
class unary_negate
: public unary_function<typename Predicate::argument_type, bool> {
protected:
Predicate pred; //内部成员
public:
explicit unary_negate(const Predicate& x) : pred(x) {}
bool operator()(const typename Predicate::argument_type& x) const {
return !pred(x); //将pred的运算结果加上否定运算
}
};
//辅助函数,使我们得以更方便使用unary_negate
template <class Predicate>
inline unary_negate<Predicate> not1(const Predicate& pred) {
return unary_negate<Predicate>(pred);
}
//以下适配器用来表示某个 "可适配 binary predicate" 的逻辑负值
template <class Predicate>
class binary_negate
: public binary_function<typename Predicate::first_argument_type,
typename Predicate::second_argument_type,
bool> {
protected:
Predicate pred; //内部成员
public:
explicit binary_negate(const Predicate& x) : pred(x) {}
bool operator()(const typename Predicate::first_argument_type& x,
const typename Predicate::second_argument_type& y) const {
return !pred(x, y); //将pred的运算结果加上否定运算
}
};
//辅助函数,使我们得以更方便使用binary_negate
template <class Predicate>
inline binary_negate<Predicate> not2(const Predicate& pred) {
return binary_negate<Predicate>(pred);
}
//以下适配器用来表示某个 "可适配 binary function" 转换为 “unary function”
template <class Operation>
class binder1st
: public unary_function<typename Operation::second_argument_type,
typename Operation::result_type> {
protected:
Operation op; //内部成员
typename Operation::first_argument_type value; //内部成员
public:
binder1st(const Operation& x,
const typename Operation::first_argument_type& y)
: op(x), value(y) {} //将表达式和第一参数记录于内部成员
typename Operation::result_type
operator()(const typename Operation::second_argument_type& x) const {
return op(value, x); //实际调用表达式,并将value绑定为第一参数
}
};
//辅助函数,使我们得以更方便使用binder1st
template <class Operation, class T>
inline binder1st<Operation> bind1st(const Operation& op, const T& x) {
//先把x转型为op的第一参数类型
typedef typename Operation::first_argument_type arg1_type;
return binder1st<Operation>(op, arg1_type(x));
}
//以下适配器用来表示某个 "可适配 binary function" 转换为 “unary function”
template <class Operation>
class binder2nd
: public unary_function<typename Operation::first_argument_type,
typename Operation::result_type> {
protected:
Operation op; //内部成员
typename Operation::second_argument_type value; //内部成员
public:
binder2nd(const Operation& x,
const typename Operation::second_argument_type& y)
: op(x), value(y) {} //将表达式和第二参数记录于内部成员
typename Operation::result_type
operator()(const typename Operation::first_argument_type& x) const {
return op(x, value); //实际调用表达式,并将value绑定为第二参数
}
};
//辅助函数,使我们得以更方便使用binder2nd
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T& x) {
//先把x转型为op的第一参数类型
typedef typename Operation::second_argument_type arg2_type;
return binder2nd<Operation>(op, arg2_type(x));
}
//已知两个 "可适配 unary function" f(),g(),以下适配器用来产生一个h(),
//使 h(x) = f(g(x))
template <class Operation1, class Operation2>
class unary_compose : public unary_function<typename Operation2::argument_type,
typename Operation1::result_type> {
protected:
Operation1 op1; //内部成员
Operation2 op2; //内部成员
public:
//构造函数,将两个表达式记录于内部成员
unary_compose(const Operation1& x, const Operation2& y) : op1(x), op2(y) {}
typename Operation1::result_type
operator()(const typename Operation2::argument_type& x) const {
return op1(op2(x)); //函数合成
}
};
//辅助函数,让我们得以方便运用unary_compose
template <class Operation1, class Operation2>
inline unary_compose<Operation1, Operation2> compose1(const Operation1& op1,
const Operation2& op2) {
return unary_compose<Operation1, Operation2>(op1, op2);
}
//已知一个 “可适配 binary function” f 和 两个 "可适配 unary function" g1,g2,
//以下适配器用来产生一个h,使 h(x) = f(g1(x),g2(x))
template <class Operation1, class Operation2, class Operation3>
class binary_compose
: public unary_function<typename Operation2::argument_type,
typename Operation1::result_type> {
protected:
Operation1 op1; //内部成员
Operation2 op2; //内部成员
Operation3 op3; //内部成员
public:
//构造函数,将三个表达式记录于内部成员
binary_compose(const Operation1& x, const Operation2& y,
const Operation3& z) : op1(x), op2(y), op3(z) { }
typename Operation1::result_type
operator()(const typename Operation2::argument_type& x) const {
return op1(op2(x), op3(x)); //函数合成
}
};
//辅助函数,让我们得以方便运用binary_compose
template <class Operation1, class Operation2, class Operation3>
inline binary_compose<Operation1, Operation2, Operation3>
compose2(const Operation1& op1, const Operation2& op2, const Operation3& op3) {
return binary_compose<Operation1, Operation2, Operation3>(op1, op2, op3);
}
//以下适配器其实就是把一个一元函数指针包起来
//当仿函数被动调用时,就调用该函数指针
template <class Arg, class Result>
class pointer_to_unary_function : public unary_function<Arg, Result> {
protected:
Result (*ptr)(Arg); //内部成员,一个函数指针
public:
pointer_to_unary_function() {}
//构造函数,将函数指针记录于内部成员中
explicit pointer_to_unary_function(Result (*x)(Arg)) : ptr(x) {}
//通过函数指针指向函数
Result operator()(Arg x) const { return ptr(x); }
};
//辅助函数,让我们得以方便使用pointer_to_unary_function
template <class Arg, class Result>
inline pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) {
return pointer_to_unary_function<Arg, Result>(x);
}
//以下适配器其实就是把一个二元函数指针包起来
//当仿函数被动调用时,就调用该函数指针
template <class Arg1, class Arg2, class Result>
class pointer_to_binary_function : public binary_function<Arg1, Arg2, Result> {
protected:
Result (*ptr)(Arg1, Arg2); //内部成员,一个函数指针
public:
pointer_to_binary_function() {}
//构造函数,将函数指针记录于内部成员中
explicit pointer_to_binary_function(Result (*x)(Arg1, Arg2)) : ptr(x) {}
//通过函数指针指向函数
Result operator()(Arg1 x, Arg2 y) const { return ptr(x, y); }
};
//辅助函数,让我们得以方便使用pointer_to_binary_function
template <class Arg1, class Arg2, class Result>
inline pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (*x)(Arg1, Arg2)) {
return pointer_to_binary_function<Arg1, Arg2, Result>(x);
}
假设Shape是一个继承体系中的基类,并且具有虚函数display(),有一个vector<Shape*> V,那么可以给for_each()传入一个以适配器mem_fun修饰的display():
for_each(V.begin(),V.end(),mem_fun(&Shape::display));
不能写成:
for_each(V.begin(),V.end(),&Shape::display);
for_each(V.begin(),V.end(),Shape::display);
以下是用于成员函数的适配器的实现:
//“无任何参数”、“通过pointer调用”、“non-const成员函数”
template <class S, class T>
class mem_fun_t : public unary_function<T*, S> {
public:
explicit mem_fun_t(S (T::*pf)()) : f(pf) {} //构造函数
S operator()(T* p) const { return (p->*f)(); } //转调用
private:
S (T::*f)();
};
//“无任何参数”、“通过pointer调用”、“const成员函数”
template <class S, class T>
class const_mem_fun_t : public unary_function<const T*, S> {
public:
explicit const_mem_fun_t(S (T::*pf)() const) : f(pf) {} //构造函数
S operator()(const T* p) const { return (p->*f)(); } //转调用
private:
S (T::*f)() const;
};
//“无任何参数”、“通过reference调用”、“non-const成员函数”
template <class S, class T>
class mem_fun_ref_t : public unary_function<T, S> {
public:
explicit mem_fun_ref_t(S (T::*pf)()) : f(pf) {} //构造函数
S operator()(T& r) const { return (r.*f)(); } //转调用
private:
S (T::*f)();
};
//“无任何参数”、“通过reference调用”、“const成员函数”
template <class S, class T>
class const_mem_fun_ref_t : public unary_function<T, S> {
public:
explicit const_mem_fun_ref_t(S (T::*pf)() const) : f(pf) {} //构造函数
S operator()(const T& r) const { return (r.*f)(); } //转调用
private:
S (T::*f)() const;
};
//“有1个参数”、“通过pointer调用”、“non-const成员函数”
template <class S, class T, class A>
class mem_fun1_t : public binary_function<T*, A, S> {
public:
explicit mem_fun1_t(S (T::*pf)(A)) : f(pf) {} //构造函数
S operator()(T* p, A x) const { return (p->*f)(x); } //转调用
private:
S (T::*f)(A);
};
//“有1个参数”、“通过pointer调用”、“const成员函数”
template <class S, class T, class A>
class const_mem_fun1_t : public binary_function<const T*, A, S> {
public:
explicit const_mem_fun1_t(S (T::*pf)(A) const) : f(pf) {} //构造函数
S operator()(const T* p, A x) const { return (p->*f)(x); } //转调用
private:
S (T::*f)(A) const;
};
//“有1个参数”、“通过reference调用”、“non-const成员函数”
template <class S, class T, class A>
class mem_fun1_ref_t : public binary_function<T, A, S> {
public:
explicit mem_fun1_ref_t(S (T::*pf)(A)) : f(pf) {} //构造函数
S operator()(T& r, A x) const { return (r.*f)(x); } //转调用
private:
S (T::*f)(A);
};
//“有1个参数”、“通过reference调用”、“const成员函数”
template <class S, class T, class A>
class const_mem_fun1_ref_t : public binary_function<T, A, S> {
public:
explicit const_mem_fun1_ref_t(S (T::*pf)(A) const) : f(pf) {} //构造函数
S operator()(const T& r, A x) const { return (r.*f)(x); } //转调用
private:
S (T::*f)(A) const;
};
/*********************************************************
* 下面的8个辅助函数简化了上面8个类的使用
* mem_fun 与 mem_fun_ref
* mem_fun1 与 mem_fun1_ref:C++标准已经去掉了1,改成和上面2个
函数重载的形式
*********************************************************/
template <class S, class T>
inline mem_fun_t<S,T> mem_fun(S (T::*f)()) {
return mem_fun_t<S,T>(f);
}
template <class S, class T>
inline const_mem_fun_t<S,T> mem_fun(S (T::*f)() const) {
return const_mem_fun_t<S,T>(f);
}
template <class S, class T>
inline mem_fun_ref_t<S,T> mem_fun_ref(S (T::*f)()) {
return mem_fun_ref_t<S,T>(f);
}
template <class S, class T>
inline const_mem_fun_ref_t<S,T> mem_fun_ref(S (T::*f)() const) {
return const_mem_fun_ref_t<S,T>(f);
}
template <class S, class T, class A>
inline mem_fun1_t<S,T,A> mem_fun1(S (T::*f)(A)) {
return mem_fun1_t<S,T,A>(f);
}
template <class S, class T, class A>
inline const_mem_fun1_t<S,T,A> mem_fun1(S (T::*f)(A) const) {
return const_mem_fun1_t<S,T,A>(f);
}
template <class S, class T, class A>
inline mem_fun1_ref_t<S,T,A> mem_fun1_ref(S (T::*f)(A)) {
return mem_fun1_ref_t<S,T,A>(f);
}
template <class S, class T, class A>
inline const_mem_fun1_ref_t<S,T,A> mem_fun1_ref(S (T::*f)(A) const) {
return const_mem_fun1_ref_t<S,T,A>(f);
}