一.简介
1.GNU源代码开发精神2.STL版本3.SGI STL头文件分布4.STL六大部件 二.空间分配器
1.空间分配器的标准接口2.SGI标准的空间分配器std::allocator3.SGI特殊的空间分配器std::alloc
3.1 对象构造与析构3.2 内存分配与释放
3.2.1 两级分配器3.2.2 第一级分配器__malloc_alloc_template3.2.3 第二级分配器__default_alloc_template 3.3 内存基本处理工具 三.迭代器与traits编程技法
1.迭代器相应类型2.traits编程技法3.std::iterator的保证4.SGI STL的__type_traits 四.顺序容器
1.vector2.list3.deque4.stack5.queue6.heap7.priority_queue8.slist 五.关联容器
1.RB-tree2.set3.map4.multiset5.multimap6.hashtable7.hash_set8.hash_map9.hash_multiset10.hash_multimap 六.算法
1.区间拷贝2.set相关算法3.排序sort4.其它算法 七.仿函数
1.仿函数的相应类型2.算术类仿函数3.关系运算类仿函数4.逻辑运算类仿函数5.证同，选择与投射 八.适配器
1.容器适配器2.迭代器适配器
2.1 insert iterators2.2 reverse iterators2.3 iostream iterators 3.函数适配器
3.1 not1和not23.2 bind1st和bind2st3.3 compose1和compose23.4 用于函数指针的ptr_fun3.5 用于成员函数指针的mem_fun和mem_fun_ref
一.简介
1.GNU源代码开放精神
全世界所有的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
2.STL版本
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正面影响）可读性很高为了具有高度移植性，考虑了不同编译器的不同编译能力
3.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准备了一个环境组态文件
组态测试程序：
编译器对组态的支持组态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）
4.STL六大部件
最重要的2个是容器与算法
容器(container)分配器(Allocator)算法(Algorithms)迭代器(Iterrators)适配器(Adaptors)仿函数(Functors)
二.空间分配器
在运用层面，不需要关注空间分配器。但是在容器背后，空间分配器负责容器中元素空间的分配
不称作”内存分配器“，是因为分配的空间不一定是内存，可以是磁盘或其它辅助存储介质。可以实现一个获取磁盘空间的allocator。不过这里介绍的空间分配器获取的空间是内存
1.空间分配器的标准接口
通常，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 拥有唯一成员other,是一个typedef，代表allocator
allocator::rebind
//构造函数
allocator::allocator()
//拷贝构造函数
allocator::allocator(const allocator&)
template
//析构函数
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的分配器，符合部分标准
2.SGI标准的空间分配器std::allocator
虽然SGI也定义有一个符合”部分“标准、名为allocator的分配器，但SGI自己从未用过它，也不建议我们使用。主要原因是效率不佳，只把C++的::operator new和::operator delete做一层薄薄的包装而已
3.SGI特殊的空间分配器std::alloc
STL标准规定分配器定义于
真正在SGI STL中大显身手的分配器（即SGI特殊的空间分配器std::alloc）或为第一级分配器，或为第二级分配器
3.1 对象构造与析构
STL规定分配器必须拥有名为construct()和destroy()的两个成员函数，然而SGI特殊的空间分配器std::alloc并未遵守这一规则，所以实际上这部分属于STL allocator，但不属于std::alloc。换句话说，SGI特殊的空间分配器std::alloc不包含”3.1 对象构造与析构“，只包含”3.2 内存分配与释放“
3.2 内存分配与释放
SGI对内存分配与释放的设计哲学如下：
向system heap申请空间考虑多线程状态考虑内存不足时的应变措施考虑过多“小型区块”可能造成的内存碎片问题（SGI设计了双层级分配器）
C++的内存分配基本操作是::operator new(),内存释放基本操作是::operator delete()。这两个全局函数相当于C的malloc()和free()函数。SGI正是以malloc和free()完成内存的分配与释放
3.2.1 两级分配器
考虑到小型区块所可能造成的内存碎片问题，SGI设计了双层级分配器：
第一级分配器
直接使用malloc()和free() 第二级分配器
当分配区块超过128bytes时，视为“足够大”，调用第一级分配器当分配区块小于128bytes时，视为“过小”，为了降低额外负担，采用复杂的memory pool整理方式，不再求助于第一级分配器
无论alloc被定义为第一级或第二级分配器，SGI还为它再包装一个接口，使分配器的接口能够符合STL规格：
template
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已经把它设为第二级分配器
两级分配器都定义在头文件
3.2.2 第一级分配器__malloc_alloc_template
//一般而言是线程安全，并且对于空间的运用比较高效
//无“template型别参数”，至于”非型别参数“inst，则完全没派上用场
template
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
void (* __malloc_alloc_template
#endif
template
void * __malloc_alloc_template
{
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
void * __malloc_alloc_template
{
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的实现）
3.2.3 第二级分配器__default_alloc_template
第二级分配器多了一些机制，避免太多小额区块造成内存的碎片，小额区块存在下列问题：
产生内存碎片额外负担。额外负担是一些区块信息，用以管理内存。区块越小，额外负担所占的比例就越大，越显浪费
当区块大于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也定义在头文件
#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
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
char *__default_alloc_template
template
char *__default_alloc_template
template
size_t __default_alloc_template
template
__default_alloc_template
__default_alloc_template
{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(附加量)个区块留给内存池…
3.3 内存基本处理工具
STL定义了5个全局函数，作用于未初始化空间上，有助于容器的实现：
作用于单个对象（见3.1 对象构造与析构，SGI STL定义在头文件
construct()函数（构造单个对象）destroy()函数（析构单个对象） 作用于容器的区间（本节，SGI STL定义在头文件
uninitialized_copy()函数uninitialized_fill()函数uninitialized_fill_n()函数
容器的全区间构造函数通常分2步：
分配内存区块，足以包含范围内的所有元素调用上述3个函数在全区间范围内构造对象（因此，这3个函数使我们能够将内存的分配与对象的构造行为分离；并且3个函数都具有”commit or rollback“语意，要么所有对象都构造成功，要么一个都没有构造）
三.迭代器与traits编程技法
1.迭代器相应类型
在算法中运用迭代器时，很可能会用到其相应类型。所谓相应类型，迭代器所指之物的类型便是其中之一，算法可以在函数体中使用迭代器所指之物的类型来定义变量，也可能将迭代器所指之物的类型作为算法的返回值：
在函数体中使用迭代器所指之物的类型
C++支持sizeof()，但并未支持typeof()。即便动用RTTI性质中的typeid()，获得的也只是类型名称，不能拿来做变量声明这里利用函数模板的参数推导机制解决。算法func()作为对外接口，算法的所有逻辑另外封装在一个实现函数func_impl()中，由于它是一个函数模板，一旦被调用，编译器就会自动进行参数推导，导出类型T 迭代器所指之物的类型作为算法的返回类型
函数模板的参数推导机制推导的是参数，无法推导函数的返回类型这里使用嵌套类型声明解决。但是，对于类类型的迭代器，可以正常工作，但是非类类型的原生指针无法处理
通过上图，可以了解到在算法中对迭代器相应类型的需求。除了迭代器所指之物的类型(value type)，迭代器相应类型还包括另外4种，在traits编程技法中将会介绍，并且会提到如何使用traits来解决上面的问题（这也是STL中实际使用的方法）
2.traits编程技法
上一节所使用的方法，在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
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（定义于
//针对原生指针的偏特化版本
template
struct iterator_traits
//原生指针是一种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
struct iterator_traits
//原生指针是一种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
inline typename iterator_traits
iterator_category(const Iterator&) {
typedef typename iterator_traits
return category();
}
//这个函数可以很方便地萃取distance type
template
inline typename iterator_traits
distance_type(const Iterator&) {
return static_cast
}
//这个函数可以很方便地萃取value type
template
inline typename iterator_traits
value_type(const Iterator&) {
return static_cast
}
2.1 迭代器类型
设计算法时，如果可能，尽量针对某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义，这样才能在不同情况下提供最大效率，如下图的advanced()函数，用于移动迭代器：
在上图中，每个__advance()的最后一个参数都只声明类型，并未指定参数名称，因为它纯粹只是用来激活重载机制，函数之中根本不使用该参数。如果加上参数名称也没有错，但是没必要
将advance()中的iterator_category(i)展开得到iterator_traits
上图以class来定义迭代器的各种分类标签，有下列好处：
可以促成重载机制的成功运作通过继承，可以不必再写“单纯只做传递调用”的函数（如__advance()的Forward Iterator版只是单纯的调用Input Iterator版，因此可以省略）,可以通过这个例子来模拟证实
3.std::iterator的保证
为了符合规范，任何迭代器都应该提供5个内嵌相应类型，以便于traits萃取，否则便是自别于整个STL架构，可能无法与其它STL组件顺利搭配。然而，写代码难免会有遗漏。因此，STL提供了一个iterators class如下，如果每个新设计的迭代器都继承自它，就可保证符合STL所需的规范；
template 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 struct ListIter : public std::iterator ... }; 4.SGI STL的__type_traits 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 1.vector array是静态空间，一旦配置了就不能改变；vector与array非常相似，但是vector是动态空间，随着元素的加入，内部机制会自动扩充以容纳新元素 SGI STL中vector的定义 1.1 迭代器 vector维护的是一个连续线性空间，所以不论其元素类型为何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator*，operator->，operator++，operator–，operator+，operator-，operator+=，operator-=，普通指针天生就具备。vector支持随机存取，而普通指针正有着这样的能力。所以，vector提供的是Random Access Iterators： template class vector{ public: typedef T value_type; typedef value_type* iterator; //vector的迭代器时普通指针 ... }; 1.2 分配器 vector缺省使用alloc作为空间分配器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位： template class vector{ protected: typedef simple_alloc ... }; 因此，data_allocator::allocate(n)表示分配n个元素空间 1.3 vector操作的实现 常见的vector操作包括： vector(size_type n,const T &value) fill_initialize(size_type n,const T &value) allocate_and_fill(size_type n, const T& x) push_back(const T &x) insert_aux(iterator position,const T &x) pop_back()erase(iterator first, iterator last)erase(iterator position)insert(iterator position, size_type n, const T& x) 插入操作可能造成vector的3个指针重新配置，导致原有的迭代器全部失效 2.list SGI STL中list的定义 2.1 节点 template struct __list_node{ typedef void* void_pointer; void_pointer prev; //类型为void* void_pointer next; T data; }; 2.2 迭代器 list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在 list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。list中，迭代器与节点的关系见下图： 由于STL list是一个双向链表，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterators list的插入和接合操作都不会造成原有的list迭代器失效，对于删除操作，也只有”指向被删除元素“的那个迭代器失效，其它迭代器不受任何影响 template struct __list_iterator { typedef __list_iterator typedef __list_iterator typedef __list_iterator typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node 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; } }; 2.3 list的数据结构 SGI list不仅是一个双向链表，还是一个环状双向链表。所以它只需要一个指针，便可完整表现整个链表： template class list { protected: typedef __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; } 2.4 分配器 list缺省使用alloc作为空间分配器，并据此另外定义了一个list_node_allocator，为的是更方便以节点大小为配置单位： template class list { protected: typedef simple_alloc ... }; 因此，list_node_allocator::allocate(n)表示分配n个节点空间 2.5 list操作的实现 节点操作 分配一个节点：get_node释放一个节点：put_node生成（分配并构造）一个节点：create_node销毁（析构并释放）一个节点：destroy_node节点插入：push_back和push_front insert 节点移除：erase,pop_front和pop_back移除某一数值的所有节点：remove移除数值相同的连续节点：unique 链表操作 创建一个空链表：list() empty_initialize 链表清空：clear 链表拼接：splice 将[first,last)内的元素移动到position之前：transfer（[first,last)区间可以在同一个list之中，transfer并非公开接口，公开的是splice） 3.deque deque是一种双向开口的连续线性空间 deque和vector最大的差异： deque允许于常数时间内对起头端进行元素的插入或移除操作deque没有所谓容量观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来（deque没有必要提供所谓的空间保留功能） 3.1 迭代器 deque是分段连续空间。维持其”整体连续“假象的任务，落在了迭代器的operator++和operator–两个运算子身上 deque迭代器必须能够指出分段连续空间（即缓冲区）在哪；必须能够判断自己是否已经处于其所在缓冲器的边缘。为了能够正确跳跃，迭代器必须随时掌握中控器map template struct __deque_iterator { //未继承std::iterator typedef __deque_iterator typedef __deque_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 ... }; 迭代器操作： 更新迭代器指向的缓冲区：set_node解引用*成员选择->迭代器相减-前置++和后置++前置–和后置–复合赋值+=和-=迭代器+n和-n随机存取[]相等判断==，!=和< 3.3 deque的数据结构 deque采用一块所谓的map作为主控(中控器)。这里所谓的map是指一小块连续空间，其中每个元素都是一个指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示使用512bytes缓冲区 deque除了维护一个指向map的指针外，也维护start，finish两个迭代器。分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外，也必须记住目前的map大小。因为一旦map所提供的节点不足，就必须重新配置更大的一块map temlate class deque{ public: //Basic types typedef T value_type; typedef value_type* pointer; typedef size_t size_type; ... public: typedef __deque_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的中控器、缓冲区、迭代器的关系如下图： 3.4 分配器 deque自行定义了2个专属的空间配置器： protected: //专属的空间分配器，每次分配一个元素大小 typedef simple_alloc //专属的空间分配器，每次分配一个指针大小 typedef simple_alloc 3.5 deque操作的实现 deque构造与初始化：deque 元素初始化fill_initialize 空间分配与成员设定create_map_and_nodes 插入操作： 在队列末尾插入：push_back 最后缓冲区只有1个可用空间时：push_back_aux map不足时：reserve_map_at_back reallocate_map 在队列首部插入：push_front 第一个缓冲区没有可用空间时：push_front_aux map不足时：reserve_map_at_front reallocate_map 指定位置插入一个元素：insert 在首部插入：push_front在尾部插入：push_back在中间插入：insert_aux 弹出操作： 弹出队列末尾元素：pop_back 最后缓冲区没有元素时：pop_back_aux 弹出队列首部元素：pop_front 第一个缓冲区仅有一个元素时：pop_front_aux 清除所有元素：clear清除某个区间的元素：erase 4.stack 具有”修改某物接口，形成另一种风貌“的性质者，称为适配器。因此，STL stack往往不被归类为容器，而被归类为容器适配器 SGI STL以deque作为缺省情况下的stack底部结构，定义如下： template 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 bool operator==(const stack return x.c == y.c; } template bool operator<(const stack return x.c < y.c; } 只有stack顶端的元素有机会被外界取用，stack不提供遍历功能，也不提供迭代器 指定其它容器作为stack的底层容器的方法： stack 5.queue queue（队列）是一种先进先出的数据结构，尾端插入，首部移出 SGI STL以deque作为缺省情况下的queue底部结构，定义如下： template 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 bool operator==(const queue return x.c == y.c; } template bool operator<(const queue return x.c < y.c; } 只有首部元素才有机会被外界取用，queue不提供遍历功能，也不提供迭代器 指定其它容器作为queue的底层容器的方法： queue 6.heap heap并不归属与STL容器组件，它是个幕后英雄，扮演priority queue的助手 heap是一颗完全二叉树，完全二叉树使用数组实现，因此使用一个vector作为heap的结构，然后通过一组xxx_heap算法，使其符合heap的性质 上溯（在此之前应该push_back）：push_heap __push_heap_aux __push_heap pop_heap（在此之后应该pop_back） __pop_heap_aux __pop_heap __adjust_heap sort_heap make_heap __make_heap 7.priority_queue 顾名思义，priority_queue就是具有优先级的queue，允许首部移出，尾端插入。缺省情况下利用一个max-heap完成，因此首部元素优先级最高 以下为SGI STL中priority_queue的定义： template class Compare = less 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 priority_queue(InputIterator first, InputIterator last, const Compare& x) : c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); } template 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只有首部的元素有机会被外界取用。不提供遍历功能，也不提供迭代器 8.slist slist并不在标准规格之内，由SGI STL提供，slist和list不同的是slist是单链表 单链表每个节点的消耗更小，但是只支持单向遍历，所以功能会受到许多限制 SGI STL中slist的定义 8.1 slist的节点 节点相关的结构： //单向链表的节点基本结构 struct __slist_node_base { __slist_node_base *next; }; //单向链表的节点结构 template 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; } 8.2 slist的迭代器 迭代器的定义如下： //单向链表的迭代器基本结构 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 struct __slist_iterator : public __slist_iterator_base { typedef __slist_iterator typedef __slist_iterator typedef __slist_iterator typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __slist_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(散列多键映射表) 1.RB-tree 1.1 RB-tree的节点 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 struct __rb_tree_node : public __rb_tree_node_base { typedef __rb_tree_node Value value_field; //RB-tree节点的value }; 键和值都包含在value_field中 1.2 RB-tree的迭代器 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 struct __rb_tree_iterator : public __rb_tree_base_iterator { typedef Value value_type; typedef Ref reference; typedef Ptr pointer; typedef __rb_tree_iterator typedef __rb_tree_iterator typedef __rb_tree_iterator typedef __rb_tree_node __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; } }; 1.3 RB-tree操作的实现 SGI STL中RB-tree的定义 节点操作： 涉及内存管理的操作 分配节点：get_node释放节点：put_node创建节点：create_node拷贝节点：clone_node销毁节点：destroy_node 获取节点成员： leftrightparentvaluekeycolor RB-tree操作 创建空RB-tree：rb_tree 初始化：init 获取root节点：root 获取最左子节点：leftmost 获取最右子节点：rightmost 获取起始节点：begin 获取末尾节点：end 是否为空：empty 大小：size 插入节点： 节点值独一无二：insert_unique __insert __rb_tree_rebalance __rb_tree_rotate_right 允许节点值重复：insert_equal __insert（同上） __rb_tree_rebalance（同上） __rb_tree_rotate_left（同上）__rb_tree_rotate_right（同上） 元素搜索： find 2.set SGI STL中set的定义 set的所有元素都会根据元素的键值自动被排序。元素的键值就是实值，实值就是键值、set不允许两个元素具有相同的键值 template class set { public: ... //键值和实值类型相同，比较函数也是同一个 typedef Key key_type; typedef Key value_type; typedef Compare key_compare; typedef Compare value_compare; private: ... typedef rb_tree identity 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的操作行为而已 3.map SGI STL中map的定义 map的所有元素会根据元素的键值自动被排序。所有元素都是pair，同时拥有键值和实值，第一个元素被视为键值，第二个元素被视为实值。map不允许两个元素拥有相同的键值 template class map { public: typedef Key key_type; //键值类型 typedef T data_type; //实值类型 typedef T mapped_type; typedef pair typedef Compare key_compare; //键值比较函数 ... private: typedef rb_tree select1st 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 ... }; 可以通过map的迭代器修改元素的实值，不能修改元素的键值 map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的map操作行为，都只是转调用RB-tree的操作行为而已 4.multiset SGI STL中set的定义 multiset的特性及用法和set完全相同，唯一的差别在于它允许键值重复，插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique() 5.multimap SGI STL中map的定义 multimap的特性及用法和map完全相同，唯一的差别在于它允许键值重复，插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique() 6.hashtable SGI STL中以开哈希实现hash table，hash table表格中的元素为桶，每个桶中包含了哈希到这个桶中的节点，节点定义如下： template struct __hashtable_node { __hashtable_node *next; Value val; }; 6.1 hashtable的迭代器 template class ExtractKey, class EqualKey, class Alloc> struct __hashtable_iterator { typedef hashtable hashtable; typedef __hashtable_iterator ExtractKey, EqualKey, Alloc> iterator; typedef __hashtable_const_iterator ExtractKey, EqualKey, Alloc> const_iterator; typedef __hashtable_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 __hashtable_iterator __hashtable_iterator { 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 inline __hashtable_iterator __hashtable_iterator { iterator tmp = *this; ++*this; return tmp; } hashtable的迭代器没有后退操作，hashtable也没有定义所谓的逆向迭代器 6.2 hashtable的实现 SGI STL中hashtable的定义 template class ExtractKey, class EqualKey, class Alloc = alloc> class hashtable; ... template 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 typedef simple_alloc 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; } 6.3 hashtable操作的实现 节点操作 涉及内存管理 创建节点：new_node销毁节点：delete_node hashtable操作 创建满足n个bucket的hashtable：hashtable initialize_buckets 插入节点 不允许键值重复： insert_unique 判断和重新分配bucket：resizeinsert_unique_noresize 允许键值重复：insert_equal 判断和重新分配bucket：resize（同上）insert_equal_noresize 哈希映射寻找bucket 接受实值和buckets个数：bkt_num只接受实值：bkt_num只接受键值：bkt_num_key接受键值和buckets个数：bkt_num_key 清除：clear复制：copy_from查找元素：find统计元素个数：count 6.4 hash functions 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 { size_t operator()(const char* s) const { return __stl_hash_string(s); } }; __STL_TEMPLATE_NULL struct hash { size_t operator()(const char* s) const { return __stl_hash_string(s); } }; __STL_TEMPLATE_NULL struct hash size_t operator()(char x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(unsigned char x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(unsigned char x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(short x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(unsigned short x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(int x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(unsigned int x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(long x) const { return x; } }; __STL_TEMPLATE_NULL struct hash size_t operator()(unsigned long x) const { return x; } }; 7.hash_set SGI STL中hash_set的定义 hash_set以hashtable为底层机制，由于hash_set所供应的操作接口hashtable都提供了，所以几乎所有的hash_set操作行为，都只是转调用hashtable的操作行为而已 8.hash_map SGI STL中hash_map的定义 hash_map以hashtable为底层机制，由于hash_map所供应的操作接口hashtable都提供了，所以几乎所有的hash_map操作行为，都只是转调用hashtable的操作行为而已 9.hash_multiset SGI STL中hash_multiset的定义 hash_multiset和hash_set实现上的唯一差别在于，前者的元素插入操作采用底层机制hashtable的insert_equal()，后者则是采用insert_unique() 10.hash_multimap SGI STL中hash_multimap的定义 hash_multimap和hash_map实现上的唯一差别在于，前者的元素插入操作采用底层机制hashtable的insert_equal()，后者则是采用insert_unique() 六.算法 1.区间拷贝 1.1 copy SGI STL的copy算法用尽各种办法，包括函数重载、类型特性、偏特化等编程技巧来尽可能地加强效率 泛化版本 copy 泛化版本：__copy_dispatch 版本一：__copy版本二：__copy __copy_d 偏特化版本：__copy_dispatch __copy_t（指针所指对象具有trivial…）__copy_t（指针所指对象具有non-trivial…） 偏特化版本：__copy_dispatch __copy_t（同上） 特化版本 copy（针对const char*）copy（针对const wchar_t*） 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 1.2 copy_backward copy_backward将[first,last)区间的每一个元素，以逆行的方向复制到以result-1为起点，方向亦为逆行的区间上。换句话说，copy_backward算法会执行赋值操作*(result-1) = *(last - 1),*(result-2) = *(last - 2),...以此类推，返回一个迭代器：result-(last-first) copy_backward所接受的迭代器必须是BidirectionalIterators，才能够“倒行逆施” 2.set相关算法 这部分介绍的4个算法所接受的set，必须是有序区间，元素可能重复。换句话说，它们可以接受STL的set/multiset容器作为输入区间。hash_set/hash_multiset两种容器，以hashtable为底层机制，其内的元素并未呈现排序状态，所以虽然名称中也有set字样，却不可应用于这里的4个算法 2.1 set_union 这个函数求集合s1和s2的并集。s1和s2及其并集都是以排序区间表示。函数返回一个迭代器，指向输出区间的尾端 s1和s2内的每个元素都不需要唯一，因此，如果某个值在s1出现n此，在s2出现m次，那么该值在输出区间中会出现max(m,n)次 SGI SLT中set_union的实现，操作示例如下： 2.2 set_intersection 这个函数求集合s1和s2的交集。s1和s2及其交集都是以排序区间表示。函数返回一个迭代器，指向输出区间的尾端 SGI SLT中set_intersection的实现，操作示例如下： 2.3 set_difference 该函数计算两个集合的差集，即当s1为第一个参数，s2为第二个参数时，计算s1-s2。内含“出现于s1但不出现于s2”的每一个元素。s1和s2及其差集都是以排序区间表示。函数返回一个迭代器，指向输出区间的尾端 SGI SLT中set_difference的实现，操作示例如下： 2.4 set_symmetric_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的实现，操作示例如下： 3.排序sort 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时，继续递归排序 __final_insertion_sort（此时，已经基本有序） 当数组区间大于__stl_threshold(16)时 对前面大小为16的区间调用：__insertion_sort __linear_insert __unguarded_linear_insert 对后面的区间调用：__unguarded_insertion_sort __unguarded_insertion_sort_aux __unguarded_linear_insert 当数组区间小于等于__stl_threshold(16)时 调用：__insertion_sort（同上） 4.其它算法 相对简单的算法： 查找 adjacent_find（查找第一对满足条件的相邻元素，返回第一个元素的迭代器） 版本一版本二 findfind_if（可以指定操作）find_end（在区间一中查找区间二最后一次出现的位置） 版本一 单向迭代器版：__find_end双向迭代器版：__find_end 版本二（可以指定操作） 单向迭代器版：__find_end双向迭代器版：__find_end find_first_of（在区间一中查找区间二中任一元素第一次出现点） 版本一版本二（允许指定操作） max_element 版本一版本二（允许指定比较操作） min_element 版本一版本二（允许指定比较操作） search（在序列一的区间中查找序列二的首次出现点） 版本一版本二（允许指定操作） search_n（在序列一中查找连续n个满足条件的元素的起点） 版本一版本二 统计 count（统计等于某值的个数） 版本一版本二（计数变量作为参数传入） count_if（可以指定操作） 版本一版本二（计数变量作为参数传入） 单区间操作 for_each（将仿函数f施行于指定区间，f不允许修改元素，因为迭代器类型是InputIterators）generate（将仿函数gen的运算结果赋值到指定区间的所有元素上）generate_n（将仿函数gen的运算结果赋值到迭代器first开始的n个元素上）partition（不保证元素的原始相对位置） stable_partition（保留元素的原始相对位置）remove（区间大小并不发送变化，需要移除的元素会被后面的覆盖，区间尾部会有残余，返回指向第一个残余元素的迭代器） remove_copy remove_if remove_copy_if replace replace_copy repalce_if replace_copy_if reverse 迭代器为双向迭代器：__reverse迭代器为随机迭代器：__reverse reverse_copy rotate（将[first,middle)和[middle,last)的元素互换，middle所指元素将成为容器第一个元素） 迭代器为向前迭代器：__rotate 迭代器为双向迭代器：__rotate 迭代器为随机迭代器：__rotate __gcd__rotate_cycle rotate_copy transform 版本一版本二 unique（移除相邻的重复元素，必须相邻，所以要先排序。和remove一样，会有残余） 版本一版本二（允许指定操作） unique_copy 迭代器为向前迭代器：__unique_copy迭代器为输出迭代器(不能读)：__unique_copy __unique_copy 双区间操作 includes（判断区间二是否“涵盖于”区间一，两个区间必须有序） 版本一版本二 merged（合并两个区间，置于另一段空间，返回指向结果序列最后元素下一位位置的迭代器） 版本一版本二（允许指定操作） 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 单区间操作 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 版本二（运行指定比较操作） __partial_sort partial_sort_copy 版本一版本二（允许指定比较操作） inplace_merge inplace_merge_aux 有额外的缓冲区辅助：__merge_adaptive 当序列1较小，且缓冲区足够容纳序列1 当序列2较小，且缓冲区足够容纳序列2 当缓冲区不足以容纳序列1和序列2 __rotate_adaptive nth_element __nth_element 七.仿函数 在STL标准规格定案后，仿函数采用函数对象作为新名称 函数指针的缺点在于：不能满足STL对抽象性的要求，也不能满足软件积木的要求——函数指针无法和STL其它组件（如适配器）搭配，产生更灵活的变化 就实现而言，仿函数其实就是一个“行为类似函数”的对象，为了能够“行为类似函数”，其类别定义中必须自定义function call运算子。拥有这样的运算子后，就可以在仿函数的对象后面加上一对小括号，以此调用仿函数所定义的operator() STL仿函数的分类，若以操作数的个数划分，可分为一元和二元仿函数，若以功能划分，可分为算术运算，关系运算，逻辑运算三大类 任何应用程序欲使用STL內建的仿函数，都必须含入头文件，SGI则将它们实际定义于 1.仿函数的相应类型 STL仿函数应该有能力被函数适配器修饰，彼此像积木一样地串接。为了拥有适配能力，每一个仿函数必须定义自己的相应类型。就像迭代器如果要融入整个STL大家庭，也必须依照规定定义自己的5个相应类型一样。这些相应类型是为了让适配器能够取出，获得仿函数的某些信息 仿函数的相应类型主要用来表现函数参数类型和传回值类型 为方便起见， 1.1 unary_function unary_function用来呈现一元函数的参数类型和返回值类型： template struct unary_function { typedef Arg argument_type; typedef Result result_type; }; 1.2 binary_function binary_function用来呈现二元函数的第一参数类型，第二参数类型，以及返回值类型： template struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; }; 2.算术类仿函数 以下为STL内建的“算术类仿函数”，除了“否定”运算为一元运算，其它都是二元运算： 加法：plus template struct plus : public binary_function T operator()(const T& x, const T& y) const { return x + y; } }; template struct minus : public binary_function T operator()(const T& x, const T& y) const { return x - y; } }; template struct multiplies : public binary_function T operator()(const T& x, const T& y) const { return x * y; } }; template struct divides : public binary_function T operator()(const T& x, const T& y) const { return x / y; } }; template struct modulus : public binary_function T operator()(const T& x, const T& y) const { return x % y; } }; template struct negate : public unary_function T operator()(const T& x) const { return -x; } }; 3.关系运算类仿函数 以下为STL内建的“关系运算类仿函数”，每一个都是二元运算： 等于：equal_to template struct equal_to : public binary_function bool operator()(const T& x, const T& y) const { return x == y; } }; template struct not_equal_to : public binary_function bool operator()(const T& x, const T& y) const { return x != y; } }; template struct greater : public binary_function bool operator()(const T& x, const T& y) const { return x > y; } }; template struct less : public binary_function bool operator()(const T& x, const T& y) const { return x < y; } }; template struct greater_equal : public binary_function bool operator()(const T& x, const T& y) const { return x >= y; } }; template struct less_equal : public binary_function bool operator()(const T& x, const T& y) const { return x <= y; } }; 4.逻辑运算类仿函数 以下为STL内建的“逻辑运算类仿函数”，其中And和Or是二元运算，Not为一元运算： 逻辑运算 And：logical_and template struct logical_and : public binary_function bool operator()(const T& x, const T& y) const { return x && y; } }; template struct logical_or : public binary_function bool operator()(const T& x, const T& y) const { return x || y; } }; template struct logical_not : public unary_function bool operator()(const T& x) const { return !x; } }; 5.证同，选择与投射 C++标准并未涵盖这里介绍的任何一个仿函数，不过它们常常存在于各个实现品中作为内部运用。在SGI STL中的实现如下： //证同函数。任何数值通过此函数后，不会有任何改变 //此函数运用于 //那是因为set元素的键值即实值，所以采用identity template struct identity : public unary_function const T& operator()(const T& x) const { return x; } }; //选择函数：接受一个pair，传回其第一元素 //此函数运用于 //由于map系以pair元素的第一元素为其键值，所以采用select1st template struct select1st : public unary_function const typename Pair::first_type& operator()(const Pair& x) const { return x.first; } }; //选择函数：接受一个pair,传回其第二元素 //SGI STL并未运用此函数 template struct select2nd : public unary_function const typename Pair::second_type& operator()(const Pair& x) const { return x.second; } }; //投射函数：传回其第一参数，忽略第二参数 template struct project1st : public binary_function Arg1 operator()(const Arg1& x, const Arg2&) const { return x; } }; //投射函数：传回第二参数，忽略第一参数 template struct project2nd : public binary_function Arg2 operator()(const Arg1&, const Arg2& y) const { return y; } }; 八.适配器 适配器在STL组件的灵活组合运用功能上，扮演着轴承、转换器的角色 STL所提供的各种适配器中：1）改变仿函数接口者，称为函数适配器；2）改变容器接口者，称为容器适配器；3）改变迭代器接口者，称为迭代器适配器 1.容器适配器 STL提供两个容器适配器：queue和stack，它们修饰deque的接口而生成新的容器风貌 stack的底层由deque构成。stack封锁住了所有的deque对外接口，只开放符合stack原则的几个函数 queue的底层也由deque构成。queue封锁住了所有的deque对外接口，只开放符合queue原则的几个函数 stack和queue的具体详见第四章 2.迭代器适配器 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将它们实际定义于 2.1 insert iterators insert iterators实现的主要观念是：每一个insert iterators内部都维护有一个容器（必须由用户指定）；容器当然有自己的迭代器，于是，当客户端对insert iterators做赋值操作时，就在insert iterators中被转为对该容器的迭代器做插入操作（也就是说，调用底层容器的push_front()或push_back()或insert()） 其它迭代器惯常的行为如：operator++、operator++(int)、operator*都被关闭，更没有提供operator–或operator–(int)或operator->等功能，因此类型被定义为output_iterator_tag 2.1.1 back_insert_iterator template 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 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 back_insert_iterator back_insert_iterator }; //这是一个辅助函数，帮助我们方便使用back_insert_iterator template inline back_insert_iterator return back_insert_iterator } 2.1.2 front_insert_iterator template 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 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 front_insert_iterator front_insert_iterator }; //这是一个辅助函数，帮助我们方便使用front_insert_iterator template inline front_insert_iterator return front_insert_iterator } 2.1.3 insert_iterator template 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 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 insert_iterator insert_iterator }; //这是一个辅助函数，帮助我们方便使用insert_iterator //和前2个插入迭代器不容，这里还需额外传入一个底层容器的迭代器 template inline insert_iterator typedef typename Container::iterator iter; return insert_iterator } 2.2 reverse iterators 可以通过一个双向顺序容器调用rbegin()，和rend()来获取相应的逆向迭代器。只要双向顺序容器提供了begin(),end()，它的rbegin()和rend()就如同下面的形式。单向顺序容器slist不可使用reserve iterators。有些容器如stack、queue、priority_queue并不提供begin()，end()，当然也就没有rbegin()和rend()： template class vector { public: typedef T value_type; typedef value_type* iterator; //容器迭代器类型 typedef reverse_iterator reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } ... }; template class list { public: typedef __list_iterator typedef reverse_iterator reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } ... }; template class deque { public: typedef __deque_iterator typedef 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 reverse_iterator { protected: Iterator current; //对应的正向迭代器 public: //迭代器的5种相应类型都和其对应的正向迭代器相同 typedef typename iterator_traits iterator_category; typedef typename iterator_traits value_type; typedef typename iterator_traits difference_type; typedef typename iterator_traits pointer; typedef typename iterator_traits reference; typedef Iterator iterator_type; //代表正向迭代器 typedef reverse_iterator 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); } }; 2.3 iostream iterators 2.3.1 istream_iterator 所谓绑定一个istream object，其实就是在istream iterator内部维护一个istream member，客户端对于这个迭代器所做的operator++操作，会被引导调用迭代器内部所含的那个istream member的输入操作(operator>>)。这个迭代器是个input iterator，不具备operator– //此版本是旧有的HP规格，未符合标准接口：istream_iterator //然而一般使用input iterators时都只使用第一个template参数、此时以下仍适用 //SGI STL 3.3已实现出符合标准接口的istream_iterator，做法与本版大同小异 template class istream_iterator { friend bool operator== __STL_NULL_TMPL_ARGS (const istream_iterator const istream_iterator 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 // istream_iterator reference operator*() const { return value; } pointer operator->() const { return &(operator*()); } //迭代器前进一个位置，就代表要读取一次数据 istream_iterator read(); return *this; } istream_iterator istream_iterator read(); return tmp; } }; 下图展示了copy()和istream_iterator共同合作的例子： 2.3.2 ostream_iterator 所谓绑定一个ostream object，其实就是在oßstream iterator内部维护一个ostream member，客户端对于这个迭代器所做的operator=操作，会被引导调用迭代器内部所含的那个ostream member的输出操作(operator<<)。这个迭代器是个Onput iterator //此版本是旧有的HP规格，未符合标准接口：istream_iterator //然而一般使用onput iterators时都只使用第一个template参数、此时以下仍适用 //SGI STL 3.3已实现出符合标准接口的ostream_iterator，做法与本版大同小异 template 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 *stream << value; //关键，输出数值 if (string) *stream << string; //如果间隔符号不为空，输出间隔符号 return *this; } ostream_iterator ostream_iterator ostream_iterator }; 下图展示了copy()和ostream_iterator共同合作的例子： 3.函数适配器 函数适配器(functor adapters，亦即function adapters)是所有适配器中数量最庞大的一个族群，其适配灵活度也是前2者所不能及，可以适配、适配、再适配 函数适配器的价值：通过它们之间的绑定、组合、修饰能力，几乎可以无限制地创造出各种可能的表达式，搭配STL算法一起演出。下表是STL函数适配器一览表： 适配操作包括： bind、negate、compose对一般函数或成员函数的修饰 C++标准规定，这些适配器的接口可由 注意，所有期望获得适配能力的组件，本身都必须是可适配的。换句话说，1）一元仿函数必须继承自unary_function；2）二元仿函数必须继承自binary_function；3）成员函数必须以mem_fun处理过；4）一般函数必须以ptr_fun处理过。一个未经ptr_fun处理过的一般函数，虽然也能以函数指针的形式传给STL算法使用，却无法拥有任何适配能力 下图是count_if()和bind2nd(less(),12)的搭配实例； 3.1 not1和not2 3.1.1 not1 //以下适配器用来表示某个 "可适配 predicate" 的逻辑负值 template class unary_negate : public unary_function 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 inline unary_negate return unary_negate } 3.1.2 not2 //以下适配器用来表示某个 "可适配 binary predicate" 的逻辑负值 template class binary_negate : public binary_function 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 inline binary_negate return binary_negate } 3.2 bind1st和bind2st 3.2.1 bind1st //以下适配器用来表示某个 "可适配 binary function" 转换为 “unary function” template class binder1st : public unary_function 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 inline binder1st //先把x转型为op的第一参数类型 typedef typename Operation::first_argument_type arg1_type; return binder1st } 3.2.2 bind2st //以下适配器用来表示某个 "可适配 binary function" 转换为 “unary function” template class binder2nd : public unary_function 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 inline binder2nd //先把x转型为op的第一参数类型 typedef typename Operation::second_argument_type arg2_type; return binder2nd } 3.3 compose1和compose2 3.3.1 compose1 //已知两个 "可适配 unary function" f(),g()，以下适配器用来产生一个h()， //使 h(x) = f(g(x)) template class unary_compose : public unary_function 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 inline unary_compose const Operation2& op2) { return unary_compose } 3.3.2 compose2 //已知一个 “可适配 binary function” f 和 两个 "可适配 unary function" g1,g2， //以下适配器用来产生一个h，使 h(x) = f(g1(x),g2(x)) template class binary_compose : public unary_function 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 inline binary_compose compose2(const Operation1& op1, const Operation2& op2, const Operation3& op3) { return binary_compose } 3.4 用于函数指针的ptr_fun //以下适配器其实就是把一个一元函数指针包起来 //当仿函数被动调用时，就调用该函数指针 template class pointer_to_unary_function : public unary_function 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 inline pointer_to_unary_function return pointer_to_unary_function } //以下适配器其实就是把一个二元函数指针包起来 //当仿函数被动调用时，就调用该函数指针 template class pointer_to_binary_function : public binary_function 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 inline pointer_to_binary_function ptr_fun(Result (*x)(Arg1, Arg2)) { return pointer_to_binary_function } 3.5 用于成员函数指针的mem_fun和mem_fun_ref 假设Shape是一个继承体系中的基类，并且具有虚函数display()，有一个vector 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 mem_fun_t : public unary_function 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 const_mem_fun_t : public unary_function 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 mem_fun_ref_t : public unary_function 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 const_mem_fun_ref_t : public unary_function 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 mem_fun1_t : public binary_function 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 const_mem_fun1_t : public binary_function 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 mem_fun1_ref_t : public binary_function 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 const_mem_fun1_ref_t : public binary_function 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 inline mem_fun_t return mem_fun_t } template inline const_mem_fun_t return const_mem_fun_t } template inline mem_fun_ref_t return mem_fun_ref_t } template inline const_mem_fun_ref_t return const_mem_fun_ref_t } template inline mem_fun1_t return mem_fun1_t } template inline const_mem_fun1_t return const_mem_fun1_t } template inline mem_fun1_ref_t return mem_fun1_ref_t } template inline const_mem_fun1_ref_t return const_mem_fun1_ref_t }
友情链接：
Copyright © 2022 战国无双-策略国战活动站 All Rights Reserved.