重返C++，先从STL入手。这里会记录一些重点。

follow 侯捷大师的《STL源码剖析》

声明

博客大部分内容都来源于《STL源码剖析》这本书（copy了个人认为重要的部分，包括代码），对于一些不容易明白的地方会查找其他资料进行补充。

由于电子的文字版只有前四章，因此后面的章节只能截扫描版的图。由于cdn加速不稳定，图片可能要用魔法才能加载(′⌒`)

概念与基础

STL六大组件

1.容器（containers）：各种数据结构，如vector, list, deque, set, map，用来存放数据。从实作的角度看，STL 容器是一种 class template。就体积而言，这一部份很像冰山在海面下的比率。

2.算法（algorithms）：各种常用算法如sort, search, copy, erase…。从实作的角度看，STL 算法是一种 function template。

3.迭代器（iterators）：扮演容器与算法之间的胶着剂，是所谓的「泛型指标」。共有五种类型，以及其它衍生变化。从实作的角度看，迭代器是一种将operator*, operator->, operator++, operator–等指标相关操作予以多载化的 class template。所有STL容器都附带有自己专属的迭代器—是的，只有容器设计者才知道如何巡访自己的元素。原生指标（native pointer）也是一种迭代器。

4.仿函式（functors）：行为类似函式，可做为算法的某种策略（policy）。从实作的角度看，仿函式是一种重载了 operator()的 class 或class template。一般函式指标可视为狭义的仿函式。

5.配接器（adapters）：一种用来修饰容器（containers）或仿函式（functors）或迭代器（iterators）接口的东西。例如 STL 提供的 queue 和stack，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完全借重 deque，所有动作都由底层的 deque供应。改变functor接口者，称为function adapter，改变container接口者，称为container adapter，改变iterator界面者，称为iterator adapter。配接器的实作技术很难一言以蔽之，必须逐一分析。

6.配置器（allocators）：负责空间配置与管理，详见第 2 章。从实作的角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的 class template。

STL六大组件的交互关系：Container透过Allocator取得数据储存空间，Algorithm透过Iterator存取Container内容，Functor可以协助 Algorithm完成不同的策略变化，Adapter可以修饰或套接 Functor。

SGI STL文件分布与简介

概略可分为五组：

C++标准规范下的 C 头文件（无扩展名），例如cstdio, cstdlib, cstring…
C++标准链接库中不属于 STL范畴者，例如 stream, string…相关文件。
STL标准头文件（无扩展名），例如vector, deque, list, map, algorithm, functional…
C++ Standard 定案前，HP 所规范的 STL 头文件，例如vector.h, deque.h, list.h, map.h, algo.h, function.h…
SGI STL 内部文件（STL 真正实作于此），例如stl_vector.h, stl_deque.h, stl_list.h, stl_map.h, stl_algo.h, stl_function.h…

SGI STL 的编译器组态设定(configuration)

不同的编译器对C++语言的支持程度不尽相同。做为一个希望具备广泛移植能力的链接库，SGI STL 准备了一个环境组态文件<stl_config.h>，其中定义许多常数，标示某些状态的成立与否。所有 STL 头文件都会直接或间接含入这个组态文件，并以条件式写法，让前处理器（pre-processor）根据各个常数决定取舍哪一段程序码。

<stl_config.h>文件起始处有一份常数定义说明，然后即针对各家不同的编译器以及可能的不同版本，给予常数设定。

这里先介绍<stl_config.h>中的预定义组态配置项：

__STL_STATIC_TEMPLATE_MEMBER_BUG

如果编译器无法处理static member of template classes(模板类静态成员)就定义
__STL_CLASS_PARTIAL_SPECIALIZATION

如果编译器支持 partial specialization of class templates(模板类偏特化)就定义。

偏特化：模板为什么要特化，因为编译器认为，对于特定的类型，如果你能对某一功能更好的实现，那么就该听你的。

模板分为类模板与函数模板，特化分为全特化与偏特化。全特化就是限定死模板实现的具体类型，偏特化就是如果这个模板有多个类型，那么只限定其中的一部分。

使用template定义类时可以使用const *等做特殊设计。
1
2
3
4
5
template <class T1 , class T2>//泛型
struct test{....};

template <class T>
struct test<T*, const T* > {....};//偏特化

__STL_FUNCTION_TMPL_PARTIAL_ORDER

如果编译器支持partial ordering of function templates或者说partial specialization of function templates就定义，可以理解为对函数模板的重载的支持

对于一个函数模板，如果定义了另一个函数模板且函数名相同，会根据template的参数表进行调用，要注意的是，第二个函数模板需要知道参数，可以在函数后面加上例如，max<T,T>或者函数之前声明类struct<T,T>。

template<typename T1, typename T2>
struct Bar
{
 void operator()(T1 const& t1, T2 const& t2)
 {
    std::cerr << "In Bar<T1, T2>(" << t1 << ", " << t2 << ")\n";
 }
};
template<typename T2>
struct Bar<int, T2>//声明<T1,T2>
{
 void operator()(int t1, T2 const& t2)
 {
    std::cerr << "In Bar<int, T2>(" << t1 << ", " << t2 << ")\n";
 }
};
/* 下列代码也可以
template<typename T2>
void operator()<int, T2>(int t1, T2 const& t2)
 {
    std::cerr << "In Bar<int, T2>(" << t1 << ", " << t2 << ")\n";
 }
 */
template<typename T1, typename T2>
void bar(T1 const& t1, T2 const& t2)
{
   Bar<T1, T2> b;
   b(t1, t2);
}

__STL_MEMBER_TEMPLATES

如果编译器支持template members of classes 就定义，看英文就知道，模板类中嵌套模板

template <class T>
class vector{
public:
	template <class TT> 
	void test(TT a,TT b) {
		cout << a << ' ' << b << endl; 
	}
};

__STL_LIMITED_DEFAULT_TEMPLAES

用到前一个模板的模板形参的某一个具现体作为当前模板的模板形参的默认值
1
2
template <class T, class Se = queue<T> >
class test {....};
__STL_NON_TYPE_TMPL_PARAM_BUG

测试类模板是否使用非类型模板参数（non-type template parameters），或着是否template 可以使用无参数类型模板
1
2
3
4
5
6
7
8
9
10
template<int size>
class CTest
{
int m_data[size];
};

void main()
{
CTest<10> obj;
}
非类型模板：非类型模板参数(nontype template parameters), 可以使用整型类型(integral type)，指针(pointer)或者是引用(reference);绑定非类型整数形参(nontype integral parameter) 的实参(argument) 必须是常量表达式(constant expression, constexpr)；不能把普通的局部对象或者动态对象 绑定指针或引用的非类型形参, 可以使用全局类型进行绑定。

__STL_NULL_TMPL_ARGS

友元约束模板：可以依据之前对非友元函数的定义来对友元函数进行约束

template<class T,class Sequence>
class stack;
 
template<class T,class Sequence>
bool operator==(const stack<T,Sequence>& x,const stack<T,Sequence>& y);

template<class T,class Sequence=deque<T> >
class stack
{
    //friend bool operator==<T>(const stack<T>&,const stack<T>&);
    //下面的都是等价于上面的
    //friend bool operator== <T>(const stack&,const stack&);
    friend bool operator== <>(const stack&,const stack&);
    Sequence c;
};
 template<class T,class Sequence>
bool operator==(const stack<T,Sequence> &x,const stack<T,Sequence> &y)
{
    return cout<<"operator=="<<'\t';
}
int main()
{
    stack<int> x;
    stack<int> y;
    cout<<(x==y)<<endl;
    
    stack<char> y1;
//    cout<<(x==y1)<<endl;
}

__STL_TEMPLATE_NULL

即 template <> 显式的模板特化，对template进行具体化，在定义参数时就可以使用具体化的定义。函数同理。

template<class T> struct test {....};
template<> struct test<int>{.....};

template<class Any>
void swap(Any &,Any &b){......;} 
template <> void swap<int>(int &,int &){......;}

以下是 GNU C++ 2.91.57 <stl_config.h>的完整内容：

#ifndef __STL_CONFIG_H 
# define __STL_CONFIG_H 
//文件所做的事情：
// (1) 如果编译器没有定义 bool, true, false，就定义它们
// (2) 如果编译器的标准链接库᳾支持 drand48()函式，就定义 __STL_NO_DRAND48 
// (3) 如果编译器无法处理 static members of template classes，就定义
// 		__STL_STATIC_TEMPLATE_MEMBER_BUG
// (4) 如果编译器᳾支持关键词 typename，就将'typename'定义为一个 null macro. 
// (5) 如果编译器支持 partial specialization of class templates，就定义
// 		__STL_CLASS_PARTIAL_SPECIALIZATION. 
// (6) 如果编译器支持 partial ordering of function templates（亦称为
// 		partial specialization of function templates），就定义
// 		__STL_FUNCTION_TMPL_PARTIAL_ORDER
// (7) 如果编译器允许我们在呼叫一个 function template时可以明白指定其
// 		template arguments，就定义__STL_EXPLICIT_FUNCTION_TMPL_ARGS
// (8) 如果编译器支持 template members of classes，就定义
// 		__STL_MEMBER_TEMPLATES. 
// (9) 如果编译器不支持关键词 explicit，就定义'explicit'为一个 null macro. 
// (10) 如果编译器无法根据前一个 template parameters设定下一个 template 
// 		parameters 的默认值，就定义__STL_LIMITED_DEFAULT_TEMPLATES
// (11) 如果编译器针对 non-type template parameters 执行 function template 
// 		的自变量推导（argument deduction）时有问题，就定义
// 		__STL_NON_TYPE_TMPL_PARAM_BUG. 
// (12) 如果编译器无法支持迭代器的 operator->，就定义
// 		__SGI_STL_NO_ARROW_OPERATOR
// (13) 如果编译器（在你所选择的模式中）支持 exceptions，就定义
// 		__STL_USE_EXCEPTIONS
// (14) 定义__STL_USE_NAMESPACES 可使我们自动获得 using std::list;之类的叙句
// (15) 如果本链接库由 SGI编译器来编译，而且使用者并未选择 pthreads 
// 		或其它 threads，就定义__STL_SGI_THREADS. 
// (16) 如果ᴀ链接库由一个 WIN32 编译器编译，并且在多绪模式下，就定义
// 		__STL_WIN32THREADS
// (17) 适当地定义与 namespace相关的 macros 如 __STD, __STL_BEGIN_NAMESPACE。
// (18) 适当地定义 exception 相关的 macros 如 __STL_TRY, __STL_UNWIND。
// (19) 根据__STL_ASSERTIONS是否定义，将 __stl_assert 定义为一个
// 		测试动作或一个 null macro。
#ifdef _PTHREADS 
# define __STL_PTHREADS 
#endif 
# if defined(__sgi) && !defined(__GNUC__) 
//使用 SGI STL但却不是使用 GNU C++ 
# if !defined(_BOOL) //没有BOOL就定义
# define __STL_NEED_BOOL 
# endif 
# if !defined(_TYPENAME_IS_KEYWORD) 
# define __STL_NEED_TYPENAME 
# endif 
# ifdef _PARTIAL_SPECIALIZATION_OF_CLASS_TEMPLATES 
# define __STL_CLASS_PARTIAL_SPECIALIZATION 
# endif 
# ifdef _MEMBER_TEMPLATES 
# define __STL_MEMBER_TEMPLATES 
# endif 
# if !defined(_EXPLICIT_IS_KEYWORD) 
# define __STL_NEED_EXPLICIT 
# endif 
# ifdef __EXCEPTIONS 
# define __STL_USE_EXCEPTIONS 
# endif 
# if (_COMPILER_VERSION >= 721) && defined(_NAMESPACES)
# define __STL_USE_NAMESPACES 
# endif 
# if !defined(_NOTHREADS) && !defined(__STL_PTHREADS) 
# define __STL_SGI_THREADS 
# endif 
# endif 
# ifdef__GNUC__
# include <_G_config.h> 
# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) 
# define __STL_STATIC_TEMPLATE_MEMBER_BUG 
# define __STL_NEED_TYPENAME 
# define __STL_NEED_EXPLICIT 
# else // 这里可看出 GNUC 2.8+ 的能力
# define __STL_CLASS_PARTIAL_SPECIALIZATION
# define __STL_FUNCTION_TMPL_PARTIAL_ORDER
# define __STL_EXPLICIT_FUNCTION_TMPL_ARGS
# define __STL_MEMBER_TEMPLATES
# endif 
/* glibc pre 2.0 is very buggy. We have to disable thread for it. 
 It should be upgraded to glibc 2.0 or later. */ 
# if !defined(_NOTHREADS) && __GLIBC__ >= 2 && defined(_G_USING_THUNKS) 
# define __STL_PTHREADS 
# endif 
# ifdef __EXCEPTIONS 
# define __STL_USE_EXCEPTIONS 
# endif 
# endif 
# if defined(__SUNPRO_CC) 
# define __STL_NEED_BOOL 
# define __STL_NEED_TYPENAME 
# define __STL_NEED_EXPLICIT 
# define __STL_USE_EXCEPTIONS 
# endif 
# if defined(__COMO__) 
# define __STL_MEMBER_TEMPLATES 
# define __STL_CLASS_PARTIAL_SPECIALIZATION 
# define __STL_USE_EXCEPTIONS 
# define __STL_USE_NAMESPACES 
# endif 
//侯捷注：VC6的版ᴀ号码是 1200 
# if defined(_MSC_VER) 
# if _MSC_VER > 1000 
# include <yvals.h> 
# else 
//此文件在 MSDEV\VC98\INCLUDE 
# define __STL_NEED_BOOL
# endif 
# define __STL_NO_DRAND48 
# define __STL_NEED_TYPENAME 
# if _MSC_VER < 1100 
# define __STL_NEED_EXPLICIT 
# endif 
# define __STL_NON_TYPE_TMPL_PARAM_BUG
# define __SGI_STL_NO_ARROW_OPERATOR
# ifdef _CPPUNWIND 
# define __STL_USE_EXCEPTIONS 
# endif 
# ifdef _MT 
# define __STL_WIN32THREADS 
# endif 
# endif 
//侯捷注：Inprise Borland C++builder也定义有此常数。
// C++Builder 的表现岂有如下所示这般差劲？
# if defined(__BORLANDC__) 
# define __STL_NO_DRAND48 
# define __STL_NEED_TYPENAME 
# define __STL_LIMITED_DEFAULT_TEMPLATES
# define __SGI_STL_NO_ARROW_OPERATOR
# define __STL_NON_TYPE_TMPL_PARAM_BUG
# ifdef _CPPUNWIND 
# define __STL_USE_EXCEPTIONS 
# endif 
# ifdef __MT__ 
# define __STL_WIN32THREADS 
# endif 
# endif 
# if defined(__STL_NEED_BOOL) 
 typedef int bool; 
# define true 1 
# define false 0 
# endif 
# ifdef __STL_NEED_TYPENAME 
23 
# define typename//侯捷：难道不该 #define typename class 吗？
# endif 
# ifdef __STL_NEED_EXPLICIT 
# define explicit
# endif 
# ifdef__STL_EXPLICIT_FUNCTION_TMPL_ARGS
# define __STL_NULL_TMPL_ARGS<> 
# else
# define __STL_NULL_TMPL_ARGS 
# endif 
# ifdef__STL_CLASS_PARTIAL_SPECIALIZATION
# define __STL_TEMPLATE_NULLtemplate<> 
# else 
# define __STL_TEMPLATE_NULL 
# endif 
// __STL_NO_NAMESPACES is a hook so that users can disable namespaces 
// without having to edit library headers. 
# if defined(__STL_USE_NAMESPACES) && !defined(__STL_NO_NAMESPACES) 
# define __STD std 
# define __STL_BEGIN_NAMESPACE namespacestd { 
# define __STL_END_NAMESPACE } 
# define __STL_USE_NAMESPACE_FOR_RELOPS 
# define __STL_BEGIN_RELOPS_NAMESPACE namespace std { 
# define __STL_END_RELOPS_NAMESPACE } 
# define __STD_RELOPS std 
# else 
# define __STD 
# define __STL_BEGIN_NAMESPACE 
# define __STL_END_NAMESPACE 
# undef __STL_USE_NAMESPACE_FOR_RELOPS 
# define __STL_BEGIN_RELOPS_NAMESPACE 
# define __STL_END_RELOPS_NAMESPACE 
# define __STD_RELOPS 
# endif 
# ifdef __STL_USE_EXCEPTIONS 
# define __STL_TRY try 
# define __STL_CATCH_ALL catch(...) 
# define __STL_RETHROWthrow 
# define __STL_NOTHROWthrow() 
# define __STL_UNWIND(action) catch(...) { action; throw; } 
# else 
# define __STL_TRY 
# define __STL_CATCH_ALL if (false) 
# define __STL_RETHROW 
# define __STL_NOTHROW 
# define __STL_UNWIND(action) 
# endif 
#ifdef __STL_ASSERTIONS 
# include <stdio.h> 
# define __stl_assert(expr) \ 
 if (!(expr)) {fprintf(stderr, "%s:%d STL assertion failure: %s\n", \ 
 __FILE__, __LINE__,# expr);abort(); }
#else 
# define __stl_assert(expr) 
#endif 
#endif /* __STL_CONFIG_H */ 
// Local Variables: 
// mode:C++ 
// End:

下面这个小程序，用来测试 GCC 的常数设定：

// file: 1config.cpp 
// test configurations defined in <stl_config.h> 
#include <vector> // which included <stl_algobase.h>, 
// and then <stl_config.h> 
#include <iostream> 
using namespace std; 
int main() 
{ 
# if defined(__sgi) 
 cout << "__sgi" << endl; // none! 
# endif 
# if defined(__GNUC__) 
 cout << "__GNUC__" << endl; // __GNUC__ 
 cout << __GNUC__ << ' ' << __GNUC_MINOR__ << endl; // 2 91 
 // cout << __GLIBC__ << endl; // __GLIBC__ undeclared 
# endif 
// case 2 
#ifdef __STL_NO_DRAND48 
 cout << "__STL_NO_DRAND48 defined" << endl; 
#else 
 cout << "__STL_NO_DRAND48 undefined" << endl; 
#endif 
// case 3 
#ifdef __STL_STATIC_TEMPLATE_MEMBER_BUG 
 cout << "__STL_STATIC_TEMPLATE_MEMBER_BUG defined" << endl; 
#else 
 cout << "__STL_STATIC_TEMPLATE_MEMBER_BUG undefined" << endl; 
#endif 
// case 5 
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
 cout << "__STL_CLASS_PARTIAL_SPECIALIZATION defined" << endl; 
#else
cout << "__STL_CLASS_PARTIAL_SPECIALIZATION undefined" << endl; 
#endif 
// case 6 
...以下写法类似。详见文件 config.cpp（可自侯捷网站下载）。
}

执行结果如下，由此可窥见 GCC 对各种 C++特性的支持程度：

__GNUC__ 
2 91 
__STL_NO_DRAND48 undefined 
__STL_STATIC_TEMPLATE_MEMBER_BUG undefined 
__STL_CLASS_PARTIAL_SPECIALIZATION defined 
__STL_FUNCTION_TMPL_PARTIAL_ORDER defined 
__STL_EXPLICIT_FUNCTION_TMPL_ARGS defined 
__STL_MEMBER_TEMPLATES defined 
__STL_LIMITED_DEFAULT_TEMPLATES undefined 
__STL_NON_TYPE_TMPL_PARAM_BUG undefined 
__SGI_STL_NO_ARROW_OPERATOR undefined 
__STL_USE_EXCEPTIONS defined 
__STL_USE_NAMESPACES undefined 
__STL_SGI_THREADS undefined 
__STL_WIN32THREADS undefined 
__STL_NO_NAMESPACES undefined 
__STL_NEED_TYPENAME undefined 
__STL_NEED_BOOL undefined 
__STL_NEED_EXPLICIT undefined 
__STL_ASSERTIONS undefined

C++ 一些特殊语法

暂时对象产生与运用

所谓暂时对象（临时对象），就是一种无名对象（unnamed objects）。它的出现如果不在程序员的预期之下（例如任何pass by value动作都会引发copy动作，于是形成一个暂时对象），往往造成效率上的负担。

有时候刻意制造一些暂时对象，却又是使程序干净清爽的技巧。刻意制造暂时对象的方法是，在型别名称之后直接加一对小括号，并可指定初值，例如Shape(3,5)或int(8)，其意义相当于唤起相应的constructor且不指定物件名称 。
STL 中将暂时对象技巧用于仿函式（functor）与算法搭配，例如：

// file: 1config-temporary-object.cpp 
//ᴀ例测试仿函式用于 for_each() 的情形
// vc6[o] cb4[o] gcc[o] 
#include <vector> 
#include <algorithm> 
#include <iostream> 
using namespace std; 
template <typename T> 
class print 
{ 
public: 
 void operator()(const T& elem) // operator() 多载化
 { cout << elem << ' '; } 
}; 
int main() 
{ 
 int ia[6] = { 0,1,2,3,4,5 }; 
 vector< int > iv(ia, ia+6); 
 // print<int>() 是一个暂时对象，不是一个函式呼叫动作
 for_each(iv.begin(), iv.end(), print<int>()); 
}

最后一行便是产生「function template具现体」print的一个暂时对象。这个对象将被传入for_each()之中起作用。当for_each()结束，这个暂时对象也就结束了它的生命。

静态常量整数成员在类内直接初始化

如果 class内含 const static integral data member，那么根据 C++标准规格，可以在class之内直接给予初值。所谓integral泛指所有整数型别，不单只是指int

// file: 1config-inclass-init.cpp 
// test in-class initialization of static const integral members 
// ref. C++ Primer 3/e, p.643 
// vc6[x] cb4[o] gcc[o] 
#include <iostream> 
using namespace std; 
template <typename T> 
class testClass { 
public: // expedient 
static const int _datai = 5; 
static const long _datal = 3L; 
static const char _datac = 'c'; 
}; 
int main() 
{ 
 cout << testClass<int>::_datai << endl; // 5 
 cout << testClass<int>::_datal << endl; // 3 
 cout << testClass<int>::_datac << endl; // c 
}

increment/decrement/dereference运算子

increment / dereference 运算子在迭代器的实作上占有非常重要的地位，因为任何一个迭代器都必须实作出前进（increment,operator++ ）和取值（dereference, operator*）功能，前者还分为前置式（prefix）和后置式（postfix）两种，有非常规律的写法。有些迭代器具备双向移动功能，那么就必须再提供 decrement 运算子（也分前置式和后置式两种）。

前闭后开区间表示法[)

任何STL 算法都需要获得由一对迭代器（泛型指针）所表示的区间，表示操作范围，这一对所表示的区间是前闭后开的，[first ,lasr) 表示 first 到 last - 1。迭代器 last 所指的是「最后一个元素的下一位置」。这种off by one（偏移一格，或说 pass the end）的标示法，带来许多方便。

function call(函数调用) 运算子（operator()）

函式呼叫动作（C++ 语法中的左右小括号）也可以被多载化（重载）。许多STL算法都提供两个版本，一个用于一般状况（例如排序时以递增方式排列），一个用于特殊状况（例如排序时由使用者指定以何种特殊关系进行排列）。像这种情况，需要使用者指定某个条件或某个策略，而条件或策略的背后由一整组动作构成，便需要某种特殊的东西来代表这「一整组动作」。代表「一整组动作」的，当然是函式。过去 C语言时代，欲将函式当做参数传递，唯有透过函式指针（pointer to function，或称 function pointer）才能达成。
但是函数指针使用时有缺点：1. 无法持有自己的状态（所谓区域状态，local states）；2.无法达到组件技术中的可配接性（adaptability）—也就是无法再将某些修饰条件加诸于其上而改变其状态。

STL 算法的特殊版本所接受的所谓「条件」或「策略」或「一整组动作」，都以仿函式形式呈现。所谓仿函式（functor）就是使用起来像函式一样的东西。如果你针对某个 class 进行operator() 多载化，它就成为一个仿函式。

仿函数

仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类。

仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator() 运算符。因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符。

使用：对类进行operator() 进行重载，这个类就是仿函数，可以通过编码使仿函数变为可配接的，对象当做函数名

优点：

仿函数是对象，可以拥有成员函数和成员变量，即仿函数拥有状态(states)
每个仿函数都有自己的类型
仿函数通常比一般函数快（很多信息编译期确定）

仿函数与函数指针相比的优势

仿函数是一个类，是数据以及对数据操作的行为的集合，要成为仿函数必须重载()。函数指针是无法保存数据的，所以仿函数比函数指针功能更强，因为它可以保存数据，这一特性，是函数指针无法比拟的优势。

总结

第一章只是简单介绍了一下stl，包括组件基本内容和组件之间的关系，其实后面具体去了解了也就明白了。而组态部分比较繁杂（个人感觉），是关于编译器对stl支持程度的设定，这部分目前还不知道有什么作用、怎么去学习，因此也就没有具体去看，实际上后面的内容也基本与组态无关。

然后是一些特殊语法，没有讲多细致，后面具体学就行，注意前闭后开这个贯穿全文的条件即可。

空间配置器

以STL 的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作默默付出。但若以STL 的实作角度而言，第一个需要介绍的就是空间配置器，因为整个STL的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放数据。不先掌握空间配置器的原理，难免在观察其它 STL 组件的实作时处处遇到挡路石。

为什么不说allocator是内存配置器而说它是空间配置器呢？因为，空间不一定是内存，空间也可以是磁盘或其它辅助储存媒体。是的，你可以写一个 allocator，直接向硬盘取空间。以下介绍的是 SGI STL 提供的配置器，配置的对象，呃，是的，是内存。

空间配置器的标准接口

//各种type
allocator::value_type 
allocator::pointer 
allocator::const_pointer 
allocator::reference 
allocator::const_reference 
allocator::size_type 
allocator::difference_type
    
allocator::rebind 
//一个巢状的（nested）class template。class rebind<U>拥有唯一成员other，那是一个 typedef，代表allocator<U>。
allocator::allocator() 
//default constructor。//默认构造函数
allocator::allocator(const allocator&) 
//copy constructor。//拷贝构造函数
template <class U>allocator::allocator(const allocator<U>&) 
//泛化的copy constructor。//泛化的拷贝构造
allocator::~allocator() 
//default constructor。//析构函数
pointer allocator::address(reference x) const 
//传回某个对象的地址。算式a.address(x)等同于&x。//返回某个对象的地址
const_pointer allocator::address(const_reference x) const 
//传回某个const对象的地址。算式a.address(x)等同于&x。//返回某个const对象的地址
pointer allocator::allocate(size_type n, cosnt void* = 0) 
//配置空间，足以储存n个T对象。第二自变量是个提示。实作上可能会利用它来增进区域性（locality），或完全忽略之。
void allocator::deallocate(pointer p, size_type n) 
//归还先前配置的空间。
size_type allocator::max_size() const 
//传回可成功配置的最大量。
void allocator::construct(pointer p, const T& x) 
//等同于new(const void*) p) T(x)。//构造T对象
void allocator::destroy(pointer p) 
//等同于p->~T()。//对象T的析构

设计一个简单的空间配置器 JJ::allocator

根据前述的标准接口，我们可以自行完成一个功能简单、接口不怎么齐全的allocator如下：

// file: 2jjalloc.h 
#ifndef _JJALLOC_ 
#define _JJALLOC_
#include <new> // for placement new. 
#include <cstddef> // for ptrdiff_t, size_t 
#include <cstdlib> // for exit() 
#include <climits> // for UINT_MAX 
#include <iostream> // for cerr 
namespace JJ
{ 
    //使用operator new 分配空间
template <class T> 
inline T* _allocate(ptrdiff_t size, T*) { 
 set_new_handler(0); //注释1
 T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));//注释2 
 if (tmp == 0) { 
 cerr << "out of memory" << endl; 
 exit(1); 
 } 
 return tmp; 
} 
    //使用operator delete回收空间
template <class T> 
inline void _deallocate(T* buffer) { 
 ::operator delete(buffer); 
} 
    //在指定内存上构造一个对象
template <class T1, class T2> 
inline void _construct(T1* p, const T2& value) { 
 new(p) T1(value); // placement new. invoke ctor of T1. 
} 
    //析构一个对象
template <class T> 
inline void _destroy(T* ptr) { 
 ptr->~T(); 
} 
    //遵循allocator的标准定义相关结构
template <class T> 
class allocator { 
public: 
 typedef T value_type; 
 typedef T* pointer; 
 typedef const T* const_pointer; 
 typedef T& reference; 
 typedef const T& const_reference; 
 typedef size_t size_type; 
 typedef ptrdiff_tdifference_type; 
// rebind allocator of type U 
 template <class U>
 struct rebind { 
 typedef allocator<U> other; 
 }; 
// hint used for locality. ref.[Austern],p189 
 pointer allocate(size_type n, const void* hint=0) { 
 return _allocate((difference_type)n, (pointer)0); 
 } 
 void deallocate(pointer p, size_type n) { _deallocate(p); } 
 void construct(pointer p, const T& value) { 
_construct(p, value); 
 } 
 void destroy(pointer p) {_destroy(p); } 
 pointer address(reference x) { return (pointer)&x; } 
 const_pointer const_address(const_reference x) { 
 return (const_pointer)&x; 
 } 
 size_type max_size() const { 
 return size_type(UINT_MAX/sizeof(T)); 
 } 
}; 
} // end of namespace JJ 
#endif // _JJALLOC_

注释1：set_new_handler(0);

new_handler，顾名思义就是一个处理程序，当程序向内存的分配请求无法满足时将有两种可能:
1. 抛出异常
2. 设置一个异常处理函数，这就是所谓的new_handler（类似于中断机制，本质上来说就是一个函数指针）
当第二种情况发生以后，我们可以通过new_handler删除无用的内存，以及设置新的new_handler，而这个set_new_handler就是来进行设置的。

set_new_handler(0)主要是为了卸载目前的内存分配异常处理函数，这样一来一旦分配内存失败的话，C++就会强制性抛出std:bad_alloc异常，而不是跑到处理某个异常处理函数去处理。
注释2：*T *tmp=(T*)(::operator new((size_t)(sizesizeof(T)))); **::访问符放到最前面的意思是使用全局版本，这个operator new就得好好说说。

new 的三种形式
- 1.new operator (就是我们常用的new)
- 2.operator new
- 3.placement new
我们在程序中使用new的时候，实际上做了两件事情：
一、申请内存
二、构造对象
简单的理解，new完成了一套比较完备的服务，而operator new，只是申请内存，placement new是在申请的内存中进行构造对象，第2、3中形式就是对new的拆分。

简单应用：

// file: 2jjalloc.cpp 
// VC6[o], BCB4[o], GCC2.9[x]. 
#include "jjalloc.h" 
#include <vector> 
#include <iostream> 
using namespace std; 
int main() 
{ 
 int ia[5] = {0,1,2,3,4}; 
 unsigned int i; 
 vector<int,JJ::allocator<int> > iv(ia, ia+5);
 for(i=0; i<iv.size(); i++) 
 cout << iv[i] << ' '; 
 cout << endl; 
}

具备次配置力（sub-allocation）的 SGI 空间配置器

SGI STL 的配置器与众不同，也与标准规范不同，其名称是alloc而非allocator，而且不接受任何自变量。换句话说如果你要在程序中明白采用SGI 配置器，不能采用标准写法：vector<int,**std::allocator<int>** > iv;// in VC or CB。

必须这么写：vector<int,**std::alloc**<int>> iv; // in GCC

SGI STL allocator未能符合标准规格，这个事实通常不会对我们带来困扰，因为通常我们使用预设的空间配置器，很少需要自行指定配置器名称，而SGI STL的每一个容器都已经指定其预设的空间配置器为alloc。

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

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

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

allocator只是基层内存配置/解放行为（也就是::operator new和::operator delete）的一层薄薄包装，并没有考虑到任何效率上的强化。SGI 另有法宝供本身内部使用。

一般而言，我们所习惯的 C++ 内存配置动作和释放动作是这样：

1
2
3

class Foo { ... }; 
Foo* pf = new Foo;//配置内存，然后建构对象
delete pf; //将对象解构，然后释放内存

这其中的 new算式内含两阶段动作：

(1) 呼叫::operator new配置内存；
(2) 呼叫Foo::Foo()建构对象内容。

delete算式也内含两阶段动作：

(1)呼叫 Foo::~Foo()将对象解构；
(2)呼叫::operator delete释放内存。

为了精密分工，STL allocator决定将这两阶段动作区分开来。内存配置动作由alloc:allocate()负责，内存释放动作由alloc::deallocate()负责；对象建构动作由::construct()负责，对象解构动作由::destroy()负责。

STL标准规格告诉我们，配置器定义于之中，SGI 内含以下两个文件：

#include <stl_alloc.h> //负责内存空间的配置与释放

#include <stl_construct.h> //负责对象内容的建构与解构

内存空间的配置/释放与对象内容的建构/解构，分别着落在这两个文件身上。其中<stl_construct.h>定义有两个基本函数：建构用的 construct()和解构用的destroy()。

建构和解构基本工具：construct() 和 destroy()

下面是<stl_construct.h> 的部份内容

#include <new.h> //欲使用placement new，需先含入此文件
template <class T1, class T2> 
inline void construct(T1* p, const T2& value) { 
new (p) T1(value); //placement new;唤起 T1::T1(value); 就是在指针p所指向的内存空间创建一个T1类型的对象，但是对象的内容是从T2类型的对象转换过来的（调用了T1的构造函数，T1::T1(value)）。在已有空间的基础上重新调整分配的空间，类似于realloc函数。这个操作就是把已有的空间当成一个缓冲区来使用，这样子就减少了分配空间所耗费的时间，因为直接用new操作符分配内存的话，在堆中查找足够大的剩余空间速度是比较慢的。

} 
//以下是 destroy()第一版本，接受一个指标。
template <class T> 
inline void destroy(T* pointer) { 
} 
pointer->~T(); //唤起 dtor ~T() 
//以下是 destroy()第二版本，接受两个迭代器。此函式设法找出元素的数值型别，
//进而利用 __type_traits<>求取最适当措施。
template <class ForwardIterator> 
inline void destroy(ForwardIterator first, ForwardIterator last) { 
__destroy(first, last, value_type(first)); 
} 
//判断元素的数值型别（value type）是否有trivial destructor 
template <class ForwardIterator, class T> 
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) 
{ 
 typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor; 
__destroy_aux(first, last, trivial_destructor()); 
} 
//如果元素的数值型别（value type）有non-trivial destructor…
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) { 
 for ( ; first < last; ++first) 
destroy(&*first); 
} 
//如果元素的数值型别（value type）有trivial destructor…
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} //什么也不做
//以下是 destroy()第二版本针对迭代器为 char*和 wchar_t*的特化版
inline void destroy(char*, char*) {} 
inline void destroy(wchar_t*, wchar_t*) {}

这两个做为建构、解构之用的函式被设计为全域函式，符合 STL 的规范。此外STL 还规定配置器必须拥有名为 construct()和destroy()的两个成员函式，然而真正在 SGI STL 中大显身手的那个名为 std::alloc 的配置器并未遵守此一规则。

上述construct()接受一个指标p和一个初值value，此函式的用途就是将初值设定到指标所指的空间上。C++ 的placement new运算子可用来完成此一任务。

destroy()有两个版本，第一版本接受一个指标，准备将该指标所指之物解构掉。这很简单，直接呼叫该对象的解构式即可。第二版本接受first和last两个迭代器（所谓迭代器，第三章有详细介绍），准备将[first,last)范围内的所有物件解构掉。我们不知道这个范围有多大，万一很大，而每个物件的解构式都无关痛痒（所谓 trivialdestructor），那么一次次呼叫这些无关痛痒的解构式，对效率是一种蕲伤。

因此，这里首先利用value_type()获得迭代器所指物件的型别，再利用 __type_traits<T> 判别该型别的解构式是否无关痛痒。若是（__true_type），什么也不做就结束；若否（__false_type），这才以循环方式巡访整个范围，并在循环中每经历一个对象就呼叫第一个版本的 destroy()。

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

看完了内存配置后的对象建构行为，和内存释放前的对象解构行为，现在我们来看看内存的配置和释放。

对象建构前的空间配置，和对象解构后的空间释放，由<stl_alloc.h>负责，SGI 对此的设计哲学如下：

向 system heap要求空间。
考虑多绪（multi-threads）状态。
考虑内存不足时的应变措施。
考虑过多「小型区块」可能造成的内存破碎（fragment）问题。

为了将问题控制在一定的复杂度内，以下的讨论以及所摘录的源码，皆排除多绪状态的处理。

C++的记忆体配置基本动作是::operator new() ，记忆体释放基本动作是::operator delete()。这两个全域函式相当于 C 的 malloc()和 free() 函式。是的，正是如此，SGI 正是以malloc() 和free() 完成内存的配置与释放。

考虑小型区块所可能造成的内存破碎问题，SGI 设计了双层级配置器，第一级配置器直接使用 malloc()和free()，第二级配置器则视情况采用不同的策略：

当配置区块超过128bytes，视之为「足够大」，便呼叫第一级配置器；

当配置区块小于 128bytes，视之为「过小」，为了降低额外负担（overhead），便采用复杂的memory pool整理方式，而不再求助于第一级配置器。整个设计究竟只开放第一级配置器，或是同时开放第二级配置器，取决于__USE_MALLOC是否被定义（可以轻易测试出来，SGI STL 并未定义__USE_MALLOC）：

# ifdef __USE_MALLOC 
... 
typedef __malloc_alloc_template<0> malloc_alloc; 
typedef malloc_alloc alloc; //令 alloc为第一级配置器
# else 
... 
//令 alloc 为第二级配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; 
#endif /* ! __USE_MALLOC */

其中 __malloc_alloc_template就是第一级配置器， __default_alloc__template就是第二级配置器。再次提醒，alloc并不接受任何 template 型别参数。

无论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)); } 
};

其内部四个成员函式其实都是单纯的转呼叫，呼叫传入之配置器（可能是第一级，也可能是第二级）的成员函式。这个接口使配置器的配置单位从 bytes转为个别元素的大小（sizeof(T)）。SGI STL 容器全都使用这个 simple_alloc 接口，例如：

template <class T, class Alloc = alloc> // 预设使用 alloc为配置器
class vector { 
protected: 
// 专属之空间配置器，每次配置一个元素大小
 typedef simple_alloc<value_type, Alloc>data_allocator; 
 void deallocate() { 
 if (...) 
data_allocator::deallocate(start, end_of_storage - start); 
 } 
... 
};

一、二级配置器的关系，接口包装，及实际运用方式，可于下图略见端倪。

第一级配置器 __malloc_alloc_template

第一级配置器：

#if 0 
# include <new> 
# define __THROW_BAD_ALLOC throw bad_alloc 
#elif !defined(__THROW_BAD_ALLOC) 
# include <iostream.h> 
# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
#endif 
// malloc-based allocator. 通常比稍后介绍的 default alloc 速度慢，
//一般而言是 thread-safe，并且对于空间的运用比较高效（efficient）。
//以下是第一级配置器。
//注意，无「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); 
static void (* __malloc_alloc_oom_handler)();
    
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 
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
//初值为 0。有待客端设定。
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; 
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); 
 } 
} 
//注意，以下直接将参数 inst指定为 0。
typedef __malloc_alloc_template<0> malloc_alloc;

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

所谓 C++ new handler 机制是，你可以要求系统在内存配置需求无法被满足时，唤起一个你所指定的函式。换句话说一旦::operator new无法达成任务，在丢出std::bad_alloc异常状态之前，会先呼叫由客端指定的处理例程。此处理例程通常即被称为 new-handler。

第二级配置器 __default_alloc_template

第二级配置器多了一些机制，避免太多小额区块造成内存的破碎。小额区块带来的其实不仅是内存破碎而已，配置时的额外负担（overhead）也是一大问题。额外负担永远无法避免，毕竟系统要靠这多出来的空间来管理内存，但是区块愈小，额外负担所占的比例就愈大、愈显得浪费。额外负担图示如下：

SGI第二级配置器的作法是，如果区块够大，超过 128 bytes，就移交第一级配置器处理。当区块小于 128 bytes，则以内存池（memory pool）管理，此法又称为次层配置（sub-allocation）：每次配置一大块内存，并维护对应之自由串行（free-list）。下次若再有相同大小的内存需求，就直接从free-lists中拨出。如果客端释还小额区块，就由配置器回收到free-lists中—配置器除了负责配置，也负责回收。为了方便管理，SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数（例如客端要求 30 bytes，就自动调整为 32 bytes），并维护 16 个 free-lists，各自管理大小分别为 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128 bytes的小额区块。free-lists 的节点结构如下：

unionobj { 
 union obj * free_list_link; 
 char client_data[1]; /* The client sees this. */ 
 };

或许会想，为了维护串行（lists），每个节点需要额外的指标（指向下一个节点），这不又造成另一种额外负担吗？这个顾虑是对的，但早已有好的解决办法。注意，上述obj所用的是union（联合），由于union之故，从其第一字段观之，obj可被视为一个指标，指向相同形式的另一个obj。从其第二字段观之，obj可被视为一个指标，指向实际区块，如下图。

一物二用的结果是，不会为了维护串行所必须的指针而造成内存的另一种浪费。这种技巧在强型（strongly typed）语言如 Java 中行不通，但是在非强型语言如 C++ 中十分普遍

注：Union在C++内存模型，可以理解为一块“共享内存”(不是多线（进）程概念中的共享内存)。Union开辟的大小，是其内部定义的所有元素中最大的元素。“联合”是一种特殊的类，也是一种构造类型的数据结构。在一个“联合”内可以定义多种不同的数据类型，一个被说明为该“联合”类型的变量中，允许装入该“联合”所定义的任何一种数据，这些数据共享同一段内存，已达到节省空间的目的（还有一个节省空间的类型：位域）。这是一个非常特殊的地方，也是联合的特征。这里所谓的共享不是指把多个成员同时装入一个联合变量内，而是指该联合变量可被赋予任一成员值，但每次只能赋一种值，赋入新值则冲去旧值。

第二级配置器的部份实作内容：

enum {__ALIGN = 8};//小型区块的上调边界
enum {__MAX_BYTES = 128};//小型区块的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-lists个数
//以下是第二级配置器。
//注意，无「template 型别参数」，且第二参数完全没派上用场。
//第一参数用于多绪环境下。本书不讨论多绪环境。
template <bool threads, int inst> 
class __default_alloc_template { 
private: 
 // ROUND_UP() 将 bytes上调至 8的倍数。
 static size_t ROUND_UP(size_t bytes) { 
 return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1)); 
 } 
private: 
 unionobj { //free-lists 的节点构造
 union obj * free_list_link; 
 char client_data[1]; /* The client sees this. */ 
 }; 
private: 
// 16 个 free-lists 
 static obj * volatilefree_list[__NFREELISTS]; 
// 以下函式根据区块大小，决定使用第 n号 free-list。n 从 1 起算。
 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()

身为一个配置器，__default_alloc_template 拥有配置器的标准介面函式allocate()。此函式首先判断区块大小，大于 128 bytes 就呼叫第一级配置器，小于 128 bytes 就检查对应的 free list。如果free list之内有可用的区块，就直接拿来用，如果没有可用区块，就将区块大小上调至 8 倍数边界，然后呼叫refill()，准备为 free list 重新填充空间。

// n must be > 0 
 static void *allocate(size_t n) 
 { 
 obj * volatile * my_free_list;
 obj * result; 
// 大于 128 就呼叫第一级配置器
 if (n > (size_t) __MAX_BYTES) 
 return(malloc_alloc::allocate(n)); 
 } 
// 寻找 16 个 free lists 中适当的一个
 my_free_list = free_list + FREELIST_INDEX(n); 
 result = *my_free_list; 
 if (result == 0) { 
// 没找到可用的 free list，准备重新填充 free list
 void *r = refill(ROUND_UP(n)); 
 return r; 
 } 
// 调整 free list
//下节详述
 *my_free_list = result -> free_list_link; 
 return (result); 
 };

区块自free list拨出的操作如下图

空间释还函式 deallocate()

身为一个配置器，__default_alloc_template 拥有配置器标准介面函式deallocate()。此函式首先判断区块大小，大于 128 bytes 就呼叫第一级配置器，小于 128 bytes 就找出对应的 free list，将区块回收。

// p 不可以是 0 
 static void deallocate(void *p, size_t n) 
 { 
 obj *q = (obj *)p; 
 obj * volatile * my_free_list; 
// 大于 128 就呼叫第一级配置器
 if (n > (size_t) __MAX_BYTES) { 
malloc_alloc::deallocate(p, n); 
 return; 
 } 
// 寻找对应的 free list
 my_free_list = free_list + FREELIST_INDEX(n); 
// 调整 free list，回收区块
 q -> free_list_link = *my_free_list; 
 *my_free_list = q; 
 }

区块回收纳入free list的动作，如下图

重新充填 free lists

讨论先前说过的 allocate()。当它发现free list中没有可用区块了，就呼叫refill() 准备为free list重新填充空间。新的空间将取自内存池（经由chunk_alloc()完成）。预设取得20个新节点（新区块），但万一内存池空间不足，获得的节点数（区块数）可能小于 20：

//传回一个大小为 n的对象，并且有时候会为适当的freelist增加节点. 
//假设 n已经适当上调至 8的倍数。
template <bool threads, int inst> 
void* __default_alloc_template<threads, inst>::refill(size_t n) 
{ 
 int nobjs = 20; 
// 呼叫 chunk_alloc()，尝试取得 nobjs个区块做为 free list的新节点。
 // 注意参数 nobjs是pass by reference。
 char * chunk =chunk_alloc(n, nobjs); //下节详述
 obj * volatile * my_free_list; 
 obj * result; 
 obj * current_obj, * next_obj; 
 int i; 
// 如果只获得一个区块，这个区块就拨给呼叫者用，free list无新节点。
 if (1 == nobjs) return(chunk); 
// 否则准备调整 free list，纳入新节点。
 my_free_list = free_list + FREELIST_INDEX(n); 
// 以下在 chunk空间内建立freelist
 result = (obj *)chunk; //这一块准备传回给客端
// 以下导引 free list指向新配置的空间（取自内存池）
 *my_free_list = next_obj = (obj *)(chunk + n); 
// 以下将 free list 的各节点串接起来。
 for (i = 1; ; i++) {//从 1 开始，因为第 0 个将传回给客端
 current_obj = next_obj; 
 next_obj = (obj *)((char *)next_obj + n); 
 if (nobjs - 1 == i) { 
 current_obj -> free_list_link = 0; 
 break; 
 } else { 
 current_obj -> free_list_link = next_obj; 
 } 
 } 
 return(result); 
}

内存池（memory pool）

从内存池中取空间给free list使用，是 chunk_alloc()的工作：

//假设 size 已经适当上调至 8的倍数。
//注意参数 nobjs是pass by reference。
template <bool threads, int inst> 
char* 
__default_alloc_template<threads, inst>::
chunk_alloc(size_t size, int& nobjs) 
{ 
 char * result; 
 size_t total_bytes = size * nobjs; 
 size_t bytes_left = end_free - start_free;// 内存池剩余空间
 if (bytes_left >= total_bytes) { 
// 内存池剩余空间完全满足需求量。
 result = start_free; 
 start_free += total_bytes;
 return(result); 
 } else if (bytes_left >= size) { 
// 内存池剩余空间不能完全满足需求量，但足够供应一个（含）以上的区块。
 nobjs = bytes_left/size; 
 total_bytes = size * nobjs; 
 result = start_free; 
 start_free += total_bytes; 
 return(result); 
 } else { 
// 内存池剩余空间连一个区块的大小都无法提供。
 size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); 
// 以下试着让内存池中的残余零头还有利用价值。
 if (bytes_left > 0) { 
// 内存池内还有一些零头，先配给适当的 free list，因为其他free list区块可能更小
// 首先寻找适当的 free list。
 obj * volatile * my_free_list = 
 free_list + FREELIST_INDEX(bytes_left); 
// 调整 free list，将内存池中的残余空间编入。
 ((obj *)start_free) -> free_list_link = *my_free_list; 
 *my_free_list = (obj *)start_free; 
 }
     // 配置 heap 空间
 start_free = (char *)malloc(bytes_to_get); 
 if (0 == start_free) { 
// heap 空间不足，malloc() 失败。
 int i; 
 obj * volatile * my_free_list, *p; 
// 试着检视我们手上拥有的东西。这不会造成伤害。我们不打算尝试配置
 // 较小的区块，因为那在多行程（multi-process）机器上容易导致灾难
// 以下搜寻适当的 free list，
 // 所谓适当是指「尚有未用区块，且区块够大」之 free list。
 for (i = size; i <= __MAX_BYTES; i += __ALIGN) { 
 my_free_list = free_list + FREELIST_INDEX(i); 
 p = *my_free_list; 
 if (0 != p) {//free list 内尚有未用区块。
 // 调整 free list以释出未用区块
 *my_free_list = p -> free_list_link; 
 start_free = (char *)p; 
 end_free = start_free + i; 
// 递归呼叫自己，为了修正 nobjs。
 return(chunk_alloc(size, nobjs)); 
// 注意，任何残余零头终将被编入适当的 free-list中备用。
 } 
 } 
 end_free = 0; // 如果出现意外（山穷水尽，到处都没内存可用了）
// 呼叫第一级配置器，看看out-of-memory机制能否尽点力
 start_free = (char *)malloc_alloc::allocate(bytes_to_get); 
// 这会导致掷出异常（exception），或内存不足的情况获得改善。
     } 
 heap_size += bytes_to_get; 
 end_free = start_free + bytes_to_get; 
 // 递归呼叫自己，为了修正 nobjs。
 return(chunk_alloc(size, nobjs)); 
 } 
}

上述的 chunk_alloc()函式以end_free - start_free 来判断内存池的“水量”。如果水量充足，就直接拨出 20 个区块传回给 free list。如果水量不足以提供 20 个区块，但还足够供应一个以上的区块，就拨出这不足20个区块的空间出去。这时候其pass by reference 的 nobjs 参数将被修改为实际能够供应的区块数。如果内存池连一个区块空间都无法供应，对客端显然无法交待，此时便需利用malloc() 从 heap 中配置内存，为内存池注入活水源头以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。

一个例子见下图，假设程序一开始，客端就呼叫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（附加量）个区块留给内存池……。

万一整个system heap 空间都不够了（以至无法为内存池注入活水源头），malloc()行动失败，chunk_alloc()就四处寻找有无「尚有未用区块，且区块够大」之free lists。找到的话就挖一块交出，找不到的话就呼叫第一级配置器。第一级配置器其实也是使用malloc()来配置内存，但它有 out-of-memory 处理机制（类似 new-handler 机制），或许有机会释放其它的内存拿来此处使用。如果可以，就成功，否则发出bad_alloc异常。

内存基本处理工具

STL定义有五个全域函式，作用于未初始化空间上。这样的功能对于容器的实作很有帮助。

前两个函式是用于建构的construct()和用于解构的destroy()，另三个函式是uninitialized_copy()、uninitialized_fill()、uninitialized_fill_n()，分别对应于高阶函式copy()、fill()、fill_n()——这些都是 STL 算法。如果要使用本节的三个低阶函式，应该含入，不过SGI 把它们实际定义于。

uninitialized_copy（复制迭代器）

1
2
3

template <class InputIterator, class ForwardIterator> 
ForwardIterator 
uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

注：

InputIterator：输入迭代器。支持对容器元素的逐个遍历，以及对元素的读取（input)；
OutputIterator：输出迭代器。支持对容器元素的逐个遍历，以及对元素的写入（output)。
ForwardIterator：前向迭代器。向前逐个遍历元素。可以对元素读取；
BidirectionalIterator：双向迭代器。支持向前向后逐个遍历元素，可以对元素读取。
RandomAccessIterator：随机访问迭代器。支持O(1)时间复杂度对元素的随机位置访问，支持对元素的读取。

输出迭代器可以修改元素，这可能会导致内部结构的调整，进而导致原有的迭代器失效！可能的情况有：
	结构和元素顺序变更：比如对map，set，priority_queue插入元素；
	内存变化：比如对vector插入元素，可能导致重新申请内存并拷贝

uninitialized_copy() 使我们能够将内存的配置与对象的建构行为分离开来。如果做为输出目的地的 [result, result+(last-first)) 范围内的每一个迭代器都指向未初始化区域，则 uninitialized_copy() 会使用copy constructor，为身为输入来源之 [first,last) 范围内的每一个对象产生一份复制品，放进输出范围中。换句话说，针对输入范围内的每一个迭代器 i，此函式会呼叫construct(&*(result+(i-first)),*i)，产生*i的复制品，放置于输出范围的相对位置上。

如果需要实作一个容器，uninitialized_copy()这样的函式会带来很大的帮助，因为容器的全范围建构式（range constructor）通常以两个步骤完成：

配置内存区块，足以包含范围内的所有元素。
使用uninitialized_copy()，在该内存区块上建构元素。

C++标准规格书要求uninitialized_copy()具有 “commit or rollback“语意，意思是要不就「建构出所有必要元素」，要不就（当有任何一个copy constructor 失败时）「不建构任何东西」。

uninitialized_fill （填充给定对象的值）

1 2	template <class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

uninitialized_fill() 也能够使我们将内存配置与对象的建构行为分离开来。如果[first,last)范围内的每个迭代器都指向未初始化的内存，那么

uninitialized_fill()会在该范围内产生x（上式第三参数）的复制品。换句话说uninitialized_fill()会针对操作范围内的每个迭代器 i ，呼叫construct(&*i, x)，在i所指之处产生x的复制品。

和 uninitialized_copy()一样，uninitialized_fill() 必须具备 “commit or rollback“语意，换句话说它要不就产生出所有必要元素，要不就不产生任何元素。如果有任何一个copy constructor丢出异常（exception），uninitialized_fill() 必须能够将已产生之所有元素解构掉。

uninitialized_fill_n （fill的不同参数写法）

1
2
3

template <class ForwardIterator, class Size, class T> 
ForwardIterator 
uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

uninitialized_fill_n()能够使我们将内存配置与对象建构行为分离开来。它会为指定范围内的所有元素设定相同的初值。

如果[first, first+n)范围内的每一个迭代器都指向未初始化的内存，那么uninitialized_fill_n()会呼叫copy constructor，在该范围内产生x（上式第三参数）的复制品。也就是说面对 [first,first+n)范围内的每个迭代器 i，uninitialized_fill_n()会呼叫construct(&*i, x)，在对应位置处产生x 的复制品。

uninitialized_fill_n()也具有 “commit or rollback“语意：要不就产生所有必要的元素，否则就不产生任何元素。如果任何一个copy constructor丢出异常（exception），uninitialized_fill_n() 必须解构已产生的所有元素。

具体实现

uninitialized_fill_n

本函式接受三个参数：

迭代器first指向欲初始化空间的起始处
n表示欲初始化空间的大小
x表示初值

template <class ForwardIterator, class Size, class T> 
inline ForwardIterator uninitialized_fill_n(ForwardIteratorfirst, Size n, const T&x) { 
 return __uninitialized_fill_n(first, n, x, value_type(first)); 
 // 以上，利用 value_type() 取出 first的 value type. 
}

这个函式的进行逻辑是，首先萃取出迭代器 first 的 value type（详见下节），然后判断该型别是否为 POD型别：

template <class ForwardIterator, class Size, class T, class T1> 
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n, const T& x, T1*)
{ 
 // 以下 __type_traits<> 技法，详见下节
 typedef typename __type_traits<T1>::is_POD_typeis_POD; 
 return __uninitialized_fill_n_aux(first, n, x, is_POD()); 
}

POD意指 Plain Old Data，也就是纯量型别（scalar types）或传统的 C struct型别。POD型别必然拥有 trivialctor/dtor/copy/assignment函式，因此，可以对POD型别采取最有效率的初值填写手法，而对non-POD 型别采取最保险安全的作法：

//如果 copy construction 等同于 assignment, 而且
// destructor 是 trivial，以下就有效。
//如果是 POD型别，执行流程就会转进到以下函式。这是藉由 function template 
//的自变量推导机制而得。
template <class ForwardIterator, class Size, class T> 
inline ForwardIterator 
__uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __true_type) { 
 return fill_n(first, n, x);//交由高阶函式执行。见第6节。//注：实际上就是走访容器，执行赋值构造函数（因为pod型必有assignment构造函数）
} 
// 如果不是 POD 型别，执行流程就会转进到以下函式。这是藉由 function template 
//的自变量推导机制而得。
template <class ForwardIterator, class Size, class T> 
ForwardIterator 
__uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __false_type) { 
 ForwardIterator cur = first; 
// 为求阅读顺畅，以下将原本该有的异常处理（exception handling）省略。
 for ( ; n > 0; --n, ++cur) 
 construct(&*cur, x); //注：调用placement new
 return cur; 
}

uninitialized_copy

本函式接受三个参数：

迭代器first指向输入端的起始位置
迭代器last指向输入端的结束位置（前闭后开区间）
迭代器result指向输出端（欲初始化空间）的起始处

template <class InputIterator, class ForwardIterator> 
inline ForwardIterator 
uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result) { 
 return __uninitialized_copy(first, last, result,value_type(result)); 
 // 以上，利用 value_type() 取出 first的 value type. 
}

这个函式的进行逻辑是，首先萃取出迭代器 result 的 value type，然后判断该型别是否为 POD型别：

template <class InputIterator, class ForwardIterator, class T> 
inline ForwardIterator 
__uninitialized_copy(InputIterator first, InputIterator last, 
 ForwardIterator result, T*) { 
 typedef typename __type_traits<T>::is_POD_type is_POD; 
 return __uninitialized_copy_aux(first, last, result,is_POD()); 
 // 以上，企图利用 is_POD() 所获得的结果，让编译器做自变量推导。
}

//如果 copy construction 等同于 assignment, 而且
// destructor 是 trivial，以下就有效。
//如果是 POD型别，执行流程就会转进到以下函式。这是藉由 function template 
//的自变量推导机制而得。
template <class InputIterator, class ForwardIterator> 
inline ForwardIterator 
__uninitialized_copy_aux(InputIterator first, InputIterator last, 
 ForwardIterator result, 
__true_type) { 
 return copy(first, last, result);//呼叫 STL算法 copy() 
} 
// 如果是 non-POD型别，执行流程就会转进到以下函式。这是藉由 function template 
//的自变量推导机制而得。
template <class InputIterator, class ForwardIterator> 
ForwardIterator 
__uninitialized_copy_aux(InputIterator first, InputIterator last, 
 ForwardIterator result, 
__false_type) { 
 ForwardIterator cur = result; 
// 为求阅读顺畅，以下将原本该有的异常处理（exception handling）省略。
 for ( ; first != last; ++first, ++cur) 
construct(&*cur, *first);//必须一个一个元素地建构，无法批量进行
 return cur; 
 } 
}

针对char和wchar_t两种型别，可以最具效率的作法memmove（直接搬移内存内容）来执行复制行为。因此 SGI 得以为这两种型别设计一份特化版本。

//以下是针对 const char*的特化版本
inline char*uninitialized_copy(const char* first, const char* last, 
 char* result) { 
memmove(result, first, last - first); 
 return result + (last - first); 
} 
//以下是针对 const wchar_t* 的特化版本
inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last, 
 wchar_t* result) { 
memmove(result, first, sizeof(wchar_t) * (last - first)); 
 return result + (last - first); 
}

uninitialized_fill

本函式接受三个参数：

迭代器first指向输出端（欲初始化空间）的起始处
迭代器last指向输出端（欲初始化空间）的结束处（前闭后开区间）
x表示初值

template <class ForwardIterator, class T> 
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x) { 
__uninitialized_fill(first, last, x, value_type(first)); 
}

这个函式的进行逻辑是，首先萃取出迭代器 first 的 value type，然后判断该型别是否为 POD型别：

template <class ForwardIterator, class T, class T1> 
inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last, 
 const T& x, T1*) { 
 typedef typename __type_traits<T1>::is_POD_type is_POD; 
__uninitialized_fill_aux(first, last, x, is_POD()); 
}

//如果 copy construction 等同于 assignment, 而且
// destructor 是 trivial，以下就有效。
//如果是 POD型别，执行流程就会转进到以下函式。这是藉由 function template 
//的自变量推导机制而得。
template <class ForwardIterator, class T> 
inline void 
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
 const T& x, __true_type) 
{ 
fill(first, last, x);//呼叫 STL算法 fill() 
} 
// 如果是 non-POD型别，执行流程就会转进到以下函式。这是藉由 function template 
//的自变量推导机制而得。
template <class ForwardIterator, class T> 
void 
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
 const T& x, __false_type) 
{ 
 ForwardIterator cur = first; 
// 为求阅读顺畅，以下将原本该有的异常处理（exception handling）省略。
 for ( ; cur != last; ++cur) 
construct(&*cur, x);//必须一个一个元素地建构，无法批量进行
 } 
}

下图是三个内存基本函数的泛型版本和特化版本图示

总结

空间配置器是最底层的操作之一，STL把传统的new（new operator）分成两步来做（这是核心），也即operator new（配置内存）和placement new（建构元素）。其中建构元素的操作对应使用construct()和destroy()函数，配置内存的操作使用allocate()和deallocate()函数。（分开来可以提高效率，比如重新建构元素就不用直接从分配空间开始，用原来的空间即可）

配置内存分为一级配置和二级配置，根据__USE_MALLOC 是否定义区分使用，如果为true则为第一级配置器。第一级配置器直接使用malloc(), free(), realloc()等 C函式执行实际的内存动作（包括自定义handler）。第二级配置器的作法是，如果区块够大，超过 128 bytes，就移交第一级配置器处理。当区块小于 128 bytes，则以内存池（memory pool）管理。首先第二级配置器有一个串行，有16个节点，每个节点有许多内存区块，大小为8*（n+1），其中n是节点编号。每次调用allocate()就找合适的区块，deallocate()把区块空间归还即可。而内存池负责给予串行内存区块，涉及内存不够时的一些其他操作（比如从其他区块拿，或者从堆拿空间）。

在泛型的同时判别一些特化版本，进一步提高效率。

迭代器（iterators）概念与traits 编程技法

迭代器（iterators）是一种抽象的设计概念，现实程序语言中并没有直接对映于这个概念的实物。《Design Patterns》一书提供有 23 个设计样式（design patterns）的完整描述，其中 iterator 样式定义如下：提供一种方法，俾得依序巡访某个聚合物（容器）所含的各个元素，而又无需曝露该聚合物的内部表述方式。

迭代器设计思维—STL 关键所在

STL 的中心思想在于，将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起。容器和算法的泛型化，从技术角度来看并不困难，C++ 的 class templates 和 function templates可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。

以下是容器、算法、迭代器（iterator，扮演黏胶角色）的合作展示。以算法 find() 为例，它接受两个迭代器和一个「搜寻标的」：

//摘自 SGI <stl_algo.h> 
template <class InputIterator, class T> 
InputIterator find(InputIterator first, 
 InputIterator last, 
 const T& value) { 
 while (first != last && *first != value) 
 ++first; 
 return first; 
}

只要给予不同的迭代器，find()便能够对不同的容器做搜寻动作。

迭代器（iterator）是一种 smart pointer

迭代器是一种行为类似指针的对象，而指针的各种行为中最常见也最重要的便是内容提领（dereference）和成员取用（member access），因此迭代器最重要的编程工作就是对 operator* 和 operator-> 进行多载化（overloading）工程。

C++ 标准链接库有一个auto_ptr可供我们参考。任何一本详尽的 C++ 语法书籍都应该谈到auto_ptr，这是一个用来包装原生指标（native pointer）的对象，声名狼藉的内存漏洞（memory leak）问题可藉此获得解决。auto_ptr用法如下，和原生指标一模一样：

void func() 
{ 
 auto_ptr<string> ps(new string("jjhou")); 
 cout << *ps << endl; 
 cout << ps->size() << endl; 
//输出：jjhou 
//输出：5 
// 离开前不需 delete, auto_ptr 会自动释放内存
}

函式第一行的意思是，以算式new 动态配置一个初值为”jjhou”的string物件，并将所得结果（一个原生指针）做为auto_ptr<string>对象的初值。注意，auto_ptr 角括号内放的是「原生指针所指对象」的型别，而不是原生指标的型别。

auto_ptr的源码在头文件中，这里就不给出了。

现在来为list（串行）设计一个迭代器。假设 list 及其节点的结构如下：

// file: 3mylist.h 
template <typename T> 
class List //容器
{ 
 void insert_front(T value); 
 void insert_end(T value); 
 void display(std::ostream &os = std::cout) const; 
 // ... 
private: 
 ListItem<T>* _end; 
 ListItem<T>* _front; 
 long _size; 
}; 
template <typename T> 
class ListItem //节点结构，值和指针
{ 
public: 
 T value() const { return _value; } 
 ListItem* next() const { return _next; } 
 ... 
private: 
 T _value; 
 ListItem* _next; // 单向串行（single linked list）
};

要将这个List套用到先前所说的find()，需要为它设计一个行为类似指标的外衣，也就是一个迭代器。当我们提领（dereference）此一迭代器（用***），传回的应该是个ListItem 对象；当我们累加该迭代器（用++**），它应该指向下一个ListItem 物件。为了让此迭代器适用于任何型态的节点，而不只限于ListItem，我们可以将它设计为一个 class template：

// file : 3mylist-iter.h 
#include "3mylist.h" 
template <class Item> // Item 可以是单向串行节点或双向串行节点。
struct ListIter //此处这个迭代器特定只为串行服务，因为其
{ //独特的 operator++ 之故。
 Item* ptr;//保持与容器之间的一个联系（keep a reference to Container）
 ListIter(Item* p = 0) // default ctor 
 : ptr(p) { } 
// 不必实作 copy ctor，因为编译器提供的预设行为已足够。
 // 不必实作 operator=，因为编译器提供的预设行为已足够。
 Item&operator*() const { return *ptr; } //注：返回一个左值，可以赋值，要用引用
 Item*operator->() const { return ptr; } //注：返回一个指针
// 以下两个 operator++ 遵循标准作法，参见[Meyers96]条款 6 
// (1) pre-increment operator 
 ListIter&operator++() 
 { ptr = ptr->next(); return *this; } 
// (2) post-increment operator 
 ListIter operator++(int)//注：tmp是临时变量，因此函数返回类型不能用引用，也不是左值
 { ListIter tmp = *this; ++*this; return tmp; } 
 bool operator==(const ListIter& i) const 
 { return ptr == i.ptr; } 
 bool operator!=(const ListIter& i) const 
 { return ptr != i.ptr; } 
};

现在我们可以这样子将 List和find()藉由ListIter 黏合起来（使自己设计的List能通过ListIter来使用find()）：

// 3mylist-iter-test.cpp 
void main() 
{ 
 List<int> mylist; 
 for(int i=0; i<5; ++i) { 
 mylist.insert_front(i); 
 mylist.insert_end(i+2); 
 } 
 mylist.display(); // 10 ( 4 3 2 1 0 2 3 4 5 6 ) 
 ListIter<ListItem<int> >begin(mylist.front()); 
 ListIter<ListItem<int> >end; // default 0, null 
 ListIter<ListItem<int> > iter; // default 0, null
 iter = find(begin, end, 3); 
 if (iter == end) 
 cout << "not found" << endl; 
 else 
 cout << "found. " << iter->value() << endl; 
// 执行结果：found. 3 
 iter = find(begin, end, 7); 
 if (iter == end) 
 cout << "not found" << endl; 
 else 
 cout << "found. " << iter->value() << endl; 
// 执行结果：not found 
}

注意，由于find()函式内以*iter != value来检查元素值是否吻合，而本例之中value的型别是int，iter的型别是ListItem<int>，两者之间并无可供使用的operator!=，所以我必须另外写一个全域的operator!=多载函式，并以int和ListItem<int>做为它的两个参数型别：

1
2
3

template <typename T> 
bool operator!=(const ListItem<T>& item,T n) 
{ return item.value() != n; }

从以上实作可以看出，为了完成一个针对 List 而设计的迭代器，我们无可避免地曝露了太多List实作细节：在main()之中为了制作begin和end两个迭代器，我们曝露了ListItem；在ListIter class之中为了达成operator++的目的，我们曝露了 ListItem 的操作函式next()。

如果不是为了迭代器，ListItem 原本应该完全隐藏起来不曝光的。换句话说，要设计出 ListIter，首先必须对 List 的实作细节有非常丰富的了解。既然这无可避免，干脆就把迭代器的开发工作交给List的设计者好了，如此一来所有实作细节反而得以封装起来不被使用者看到。这正是为什么每一种 STL容器都提供有专属迭代器的缘故。

迭代器相应型别（associated types）

上述的ListIter提供了一个迭代器雏形。如果将思想拉得更高远一些，我们便会发现，算法之中运用迭代器时，很可能会用到其相应型别（associated type）。什么是相应型别？迭代器所指之物的型别便是其一。

假设算法中有必要宣告一个变量，以「迭代器所指对象的型别」为型别，如何是好？毕竟C++只支援**sizeof()，并未支持typeof()**。

解决办法是：利用 function template （函数模板）的自变量推导（argument deducation）机制，例如

template <class I, class T> 
void func_impl(I iter, T t) //多了类型T，T是迭代器指向对象的类型
{ 
 T tmp; // 这里解决了问题。T就是迭代器所指之物的型别，本例为 int 
// ... 这里做原本 func()应该做的全部工作
}; 
template <class I> 
inline 
void func(I iter) 
{ 
 func_impl(iter,*iter);// func 的工作全部移往 func_impl 
} 
int main() 
{ 
 int i; 
 func(&i); 
}

我们以func()为对外界面，却**把实际动作全部置于func_impl() **之中。由于func_impl()是一个 function template，一旦被呼叫，编译器会自动进行 template 自变量推导。于是导出型别T，顺利解决了问题。

迭代器相应型别（associated types）不只是「迭代器所指对象的型别」一种而已。根据经验，最常用的相应型别有五种，然而并非任何情况下任何一种都可利用上述的 template自变量推导机制来取得。我们需要更全面的解法。

Traits 编程技法——STL 源码门钥

迭代器所指物件的型别，称为该迭代器的value type。上述的自变量型别推导技巧虽然可用于 value type，却非全面可用：万一value type必须用于函式的传回值，就束手无策了，毕竟函式的「template 自变量推导机制」推而导之的只是自变量，无法推导函式的回返值型别。

声明内嵌型别似乎是个好主意，像这样：

template <class T> 
struct MyIter 
 typedef T value_type; // 内嵌型别声明（nested type）
 T* ptr; 
 MyIter(T* p=0) : ptr(p) { } 
 T& operator*() const { return *ptr; } 
 // ... 
}; 
template <class I> //注：I指上面的MyIter
typename I::value_type //这一整行是 func的回返值型别
func(I ite) 
{ return *ite; } 
// ... 
MyIter<int> ite(new int(8)); 
cout << func(ite); //输出：8

注意，func()的回返型别必须加上关键词 typename，因为T是一个 template参数，在它被编译器具现化之前，编译器对T一无所悉，换句话说编译器此时并不知道MyIter<T>::value_type代表的是一个型别或是一个 member function或是一个 data member。关键词typename的用意在告诉编译器说这是一个型别，如此才能顺利通过编译。

看起来不错。但是有个隐晦的陷阱：并不是所有迭代器都是 class type。原生指标就不是。如果不是 class type，就无法为它定义内嵌型别。但 STL（以及整个泛型思维）绝对必须接受原生指标做为一种迭代器，所以上面这样还不够。更好的方式是使用template partial specialization（模板偏特化）。

Partial Specialization（偏特化）的意义：如果 class template拥有一个以上的 template 参数，我们可以针对其中某个（或数个，但非全部）template参数进行特化工作。换句话说我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些template参数赋予明确的指定）。

假设有一个 class template如下：

1 2	template<typename U, typename V, typename T> class C { ... };

partial specialization的字面意义容易误导我们以为，所谓「偏特化版」一定是对template参数 U 或 V 或 T（或某种组合）指定某个自变量值。事实不然，「所谓partial specialization的意思是提供另一份 template定义式，而其本身仍为 templatized」。《泛型技术》一书对 partial specialization 的定义是：「针对（任何）template 参数更进一步的条件限制，所设计出来的一个特化版本」。

由此，面对以下这么一个 class template：

1 2	template<typename T> class C { ... }; // 这个泛化版本允许（接受）T为任何型别

我们便很容易接受它有一个型式如下的partial specialization：

1
2
3

template<typename T> 
class C<T*> { ... }; //这个特化版本仅适用于「T为原生指针」的情况
 // 「T为原生指针」便是「T 为任何型别」的一个更进一步的条件限制

注：原生指针即 (类型名*p)样子的指针，类型名可以是基础类型，如int，double等，也可以是一个自己定义的Class类。相反的如果一个类重载了‘*’和‘**->*’的运算符，可以像指针一样用‘’和‘->’操作，就不是原生的，如iterator等。

有了这项利器，我们便可以解决前述「内嵌型别」未能解决的问题。先前的问题是，原生指针并非 class，因此无法为它们定义内嵌型别。现在，我们可以针对「迭代器之 template自变量为指标」者，设计特化版的迭代器。

下面这个 class template专门用来「萃取」迭代器的特性，而 value type 正是迭代器的特性之一：

template <class I> 
struct iterator_traits { // traits 意为「特性」
 typedef typename I::value_type value_type; 
};

这个所谓的traits，其意义是，如果I定义有自己的value type，那么透过这个traits的作用，萃取出来的value_type就是I::value_type。换句话说如果I 定义有自己的value type，先前那个func()可以改写成这样：

template <class I> 
typename iterator_traits<I>::value_type // 这一整行是函式回返型别，注：此时类I内定义了value_type
func(I ite) 
{ return *ite; }

这样做的好处是traits可以拥有特化版本。现在，我们令 iterator_traites拥有一个partial specializations 如下：

template <class T> 
struct iterator_traits<T*> { //偏特化版—迭代器是个原生指标，注：此时T（比如int）也许没有定义value_type，则可以根据T* 获取T，也就得到了type
 typedef T value_type; 
};

于是，原生指标int* 虽然不是一种 class type，亦可透过traits取其value type。这就解决了先前的问题。

但是请注意，针对「指向常数对象的指针（pointer-to-const）」，下面这个式子得到什么结果：

1	iterator_traits<const int*>::value_type

获得的是const int而非int。这不是所期望的。我们希望利用这种机制来宣告一个暂时变量，使其型别与迭代器的value type相同，而现在，宣告一个无法赋值（因const之故）的暂时变数，没什么用！因此，如果迭代器是个pointer-to-const，我们应该设法令其value type为一个 non-const型别。只要另外设计一个特化版本，就能解决这个问题：

template <class T> 
struct iterator_traits<const T*> { // 偏特化版—当迭代器是个pointer-to-const ，注：这个版本多了const，针对const的实例会进入这个版本，萃取T
 typedef T value_type; // 萃取出来的型别应该是 T 而非 const T
};

现在，不论面对的是迭代器MyIter，或是原生指标int或const int，都可以透过traits取出正确的（我们所期望的）value type。

下图说明traits所扮演的「特性萃取机」角色，萃取各个迭代器的特性。这里所谓的迭代器特性，指的是迭代器的相应型别（associated types）。当然，若要这个「特性萃取机」traits能够有效运作，每一个迭代器必须遵循约定，自行以内嵌型别定义（nested typedef）的方式定义出相应型别（associated types）。这种一个约定，谁不遵守这个约定，谁就不能相容于 STL 这个大家庭。

根据经验，最常用到的迭代器相应型别有五种：

value type
difference type
pointer
reference
iterator catagory

如果你希望你所开发的容器能与 STL 水乳交融，一定要为你的容器的迭代器定义这五种相应型别。「特性萃取机」traits 会很忠实地

将原汁原味榨取出来：

template <class I> 
struct iterator_traits { 
 typedef typename I::iterator_category iterator_category; 
 typedef typename I::value_type value_type; 
 typedef typename I::difference_type difference_type; 
 typedef typename I::pointer pointer; 
 typedef typename I::reference reference; 
};

iterator_traits必须针对传入之型别为 pointer 及 pointer-to-const者，设计特化版本，见下节。

迭代器相应型别之一：value type

所谓value type，是指迭代器所指对象的型别。任何一个打算与 STL算法有完美搭配的 class，都应该定义自己的 value type 内嵌型别，作法就像上节所述。

迭代器相应型别之二：difference type

difference type 用来表示两个迭代器之间的距离，也因此，它可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。

如果一个泛型算法提供计数功能，例如 STL的count()，其传回值就必须使用迭代器的 difference type：

template <class I, class T> 
typename iterator_traits<I>::difference_type //这一整行是函式回返型别
count(I first, I last, const T& value) { 
 typename iterator_traits<I>::difference_type n = 0; 
 for ( ; first != last; ++first) 
 if (*first == value) 
 ++n; 
 return n; 
}

针对相应型别difference type，traits的两个（针对原生指标而写的）特化版本如下，以C++内建的ptrdiff_t（定义于头文件）做为原生指标的difference type：

template <class I> 
struct iterator_traits { 
 ... 
 typedef typename I::difference_type difference_type; 
}; 
//针对原生指标而设计的「偏特化（partial specialization）」版
template <class T> 
struct iterator_traits<T*> { 
 ... 
 typedef ptrdiff_t difference_type; 
}; 
//针对原生的 pointer-to-const 而设计的「偏特化（partial specialization）」版
template <class T> 
struct iterator_traits<const T*> {
 ...
 typedef ptrdiff_t difference_type; 
};

现在，任何时候当我们需要任何迭代器 I的difference type，可以这么写：

1	typename iterator_traits<I>::difference_type

迭代器相应型别之三：reference type

从「迭代器所指之物的内容是否允许改变」的角度观之，迭代器分为两种：不允许改变「所指对象之内容」者，称为constant iterators，例如const int* pic；允许改变「所指对象之内容」者，称为 mutable iterators，例如int* pi。

当我们对一个 mutable iterators做提领动作时，获得的不应该是个右值（rvalue），应该是个左值（lvalue），因为右值不允许赋值动作（assignment），左值才允许：

int* pi = new int(5); 
const int* pci = new int(9); 
*pi = 7; // 对 mutable iterator做提领动作时，获得的应该是个左值，允许赋值。
*pci = 1; // 这个动作不允许，因为 pci是个constant iterator，
// 提领 pci所得结果，是个右值，不允许被赋值。

在 C++中，函式如果要传回左值，都是以by reference的方式进行，所以当p是个 mutable iterators时，如果其value type是T，那么*p的型别不应该是T，应该是 T&（因为传回引用才是左值，才能进行赋值）。将此道理扩充，如果 p是一个 constant iterators，其value type是 T，那么*p的型别不应该是const T，而应该是const T&。这里所讨论的*p的型别，即所谓的reference type。实作细节将在下一小节一并展示。

迭代器相应型别之四：pointer type

pointers和 references 在 C++中有非常密切的关连。如果「传回一个左值，令它代表p所指之物」是可能的，那么「传回一个左值，令它代表p所指之物的位址」也一定可以。也就是说我们能够传回一个 pointer，指向迭代器所指之物。

这些相应型别已在先前的ListIter class中出现过：

1 2	Item& operator() const { return ptr; } Item* operator->() const { return ptr; }

Item&便是 ListIter的reference type而 Item*便是其pointer type。

现在把 reference type和pointer type 这两个相应型别加入traits内：

template <class I> 
struct iterator_traits { 
 ... 
 typedef typename I::pointer pointer; 
 typedef typename I::reference reference; 
}; 
//针对原生指标而设计的「偏特化版（partial specialization）」
template <class T> 
struct iterator_traits<T*> { 
 ... 
 typedef T* pointer; 
 typedef T& reference; 
}; 
//针对原生的 pointer-to-const 而设计的「偏特化版（partial specialization）」
template <class T> 
struct iterator_traits<const T*> { 
 ... 
 typedef const T* pointer; 
 typedef const T& reference; 
};

迭代器相应型别之五：iterator_category

最后一个（第五个）迭代器相应型别会引发较大规模的写码工程。在那之前，必须先讨论迭代器的分类。

根据移动特性与施行动作，迭代器被分为五类：（注：这里的只读和只写或读写，可以理解为作为左值还是右值）

Input Iterator：这种迭代器所指对象，不允许外界改变。只读（read only）。
Output Iterator：唯写（write only）。
Forward Iterator：允许「写入型」算法（例如replace()）在此种迭代器所形成的区间上做读写动作。
Bidirectional Iterator：可双向移动。某些算法需要逆向走访某个迭代器区间（例如逆向拷贝某范围内的元素），就可以使用 Bidirectional Iterators。
Random Access Iterator：前四种迭代器都只供应一部份指标算术能力（前三种支持operator++，第四种再加上operator–），第五种则涵盖所有指标算术能力，包括p+n, p-n, p[n], p1-p2, p1<p2。

这些迭代器的分类与从属关系，可以用下图表示。直线与箭头代表的并非 C++ 的继承关系，而是所谓concept（概念）与refinement（强化）的关系。

设计算法时，如果可能，我们尽量针对图中的某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义，这样才能在不同情况下提供最大效率。研究STL 的过程中，每一分每一秒我们都要明确，效率是个重要课题。假设有个算法可接受Forward Iterator，你以Random Access Iterator喂给它，它当然也会接受，因为一个Random Access Iterator必然是一个Forward Iterator（如图）。但是可用并不代表最佳！

以 advanced()为例

拿advance() 来说（这是许多算法内部常用的一个函式），此函式有两个参数，迭代器p和数值n；函式内部将p累进n次（前进n距离）。下面有三份定义，一份针对Input Iterator，一份针对Bidirectional Iterator，另一份针对Random Access Iterator。倒是没有针对ForwardIterator而设计的版本，因为那和针对InputIterator而设计的版本完全一致。

template <class InputIterator, class Distance> 
void advance_II(InputIterator& i, Distance n) 
{ 
// 单向，逐一前进
 while (n--) ++i; //或写 for ( ; n > 0; --n, ++i );
} 
template <class BidirectionalIterator, class Distance> 
void advance_BI(BidirectionalIterator& i, Distance n) 
{ 
// 双向，逐一前进
 if (n >= 0) 
 while (n--) ++i; 
 else 
 while (n++) --i; 
} 
//或写 for ( ; n > 0; --n, ++i ); 
//或写 for ( ; n < 0; ++n, --i ); 
template <class RandomAccessIterator, class Distance> 
void advance_RAI(RandomAccessIterator& i, Distance n) 
{ 
// 双向，跳跃前进
 i += n; 
}

现在，当程序呼叫 advance()，应该选用（呼叫）哪一份函式定义呢？如果选择advance_II()，对Random Access Iterator而言极度缺乏效率，原本O(1)的操作竟成为O(N)。如果选择advance_RAI()，则它无法接受Input Iterator。我们需要将三者合一，下面是一种作法：

template <class InputIterator, class Distance> 
void advance(InputIterator& i, Distance n) 
{ 
 if (is_random_access_iterator(i)) //此函式有待设计
	advance_RAI(i, n); 
 else if (is_bidirectional_iterator(i))//此函式有待设计
	advance_BI(i, n); 
 else 
	advance_II(i, n); 
}

但是像这样在执行时期才决定使用哪一个版本，会影响程序效率。最好能够在编译期就选择正确的版本。多载化函式机制可以达成这个目标：

前述三个advance_xx()都有两个函式参数，型别都未定（因为都是 template参数）。为了令其同名，形成多载化函式，我们必须加上一个型别已确定的函式参数，使函式多载化机制得以有效运作起来。

设计考虑如下：如果traits有能力萃取出迭代器的种类，我们便可利用这个「迭代器类型」相应型别做为advanced()的第三参数。这个相应型别一定必须是个class type，不能只是数值号码类的东西，因为编译器需仰赖它（一个型别）来进行多载化决议程序（overloaded resolution）。下面定义五个 classes，代表五种迭代器类型：

//五个做为标记用的型别（tag types）
struct input_iterator_tag { }; 
struct output_iterator_tag { }; 
struct forward_iterator_tag : public input_iterator_tag { }; //继承，见后面的分析
struct bidirectional_iterator_tag : public forward_iterator_tag { }; //继承
struct random_access_iterator_tag : public bidirectional_iterator_tag { };//继承

这些 classes只做为标记用，所以不需要任何成员。至于为什么运用继承机制，稍后再解释。现在重新设计 __advance()（由于只在内部使用，所以函式名称加上特定的前导符），并加上第三参数，使它们形成多载化：

template <class InputIterator, class Distance> 
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) 
{ 
// 单向，逐一前进
 while (n--) ++i; 
} 
//这是一个单纯的转呼叫函式（trivial forwarding function）。稍后讨论如何免除之。
template <class ForwardIterator, class Distance> 
inline void __advance(ForwardIterator& i, Distance n, forward_iterator_tag) 
{ 
// 单纯地进行转呼叫（forwarding），注：可以透过继承消除，直接做InputIterator版的，这个ForwardIterator版可以不写
 advance(i, n, input_iterator_tag()); 
} 
template <class BidiectionalIterator, class Distance> 
inline void __advance(BidiectionalIterator& i, Distance n, bidirectional_iterator_tag) 
{ 
// 双向，逐一前进
 if (n >= 0) 
 while (n--) ++i; 
 else 
 while (n++) --i; 
} 
template <class RandomAccessIterator, class Distance> 
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
{ 
// 双向，跳跃前进
 i += n; 
}

注意上述语法，每个 __advance()的最后一个参数都只宣告型别，并未指定参数名称，因为它纯粹只是用来启动多载化机制，函式之中根本不使用该参数。如果硬要加上参数名称也可以，画蛇添足罢了。

行进至此，还需要一个对外开放的上层控制介面，呼叫上述各个多载化的__advance()。此一上层介面只需两个参数，当它准备将工作转给上述的__advance()时，才自行加上第三自变量：迭代器类型。因此，这个上层函式必须有能力从它所获得的迭代器中推导出其类型—这份工作自然是交给 traits 机制：

template <class InputIterator, class Distance> 
inline void advance(InputIterator& i, Distance n) 
{ 
 __advance(i, n, iterator_traits<InputIterator>::iterator_category());//括号是为了产生暂时对象，否则只是一个类型名称
}

注意上述语法，iterator_traits<Iterator>::iterator_category() 将产生一个暂时对象（道理就像 int()会产生一个 int 暂时对象一样），其型别应该隶属前述五个迭代器类型之一。然后，根据这个型别，编译器才决定呼叫哪一个__advance()多载函式。

因此，为了满足上述行为，traits必须再增加一个相应型别：

template <class I> 
struct iterator_traits { 
 ... 
 typedef typename I::iterator_category iterator_category; //新增加的
}; 
//针对原生指标而设计的「偏特化版（partial specialization）」
template <class T> 
struct iterator_traits<T*> { 
 ... 
// 注意，原生指标是一种 Random Access Iterator
 typedef random_access_iterator_tag iterator_category; //新增加的
}; 
//针对原生的 pointer-to-const 而设计的「偏特化版（partial specialization）」
template <class T> 
struct iterator_traits<const T*> 
 ... 
// 注意，原生的 pointer-to-const是一种 Random Access Iterator
 typedef random_access_iterator_tag iterator_category; //新增加的
};

任何一个迭代器，其类型永远应该落在「该迭代器所隶属之各种类型中，最强化的那个」。例如int*既是Random Access Iterator又是 Bidirectional Iterator，同时也是Forward Iterator，而且也是Input Iterator，那么，其类型应该归属为random_access_iterator_tag。

你是否注意到advance()的 template参数名称取得好像不怎么理想：

1 2	template <class InputIterator, class Distance> inline void advance(InputIterator& i, Distance n);

按说advanced()既然可以接受各种类型的迭代器，就不应将其型别参数命名为InputIterator。这其实是 STL 算法的一个命名规则：以算法所能接受之最低阶迭代器类型，来为其迭代器型别参数命名。（注：毕竟只是命名，传入之后可以自动推导类型）

**消除「单纯转呼叫函式」 **

以 class 来定义迭代器的各种分类标签，不仅可以促成多载化机制的成功运作（使编译器得以正确执行多载化决议程序，overloaded resolution），另一个好处是，透过继承，我们可以不必再写「单纯只做转呼叫」的函式（例如前述的advance() ForwardIterator版）。考虑下面这个小例子，从其输出结果可以看出端倪：

// file: 3tag-test.cpp 
//模拟测试 tag types继承关系所带来的影响。
#include <iostream> 
using namespace std; 
struct B { }; 
struct D1 : public B { }; 
// B 可比拟为 InputIterator 
// D1 可比拟为 ForwardIterator 
struct D2 : public D1 { }; // D2 可比拟为 BidirectionalIterator 
template <class I> 
func(I& p, B) 
{ cout << "B version" << endl; } 
template <class I> 
func(I& p, D2) 
{ cout << "D2 version" << endl; } 
int main() 
{ 
 int* p; 
 func(p, B()); // 参数与自变量完全吻合。输出: "B version" 
 func(p, D1()); // 参数与自变量未能完全吻合；因继承关系而自动转呼叫。输出:"B version" 
 func(p, D2()); // 参数与自变量完全吻合。输出: "D2 version"
}

以 distance()为例

关于「迭代器类型标签」的应用，以下再举一例。distance() 也是常用的一个迭代器操作函式，用来计算两个迭代器之间的距离。针对不同的迭代器类型，它可以有不同的计算方式，带来不同的效率。整个设计模式和前述的advance()如出一辙：

template <class InputIterator> 
inline iterator_traits<InputIterator>::difference_type 
__distance(InputIterator first, InputIterator last,  input_iterator_tag) { 
 iterator_traits<InputIterator>::difference_type n = 0; 
// 逐一累计距离
 while (first != last) { 
 ++first; ++n; 
 } 
 return n; 
} 
template <class RandomAccessIterator> 
inline iterator_traits<RandomAccessIterator>::difference_type 
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { 
 // 直接计算差距
 return last - first; 
} 
template <class InputIterator> 
inline iterator_traits<InputIterator>::difference_type 
distance(InputIterator first, InputIterator last) { 
 typedef typename iterator_traits<InputIterator>::iterator_category category; 
 return __distance(first, last, category()); 
}

注意，distance()可接受任何类型的迭代器；其 template型别参数之所以命名为InputIterator，是为了遵循STL 算法的命名规则：以算法所能接受之最初级类型来为其迭代器型别参数命名。

此外也请注意，由于迭代器类型之间存在着继承关系，「转呼叫（forwarding）」的行为模式因此自然存在——这一点已在前一节讨论过。换句话说，当客端呼叫distance()并使用 Output Iterators 或 Forward Iterators 或Bidirectional Iterators，统统都会转呼叫 Input Iterator版的那个__distance() 函式。（注：这时因为有继承，就不用对这3类迭代器写单纯的呼叫函数了）

std::iterator 的保证

为了符合规范，任何迭代器都应该提供五个内嵌相应型别，以利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 Referencereference; 
};

iterator class不含任何成员，纯粹只是型别定义，所以继承它并不会招致任何额外负担。由于后三个参数皆有默认值，新的迭代器只需提供前两个参数即可。

先前的 ListIter，如果改用正式规格，应该这么写：

template <class Item> 
struct ListIter : 
 public std::iterator<std::forward_iterator_tag, Item> 
{ ... }

iterator 源码完整重列

以下重新列出 SGI STL <stl_iterator.h>头文件内与本章相关的程序代码。

//节录自 SGI STL <stl_iterator.h> 
//五种迭代器类型
struct input_iterator_tag {}; 
struct output_iterator_tag {}; 
struct forward_iterator_tag : public input_iterator_tag {}; 
struct bidirectional_iterator_tag : public forward_iterator_tag {}; 
struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 
//为避免写码时挂一漏万，自行开发的迭代器最好继承自下面这个 std::iterator 
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; 
}; 
//「萃取机」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; 
}; 
//针对原生指标（native pointer）而设计的 traits 偏特化版。
template <class T> 
struct iterator_traits<T*> { 
 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 而设计的 traits 偏特化版。
template <class T> 
struct iterator_traits<const T*> { 
 typedef random_access_iterator_tag iterator_category;  
 typedef T value_type; 
 typedef ptrdiff_t difference_type; 
 typedef const T* pointer; 
 typedef const T& reference; 
}; 

//这个函式可以很方便地决定某个迭代器的类型（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); 
} 
//以下是整组 distance 函式
template <class InputIterator> 
inline iterator_traits<InputIterator>::difference_type 
__distance(InputIterator first, InputIterator last, input_iterator_tag) { 
 iterator_traits<InputIterator>::difference_type n = 0; 
 while (first != last) { 
 ++first; ++n; 
 } 
 return n; 
}
template <class RandomAccessIterator> 
inline iterator_traits<RandomAccessIterator>::difference_type 
__distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { 
 return last - first;
} 
template <class InputIterator> 
inline iterator_traits<InputIterator>::difference_type 
distance(InputIterator first, InputIterator last) { 
 typedef typename iterator_traits<InputIterator>::iterator_category category; 
 return __distance(first, last,category()); 
}
//以下是整组 advance函式
template <class InputIterator, class Distance> 
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) { 
 while (n--) ++i; 
} 
template <class BidirectionalIterator, class Distance> 
inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) { 
 if (n >= 0) 
 while (n--) ++i; 
 else 
 while (n++) --i; 
} 
template <class RandomAccessIterator, class Distance> 
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) { 
 i += n; 
} 
template <class InputIterator, class Distance> 
inline void advance(InputIterator& i, Distance n) { 
__advance(i, n, iterator_category(i)); 
}

SGI STL 的私房菜： __type_traits （选看）

traits编程技法很棒，适度弥补了 C++ 语言本身的不足。STL只对迭代器加以规范，制定出iterator_traits这样的东西。SGI 把这种技法进一步扩大到迭代器以外的世界，于是有了所谓的**__type_traits。双底线前缀词意指这是SGI STL 内部所用的东西，不在 STL 标准规范之内**。

iterator_traits负责萃取迭代器的特性，__type_traits 则负责萃取型别（type）的特性。此处我们所关注的型别特性是指：这个型别是否具备non-trivial defalt ctor ？是否具备 non-trivial copy ctor？是否具备 non-trivialassignment operator？是否具备 non-trivialdtor？如果答案是否定的，我们在对这个型别进行建构、解构、拷贝、赋值等动作时，就可以采用最有效率的措施（例如根本不唤起那些constructor, destructor），而采用内存直接处理动作如malloc()、memcpy()等等，获得最高效率。这对于大规模而动作频繁的容器，有着显著的效率提升。

定义于 SGI <type_traits.h>中的__type_traits，提供了一种机制，允许针对不同的型别属性（type attributes），在编译时期完成函式派送决定（function dispatch）。这对于撰写 template很有帮助，例如，当我们准备对一个「元素型别未知」的数组执行 copy 动作时，如果我们能事先知道其元素型别是否有一个 trivial copy constructor ，便能够帮助我们决定是否可使用快速的memcpy()或memmove()。

从iterator_traits得来的经验，我们希望，程式之中可以这样运用__type_traits<T>，T代表任意型别：

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

我们希望上述式子响应我们「真」或「假」（以便我们决定采取什么策略），但其结果不应该只是个bool值，应该是个有着真/假性质的「对象」，因为我们希望利用其响应结果来进行自变量推导，而编译器只有面对 class object形式的自变量，才会做自变量推导。为此，上述式子应该传回这样的东西：

1 2	struct __true_type { }; struct __false_type { };

这两个空白 classes没有任何成员，不会带来额外负担，却又能够标示真假，满足我们所需。

为了达成上述五个式子， __type_traits内必须定义一些typedefs，其值不是__true_type就是__false_type。下面是 SGI的作法：

template <class type> 
struct __type_traits
 typedef __true_type this_dummy_member_must_be_first; 
 /* 不要移除这个成员。它通知「有能力自动将 __type_traits 特化」
的编译器说，我们现在所看到的这个 __type_traits template 是特
殊的。这是为了确保万一编译器也使用一个名为 __type_traits而其
实与此处定义并无任何关联的 template 时，所有事情都仍将顺利运作。
*/ 
 /* 以下条件应被遵守，因为编译器有可能自动为各型别产生专属的 __type_traits 
特化版ᴀ：
 - 你可以重新排列以下的成员次序
 - 你可以移除以下任何成员
 - 绝对不可以将以下成员重新命名而却没有改变编译器中的对应名称
 - 新加入的成员会被视为一般成员，除非你在编译器中加上适当支持。*/ 
 typedef __false_type has_trivial_default_constructor; 
 typedef __false_type has_trivial_copy_constructor; 
 typedef __false_type has_trivial_assignment_operator; 
 typedef __false_type has_trivial_destructor; 
 typedef __false_type is_POD_type; 
};

为什么SGI 把所有内嵌型别都定义为__false _type呢？是的，SGI 定义出最保守的值，然后（稍后可见）再针对每一个纯量型别（scalar types）设计适当的__type_traits特化版本，这样就解决了问题。

上述 __type_traits可以接受任何型别的自变量，五个typedefs将经由以下管道获得实值：

一般具现体（general instantiation），内含对所有型别都必定有效的保守值。上述各个has_trivial_xxx型别都被定义为__false_type，就是对所有型别都必定有效的保守值。经过宣告的特化版本，例如<type_traits.h> 内对所有 C++纯量型别（scalar types）提供了对映的特化宣告。这里源码不做展示了。

__types_traits在SGI STL中的应用很广。下面我举几个实例。第一个例子是uninitialized_fill_n()全域函式：

template <class ForwardIterator, class Size, class T> 
inline ForwardIteratoruninitialized_fill_n(ForwardIterator first, 
 Size n, const T& x) { 
 return __uninitialized_fill_n(first, n, x, value_type(first)); 
}

此函式以 x为蓝本，自迭代器first开始建构 n个元素。为求取最大效率，首先以value_type()萃取出迭代器first的value type，再利用__type_traits判断该型别是否为 POD型别：

template <class ForwardIterator, class Size, class T, class T1> 
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n, const T& x, T1*) 
{ 
 typedef typename __type_traits<T1>::is_POD_type is_POD; 
 return __uninitialized_fill_n_aux(first, n, x, is_POD()); 
}

以下就「是否为 POD型别」采取最适当的措施：

//如果不是 POD型别，就会派送（dispatch）到这里
template <class ForwardIterator, class Size, class T> 
ForwardIterator 
__uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __false_type) { 
 ForwardIterator cur = first; 
// 为求阅读顺畅简化，以下将原本有的异常处理（exception handling）去除。
 for ( ; n > 0; --n, ++cur) 
	construct(&*cur, x); 
 return cur; 
} 
//如果是 POD型别，就会派送（dispatch）到这里。下两行是原文件所附注解。
//如果 copy construction等同于 assignment，而且有 trivial destructor，
//以下就有效。
template <class ForwardIterator, class Size, class T> 
inline ForwardIterator 
__uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __true_type) { 
 return fill_n(first, n, x);//交由高阶函式执行，如下所示。
}
//以下是定义于 <stl_algobase.h> 中的 fill_n() 
template <class OutputIterator, class Size, class T> 
OutputIteratorfill_n(OutputIterator first, Size n, const T& value) { 
 for ( ; n > 0; --n, ++first) 
 *first = value; 
 return first; 
}

因此如果你是 SGI STL的使用者，你可以在自己的程式中充份运用这个__type_traits。假设我自行定义了一个Shape class，__type_traits 会对它产生什么效应？如果编译器够厉害（例如Silicon Graphics 的N32 和 N64 编译器），你会发现，__type_traits针对Shape萃取出来的每一个特性，其结果将取决于我的Shape是否有 trivialdefalt ctor或trivialcopy ctor或trivial assignment operator或 trivialdtor而定。但对大部份缺乏这种特异功能的编译器而言，__type_traits 针对 Shape 萃取出来的每一个特性都是__false_type ，即使Shape是个 POD型别。这样的结果当然过于保守，但是别无选择，除非我针对 Shape，自行设计一个__type_traits 特化版本，明白地告诉编译器以下事实（举例）：

template<>struct __type_traits<Shape> { 
 typedef __true_type has_trivial_default_constructor; 
 typedef __false_type has_trivial_copy_constructor; 
 typedef __false_type has_trivial_assignment_operator; 
 typedef __false_type has_trivial_destructor; 
 typedef __false_type is_POD_type; 
};

究竟一个 class什么时候该有自己的 non-trivial default constructor, non-trivial copy constructor, non-trivial assignment operator, non-trivial destructor 呢？一个简单的判断准则是：如果 class 内含指标成员，并且对它进行内存动态配置，那么这个class就需要实作出自己的 non-trivial-xxx。

即使你无法全面针对你自己定义的型别，设计__type_traits特化版本，无论如何，至少，有了这个__type_traits之后，当我们设计新的泛型算法时，面对C++纯量型别，便有足够的信息决定采用最有效的拷贝动作或赋值动作—因为每一个纯量型别都有对应的__type_traits 特化版ᴀ，其中每一个 typedef 的值都是__true_type。

总结

这章主要介绍迭代器，迭代器是一个行为类似指针的对象，重载了*和->的动作。特别的，关于重载*，涉及到了左值和右值，这里*动作提领的内容是允许赋值的，因此是左值，故而operator函数需要返回的类型是T&，是引用，否则只是创建了临时对象（可以作为右值）。迭代器为了走访容器，要重载++动作；为了判别元素，要重载==、！=动作。

在算法中，可能需要临时对象，其类型是迭代器指向对象的类型，这就需要能够根据迭代器知道这个类型。函数模板可以自动推导类型，然而这仅能推导一种类型，并且无法推导返回类型。使用traits编程技法可以更加全面。基本思想是在迭代器类内定义好类型（比如value_type），因为迭代器的模板T就告知了这样的类型。那么在算法内就可以使用这个由迭代器定义出的类型。但不是所有类型都可以自己来定义，原生类（如int）就没办法。因此需要traits来进行中间介入：使用模板偏特化。如果是自己定义的类，那么traits出来的就是类定义的value_type，如果是原生指针T*或const指针（会进入偏特化版而不使用泛化版），则萃取出来的是指针原类型T。

进一步，迭代器也有自己的类型，不同类型支持不同的操作，对算法而言一个确定的类型可以拥有最好的效率。与前面一样，可以每个迭代器定义自己的tag，用来选择执行算法不同的版本。然而为了在编译时就确定执行哪个版本（而不是用if这种，在运行才确定），要使用函数多载化，具体就是用tag作为一个新的参数，这个参数没有名称，纯粹用来选择版本，传入时加括号产生临时对象即可。依然有偏特化版本，原生指针是Random Access Iterator。

然后，为了避免单纯转呼叫动作，比如forward迭代器版本也用的是input迭代器版本的算法，如果只按上面的讨论，forward迭代器版本的算法要转呼叫input迭代器的算法。通过继承可以省去这一步，如果forward版本未定义，发现其父类input版本有定义，就自动执行input版本。这个继承被允许是因为高层级的迭代器都支持低层级迭代器的操作，呼叫低层级迭代器算法不会有冲突。再者，因为要用继承，因此tag必须是一个类（class或strut），这些tag类是预定义好的。为了方便迭代器设计，可以继承std::iterator这个类。

最后，SGI STL不只使用了5个type的traits，扩展到了更大的范围，不过原理是一样的，作用依然是提高效率。

序列式容器

容器的概观与分类

研究数据的特定排列方式，以利搜寻或排序或其它特殊目的，这一专门学科我们称为数据结构（Data Structures）。大学信息相关教育里头，与编程最有直接关系的科目，首推数据结构与算法（Algorithms）。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。STL 容器即是将运用最广的一些数据结构实作出来。

常用的数据结构不外乎 array（数组）、list（串行）、tree（树）、stack （堆栈）、queue（队列）、hash table（杂凑表）、set（集合）、map（映像表）等等。根据「资料在容器中的排列」特性，这些数据结构分为序列式（sequence）和关系型（associative）两种。

序列式容器（sequential containers）

所谓序列式容器，其中的元素都可序（ordered），但未排序（sorted）。C++ 语言本身提供了一个序列式容器array，STL另外再提供vector,list,deque, stack,queue,priority-queue等等序列式容器。其中stack和queue由于只是将deque改头换面而成，技术上被归类为一种配接器（adapter），但仍把它们放在本章讨论。本章将带你仔细看过各种序列式容器的关键实作细节。

vector

vector 概述

vector的数据安排以及操作方式，与array非常像似。两者的唯一差别在于空间的运用弹性。array是静态空间，一旦配置了就不能改变；如果要换个大（或小）一点的空间，一切细琐需由客端自己来：首先配置一块新空间，然后将元素从旧址一一搬往新址，然后再把原来的空间释还给系统。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的樽节与运用弹性有很大的帮助，我们再也不必因为害怕空间不足而一开始就要求一个大块头array了，我们可以安心使用vector，需要多少用多少。

vector的实作技术，关键在于其对大小的控制以及重新配置时的数据搬移效率。

一旦vector旧有空间满载，如果客端每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓扩充空间（不论多大），是「配置新空间 /数据搬移 /释还旧空间」的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。

vector 定义式摘要

以下是vector定义式的源码摘录。虽然 STL规定，欲使用vector者必须先含入<vector>，但 SGI STL 将vector实作于更底层的<stl_vector.h>。

// alloc是 SGI STL的空间配置器，见第二章。
template <class T, class Alloc = alloc> 
class vector { 
public: 
 // vector 的内嵌型别定义
 typedef T value_type; 
 typedef value_type* pointer; 
 typedef value_type* iterator; 
 typedef value_type& reference; 
 typedef size_t size_type; 
 typedef ptrdiff_t difference_type; 
protected:
 // 以下，simple_alloc 是 SGI STL的空间配置器，见 2.2.4节。
 typedef simple_alloc<value_type,Alloc> data_allocator; 
 iterator start; 
 iterator finish; 
 //表示目前使用空间的头
 //表示目前使用空间的尾
 iterator end_of_storage; //表示目前可用空间的尾
 void insert_aux(iterator position, const T& x); 
 void deallocate() { 
 if (start) 
 data_allocator::deallocate(start, end_of_storage - start); 
 } 
 void fill_initialize(size_type n, const T& value) { 
 start = allocate_and_fill(n, value); 
 finish = start + n; 
 end_of_storage = finish; 
 } 
public: 
 iterator begin() { return start; } 
 iterator end() { return finish; } 
 size_type size() const { return size_type(end() - begin()); } 
 size_type capacity() const { 
 return size_type(end_of_storage - begin()); } 
 bool empty() const { return begin() == end(); } 
 reference operator[](size_type n) { return *(begin() + n); } 
 //构造函数
 vector() : start(0), finish(0), end_of_storage(0) {} 
 vector(size_type n, const T& value) {fill_initialize(n, value); } 
 vector(int n, const T& value) { fill_initialize(n, value); } 
 vector(long n, const T& value) { fill_initialize(n, value); } 
 explicit vector(size_type n) { fill_initialize(n, T()); } //注：T()产生临时对象
 ~vector() {
 destroy(start, finish); //全域函式，见 2.2.3节。注：消除元素
 deallocate(); // 这是 vector 的一个 member function 。注：回收内存
 } 

 reference front() { return *begin(); } //第一个元素
 reference back() { return *(end() - 1); }//最后一个元素
 void push_back(const T& x) { 
 if (finish != end_of_storage) { 
 //将元素安插至最尾端
 construct(finish, x); //全域函式，见 2.2.3节。注：这里内存已经有了，直接建构元素
 ++finish; 
 } 
 else 
 insert_aux(end(), x); // 这是 vector 的一个 member function 
 } 

 void pop_back() { //将最尾端元素取出
  --finish; 
 destroy(finish); //全域函式，见 2.2.3节。
 } 

 iterator erase(iterator position) { //清除某位置上的元素
 if (position + 1 != end()) //注：如果不是最后一个元素
 	copy(position + 1, finish, position);//后续元素往前搬移
 --finish; 
 destroy(finish); //全域函式，见 2.2.3节。
 return position; 
 } 

 void resize(size_type new_size, const T& x) { 
 if (new_size < size()) 
 erase(begin() + new_size, end()); 
 else 
 insert(end(), new_size - size(), x); 
 } 
 void resize(size_type new_size) {resize(new_size, T()); } 
 void clear() { erase(begin(), end()); } 
protected: 
 // 配置空间并填满内容
 iterator allocate_and_fill(size_type n, const T& x) { 
 	iterator result =data_allocator::allocate(n); //分配内存
 	uninitialized_fill_n(result, n, x); // 全域函式，见 2.3 节
 return result; 
 }

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 的迭代器是普通指针
... 
};

根据上述定义，如果客端写出这样的码：

1 2	vector<int>::iterator ivite; vector<Shape>::iterator svite;

ivite的型别其实就是int*，svite的型别其实就是 Shape*。

vector 的数据结构

vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端：

template <class T, classAlloc = alloc> 
class vector { 
... 
protected: 
 iterator start; //表示目前使用空间的头
 iterator finish; //表示目前使用空间的尾
 iterator end_of_storage; //表示目前可用空间的尾，注意“使用”与“可用”之间的差别
... 
};

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

运用start, finish, end_of_storage三个迭代器，便可轻易提供首尾标示、大小、容量、空容器判断、注标（[ ]）运算子、最前端元素值、最后端元素值…等机能：

template <class T, classAlloc = alloc> 
class vector { 
... 
public: 
 iterator begin() { return start; } 
 iterator end() { return finish; } 
 size_type size() const { return size_type(end() - begin()); } 
 size_type capacity() const { 
 return size_type(end_of_storage - begin()); } 
 bool empty() const { return begin() == end(); } 
 reference operator[](size_type n) { return*(begin() + n); } //重载[]运算
 reference front() { return *begin(); }
 reference back() { return *(end() - 1); } 
 ... 
 };

大致的示意图如下：

vector 的建构与内存管理：constructor, push_back

下面是个小小的测试程序，观察重点在建构的方式、元素的添加，以及大小、容量的变化：

// filename : 4vector-test.cpp 
#include <vector> 
#include <iostream> 
#include <algorithm>
using namespace std;
int main() 
{ 
 int i; 
vector<int> iv(2,9); 
 cout << "size=" << iv.size() << endl; // size=2 
 cout << "capacity=" << iv.capacity() << endl; // capacity=2
iv.push_back(1); 
 cout << "size=" << iv.size() << endl; // size=3 
 cout << "capacity=" << iv.capacity() << endl; // capacity=4
iv.push_back(2); 
 cout << "size=" << iv.size() << endl; // size=4 
 cout << "capacity=" << iv.capacity() << endl; // capacity=4
iv.push_back(3); 
 cout << "size=" << iv.size() << endl; // size=5 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
iv.push_back(4); 
 cout << "size=" << iv.size() << endl; // size=6 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
 for(i=0; i<iv.size(); ++i) 
 cout << iv[i] << ' '; // 9 9 1 2 3 4 
 cout << endl; 
iv.push_back(5); 
 cout << "size=" << iv.size() << endl; // size=7 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
 for(i=0; i<iv.size(); ++i) 
 cout << iv[i] << ' '; // 9 9 1 2 3 4 5 
 cout << endl; 
iv.pop_back(); 
iv.pop_back(); 
 cout << "size=" << iv.size() << endl; // size=5 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
iv.pop_back(); 
 cout << "size=" << iv.size() << endl; // size=4 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
 vector<int>::iterator ivite =find(iv.begin(), iv.end(), 1); 
 if (ivite)iv.erase(ivite);
 cout << "size=" << iv.size() << endl; // size=3 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
 for(i=0; i<iv.size(); ++i) 
 cout << iv[i] << ' '; // 9 9 2 
 cout << endl; 
 ite =find(ivec.begin(), ivec.end(), 2); 
 if (ite) ivec.insert(ite,3,7); 
 cout << "size=" << iv.size() << endl; // size=6 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
 for(int i=0; i<ivec.size(); ++i) 
 cout << ivec[i] << ' '; // 9 9 7 7 7 2 
 cout << endl; 
iv.clear(); 
 cout << "size=" << iv.size() << endl; // size=0 
 cout << "capacity=" << iv.capacity() << endl; // capacity=8
}

vector预设使用alloc（第二章）做为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位：

template <class T, class Alloc = alloc> 
class vector { 
protected: 
// simple_alloc<> 见 2.2.4 节
 typedef simple_alloc<value_type,Alloc> data_allocator; 
... 
};

于是，data_allocator::allocate(n)表示配置 n 个元素空间。

vector 提供许多constructors，其中一个允许我们指定空间大小及初值：

// 建构式，允许指定 vector 大小 n和初值 value 
vector(size_type n, const T& value) {fill_initialize(n, value); } 
// 充填并予初始化
 void fill_initialize(size_type n, const T& value) { 
 start =allocate_and_fill(n, value); 
 finish = start + n; //指向下一个空的位置
 end_of_storage = finish; 
 } 
// 配置而后充填
 iterator allocate_and_fill(size_type n, const T& x) {
 iterator result =data_allocator::allocate(n); // 配置 n 个元素空间
 uninitialized_fill_n(result, n, x); // 全域函式，见 2.3 节
 return result; 
 }

uninitialized_fill_n()会根据第一参数的型别特性（type traits，3.7 节），决定使用算法 fill_n()或反复呼叫 construct() 来完成任务（见 2.3 节描述）。

当我们以push_back()将新元素安插于vector 尾端，该函式首先检查是否还有备用空间？如果有就直接在备用空间上建构元素，并调整迭代器 finish，使 vector 变大。如果没有备用空间了，就扩充空间（重新配置、搬移数据、释放原空间）：

void push_back(const T& x) { 
 if (finish != end_of_storage) { //还有备用空间
	construct(finish, x); //全域函式，见 2.2.3节。
 	++finish; 
 } 
 else //已无备用空间
     insert_aux(end(), x); // vector member function，见以下列表
 } 
template <class T, class Alloc> 
void vector<T, Alloc>::insert_aux(iterator position, const T& x) { 
 if (finish != end_of_storage) {//还有备用空间
// 在备用空间起始处建构一个元素，并以 vector 最后一个元素值为其初值。
construct(finish, *(finish - 1)); 
// 调整水位。
 ++finish; 
 T x_copy = x; 
 copy_backward(position, finish - 2, finish - 1); 
     //不要被 copy_backward() 算法的名称所误导，它不会逆转元素的顺序。它只会像 copy() 那样复制元素，但是顺序是从最后一个元素开始直到第一个元素。
 *position = x_copy; 
 } 
 else { //已无备用空间
 const size_type old_size = size(); 
 const size_type len = old_size != 0 ? 2 * old_size : 1; 
 // 以上配置原则：如果原大小为 0，则配置 1（个元素大小）；
 // 如果原大小不为 0，则配置原大小的两倍，
 // 前半段用来放置原资料，后半段准备用来放置新资料。
 iterator new_start =data_allocator::allocate(len); //实际配置
 iterator new_finish = new_start; 
 try { //异常处理模型的trycatch
// 将原 vector 的内容拷贝到新 vector。
 new_finish = uninitialized_copy(start, position, new_start); //[start,position)，左闭右开
// 为新元素设定初值 x 
construct(new_finish, x); //new_finish=position位置，是原来尾巴的下一个未用空间
// 调整水位。
 ++new_finish;  
// 将原 vector 的备用空间中的内容也忠实拷贝过来(作者疑惑：啥用途？)
 new_finish =uninitialized_copy(position, finish, new_finish); 
     //个人理解：实际上这个函数是在某个位置上插入x，只是恰好也有扩充空间的作用，因而拿来push_back()中扩充；
     //如果再考虑插入的情况，position不是最后的位置，就需要把原来后面的元素再拷贝过来
 }
 catch(...) { 
// "commit or rollback" semantics. 
 destroy(new_start, new_finish); 
 data_allocator::deallocate(new_start, len); 
 throw; 
 } 
// 解构并释放原 vector 
 destroy(begin(), end()); 
 deallocate(); 
// 调整迭代器，指向新 vector 
 start = new_start; 
 finish = new_finish; 
 end_of_storage = new_start + len; 
 } 
}

注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后建构新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心。

vector 的元素操作：pop_back, erase, clear, insert

vector所提供的元素操作动作很多，无法在有限篇幅中一一讲解——其实也没有这种必要。为搭配先前对空间配置的讨论，这里挑选数个相关函式做为解说对象。这些函式也出现在先前的测试程序中。

// 将尾端元素拿掉，并调整大小。
 void pop_back() { 
 --finish; 
 destroy(finish); 
 } 
 //将尾端标记往前移一格，表示将放弃尾端元素。
 // destroy是全域函式，见第 2 章
 // 清除 [first,last) 中的所有元素
 iterator erase(iterator first, iterator last) { 
 iterator i = copy(last, finish, first);// copy 是全域函式，第 6 章
 destroy(i, finish);// destroy是全域函式，第 2 章
 finish = finish - (last - first); 
 return first; 
 }
// 清除某个位置上的元素
 iterator erase(iterator position) { 
 if (position + 1 != end()) 
 copy(position + 1, finish, position); // copy 是全域函式，第 6 章
 --finish; 
 destroy(finish); // destroy是全域函式，2.2.3 节
 return position; 
 } 
 void clear() { erase(begin(), end()); }// erase()就定义在上面

下图展示 erase(first, last)的动作。

下面是vector::insert()实作内容：

//从 position 开始，安插 n个元素，元素初值为 x 
template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) 
{ 
 if (n != 0) {// 当 n != 0 才进行以下所有动作
 if (size_type(end_of_storage - finish) >= n) 
 // 备用空间大于等于「新增元素个数」
 T x_copy = x; 
 // 以下计算安插点之后的现有元素个数
 const size_type elems_after = finish - position; 
 iterator old_finish = finish; 
 if (elems_after > n) 
 // 「安插点之后的现有元素个数」大于「新增元素个数」
 	uninitialized_copy(finish - n, finish, finish); //分两步后移n位腾出空间
 finish += n;//将 vector 尾端标记后移
 copy_backward(position, old_finish - n, old_finish); //注：使用这个函数，只需要知道这一段元素的结尾应该copy到哪个位置（因为是从后往前copy），而不需要知道开头位置，实际上开头位置也可以算出来，但使用这个函数就不需要计算
 fill(position, position + n, x_copy);//从安插点开始填入新值
 } 
 else { 
 // 「安插点之后的现有元素个数」小于等于「新增元素个数」
 uninitialized_fill_n(finish, n - elems_after, x_copy); //注：先把一些空间填上去先，而不是直接后移腾出空间（不过感觉差不多，因为要移动到的位置下面的finish也计算出来了）
 finish += n - elems_after; 
 uninitialized_copy(position, old_finish, finish); //再把余下占用元素后移
 finish += elems_after; 
 fill(position, old_finish, x_copy); 
 } 
 } 
 else { 
 // 备用空间小于「新增元素个数」（那就必须配置额外的内存）
 // 首先决定新长度：旧长度的两倍，或旧长度+新增元素个数。
 const size_type old_size = size(); 
 const size_type len = old_size + max(old_size, n); 
 // 以下配置新的 vector 空间
 iterator new_start = data_allocator::allocate(len); 
 iterator new_finish = new_start; 
 __STL_TRY { 
 // 以下首先将旧 vector的安插点之前的元素复制到新空间。
 new_finish = uninitialized_copy(start, position, new_start); 
 // 以下再将新增元素（初值皆为 n）填入新空间。
 new_finish = uninitialized_fill_n(new_finish, n, x); 
 // 以下再将旧 vector 的安插点之后的元素复制到新空间。
 new_finish = uninitialized_copy(position, finish, new_finish); 
 } 
# ifdef __STL_USE_EXCEPTIONS 
 catch(...) { 
 // 如有异常发生，实现 "commit or rollback" semantics. 
destroy(new_start, new_finish); 
data_allocator::deallocate(new_start, len); 
 throw; 
 } 
 # endif /* __STL_USE_EXCEPTIONS */
 // 以下清除并释放旧的 vector 
destroy(start, finish); 
deallocate(); 
// 以下调整水位标记
start = new_start; 
finish = new_finish;  
end_of_storage = new_start + len; 
} 
} 
}

注意，安插完成后，新节点将位于标兵迭代器（上例之 position，标示出安插点）所指之节点的前方—这是STL对于「安插动作」的标准规范。

list

list 概述

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

list和vector是两个最常被使用的容器。什么时机下最适合使用哪一种容器，必须视元素的多寡、元素的构造复杂度（有无 non-trivial copy constructor, non-trivial copy assignmen operator）、元素存取行为的特性而定。

list 的节点（node）

list本身和 list的节点是不同的结构，需要分开设计。以下是 STL list的节点（node）结构：

template <class T> 
struct __list_node { 
 typedef void* void_pointer; 
 void_pointer prev; //型别为 void*。其实可设为 __list_node<T>* 
 void_pointer next; 
 T data; 
};

显然这是一个双向串行（有前后指针）。

list 的迭代器

list不再能够像vector一样以普通指针做为迭代器，因为其节点不保证在储存空间中连续存在。list迭代器必须有能力指向list的节点，并有能力做正确的递增、递减、取值、成员存取…等动作。所谓「list迭代器正确的递增、递减、取值、成员取用」动作是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的值，成员取用时取用的是节点的成员。

由于STL list是一个双向串行（double linked-list），迭代器必须具备前移、后移的能力。所以list提供的是Bidirectional Iterators。

list有一个重要性质：安插动作（insert）和接合动作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vector的安插动作可能造成内存重新配置，导致原有的迭代器全部失效。甚至list的元素删除动作（erase），也只有「指向被删除元素」的那个迭代器失效，其它迭代器不受任何影响。

以下是list迭代器的设计：

template<class T, class Ref, class Ptr> 
struct __list_iterator { 
 typedef __list_iterator<T, T&, T*> iterator; 
 typedef __list_iterator<T, Ref, Ptr> self; //注：感觉self和iterator没多大区别？
 typedef bidirectional_iterator_tag iterator_category; 
 typedef T value_type; 
 typedef Ptr pointer; 
 typedef Ref reference; 
 typedef __list_node<T>* link_type; 
 typedef size_t size_type; 
 typedef ptrdiff_t difference_type; 
 link_type node; //迭代器内部当然要有一个指针，指向 list 的节点
// constructor 
 __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; } 
// 以下对迭代器取值（dereference），取的是节点的资料值。
 reference operator*() const { return (*node).data; } 
// 以下是迭代器的成员存取（member access）运算子的标准作法。
 pointer operator->() const { return &(operator*()); } //注：这个指针，指向data的地址，如果对它使用*就能取出值
// 对迭代器累加 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; 
 } 
};

list 的数据结构

SGI list不仅是一个双向串行，而且还是一个环状双向串行。所以它只需要一个指标，便可以完整表现整个串行：

template <class T, class Alloc = alloc>// 预设使用 alloc 为配置器
class list { 
protected: 
 typedef __list_node<T> list_node; 
public: 
 typedef list_node* link_type; 
protected: 
 link_type node;// 只要一个指标，便可表示整个环状双向串行
... 
};

如果让指标node指向刻意置于尾端的一个空白节点，node便能符合 STL对于「前闭后开」区间的要求，成为last迭代器。

示意图如下：

这么一来，以下几个函式便都可以轻易完成：

iterator begin() { return (link_type)((*node).next); } 
iterator end() { return node; } 
bool empty() const { return node->next == node; } 
size_type size() const { 
size_type result = 0; 
distance(begin(), end(), result); // 全域函式，第 3 章。
return result; 
} 
// 取头节点的内容（元素值）。
reference front() { return *begin(); } 
// 取尾节点的内容（元素值）。
reference back() { return *(--end()); }

list 的建构与内存管理：constructor, push_back, insert

下面是一个测试程序，观察重点在建构的方式以及大小的变化：

// filename : 4list-test.cpp 
#include <list> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
 int i; 
 list<int> ilist; 
 cout << "size=" << ilist.size() << endl; // size=0 
 ilist.push_back(0); 
 ilist.push_back(1); 
 ilist.push_back(2); 
 ilist.push_back(3); 
 ilist.push_back(4); 
 cout << "size=" << ilist.size() << endl; // size=5 
 list<int>::iterator ite; 
 for(ite = ilist.begin(); ite != ilist.end(); ++ite) 
 cout << *ite << ' '; // 0 1 2 3 4 
 cout << endl; 
 ite =find(ilist.begin(), ilist.end(), 3); 
 if (ite!=0) 
 ilist.insert(ite, 99); 
 cout << "size=" << ilist.size() << endl; // size=6 
 cout << *ite << endl; // 3 
 for(ite = ilist.begin(); ite != ilist.end(); ++ite) 
 cout << *ite << ' '; // 0 1 2 99 3 4 
 cout << endl; 
 ite =find(ilist.begin(), ilist.end(), 1); 
 if (ite!=0) 
 cout << *(ilist.erase(ite)) << endl; // 2 
 for(ite = ilist.begin(); ite != ilist.end(); ++ite) 
 cout << *ite << ' '; // 0 2 99 3 4 
 cout << endl; 
}

list预设使用alloc 做为空间配置器，并据此另外定义了一个list_node_allocator，为的是更方便地以节点大小为配置单位：

template <class T, class Alloc = alloc>// 预设使用 alloc 为配置器
class list { 
protected: 
 typedef __list_node<T> list_node; 
// 专属之空间配置器，每次配置一个节点大小：
 typedef simple_alloc<list_node, Alloc> list_node_allocator; 
... 
};

于是，list_node_allocator(n)表示配置n个节点空间。以下四个函式，分别用来配置、释放、建构、摧毁一个节点：

protected: 
 // 配置一个节点并传回
 link_type get_node() { return list_node_allocator::allocate(); } 
 // 释放一个节点
 void put_node(link_type p) { list_node_allocator::deallocate(p); } 

 // 产生（配置并建构）一个节点，带有元素值
 link_type create_node(const T& x) { 
 link_type p = get_node(); 
 construct(&p->data, x); //全域函式，建构/解构基本工具。
 return p; 
 } 
 // 摧毁（解构并释放）一个节点
 void destroy_node(link_type p) { 
 destroy(&p->data); //全域函式，建构/解构基本工具
 put_node(p);
 }

list提供有许多constructors，其中一个是default constructor，允许我们不指定任何参数做出一个空的list出来：

public: 
 list() {empty_initialize(); } //产生一个空串行。
protected: 
 void empty_initialize() 
 node =get_node(); //配置一个节点空间，令 node 指向它。
 node->next = node;//令 node头尾都指向自己，不设元素值。
 node->prev = node; 
 }

当我们以 push_back() 将新元素安插于 list 尾端，此函式内部呼叫insert()：

1	void push_back(const T& x) { insert(end(), x); }

insert()是一个多载化函式，有多种型式，其中最简单的一种如下，符合以上所需。首先配置并建构一个节点，然后在尾端做适当的指标动作，将新节点安插进去：

// 函式目的：在迭代器 position 所指位置安插一个节点，内容为 x。
 iterator insert(iterator position, const T& x) { 
 link_type tmp =create_node(x); //产生一个节点（设内容为 x）
 // 调整双向指标，使 tmp安插进去。
 tmp->next = position.node; //注：从这里可以看出是在position前面安插
 tmp->prev = position.node->prev; 
 (link_type(position.node->prev))->next = tmp; 
 position.node->prev = tmp; 
 return tmp; 
 }

注意，安插完成后，新节点将位于标兵迭代器（标示出安插点）所指之节点的前方——这是STL对于「安插动作」的标准规范。由于 list 不像 vector 那样有可能在空间不足时做重新配置、数据搬移的动作，所以安插前的所有迭代器在安插动作之后都仍然有效。

list 的元素操作

元素操作的手段包括：push_front, push_back, erase, pop_front, pop_back, clear, remove, unique, splice, merge, reverse, sort

list所提供的元素操作动作很多，无法在有限的篇幅中一一讲解——其实也没有这种必要。为搭配先前对空间配置的讨论，我挑选数个相关函式做为解说对象。先前示例中出现有尾部安插动作（push_back），现在我们来看看其它的安插动作和移除动作。

// 安插一个节点，做为头节点
 void push_front(const T& x) { insert(begin(), x); } 
// 安插一个节点，做为尾节点（上一小节才介绍过）
 void push_back(const T& x) { insert(end(), x); } 
// 移除迭代器 position 所指节点
 iterator erase(iterator position) { 
 link_type next_node = link_type(position.node->next); 
 link_type prev_node = link_type(position.node->prev); 
 prev_node->next = next_node; 
 next_node->prev = prev_node; 
 //跟换指针指向的操作都是四个动作
 destroy_node(position.node); 
 return iterator(next_node);
  } 
// 移除头节点
 void pop_front() { erase(begin()); } 
// 移除尾节点
 void pop_back() 
 iterator tmp = end(); 
 erase(--tmp); 
 } 
//清除所有节点（整个串行）
template <class T, class Alloc> 
void list<T, Alloc>::clear() 
{ 
 link_type cur = (link_type) node->next; // begin() 
 while (cur != node) {//巡访每一个节点
 link_type tmp = cur; 
 cur = (link_type) cur->next; 
 destroy_node(tmp); //摧毁（解构并释放）一个节点
 } 
// 恢复 node 原始状态
 node->next = node; 
 node->prev = node; 
}
//将数值为 value之所有元素移除
template <class T, class Alloc> 
void list<T, Alloc>::remove(const T& value) { 
 iterator first = begin(); 
 iterator last = end(); 
 while (first != last) {//巡访每一个节点
 iterator next = first; 
 ++next; 
 if (*first == value)erase(first); //找到就移除
 first = next; 
 } 
} 
//移除数值相同的连续元素。注意，只有「连续而相同的元素」，才会被移除剩一个。
template <class T, class Alloc> 
void list<T, Alloc>::unique() { 
 iterator first = begin(); 
 iterator last = end(); 
 if (first == last) return;//空串行，什么都不必做。
 iterator next = first; 
 while (++next != last) { //巡访每一个节点
 if (*first == *next) //如果在此区段中有相同的元素
 	erase(next); //移除之
 else
     first = next; //调整指标
 next = first; //修正区段范围
 } 
}

由于list是一个双向环状串行，只要我们把边际条件处理好，那么，在头部或尾部安插元素（push_front和push_back），动作几乎是一样的，在头部或尾部移除元素（pop_front和pop_back），动作也几乎是一样的。移除（erase）某个迭代器所指元素，只是做一些指标搬移动作而已，并不复杂。

list内部提供一个所谓的迁移动作（transfer）：将某连续范围的元素迁移到某个特定位置之前。技术上很简单，节点间的指标移动而已。这个动作为其它的复杂动作如splice, sort, merge等奠定良好的基础。下面是transfer的源码：

protected: 
 // 将 [first,last) 内的所有元素搬移到 position 之前。
 void transfer(iterator position, iterator first, iterator last) { 
 if (position != last) { 
 (*(link_type((*last.node).prev))).next = position.node; // (1) 
 (*(link_type((*first.node).prev))).next = last.node; // (2) 
 (*(link_type((*position.node).prev))).next = first.node; // (3) 
 link_type tmp = link_type((*position.node).prev); // (4)
 (*position.node).prev = (*last.node).prev; // (5)
 (*last.node).prev = (*first.node).prev; // (6)
 (*first.node).prev = tmp; // (7)
 } 
 }

以上七个动作，一步一步地显示于下图：

transfer所接受的[first,last)区间，是否可以在同一个list之中呢？答案是可以。你只要想象上图所画的两条lists其实是同一个list的两个区段，就不难得到答案了。

上述的 transfer并非公开界面。list公开提供的是所谓的接合动作（splice）：将某连续范围的元素从一个list搬移到另一个（或同一个）list的某个定点。如果接续先前 4list-test.cpp 程序的最后执行点，继续执行以下splice动作：

int iv[5] = { 5,6,7,8,9 }; 
 list<int> ilist2(iv, iv+5); 
 // 目前，ilist的内容为 0 2 99 3 4 
 ite = find(ilist.begin(), ilist.end(), 99); 
 ilist.splice(ite,ilist2); // 0 2 5 6 7 8 9 99 3 4
 ilist.reverse(); // 4 3 99 9 8 7 6 5 2 0 
 ilist.sort();// 0 2 3 4 5 6 7 8 9 99

很容易便可看出效果，接合动作技术上很简单，只是节点间的指标移动而已，这些动作已完全由transfer()做掉了。

为了提供各种接口弹性，list::splice有许多版本：

public: 
 // 将 x接合于 position 所指位置之前。x必须不同于 *this。
 void splice(iterator position, list& x) { 
 if (!x.empty()) 
transfer(position, x.begin(), x.end()); 
 } 
 // 将 i 所指元素接合于 position 所指位置之前。position 和 i 可指向同一个 list。
 void splice(iterator position, list&, iterator i) { 
 iterator j = i; 
 ++j; 
 if (position == i || position == j) return; 
transfer(position, i, j); 
 } 
 // 将 [first,last) 内的所有元素接合于 position所指位置之前。
 // position 和[first,last)可指向同一个 list，
 // 但 position 不能位于[first,last)之内。
 void splice(iterator position, list&, iterator first, iterator last) { 
 if (first != last) 
transfer(position, first, last); 
 }

以下是merge(), reverse(), sort()的源码。有了transfer()在手，这些动作都不难完成。

// merge()将 x合并到 *this身上。两个 lists 的内容都必须先经过递增排序。
template <class T, class Alloc> 
void list<T, Alloc>::merge(list<T, Alloc>& x) { 
 iterator first1 = begin(); 
 iterator last1 = end(); 
 iterator first2 = x.begin(); 
 iterator last2 = x.end(); 
 // 注意：前提是，两个 lists都已经过递增排序，
 while (first1 != last1 && first2 != last2) //注：如同归并排序的合并部分
 if (*first2 < *first1) { 
 iterator next = first2; 
 transfer(first1, first2, ++next); 
 first2 = next; 
 } 
 else 
 ++first1; 
 if (first2 != last2) transfer(last1, first2, last2); 
}

// reverse()将 *this的内容逆向重置
template <class T, class Alloc> 
void list<T, Alloc>::reverse() { 
 // 以下判断，如果是空白串行，或仅有一个元素，就不做任何动作。
 // 使用 size() == 0 || size() == 1来判断，虽然也可以，但是比较慢。
 if (node->next == node || link_type(node->next)->next == node) 
 return; 
 iterator first = begin(); 
 ++first; 
 while (first != end()) { 
 iterator old = first; 
 ++first; 
 transfer(begin(), old, first); //左闭右开，把第2个插到最前面，把第3个插到最前面...一直下去就倒序了
 } 
}

// list 不能使用 STL 算法 sort()，必须使用自己的 sort() member function，
//因为 STL 算法 sort() 只接受 RamdonAccessIterator. 
//本函式采用 quick sort. 
template <class T, class Alloc> 
void list<T, Alloc>::sort() { 
 // 以下判断，如果是空白串行，或仅有一个元素，就不做任何动作。
 // 使用 size() == 0 || size() == 1来判断，虽然也可以，但是比较慢。
 if (node->next == node || link_type(node->next)->next == node) 
 return; 
 // 一些新的 lists，做为中介数据存放区
 list<T, Alloc> carry; 
 list<T, Alloc> counter[64]; 
 int fill = 0; 
 while (!empty()) { 
 carry.splice(carry.begin(), *this, begin()); 
 int i = 0; 
 while(i < fill && !counter[i].empty()) { 
 counter[i].merge(carry); 
 carry.swap(counter[i++]); 
 } 
 carry.swap(counter[i]); 
 if (i == fill) ++fill; 
 } 
 for (int i = 1; i < fill; ++i) 
 counter[i].merge(counter[i-1]); 
swap(counter[fill-1]); 
}

vector和list对比总结

vector类似数组（不过是动态的）使用连续空间、普通指针，迭代器是随机访问类型的；list类似链表，使用分散的空间、节点指针，迭代器是双向串行类型的。vector只针对尾部操作，而list可以针对头部和尾部。

两者在内存配置有很大的差别，vector需要预先配置一块连续空间，有元素需求时再建构元素（这样建构效率高），但连续空间一旦空间不足就需要重新配置。list则是直接重新分配一个节点，包括空间配置和元素建构。

deque

deque 概述

vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。所谓双向开口，意思是可以在头尾两端分别做元素的安插和删除动作。vector当然也可以在头尾两端做动作（从技术观点），但是其头部动作效率奇差，无法被接受。（注：因为是连续空间，头部元素不能往前扩充，vector只能整体后移或整体前移）

deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的安插或移除动作，二在于deque没有所谓容量（capacity）观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样「因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间」这样的事情在deque是不会发生的。也因此，deque没有必要提供所谓的空间保留（reserve）功能。

虽然deque也提供Ramdon Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可以道里计（稍后看到源码，你便知道），这当然在在影响了各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对 deque进行的排序动作，为了最高效率，可将deque先完整复制到一个 vector 身上，将vector排序后（利用 STL sort算法），再复制回 deque。

deque 的中控器

deque是连续空间（至少逻辑看来如此），deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的界面。避开了「重新配置、复制、释放」的轮回，代价则是复杂的迭代器架构。

受到分段连续线性空间的字面影响，可能以为deque的实作复杂度和vector相比虽不中亦不远矣，其实不然。主要因为，既曰分段连续线性空间，就必须有中央控制，而为了维护整体连续的假象，数据结构的设计及迭代器前进后退等动作都颇为繁琐。deque的实作码份量远比vector或list都多得多。

deque采用一块所谓的map（注意，不是 STL 的map容器）做为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指标，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL允许我们指定缓冲区大小，默认值 0表示将使用 512 bytes缓冲区。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque { 
public: // Basic types 
 typedef T value_type; 
 typedef value_type* pointer; 
 ... 
protected: // Internal typedefs 
 // 元素的指针的指针（pointer of pointer of T）
 typedef pointer* map_pointer; 
protected: // Data members
 map_pointer map; //指向 map，map 是块连续空间，其内的每个元素
 // 都是一个指标（称为节点），指向一块缓冲区。
 size_type map_size;// map 内可容纳多少指标。
... 
};

map其实是一个T**，也就是说它是一个指标，所指之物又是一个指标，指向型别为T的一块空间

deque 的迭代器

deque是分段连续空间。维护其「整体连续」假象的任务，着落在迭代器的operator++和operator– 两个运算子身上。

让我们思考一下，deque迭代器应该具备什么结构。首先，它必须能够指出分段连续空间（亦即缓冲区）在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，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，所以必须自行撰写五个必要的迭代器相应型别（第 3 章）
 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;//此迭代器所指之缓冲区中的现行（current）元素
 T* first;//此迭代器所指之缓冲区的头
 T* last;//此迭代器所指之缓冲区的尾（含备用空间）
 map_pointer node;//指向管控中心
 ... 
};

其中用来决定缓冲区大小的函式buffer_size()，呼叫__deque_buf_size()，后者是个全域函式，定义如下：

//如果 n不为 0，传回 n，表示 buffer size 由使用者自定。
//如果 n为 0，表示 buffer size使用默认值，那么
//如果 sz（元素大小，sizeof(value_type)）小于 512，传回 512/sz，
//如果 sz 不小于 512，传回 1。
inline size_t __deque_buf_size(size_t n, size_t sz) 
{ 
 return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1)); 
}

deque的中控器、缓冲区、迭代器的相互关系如下图，中控器控制缓冲区，迭代器能控制缓冲区，也能获取中控器的信息。

假设现在我们产生一个deque<int>，并令其缓冲区大小为32，于是每个缓冲区可容纳 32/sizeof(int)=4 个元素。经过某些操作之后，deque 拥有 20 个元素，那么其begin()和end()所传回的两个迭代器应该如下图。这两个迭代器事实上一直保持在deque内，名为start和finish，稍后在deque数据结构中便可看到）。

20个元素需要 20/8 = 3 个缓冲区，所以map之内运用了三个节点。迭代器 start 内的 cur指标当然指向缓冲区的第一个元素，迭代器 finish内的 cur指标当然指向缓冲区的最后元素（的下一位置）。注意，最后一个缓冲区尚有备用空间。稍后如果有新元素要安插于尾端，可直接拿此备用空间来使用。

下面是deque迭代器的几个关键行为。由于迭代器内对各种指标运算都做了多载化动作，所以各种指标运算如加、减、前进、后退…都不能直观视之。其中最重点的关键就是：一旦行进时遇到缓冲区边缘，要特别当心，视前进或后退而定，可能需要呼叫set_node()跳一个缓冲区：

void set_node(map_pointer new_node) { 
node = new_node; 
first = *new_node; 
last = first + difference_type(buffer_size()); 
 } 
//以下各个多载化运算子是 __deque_iterator<> 成功运作的关键。
 reference operator*() const { return *cur; } 
 pointer operator->() const { return &(operator*()); }
 difference_type operator-(const self& x) const {  
 return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur); 
 }

 self&operator++() { 
 ++cur; //切换至下一个元素。
 if (cur == last) { //如果已达所在缓冲区的尾端，
 set_node(node + 1);//就切换至下一节点（亦即缓冲区）的第一个元素。
 cur = first; 
 } 
 return *this; 
 } 

 self operator++(int) {//后置式，标准写法
 self tmp = *this; 
 ++*this; 
 return tmp; 
 } 

 self&operator--() { 
 if (cur == first) { //如果已达所在缓冲区的头端，
 set_node(node - 1);//就切换至前一节点（亦即缓冲区）的最后一个元素。
 cur = last; 
 } 
 --cur; //切换至前一个元素。
 return *this; 
 } 

 self operator--(int) {//后置式，标准写法
 self tmp = *this; 
 --*this; 
 return tmp; 
 } 

 // 以下实现随机存取。迭代器可以直接跳跃 n个距离。
 self& operator+=(difference_type n) { 
 difference_type offset = n + (cur - first); 
 if (offset >= 0 && offset < difference_type(buffer_size())) 
 // 标的位置在同一缓冲区内
 	cur += n; 
 else { 
// 标的位置不在同一缓冲区内
 difference_type node_offset = 
 offset > 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / buffer_size()) - 1; 
// 切换至正确的节点（亦即缓冲区）
set_node(node + node_offset); 
// 切换至正确的元素
 cur = first + (offset - node_offset * difference_type(buffer_size())); 
 } 
 return *this; 
 }

 self operator+(difference_type n) const { 
 self tmp = *this; //*this不变
 return tmp += n; // 唤起 operator+= 
 }

 self&operator-=(difference_type n) { return *this+= -n; } 
 // 以上利用 operator+= 来完成 operator-= 
 // 参考More Effective C++, item22: Consider using op= instead of 
 // stand-alone op. 
 self operator-(difference_type n) const { 
 self tmp = *this; 
 return tmp -= n; // 唤起 operator-= 
 } 

 // 以下实现随机存取。迭代器可以直接跳跃 n个距离。
 reference operator[](difference_type n) const { return *(*this + n); } 
 // 以上唤起 operator*, operator+ 
 bool operator==(const self& x) const { return cur == x.cur; } 
 bool operator!=(const self& x) const { return !(*this == x); } 
 bool operator<(const self& x) const { 
 return (node == x.node) ? (cur < x.cur) : (node < x.node); 
 }

deque 的数据结构

deque除了维护一个先前说过的指向map的指标外，也维护start, finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外它当然也必须记住目前的map大小。因为一旦map所提供的节点不足，就必须重新配置更大的一块map。

template <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: // Iterators 
 typedef __deque_iterator<T, T&, T*,BufSiz> iterator; 
protected: // Internal typedefs 
 // 元素的指针的指针（pointer of pointer of T）
 typedef pointer* map_pointer; 
protected: // Data members 
 iterator start; //表现第一个节点。
 iterator finish; //表现最后一个节点。
 map_pointer map; //指向 map，map 是块连续空间 ，其每个元素都是个指针，指向一个节点（缓冲区）。
 size_type map_size;// map 内有多少指标。
... 
};

有了上述结构，以下数个机能便可轻易完成：

public: // Basic accessors 
 iterator begin() { return start; } 
 iterator end() { return finish; } 
 reference operator[](size_type n) { 
 return start[difference_type(n)]; //唤起 __deque_iterator<>::operator[] 
 } 
 reference front() { return *start; } // 唤起 __deque_iterator<>::operator* 
 reference back() { 
 iterator tmp = finish; 
 --tmp;//唤起 __deque_iterator<>::operator-- 
 return *tmp; //唤起 __deque_iterator<>::operator* 
// 以上三行何不改为：return *(finish-1); 
 // 因为 __deque_iterator<> 没有为 (finish-1) 定义运算子?! 
 } 
 // 下行最后有两个 ‘;’，虽奇怪但合乎语法。
 size_type size() const { return finish - start;; } 
// 以上唤起 iterator::operator- //注：并没有operator-(iterator& x)的版本啊...
 size_type max_size() const { return size_type(-1); } 
 bool empty() const { return finish == start; }

deque 的建构与内存管理 ctor, push_back, push_front

下面是一个测试程序:

// filename : 4deque-test.cpp 
#include <deque> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
 deque<int,alloc,32> ideq(20,9); // 注意，alloc 只适用于 G++ 
 cout << "size=" << ideq.size() << endl; // size=20 
// 现在，应该已经建构了一个 deque，有 20 个 int 元素，初值皆为 9。
 // 缓冲区大小为 32bytes。
// 为每一个元素设定新值。
 for(int i=0; i<ideq.size(); ++i) 
 ideq[i] = i; 
 for(int i=0; i<ideq.size(); ++i) 
 cout << ideq[i] << ' '; // 0 1 2 3 4 5 6...19 
 cout << endl; 
// 在最尾端增加 3 个元素，其值为 0,1,2 
 for(int i=0;i<3;i++) 
 ideq.push_back(i); 
 for(int i=0; i<ideq.size(); ++i) 
 cout << ideq[i] << ' '; // 0 1 2 3 ... 19 0 1 2 
 cout << endl; 
 cout << "size=" << ideq.size() << endl; // size=23 
// 在最尾端增加 1 个元素，其值为 3 
 ideq.push_back(3); 
 for(int i=0; i<ideq.size(); ++i) 
 cout << ideq[i] << ' '; // 0 1 2 3 ... 19 0 1 2 3 
 cout << endl; 
 cout << "size=" << ideq.size() << endl; // size=24 
// 在最前端增加 1 个元素，其值为 99 
 ideq.push_front(99); 
 for(int i=0; i<ideq.size(); ++i)
     cout << ideq[i] << ' '; // 99 0 1 2 3...19 0 1 2 3 
 cout << endl; 
 cout << "size=" << ideq.size() << endl; // size=25 
// 在最前端增加 2 个元素，其值分别为 98,97 
 ideq.push_front(98); 
 ideq.push_front(97); 
 for(int i=0; i<ideq.size(); ++i) 
 cout << ideq[i] << ' '; // 97 98 99 0 1 2 3...19 0 1 2 3 
 cout << endl; 
 cout << "size=" << ideq.size() << endl; // size=27 
// 搜寻数值为 99 的元素，并打印出来。
 deque<int,alloc,32>::iterator itr; 
 itr =find(ideq.begin(), ideq.end(), 99); 
 cout << *itr << endl; // 99
 cout << *(itr.cur) << endl; // 99
}

程序一开始宣告了一个deque： deque<int,alloc,32> ideq(20,9);

其缓冲区大小为 32 bytes，并令其保留 20 个元素空间，每个元素初值为 9。为了指定deque的第三个 template参数（缓冲区大小），我们必须将前两个参数都指明出来（这是 C++语法规则），因此必须明确指定alloc（第二章）为空间配置器。

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

protected: // Internal typedefs 
// 专属之空间配置器，每次配置一个元素大小
 typedef simple_alloc<value_type, Alloc> data_allocator; 
// 专属之空间配置器，每次配置一个指针大小
 typedef simple_alloc<pointer, Alloc> map_allocator;

并提供有一个constructor如下：

deque(int n, const value_type& value):start(), finish(), map(0), map_size(0) 
 { 
 fill_initialize(n, value); 
 }

其内所呼叫的 fill_initialize()负责产生并安排好deque的结构，并将元素的初值设定妥当：

template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::fill_initialize(size_type n, const value_type& value) { 
create_map_and_nodes(n); // 把 deque 的结构都产生并安排好
map_pointer cur; 
__STL_TRY { 
// 为每个节点的缓冲区设定初值
for (cur = start.node; cur < finish.node; ++cur) 
	uninitialized_fill(*cur, *cur + buffer_size(), value); 
// 最后一个节点的设定稍有不同（因为尾端可能有备用空间，不必设初值）
uninitialized_fill(finish.first, finish.cur, value);//注意finish.cur指向末尾 
} 
 catch(...) { 
 ... 
 } 
}

其中 create_map_and_nodes()负责产生并安排好deque的结构：

template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) 
{ 
 // 需要节点数=(元素个数/每个缓冲区可容纳的元素个数)+1 
 // 如果刚好整除，会多配一个节点。
 size_type num_nodes = num_elements / buffer_size() + 1; 
 // 一个 map要管理几个节点。最少 8 个，最多是 “所需节点数加 2” 
 // （前后各预留一个，扩充时可用）。
 map_size = max(initial_map_size(), num_nodes + 2); 
 map =map_allocator::allocate(map_size); 
 // 以上配置出一个 “具有 map_size 个节点”的 map。
 // 以下令 nstart 和 nfinish 指向 map 所拥有之全部节点的最中央区段。
 // 保持在最中央，可使头尾两端的扩充能量一样大。每个节点可对应一个缓冲区。
 map_pointer nstart = map + (map_size - num_nodes) / 2; 
 map_pointer nfinish = nstart + num_nodes - 1; 
 map_pointer cur; 
 __STL_TRY { 
// 为 map 内的每个现用节点配置缓冲区。所有缓冲区加起来就是 deque 的
 // 可用空间（最后一个缓冲区可能留有一些余裕）。
 for (cur = nstart; cur <= nfinish; ++cur) 
 *cur = allocate_node(); 
 } 
 catch(...) { 
// "commit or rollback"语意：若非全部成功，就一个不留。
 ...
  } 
// 为 deque 内的两个迭代器 start 和 end设定正确内容。
start.set_node(nstart); 
finish.set_node(nfinish); 
start.cur = start.first; // first, cur 都是 public 
finish.cur = finish.first + num_elements % buffer_size(); 
// 前面说过，如果刚好整除，会多配一个节点。
 // 此时即令 cur 指向这多配的一个节点（所对映之缓冲区）的起头处。
}

接下来范例程序以注标运算子为每个元素重新设值，然后在尾端安插三个新元素：

for(int i=0; i<ideq.size(); ++i) 
ideq[i] = i; 
for(int i=0;i<3;i++) 
ideq.push_back(i);

由于此时最后一个缓冲区仍有 4 个备用元素空间，所以不会引起缓冲区的再配置。

以下是push_back()函式内容：

public: // push_* and pop_* 
 void push_back(const value_type& t) { 
 if (finish.cur != finish.last - 1) 
 // 最后缓冲区尚有一个以上的备用空间，注意是一个以上
 construct(finish.cur, t);//直接在备用空间上建构元素
 ++finish.cur;//调整最后缓冲区的使用状态
 } 
 else // 最后缓冲区已无（或只剩一个）元素备用空间。
 push_back_aux(t); 
 }

现在，如果再新增加一个新元素（3）于尾端，由于尾端只剩一个元素备用空间，于是push_back()呼叫push_back_aux()，先配置一整块新的缓冲区，再设妥新元素内容，然后更改迭代器finish的状态：

//只有当 finish.cur == finish.last – 1时才会被呼叫。
//也就是说只有当最后一个缓冲区只剩一个备用元素空间时才会被呼叫。
template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) { 
value_type t_copy = t; 
reserve_map_at_back(); // 若符合某种条件则必须重换一个 map 
*(finish.node + 1) = allocate_node();//配置一个新节点（缓冲区）
__STL_TRY { 
construct(finish.cur, t_copy); //针对标的元素设值，放在之前缓冲区的最后一个
finish.set_node(finish.node + 1); //改变 finish，令其指向新节点
finish.cur = finish.first; //设定 finish 的状态
} 
__STL_UNWIND(deallocate_node(*(finish.node + 1))); 
}

现在，deque的状态如下：

在deque的前端安插一个新元素99，push_front()函式动作如下：

public: // push_* and pop_* 
 void push_front(const value_type& t) { 
 if (start.cur != start.first) { //第一缓冲区尚有备用空间
 construct(start.cur - 1, t); // 直接在备用空间上建构元素
 --start.cur;  //调整第一缓冲区的使用状态
 } 
 else // 第一缓冲区已无备用空间
 push_front_aux(t); 
 }

由于目前状态下，第一缓冲区并无备用空间，所以呼叫push_front_aux()：

//只有当 start.cur == start.first 时才会被呼叫。
//也就是说只有当第一个缓冲区没有任何备用元素时才会被呼叫。
template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) 
{ 
 value_type t_copy = t; 
 reserve_map_at_front(); // 若符合某种条件则必须重换一个 map 
 *(start.node - 1) =allocate_node();//配置一个新节点（缓冲区）
 __STL_TRY { 
 start.set_node(start.node - 1); //改变 start，令其指向新节点
 start.cur = start.last - 1; //设定 start 的状态
 construct(start.cur, t_copy); //针对标的元素设值
 } 
 catch(...) { 
 // "commit or rollback"语意：若非全部成功，就一个不留。
 start.set_node(start.node + 1); 
 start.cur = start.first; 
 deallocate_node(*(start.node - 1)); 
 throw; 
 } 
}

插入后如下，注意向前插入是从缓冲区尾部向前插，这样能保持空间逻辑上的连续：

回头看看一个悬而᳾解的问题：什么时候map需要重新整治？这个问题的判断由reserve_map_at_back()和reserve_map_at_front()进行，实际动作则由reallocate_map()执行：

 void reserve_map_at_back (size_type nodes_to_add = 1) { 
 if (nodes_to_add + 1 > map_size - (finish.node - map)) 
 // 如果 map尾端的节点备用空间不足
 // 符合以上条件则必须重换一个 map（配置更大的，拷贝原来的，释放原来的）
 reallocate_map(nodes_to_add, false); 
 }

 void reserve_map_at_front (size_type nodes_to_add = 1) { 
 if (nodes_to_add > start.node - map) 
 // 如果 map前端的节点备用空间不足
 // 符合以上条件则必须重换一个 map（配置更大的，拷贝原来的，释放原来的）
reallocate_map(nodes_to_add, true);
 }

//注：我要晕倒了
template <class T, class Alloc, size_t BufSize> 
 void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add, bool add_at_front) { 
 size_type old_num_nodes = finish.node - start.node + 1; 
 size_type new_num_nodes = old_num_nodes + nodes_to_add; 
 map_pointer new_nstart; 
 if (map_size > 2 * new_num_nodes) { //注：这里不需要新开一块map，重新分配的原因是可能前面或者后面仍然有很大的空间，只需要把map平移一下即可		
 new_nstart = map + (map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add: 0); 
 if (new_nstart < start.node) //注：向前向后平移的判断
 copy(start.node, finish.node + 1, new_nstart); 
 else 
 copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes); 
 } 
 else { 
 size_type new_map_size = map_size +max(map_size, nodes_to_add) + 2; 
 // 配置一块空间，准备给新 map 使用。
 map_pointer new_map = map_allocator::allocate(new_map_size); 
 new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? nodes_to_add : 0); 
 // 把原 map内容拷贝过来。
 copy(start.node, finish.node + 1, new_nstart); 
 // 释放原 map 
 map_allocator::deallocate(map, map_size); 
 // 设定新 map 的起始地址与大小
 map = new_map; 
 map_size = new_map_size; 
 } 
 // 重新设定迭代器 start和 finish 
 start.set_node(new_nstart); 
 finish.set_node(new_nstart + old_num_nodes - 1); 
 }

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

pop_back() 和pop_front()。所谓pop，是将元素拿掉。无论从deque 的最前端或最尾端取元素，都需考虑在某种条件下，将缓冲区释放掉：

void pop_back() { 
 if (finish.cur != finish.first) { //注：cur原来指向下一个空的区域
 // 最后缓冲区有一个（或更多）元素
 --finish.cur; //调整指针，相当于排除了最后元素
 } 
 destroy(finish.cur);//将最后元素解构
 else 
 // 最后缓冲区没有任何元素
 pop_back_aux(); //这里将进行缓冲区的释放工作
 } 

//只有当 finish.cur == finish.first 时才会被呼叫。
template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::pop_back_aux() { 
 deallocate_node(finish.first); //释放最后一个缓冲区
 finish.set_node(finish.node - 1);//调整 finish 的状态，使指向
 finish.cur = finish.last - 1; // 上一个缓冲区的最后一个元素
 destroy(finish.cur); //将该元素解构。
}

void pop_front() { 
 if (start.cur != start.last - 1) { 
 // 第一缓冲区有一个（或更多）元素
 destroy(start.cur);//将第一元素解构
 ++start.cur; //调整指针，相当于排除了第一元素
 } 
 else 
 // 第一缓冲区仅有一个元素
 pop_front_aux(); //这里将进行缓冲区的释放工作
 } 

//只有当 start.cur == start.last - 1 时才会被呼叫。
template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::pop_front_aux() { 
 destroy(start.cur); //将第一缓冲区的第一个元素解构。
 deallocate_node(start.first); //释放第一缓冲区。
 start.set_node(start.node + 1);//调整 start的状态，使指向下一个缓冲区的第一个元素。
 start.cur = start.first;
}

下面这个例子是 clear()，用来清除整个 deque。请注意，deque的最初状态（无任何元素时）保有一个缓冲区，因此clear()完成之后回复初始状态，也一样要保留一个缓冲区：

//注意，最终需要保留一个缓冲区。这是 deque的策略，也是 deque的初始状态。
template <class T, class Alloc, size_t BufSize> 
void deque<T, Alloc, BufSize>::clear() { 
 // 以下针对头尾以外的每一个缓冲区（它们一定都是饱满的）
 for (map_pointer node = start.node + 1; node < finish.node; ++node) { 
 // 将缓冲区内的所有元素解构。注意，呼叫的是 destroy() 第二版本
 destroy(*node, *node + buffer_size()); 
 // 释放缓冲区内存
 data_allocator::deallocate(*node, buffer_size()); 
 } 
 if (start.node != finish.node) {//至少有头尾两个缓冲区
 destroy(start.cur, start.last);//将头缓冲区的目前所有元素解构
 destroy(finish.first, finish.cur); // 将尾缓冲区的目前所有元素解构
 // 以下释放尾缓冲区。注意，头缓冲区保留。
 data_allocator::deallocate(finish.first, buffer_size()); 
 } 
 else//只有一个缓冲区
 destroy(start.cur, finish.cur);//将此唯一缓冲区内的所有元素解构
 // 注意，并不释放缓冲区空间。这唯一的缓冲区将保留。
 finish = start; //调整状态
}

下面这个例子是 erase()，用来清除某个元素：

// 清除 pos所指的元素。pos为清除点。
 iterator erase(iterator pos) { //注：实际上是对pos.cur清除（因为调用*pos）
 iterator next = pos; 
 ++next; //注：pos.cur.next
 difference_type index = pos - start;//清除点之前的元素个数
 if (index < (size() >> 1)) { //如果清除点之前的元素比较少，
 copy_backward(start, pos, next);//就搬移清除点之前的元素
 } 
 pop_front(); //搬移完毕，最前一个元素赘余，去除之
 else { //清除点之后的元素比较少，
 copy(next, finish, pos);//就搬移清除点之后的元素
 } 
 pop_back(); //搬移完毕，最后一个元素赘余，去除之
 return start + index; 
 }

下面这个例子是 erase()，用来清除[first,last)区间内的所有元素：

template <class T, class Alloc, size_t BufSize> 
deque<T, Alloc, BufSize>::iterator 
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) { 
 if (first == start && last == finish) {// 如果清除区间就是整个 deque 
 clear();  //直接呼叫 clear()即可
 return finish; 
 } 
 else { 
 difference_type n = last - first;  //清除区间的长度
 difference_type elems_before = first - start;//清除区间前方的元素个数
     
     //注：这里的搬运是因为清除一个区间可能截断了连续的数据空间，因此要把可能产生的前后两端连接起来
 if (elems_before < (size() - n) / 2) { //如果前方的元素比较少，
 copy_backward(start, first, last); //向后搬移前方元素（覆盖清除区间）
 iterator new_start = start + n; //标记 deque的新起点
 destroy(start, new_start); //搬移完毕，将赘余的元素解构
 // 以下将赘余的缓冲区释放
 for (map_pointer cur = start.node; cur < new_start.node; ++cur) 
 data_allocator::deallocate(*cur, buffer_size()); 
 start = new_start;//设定 deque 的新起点
 } 
 else {//如果清除区间后方的元素比较少
 copy(last, finish, first); //向前搬移后方元素（覆盖清除区间）
 iterator new_finish = finish - n;//标记 deque的新尾点
 destroy(new_finish, finish); //搬移完毕，将赘余的元素解构
 // 以下将赘余的缓冲区释放
 for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur) 
 data_allocator::deallocate(*cur, buffer_size()); 
 finish = new_finish;//设定 deque 的新尾点
 } 
 return start + elems_before; 
 } 
}

最后一个例子是insert。deque为这个功能提供了许多版本，最基础最重要的是以下版本，允许在某个点（之前）安插一个元素，并设定其值。

// 在 position 处安插一个元素，其值为 x 
 iterator insert(iterator position, const value_type& x) { 
 if (position.cur == start.cur) {//如果安插点是 deque最前端
 push_front(x); //交给 push_front 去做
 return start; 
 } 
 else if (position.cur == finish.cur) { // 如果安插点是 deque最尾端
 push_back(x); //交给 push_back去做
 iterator tmp = finish; 
 --tmp;
 return tmp; 
 } 
 else { 
 return insert_aux(position, x); //交给 insert_aux 去做
 } 
 }

template <class T, class Alloc, size_t BufSize> 
typename deque<T, Alloc, BufSize>::iterator 
 deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) { 
 difference_type index = pos - start;//安插点之前的元素个数
 value_type x_copy = x; 
 if (index < size() / 2) { //如果安插点之前的元素个数比较少
     push_front(front()); //在最前端加入与第一元素同值的元素。注：相当于把安插点前面的元素向前移一格
     iterator front1 = start; //以下标示记号，然后进行元素搬移... 
     ++front1; 
     iterator front2 = front1; 
     ++front2; 
     pos = start + index; 
     iterator pos1 = pos; 
     ++pos1; 
     copy(front2, pos1, front1); //元素搬移，注：把原来的头元素覆盖，这样position位置就空出来了
 } 
 else { //安插点之后的元素个数比较少
     push_back(back()); //在最尾端加入与最后元素同值的元素。注：相当于把安插点后面的元素向后移一格
     iterator back1 = finish;//以下标示记号，然后进行元素搬移... 
     --back1; 
     iterator back2 = back1; 
     --back2; 
     pos = start + index; 
     copy_backward(pos, back2, back1); //元素搬移，注：把原来的尾元素覆盖，这样position位置就空出来了
     } 
 
 *pos = x_copy;//在安插点上设定新值
 return pos; 
}

总结

deque相比vector和list要复杂很多，是一个二级结构。第一级是map，一块连续的空间，其中每个node又指向第二级的一块连续的空间（缓冲区），这些连续空间可以不连续（但逻辑上连续）。为了维护这个逻辑连续，迭代器（指向map的node，也指向缓冲区的节点）的设计就变得十分复杂。同时map中的节点是从中间向两边扩展，这就使得从头部插入、删除节点与从尾部插入、删除节点的动作是对称的，使得相比vector来说，头部操作的效率变好了。当空间不足时，一定是map除了问题，可以整体前移、后移，或是重新分配一个更大的空间。

为了兼容算法的接口，迭代器所“代表”的元素就是迭代器的cur节点指向的元素（重载了的*、++等运算，都是针对cur节点）。

stack

stack 概述

stack是一种先进后出（First In Last Out，FILO）的数据结构。stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取stack的其它元素。换言之stack不允许有走访行为。

将元素推入 stack 的动作称为 push，将元素推出 stack 的动作称为pop。

stack 定义式完整列表

以某种既有容器做为底部结构，将其接口改变，使符合「先进后出」的特性，形成一个stack，是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。因此，SGI STL 便以deque做为预设情况下的stack底部结构，stack的实作因而非常简单，源码十分简短，本处完整列出。

由于stack系以底部容器完成其所有工作，而具有这种「修改某物接口，形成另一种风貌」之性质者，称为adapter（配接器），因此 STL stack往往不被归类为 container（容器），而被归类为container adapter。

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不提供走访功能，也不提供迭代器。

以 list做为 stack 的底层容器

除了deque之外，list 也是双向开口的数据结构。上述 stack 源码中使用的底层容器的函式有empty, size, back, push_back, pop_back，凡此种种 list 都具备。因此若以list为底部结构并封闭其头端开口，一样能够轻易形成一个stack。下面是作法示范。

// file : 4stack-test.cpp 
#include <stack> 
#include <list> 
#include <iostream>
#include <algorithm> 
using namespace std; 
int main() 
{ 
 stack<int,list<int> > istack; 
 istack.push(1); 
 istack.push(3); 
 istack.push(5); 
 istack.push(7); 
 cout << istack.size() << endl; // 4 
 cout << istack.top() << endl; // 7 
 istack.pop(); cout << istack.top() << endl; // 5 
 istack.pop(); cout << istack.top() << endl; // 3 
 istack.pop(); cout << istack.top() << endl; // 1 
 cout << istack.size() << endl; // 1 
}

queue

queue 概述

queue是一种先进先出（First In First Out，FIFO）的数据结构。它有两个出口。queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。但除了最底端可以加入、最顶端可以取出，没有任何其它方法可以存取queue 的其它元素。换言之 queue 不允许有走访行为。

将元素推入 queue 的动作称为 push，将元素推出 queue 的动作称为pop。

queue 定义式完整列表

SGI STL 依然以deque做为预设情况下的queue底部结构，因此queue也被归类为container adapter。

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 的操作，完成 queue的操作。
 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 顶端的元素，才有机会被外界取用。queue不提供走访功能，也不提供迭代器。

以 list做为queue 的底层容器

// file : 4queue-test.cpp 
#include <queue> 
#include <list> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
 queue<int,list<int> > iqueue; 
 iqueue.push(1); 
 iqueue.push(3); 
 iqueue.push(5); 
 iqueue.push(7); 
 cout << iqueue.size() << endl; // 4 
 cout << iqueue.front() << endl; // 1 
 iqueue.pop(); cout << iqueue.front() << endl; // 3 
 iqueue.pop(); cout << iqueue.front() << endl; // 5 
 iqueue.pop(); cout << iqueue.front() << endl; // 7 
 cout << iqueue.size() << endl; // 1 
}

heap

heap 概述

heap并不归属于STL 容器组件，它是个幕后英雄，扮演priority queue （优先级队列）的推手。顾名思义，priority queue 允许使用者以任何次序将任何元素推入容器内，但取出时一定是从优先权最高（也就是数值最高）之元素开始取。binary max heap正是具有这样的特性，适合做为 priority queue的底层机制。

为何使用堆作为优先级队列的底层

如果使用 list 做为 priority queue 的底层机制，元素安插动作可享常数时间。但是要找到list中的极值，却需要对整个list进行线性扫描。我们也可以改个作法，让元素安插前先经过排序这一关，使得 list 的元素值总是由小到大（或由大到小），但这么一来，虽然取得极值以及元素删除动作达到最高效率，元素的安插却只有线性表现。

比较麻辣的作法是以binary search tree 做为priority queue的底层机制。这么一来元素的安插和极值的取得就有*O(logN)*的表现。但这样未免小题大作，一来binary search tree的输入需要足够的随机性，二来binary search tree并不容易实作。priority queue的复杂度，最好介于queue和binary search tree之间，才算适得其所。binary heap便是这种条件下的适当候选人。

堆的一些细节

所谓binary heap就是一种complete binary tree（完全二叉树），也就是说，整棵binary tree除了最底层的叶节点(s)之外，是填满的，而最底层的叶节点(s)由左至右又不得有空隙。

complete binary tree整棵树内没有任何节点漏洞，这带来一个极大好处：我们可以利用array来储存所有节点。假设动用一个小技巧，将array的**#0元素保留（或设为无限大值或无限小值），那么当complete binary tree中的某个节点位于array的 i 处，其左子节点必位于array 的 2i 处，其右子节点必位于 array的 2i+1 处，其父节点必位于「i/2**」处（此处的「」权且代表高斯符号，取其整数）。通过这么简单的位置规则，array可以轻易实作出complete binary tree。这种以array表述tree的方式，我们称为隐式表述法（implicit representation）。

我们需要的工具就很简单了：一个array和一组heap算法（用来安插元素、删除元素、取极值、将某一整组数据排列成一个heap）。array的缺点是无法动态改变大小，而heap却需要这项功能，因此以vector代替 array是更好的选择。

根据元素排列方式，heap可分为max-heap和 min-heap （最大堆和最小堆）两种，前者每个节点的键值（key）都大于或等于其子节点键值，后者的每个节点键值（key）都小于或等于其子节点键值。因此，max-heap的最大值在根节点，并总是位于底层 array 或vector的起头处；min-heap的最小值在根节点，亦总是位于底层array或vector的起头处。STL 供应的是max-heap，因此以下说heap时，指的是max-heap。

heap 算法

push_heap 算法

插入元素首先插入到最后端，然后向上过滤。为满足 max-heap 的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的percolate up（上溯）程序：将新节点拿来与其父节点比较，如果其键值（key）比父节点大，就父子对换位置。如此一直上溯，直到不需对换或直到根节点为止。

template <class RandomAccessIterator> 
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) { 
// 注意，此函式被呼叫时，新元素应已置于底部容器的最尾端。
__push_heap_aux(first, last, distance_type(first), value_type(first)); 
} 
template <class RandomAccessIterator, class Distance, class T> 
inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*) { 
__push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1))); 
// 以上系根据 implicit representation heap的结构特性：新值必置于底部
// 容器的最尾端，此即第一个洞号：(last-first)–1。
} 
//以下这组 push_back()不允许指定「大小比较标准」
template <class RandomAccessIterator, class Distance, class T> 
void__push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value) { 
 Distance parent = (holeIndex - 1) / 2;//找出父节点
 while (holeIndex > topIndex && *(first + parent)< value) { 
 // 当尚未到达顶端，且父节点小于新值（于是不符合 heap 的次序特性）
 // 由于以上使用 operator<，可知 STL heap 是一种 max-heap（大者为父）。
 *(first + holeIndex) = *(first + parent);//令洞值为父值
 holeIndex = parent;//percolate up：调整洞号，向上提升至父节点。
 parent = (holeIndex - 1) / 2;//新洞的父节点
 } // 持续至顶端，或满足 heap 的次序特性为止。
 *(first + holeIndex) = value;//令洞值为新值，完成安插动作。
}

pop_heap 算法

既然身为max-heap，最大值必然在根节点。pop动作取走根节点（其实是移至底部容器vector的最后一个元素）之后，为了满足 complete binary tree的条件，必须将最下一层最右边的叶节点拿掉，现在我们的任务是为这个被拿掉的节点找一个适当的位置。

为满足max-heap的条件（每个节点的键值都大于或等于其子节点键值），我们执行一个所谓的percolate down（向下过滤）程序：将根节点（最大值被取走后，形成一个「洞」）填入上述那个失去生存空间的叶节点值，再将它拿来和其两个子节点比较键值（key），并与较大子节点对调位置。如此一直下放，直到这个「洞」的键值大于左右两个子节点，或直到下放至叶节点为止。

template <class RandomAccessIterator> 
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) { 
__pop_heap_aux(first, last, value_type(first)); 
} 
template <class RandomAccessIterator, class T> 
inline void __pop_heap_aux(RandomAccessIterator first, RandomAccessIterator last, T*) { 
__pop_heap(first, last-1, T(*(last-1)), distance_type(first)); 
// 以上，根据 implicit representation heap的次序特性，pop 动作的结果
 // 应为底部容器的第一个元素。因此，首先设定欲调整值为尾值，然后将首值调至
 // 尾节点（所以以上将迭代器 result 设为 last-1）。然后重整 [first, last-1)，
 // 使之重新成一个合格的 heap。
} 
//以下这组 __pop_heap() 不允许指定「大小比较标准」
template <class RandomAccessIterator, class T, class Distance> 
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance*) { 
 *result = *first;// 设定尾值为首值，于是尾值即为欲求结果，
 // 可由客端稍后再以底层容器之 pop_back() 取出尾值。
 __adjust_heap(first, Distance(0), Distance(last - first), value); 
// 以上欲重新调整 heap，洞号为 0（亦即树根处），欲调整值为 value（原尾值）。
} 
//以下这个 __adjust_heap()不允许指定「大小比较标准」
template <class RandomAccessIterator, class Distance, class T> 
void__adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value) { 
 Distance topIndex = holeIndex; 
 Distance secondChild = 2 * holeIndex + 2;//洞节点之右子节点
 while (secondChild < len) { 
// 比较洞节点之左右两个子值，然后以 secondChild代表较大子节点。
 if (*(first + secondChild) < *(first + (secondChild - 1))) 
 secondChild--; 
 // Percolate down：令较大子值为洞值，再令洞号下移至较大子节点处。
 *(first + holeIndex) = *(first + secondChild); 
 holeIndex = secondChild; 
// 找出新洞节点的右子节点
 secondChild = 2 * (secondChild + 1); 
 } 
 if (secondChild == len) {//没有右子节点，只有左子节点
// Percolate down：令左子值为洞值，再令洞号下移至左子节点处。
 *(first + holeIndex) = *(first + (secondChild - 1)); 
 holeIndex = secondChild - 1; 
 } 
// 将欲调整值填入目前的洞号内。注意，此时肯定满足次序特性。
 // 依侯捷之见，下面直接改为 *(first + holeIndex) = value; 应该可以。
__push_heap(first, holeIndex, topIndex, value); //注：就是最后把原来last元素填好位置
}

sort_heap 算法

既然每次pop_heap可获得 heap之中键值最大的元素，如果持续对整个 heap做pop_heap动作，每次将操作范围从后向前缩减一个元素（因为 pop_heap 会把键值最大的元素放在底部容器的最尾端），当整个程序执行完毕，我们便有了一个递增序列。

//以下这个 sort_heap()不允许指定「大小比较标准」
template <class RandomAccessIterator> 
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { 
 // 以下，每执行一次 pop_heap()，极值（在 STL heap 中为极大值）即被放在尾端。
 // 扣除尾端再执行一次 pop_heap()，次极值又被放在新尾端。一直下去，最后即得
 // 排序结果。
 while (last - first > 1) 
 pop_heap(first, last--);//每执行 pop_heap() 一次，操作范围即退缩一格。
}

make_heap 算法

这个算法用来将一段现有的数据转化为一个 heap。

//将 [first,last) 排列为一个 heap。
template <class RandomAccessIterator> 
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) { 
 __make_heap(first, last,value_type(first), distance_type(first)); 
} 
//以下这组 make_heap()不允许指定「大小比较标准」。
template <class RandomAccessIterator, class T, class Distance> 
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*, Distance*) { 
 if (last - first < 2) return;//如果长度为 0或 1，不必重新排列。
 Distance len = last - first; 
 // 找出第一个需要重排的子树头部，以 parent 标示出。由于任何叶节点都不需执行
 // perlocate down，所以有以下计算。parent命名不佳，名为 holeIndex更好。
 Distance parent = (len - 2)/2; 
 while (true) { 
  // 重排以 parent 为首的子树。len 是为了让 __adjust_heap()判断操作范围
  __adjust_heap(first, parent, len, T(*(first + parent))); 
  if (parent == 0) return;//走完根节点，就结束。
  parent--; //（即将重排之子树的）头部向前一个节点
 } 
}

heap 没有迭代器

heap 的所有元素都必须遵循特别的（complete binary tree）排列规则，所以 heap不提供走访功能，也不提供迭代器。

heap测试实例

#include <vector> 
#include <iostream> 
#include <algorithm> // heap algorithms 
using namespace std; 
int main() 
{ 
 { 
 // test heap (底层以 vector完成) 
 int ia[9] = {0,1,2,3,4,8,9,3,5}; 
 vector<int> ivec(ia, ia+9); 
 make_heap(ivec.begin(), ivec.end()); 
 for(int i=0; i<ivec.size(); ++i) 
 cout << ivec[i] << ' '; // 9 5 8 3 4 0 2 3 1 
 cout << endl; 
 ivec.push_back(7); 
 push_heap(ivec.begin(), ivec.end()); 
 for(int i=0; i<ivec.size(); ++i) 
 cout << ivec[i] << ' '; // 9 7 8 3 5 0 2 3 1 4 
 cout << endl; 
 pop_heap(ivec.begin(), ivec.end()); 
 cout << ivec.back() << endl; // 9.return but no remove. 
 ivec.pop_back(); // remove last elem and no return 
 for(int i=0; i<ivec.size(); ++i) 
 cout << ivec[i] << ' '; // 8 7 4 3 5 0 2 3 1 
 cout << endl; 
 sort_heap(ivec.begin(), ivec.end()); 
 for(int i=0; i<ivec.size(); ++i) 
 cout << ivec[i] << ' '; // 0 1 2 3 3 4 5 7 8 
 cout << endl; 
 }
    
 { 
 // test heap (底层以 array 完成) 
 int ia[9] = {0,1,2,3,4,8,9,3,5}; 
 make_heap(ia, ia+9); 
 // array 无法动态改变大小，因此不可以对满载的 array 做 push_heap() 动作。
 // 因为那得先在 array尾端增加一个元素。
 sort_heap(ia, ia+9); 
 for(int i=0; i<9; ++i) 
 cout << ia[i] << ' '; // 0 1 2 3 3 4 5 8 9 
 cout << endl; 
 // 经过排序之后的 heap，不再是个合法的 heap 
 // 重新再做一个 heap 
 make_heap(ia, ia+9); 
 pop_heap(ia, ia+9); 
 cout << ia[8] << endl; // 9 
 }

priority_queue

priority_queue 概述

priority_queue是一个拥有权值观念的 queue，它允许加入新元素、移除旧元素，审视元素值等功能。由于这是一个queue，所以只允许在底端加入元素，并从顶端取出元素，除此之外别无其它存取元素的途径。

priority_queue带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。权值最高者，排在最前面。

预设情况下priority_queue系利用一个max-heap 完成，后者是一个以 vector 表现的 complete binary tree。max-heap 可以满足priority_queue所需要的「依权值高低自动递增排序」的特性。

priority_queue 定义式完整列表

由于priority_queue完全以底部容器为根据，再加上heap处理规则，所以其实作非常简单。预设情况下是以vector为底部容器。源码很简短，此处完整列出。

STL priority_queue 也不被归类为container（容器），而被归类为container adapter。

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()都是泛型算法
//注意，任一个建构式都立刻于底层容器内产生一个 implicit representation 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) { 
 __STL_TRY { 
// push_heap是泛型算法，先利用底层容器的 push_back() 将新元素
c.push_back(x); // 推入末端，再重排 heap。
push_heap(c.begin(), c.end(), comp);// push_heap是泛型算法
 } 
 __STL_UNWIND(c.clear()); 
 } 
 void pop() { 
 __STL_TRY { 
 // pop_heap 是泛型算法，从 heap 内取出一个元素。它并不是真正将元素
 // 弹出，而是重排 heap，（首值被放在尾部）然后再以底层容器的 pop_back() 取得被弹出的元素
 pop_heap(c.begin(), c.end(), comp); 
 c.pop_back(); 
 } 
 __STL_UNWIND(c.clear()); 
 } 
};

priority_queue 没有迭代器

priority_queue 的所有元素，进出都有一定的规则，只有 queue 顶端的元素（权值最高者），才有机会被外界取用。priority_queue不提供走访功能，也不提供迭代器。

priority_queue 测试实例

#include <queue> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
 // test priority queue... 
 int ia[9] = {0,1,2,3,4,8,9,3,5}; 
 priority_queue<int> ipq(ia, ia+9); 
 cout << "size=" << ipq.size() << endl; // size=9 
 for(int i=0; i<ipq.size(); ++i) 
 cout << ipq.top() << ' '; // 9 9 9 9 9 9 9 9 9 
 cout << endl; 
 while(!ipq.empty()) { 
 cout << ipq.top() << ' '; // 9 8 5 4 3 3 2 1 0 
 ipq.pop(); 
 } 
 cout << endl; 
}

总结

细致观察的话，我们会发现heap只提供了算法，而没有实际上作出容器。这与前面stack有不同：stack以deque为底层容器，封装deque的操作控制deque的元素。而heap没有元素，原因是优先级队列真正的底层容器是vector，所谓“heap”在这里只是概念，用来提供算法操作。为什么需要用vector而不是一个普通的array呢？因为优先级队列是可以动态扩展的，只有vector符合动态的理念，并且其迭代器是普通指针，满足随机访问的要求。而vector的元素删除、插入都是在尾部进行的，这也是为什么heap的pop算法把元素放到尾部就停止了（没有继续解构元素），就是为了能交给vector来pop。

最后，我们会发现所有容器的pop，均不返回值，原因是元素已真正解构了。

slist

slist 概述

STL list是个双向串行（double linked list）。SGI STL 另提供了一个单向串行（single linked list），名为slist。这个容器并不在标准规格之内，不过多做一些剖析，多看多学一些实作技巧也不错。

slist和list的主要差别在于，前者的迭代器属于单向的 Forward Iterator，后者的迭代器属于双向的Bidirectional Iterator。为此，slist的功能自然也就受到许多限制。不过，单向串行所耗用的空间更小，某些动作更快，不失为另一种选择。

根据STL的习惯，安插动作会将新元素安插于指定位置之前，而非之后。然而做为一个单向串行，slist没有任何方便的办法可以回头定出前一个位置，因此它必须从头找起。换句话说，除了slist起始处附近的区域之外，在其它位置上采用insert 或erase 操作函式，都是不智之举。这便是 slist 相较于 list 之下的大缺点。为此，slist特别提供了 insert_after()和erase_after()供弹性运用。

基于同样的（效率）考虑，slist不提供 push_back()，只提供 push_front()。因此 slist的元素次序会和元素安插进来的次序相反。

slist 的节点

slist节点和其迭代器的设计，架构上比list复杂许多，运用了继承关系，因此在型别转换上有复杂的表现。

//单向串行的节点基本结构。注：只操作指针
struct __slist_node_base
{ 
 __slist_node_base* next; 
}; 
//单向串行的节点结构
template <class T> 
struct __slist_node : public __slist_node_base 
{ 
 T data; 
}; 
//全域函式：已知某一节点，安插新节点于其后。
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; 
}

slist 的迭代器

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 <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<T>::end() 时会造成 __slist_iterator(0)，于是唤起上述函式。
__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; 
 } 
//没有实作 operator--，因为这是一个 forward iterator 
};

slist 的数据结构

template <class T, class Alloc = alloc> 
class slist
{ 
public: 
 typedef T value_type; 
 typedef value_type* pointer; 
 typedef const value_type* const_pointer; 
 typedef value_type& reference; 
 typedef const value_type& const_reference; 
 typedef size_t size_type; 
 typedef ptrdiff_t difference_type; 
 typedef __slist_iterator<T, T&, T*> iterator; 
 typedef __slist_iterator<T, const T&, const T*> const_iterator; 
private: 
 typedef __slist_node<T> list_node; 
 typedef __slist_node_base list_node_base; 
 typedef __slist_iterator_base iterator_base; 
 typedef simple_alloc<list_node, Alloc>list_node_allocator; 
 static list_node* create_node(const value_type& x) { 
 list_node* node =list_node_allocator::allocate();//配置空间
 __STL_TRY { 
    construct(&node->data, x); //建构元素
	node->next = 0; 
 } 
 __STL_UNWIND(list_node_allocator::deallocate(node)); 
 return node; 
 } 
 static void destroy_node(list_node* node) { 
 destroy(&node->data); //将元素解构
 list_node_allocator::deallocate(node); //释还空间
 } 

private: 
 list_node_base head; // 头部。注意，它不是指标，是实物。
public: 
 slist() { head.next = 0; } 
 ~slist() { clear(); } 
public:
 iterator begin() { return iterator((list_node*)head.next); } 
 iterator end() { return iterator(0); } 
 size_type size() const { return __slist_size(head.next); } 
 bool empty() const { return head.next == 0; } 
 // 两个 slist互换：只要将 head 交换互指即可。
 void swap(slist& L) 
 { 
 list_node_base* tmp = head.next; 
 head.next = L.head.next; 
 L.head.next = tmp; 
 } 
public: 
 // 取头部元素
 reference front() { return ((list_node*)head.next)->data; } 
 // 从头部安插元素（新元素成为 slist 的第一个元素）
 void push_front(const value_type& x) { 
 __slist_make_link(&head,create_node(x)); 
 } 
 // 注意，没有 push_back() 
 // 从头部取走元素（删除之）。修改 head。
 void pop_front() { 
 list_node* node = (list_node*) head.next; 
 head.next = node->next; 
 destroy_node(node); 
 } 
... 
};

slist 的元素操作

#include <slist> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() 
{ 
 int i; 
 slist<int> islist; 
 cout << "size=" << islist.size() << endl; // size=0
 islist.push_front(9); 
 islist.push_front(1); 
 islist.push_front(2); 
 islist.push_front(3); 
 islist.push_front(4); 
 cout << "size=" << islist.size() << endl; // size=5 
 slist<int>::iterator ite =islist.begin(); 
 slist<int>::iterator ite2=islist.end(); 
 for(; ite != ite2; ++ite) 
 cout << *ite << ' '; // 4 3 2 1 9 
 cout << endl; 
 ite =find(islist.begin(), islist.end(), 1); 
 if (ite!=0) 
 islist.insert(ite, 99); //新元素会被安插在1的前面
 cout << "size=" << islist.size() << endl; // size=6 
 cout << *ite << endl; // 1 
 ite =islist.begin(); 
 ite2=islist.end(); 
 for(; ite != ite2; ++ite) 
 cout << *ite << ' '; // 4 3 2 99 1 9 
 cout << endl; 
 ite = find(islist.begin(), islist.end(), 3); 
 if (ite!=0) 
 cout << *(islist.erase(ite)) << endl; // 2 
 ite =islist.begin(); 
 ite2=islist.end(); 
 for(; ite != ite2; ++ite) 
 cout << *ite << ' '; // 4 2 99 1 9 
 cout << endl; 
}

练习程序中一再以循环巡访整个slist，并以迭代器是否等于slist.end() 做为循环结束条件，这其中有一些容易疏忽的地方。当我们呼叫end()企图做出一个指向尾端（下一位置）的迭代器，STL 源码是这么进行的：

iterator end() { return iterator(0); }

这会因为源码中如下的定义：

typedef __slist_iterator<T, T&, T*> iterator;

而形成这样的结果：

__slist_iterator<T, T&, T*>(0);//产生一个暂时对象，引发 ctor

从而因为源码中如下的定义：

__slist_iterator(list_node* x) : __slist_iterator_base(x) {}

而导致基础类别的建构：

__slist_iterator_base(0);

并因为源码中这样的定义：

struct __slist_iterator_base
{ 
 __slist_node_base* node;//指向节点基本结构
__slist_iterator_base(__slist_node_base* x) :node(x) {} 
 ...
};

而导致：

node(0);

总结

这一章节探索容器（序列式），可以发现一块新大陆，这里挑一点来说。

在构建一个容器之前，需要先想好基础结构，是连续的空间呢，还是一个一个的节点，这导致了内存配置的不同。
然后，需要继而构造迭代器，定义好走访的形式，是单向的还是双向的还是随机的，重载++、*、->等运算符。
然后实作容器类：
- 首先定义好一系列type供萃取使用；
- 接着定义迭代器指针，以及迭代器相关的返回函数（如end()）；
- 然后定义一系列构造函数和析构函数，又紧接着可以作出内存配置（都使用simple_alloc）、清空，元素建构、解构（construct和deconstruc全域函数）的操作；
- 最后，作出容器动作函数，如插入、删除，以及一系列辅助操作。

关联式容器

概念

树的导览

这里只作简单介绍。

二叉搜索树

首先需要是一棵二叉树：“任何节点最多只允许两个子节点。”

平衡二叉搜索树

这种不平衡状态会导致搜索的对数时间变为常数时间。尽量保持平衡能节省搜索时间。

AVL树通过高度维护每个节点的平衡因子，以此来保持平衡。平衡破坏后具体的操作涉及RR、RL、LR、LL，即单旋转和双旋转，在数据结构已涉及，这里不详细展开了。

RB-tree（红黑树）

插入节点

状况1

状况2

第二次旋转是为了满足规则4，本身G(10)的左子树在不考虑ABC时是没有黑节点的，因此要再旋转一次，把8这个黑节点转上去。实际上，第一次旋转就是把内侧插入变成了外侧插入，所以内侧插入总能用一次旋转变成外侧插入。

状况3

状况4

因为前面考虑状况123时，X这个新节点都是带着子树考虑的（从真正的叶节点递归上来），那么此时就可以把P看成新的节点，子树看成AB，然后继续向上考虑，就回到状况123了。

由上而下的程序

P是红色，说明G是黑色。由于路径自上而下检查，因此S不会是红色，否则G这个节点就已经需要修改了。所以可以保证S是黑色，归类到状态1和2。

节点设计

迭代器

关于双层结构：以后作补充。

header节点在后面图5-17。

注：对header节点的补充

原文链接：https://blog.csdn.net/sinat_41619762/article/details/115124653

红黑树有一个特殊节点header。对于一棵空红黑树，header的left和right都指向自己，parent指向0。而红黑树不为空时，红黑树的根节点的parent指向header，header的parent指向根节点，header的left和right分别指向红黑树最左端和最右端的节点。于是可以方便地获得红黑树的根节点、最左节点和最右节点。
header节点是红色的，root节点是黑色的，这用来对它们做出一定的区别。
红黑树的begin()返回的迭代器指向的就是header的left节点，而end()返回的迭代器指向的是header自己。

如果是根节点，则根节点（node==root）的父节点是header（y），根据条件根节点右子节点是null，header的右子节点和父节点都是root，则执行一次while后：node会变为header，y会变为root。则此时不能直接把y返回，因为又回到root了，注意到此时node->right（header->right）==y，则可以用这个条件判断这个特殊状况，不加以判断的话得出的结果是有问题的。

decrement()也要结合header这一个节点理解。

这里的状况不是插入节点的状况。

红黑树数据结构

红黑树的构造与内存管理

红黑树元素操作

元素插入

对于insert_unique()，注意**j–**是找按大小顺序找前一个节点，下面是一些辅助理解：

原文链接：https://blog.csdn.net/jmh1996/article/details/103466017

while结束是，x为NULL也就是待插入点,而y为插入点的父节点。
接下来初始化一个迭代器j.
如果发现comp为true,这意味着x应该插入到y的左孩子，否则应该插入到右孩子。

如果comp为true,而且刚好j又是整个树的最小值，这说明当前要插入的值比整个树的最小值还要小。于是就直接调用__insert(x, y, v) 函数进行插入。整个辅助函数，我们后面深入。

如果comp为true,但是y不是指向最小值。那么就让 j 自减一下，此时 j 指向的元素,有关系：j.value<y.value。 而且一定会有v>=j.value。如果v<j.value,那么在执行while循环的时候就应该找到是 j（或j的左子树，同时y不可能在j的左子树） 而不是 y。

接下来：
比较j.value和 v 之间那个大。
如果条件为true,说明此时j.value<v ,OK，说明v是一个全新的元素。执行正常的插入辅助程序。
如果条件为false,意味着j.value>=v，又因为v>=j.value,联立这两个条件，必然有j.value==v，说明这个v就是一个重复的元素。

如何在数学上证明x=y ？只需分别证明：x>=y 且x<=y 就可以了

__insert操作中，对于x这个节点，经过while循环后一定是null。

平衡调整

树形和颜色的调整，与前面插入节点的四个状况相符，进行一次或两次单一的旋转，并且调整节点的颜色。左旋转和右旋转与AVL树的旋转是一样的道理，不过红黑树的节点有父节点，指针的操作有所不同。

这里首先判断父节点关于祖父节点的左右关系，从而正确获得伯父节点。可以得知新节点、父节点都是红的（因为这样才需要处理）。

如果伯父节点为红，对应状况3和4，则根据前面“自上而下的程序”，改变相应节点颜色，x本身直接插入，而后检查x的祖父节点（也即while继续检查）。
如果伯父节点为黑，则是状况1和2，也即新插入的节点位于内侧和外侧的问题。进行一次判断是否多做一次旋转即可。

示例

元素搜寻

set（集合）

实作

集合的键值就是实值，实值就是键值。不允许两个元素有相同的键值。集合能自动排序，以红黑树作为底层机制。

示例

map（映射）

实作

示例

特别说明

multiset

允许键值重复的set，底层使用红黑树的insert_equal()即可。

multimap

允许键值重复的map，底层使用红黑树的insert_equal()即可。

hashtable（哈希表）

概述

线性探测

平均插入成本太高了，平均情况下要线性寻访一半表格。

二次探测

开链

桶与节点

迭代器

数据结构

构造与内存管理

示例

哈希函数

hash set

两种集合的主要区别是，搜寻元素按什么方式。（红黑树是以二叉搜索的方式，哈希表是以哈希映射，因此哈希集合的元素不会被自动排序），源码就不放出来了，了解即可。

hash map

与hash set一样的情况。

hash multiset & hash multimap

与hash set 一样的情况。

算法

概论

stl 算法总览

in-place操作，意思是所有的操作都是”就地“操作，不允许进行移动，或者称作原位操作，即不允许使用临时变量。

质变算法

非质变算法

stl 算法一般形式

主要讲一些简单的规范

泛化过程

将算法独立于数据结构，即算法适用于不同类型的结构。

从int型泛化到任意类型

从普通指针泛化到迭代器

数值算法 <stl_numeric.h>

使用数值算法，要包含头文件<numeric>，实现在 <stl_numeric.h>。

运用示例

accumulate

adjacent_difference

inner_product

partial_sum

power

如果指数n是2的幂次方，则在第一个while就做完了，因为移位后低位一直是0，直到遇到唯一一个1变成最低位，期间x不断二次幂地执行op函数。记录算好的x，然后需要把n再右移一位（把前面说的那个‘1’扔掉，移除已经做完了的操作，即2的幂次方次操作）

此时如果n仍不为0，此时继续算：每次n右移一位代表x要再平方一次，如果右移的位是1，则result要加上；如果是0则忽略，继续向下迭代。

本质上直接用下面的while即可，但先用上面的while可以略去低位很多的连续0（如果有）。

itoa

基本算法<stl_algobase.h>

运用示例

equal

fill & fill_n

iter_swap

lexicographical_compare

max

min

mismatch

swap

copy——极高的效率

assignment operator是赋值运算符

trivial意思是平凡的（原生的），也就是在类里面的构造函数（ctor）、复制构造函数（copy）、赋值函数（assignment）、析构函数（dtor）这四个函数满足至少一条：

显式(explict)定义了这四种函数。
类里有非静态非POD的数据成员。
有基类。

则这些函数是non-trivial函数，否则就是trivial的。如果这个类都是trivial ctor/dtor/copy/assignment函数，我们对这个类进行构造、析构、拷贝和赋值时可以采用最有效率的方法，不调用无所事事正真的那些ctor/dtor等，而直接采用内存操作如malloc()、memcpy()等提高性能，这也是SGI STL内部干的事情。这里的copy，关键看类是否拥有trivial assignment。

如果迭代器指向的序列是字符串，那么直接使用字符串拷贝，效率会提高。
如果迭代器本身是指针，那么它所指向的这个序列在内存上是连续存放的，所以可能可以使用memmove复制底层内存来加速。如果指针指向的类型拥有trivial operator=（例如int类型），那么直接使用memmove复制底层内存是一种更快的方法。
如果迭代器本身就是迭代器，那么所指向的元素在内存上可能不是连续存放的，所以不能使用memmove。但是迭代器有分InputIterator和RandomAccessIterator，RandomAccessIterator可以加速复制过程。

泛化版本会借助一个__copy_dispatch结构体来应对不同的迭代器类型，从而调用不同版本的底层实现函数。__copy_dispatch结构体本质上还是一个模板结构体，通过传入的模板参数获取迭代器的类型，并调用相应版本的函数。此外，__copy_dispatch结构体还是一个函数对象，重载了operator()运算符，所以可以像调用函数一样使用__copy_dispatch结构体。

至于这里为啥要使用结构体来分发函数，而不是使用函数来分发函数，主要是因为结构体支持偏特化，而函数不支持偏特化，它只支持全特化。关于偏特化和全特化的区别，可以看这篇博客：https://harttle.land/2015/10/03/cpp-template.html。因为迭代器就算是指针，指针所指向的类型也是不确定的，而全特化不能拥有不确定的类型，它不仅需要确定迭代器类型是指针，而且还要确定指针所指向的类型，所以使用全特化不能够涵盖迭代器类型为指针的所有情况。而偏特化只是在模板的基础上进一步限定了模板参数的类型，但是它仍然可以拥有不确定的类型，所以只能用结构体偏特化。就像第一点中提到的对外接口，因为已经明确了参数必须是指向char或者wchar_t的指针，不存在不确定的类型，所以可以直接使用全特化版本。

原文链接：https://blog.csdn.net/Johnsonjjj/article/details/107743872

注：这两本版本的__copy（）根据最后一个参数iterator_tag区分。

如果对象定义了赋值操作，即具备non-trivial assignment operator，则必须循环而使用对象的”=”赋值操作。

void* memmove(void* dst,const void* src,size_t count)
{
    void* ret = dst;
    //dst <= src表示，如果dst在src的前面，从前往后复制不会覆盖src中还没有复制的内容

    if (dst <= src || (char*)dst >= ((char*)src + count))
    {
        //从前往后复制，则不会出现覆盖src中没有复制的内容
        while(count--)
        {
            *(char*)dst = *(char*)src; //char类型指针，表示一个字节一个字节的复制
            dst = (char*)dst + 1; //移动一个字节
            src = (char*)src + 1;
        }
    }
    else
    {
        //从后往前复制，则不会出现覆盖src中没有复制的内容
        dst = (char*)dst + count - 1;//移动到末尾
        src = (char*)src + count - 1;
        while(count--)
        {
            *(char*)dst = *(char*)src;
            dst = (char*)dst - 1; //移动一个字节
            src = (char*)src - 1;
        }
    }
    //返回dst的头指针，还方便左值操作。
    //如：ptstr = memmove(ptstr,src,count); cout << memmove(ptstr,src,count);
    return ret; 
}

copy测试

copy_backward

set相关算法

并集 set_union

交集 set_intersection

差集 set_difference

对称差 set_symmetric_difference

heap算法

其他算法

单纯数据处理算法

adjacent_find

count

count_if

find

find_if

find_end

find_first_of

for_each

generate

generate_n

includes（有序区间）

max_element

merge（有序区间）

min_element

partition（划分）

remove

remove_copy

remove_if

remove_copy_if

replace

replace_copy

replace_if

replace_copy_if

reverse

reverse_copy

rotate

forward版本的，交换元素然后不断调整指针位置；

bidirectional版本的解法很妙。

random的就不关注了。

rotate_copy

search

找的是连续的子序列

search_n

swap_ranges

transform

unique

unique_copy

复杂数据算法

示例

lower_bound（有序区间）

upper_bound（有序区间）

也即迭代器前面的元素≤value，注意lower_bound是**<**。一个是返回该元素第一次出现的位置，一个是返回最后一次出现的位置的下一个。如果没有value元素则返回的位置都相同。

binary_search（有序区间）

next_permutation

prev_permutation

random_shuffle

partial_sort(_copy)

sort

insertion sort

quick sort

这个函数没有（while中）对first和last作边界检查，而是以两个指针交错作为中止条件，节约了比较运算的开支。可以这么做的理由是因为，选择是首尾中间位置三个值的中间值作为pivot，因此一定会在超出此有效区域之前中止指针的移动（这其中while使用小于判断而不是小于等于判断起到了作用）。过程比较简单就不放出来了。

threshold

STL sort

这里层数乘2是因为代码的while一层只递归一半，可见后面源码。

如何理解__final_insertion_sort函数呢？

首先，unguarded版本的插入算法更快，因为不用边界检测。与常规版本相比，这个版本的插入算法直接跳入__unguarded_linear_insert函数（常规版本进入__linear_insert，先看是否比当前最小值小）。
然后，注意到不用边界检测必然有一个前提条件，就是这个值不能比当前最小值小，即不能到最左边，所以必须保证全局最小值就在最左边的区间。
最后，这个函数是如何保证最小值就在最前面的阈值大小的区间中呢？答案源于前面进行的__introsort_loop，该函数只有两种情况下可能返回：
- 一是区域小于等于阈值16；二是超过递归深度阈值。我们现在只考虑最左边的子序列：
- 先假设是由于第一种情况终止了这个函数，那么该子区域小于16。而根据快排原理，左边区间的所有数据一定比右边小，可以推断出最小值一定在该小于16的子区域内。
- 假设函数是第二种情况下终止，那么对于最左边的区间，由于递归深度过深，因此该区间会调用堆排序，所以这段区间的最小值一定位于最左端（这段区间大小不一定，但数据一定都比右区间小）。再加上前面的结论：左边区间所有的数据一定比右边小，那么该区间内最左边的数据一定是整个序列的最小值。
- 因此，不论是哪种情况，都可以保证起始的16个元素中一定有最小值。
如若元素小于阈值，也即分支语句判断的那样，直接用常规的插入排序。

对sort的理解可以参考博客：https://feihu.me/blog/2014/sgi-std-sort/#为何__final_insertion_sort如此实现

equal_range（有序区间）

inplace_merge（有序区间）

常规的merge需要一个足够大的新区间，合并两个不一定连续的序列。

注意这里两个序列是连接在一起的，缓存空间只需要能安置任何一个序列，就能简单由merge（backward）完成，因为这个merge过程使用缓存先存好了一个序列，往原来容器排序合并的过程中破坏了的元素不被需要（从缓存拿）。

针对case3：

本质上是将两个序列先分成3个序列，其中中间的序列是从前面序列拿后部分元素，从后面序列拿前部分元素。然后再把中间序列分成两个序列，就有4个序列，对前两个、后两个做merge，就减少了长度；如果长度还是不够就继续减少，因为是递归调用。
接着我们看看中间序列是怎么形成的：将长的序列分两半（对照下面例子就是len2），然后另一个序列用lower_bound，这是至关重要的一点。因为两个序列都是递增序列，则middle-cut2的元素<cut2指向的元素，这样序列一使用lower_bound得到的cut1指向的元素（包括到middle的元素）一定>middle-cut2的元素，因为cut1元素>=cut2元素。并且first-cut1之间的元素<cut2-last的元素（同样由lower_bound保证：cut1略过<cut2的元素，而到>=cut2元素时停下）
紧接着用一个rotate旋转，将middle-cut2的元素与cut1-middle的元素互换位置，就能保证first-newmiddle之间的元素比newmiddle-last的元素都小。这样分别对两个区间递归merge（每个区间又包含两个小区间），就减少了长度，使得缓冲区能容纳。
真相呼之欲出。实质上为了缩小序列，把两个序列分成了四个小序列，不妨设为l1、l2、l3、l4，l1、l2由前半序列分成，l3、l4由后半序列分成。为了分别做merge，需要保证左半边的序列已经比右半边序列元素小，但直接划分的序列不能保证这个情况，因此使用了旋转。因为l1<l2，l3<l4，而使用了lower_bound，能保证l2>l3，l4>l1。在旋转后得到l1、l3，l2、l4，就保证了l1、l3都小于l2、l4，再递归对两个序列merge即可。

nth_element

这个不动点的保证是根据左边区间<nth<右边区间，nth即可得到与排序相同的值，不用管其他元素。

最后用插入排序是因为长度比较小，没必要再一点点分割了，直接排序完省事。

merge sort

仿函数（函数对象）

概观

理解：仿函数实际上是一个类或结构体，重载了**()**运算符使得其可以像函数一样调用。而且对比一般的函数指针又具有更多的功能，比如能使用模板、拥有继承等类之间的关系，利于资源管理（如果不是暂时对象可以保存数据）、使用成员变量免去一些全局变量的维护。

可配接（adaptable）的关键

unary_function

binary_function

算术运算类仿函数

第一种实例化创建方式，在main()函数栈中，第二种方式作为cout对象的”<<”运算符函数的临时对象参数（在这个运算符函数的栈中），在cout完就结束了生命周期。如果类里定义了构造函数，则在括号里加上数值就可以使用构造函数，如plus<int>(123)(3,5)，对应的不用临时对象的方式是plus<int> plusobj(123)（使用有参构造函数，否则使用无参构造函数或默认构造函数）。

关系运算类仿函数

逻辑运算类仿函数

证同、选择、投射

配接器

概观与分类

改变仿函数（functors）接口者，称为function adapter，改变容器（containers）接口者，称为container adapter，改变迭代器（iterators）接口者，称为iterator adapter。

应用于容器，container adapters

应用于迭代器，iterator adapters

应用于仿函数，functor adapters

container adapters

iterator adapters

insert iterators

reverse iterators

注意倒转后迭代器仍保持前闭后开！这使得逻辑位置改变（指向一个位置的正向、倒转迭代器取值不同，这是因为倒转迭代器先向前一步再取值），但只有这样才能保持正向迭代器的一切惯常行为。

stream iterators

用法

输入流简单用法

#include <iostream>
#include <iterator>
using namespace std;
int main() {
    //用于接收输入流中的数据
    double value1, value2;
    cout << "请输入 2 个小数: ";
    //一般用两个流迭代器来从流中读取全部的值：指向要读入的第一个值的开始迭代器，指向流的末尾的结束迭代器。在输入流的文件结束状态(End-Of-File，EOF)被识别时，就可以确定结束迭代器。
    
    //创建表示结束的输入流迭代器
    istream_iterator<double> eos;//使用默认构造函数
    //创建一个可逐个读取输入流中数据的迭代器，同时这里会让用户输入数据
    istream_iterator<double> iit(cin);
    //判断输入流中是否有数据
    if (iit != eos) {
        //读取一个元素，并赋值给 value1
        value1 = *iit;
    }
    //如果输入流中此时没有数据，则用户要输入一个；反之，如果流中有数据，iit 迭代器后移一位，做读取下一个元素做准备
    iit++;
    if (iit != eos) {
        //读取第二个元素，赋值给 value2
        value2 = *iit;
    }
    //输出读取到的 2 个元素
    cout << "value1 = " << value1 << endl;
    cout << "value2 = " << value2 << endl;
    return 0;
}

程序执行结果为：

1
2
3

请输入 2 个小数: 1.2 2.3
value1 = 1.2
value2 = 2.3

注意，只有读取到 EOF 流结束符时，程序中的 iit 才会和 eos 相等。另外，Windows 平台上使用 Ctrl+Z 组合键输入 ^Z 表示 EOF 流结束符，此结束符需要单独输入，或者输入换行符之后再输入才有效。

输出流简单用法

#include <iostream>
#include <iterator>
#include <string>
using namespace std;
int main() {
    //创建一个输出流迭代器
    ostream_iterator<string> out_it(cout);
    //向 cout 输出流写入 string 字符串
    *out_it = "http://c.biancheng.net/stl/";
    cout << endl;

    //创建一个输出流迭代器，设置分隔符 ,
    ostream_iterator<int> out_it1(cout, ",");
    //向 cout 输出流依次写入 1、2、3
    *out_it1 = 1;
    *out_it1 = 2;
    *out_it1 = 3;
    return 0;
}

程序输出结果为：

1 2	http://c.biancheng.net/stl/ 1,2,3,

在实际场景中，输出流迭代器常和 copy() 函数连用，即作为该函数第 3 个参数。比如：

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>    // std::copy
using namespace std;
int main() {
    //创建一个 vector 容器
    vector<int> myvector;
    //初始化 myvector 容器
    for (int i = 1; i < 10; ++i) {
        myvector.push_back(i);
    }
    //创建输出流迭代器
    std::ostream_iterator<int> out_it(std::cout, ", ");
    //将 myvector 容器中存储的元素写入到 cout 输出流中
    std::copy(myvector.begin(), myvector.end(), out_it);
    return 0;
}

程序执行结果为：

1	1, 2, 3, 4, 5, 6, 7, 8, 9,

function adapters

返回值逻辑否定 not1、not2

代码中常出现的pred一词，是predicate的缩写，意指这个函数会返回真假值（bool）的表达式。

参数绑定 bind1st、bind2nd

函数合成 compose1、compose2

函数指针 ptr_fun

函数指针的前置知识可以参考：C/C++ 函数指针使用总结 - 白菜菜白 - 博客园 (cnblogs.com)

使用配接器可以使用模板。

成员函数指针 mem_fun、mem_fun_ref

这其中S是函数返回值，T是函数所属的class类型。把这个类的对象传进来，获取对应的成员函数。

后记

2022/7/18

将这本书笼统地过了一遍，大概花了将近一个月的时间。因为挺久没接触c++了，（课设写的都是纯c风格、之前平时用的是python），导致很多语法都忘记了。实际上是一个边学习边复习的过程，以至于依然有许许多多地细节等待我去发现，因此我会再花五六天的时间（甚至更多）重头开始再过一遍，这次更加注重细节（作深一番追究），以及整个宏观层次的思考和总结。不过，这些都交给明天的我吧~~

2022/7/28

第二遍大概是过完了，补充了一些要点，并且之前没看懂的部分这次也能看懂了，有的部分作了总结。中间也有休息几天，大概用了七八天吧，其中也在学计网。当然很多东西是不用只根据看就能明白的，所以接下来打算做一个小型的STL，这个项目在github上：Alinshans/MyTinySTL: Achieve a tiny STL in C++11 (github.com)，已经近7kstar了，如果要进阶STL，可以一起来学习这个项目并且自己动手实践。

概念与基础

STL六大组件

SGI STL文件分布与简介

SGI STL 的编译器组态设定(configuration)

C++ 一些特殊语法

暂时对象产生与运用

静态常量整数成员在类内直接初始化

increment/decrement/dereference运算子

前闭后开区间表示法[)

function call(函数调用) 运算子（operator()）

仿函数

总结

空间配置器

空间配置器的标准接口

设计一个简单的空间配置器 JJ::allocator

具备次配置力（sub-allocation）的 SGI 空间配置器

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

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

建构和解构基本工具：construct() 和 destroy()

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

第一级配置器 __malloc_alloc_template

第二级配置器 __default_alloc_template

空间配置函式 allocate()

空间释还函式 deallocate()

重新充填 free lists

内存池（memory pool）

内存基本处理工具

uninitialized_copy（复制迭代器）

uninitialized_fill （填充给定对象的值）

uninitialized_fill_n （fill的不同参数写法）

具体实现

uninitialized_fill_n

uninitialized_copy

uninitialized_fill

总结

迭代器（iterators）概念 与traits 编程技法

迭代器设计思维—STL 关键所在

迭代器（iterator）是一种 smart pointer

迭代器相应型别（associated types）

Traits 编程技法——STL 源码门钥

迭代器相应型别之一：value type

迭代器相应型别之二：difference type

迭代器相应型别之三：reference type

迭代器相应型别之四：pointer type

迭代器相应型别之五：iterator_category

std::iterator 的保证

iterator 源码完整重列

SGI STL 的私房菜： __type_traits （选看）

总结

序列式容器

容器的概观与分类

序列式容器（sequential containers）

vector

vector 概述

vector 定义式摘要

vector 的迭代器

vector 的数据结构

vector 的建构与内存管理：constructor, push_back

vector 的元素操作：pop_back, erase, clear, insert

list

list 概述

list 的节点（node）

list 的迭代器

list 的数据结构

list 的建构与内存管理：constructor, push_back, insert

list 的元素操作

vector和list对比总结

deque

deque 概述

deque 的中控器

deque 的迭代器

deque 的数据结构

deque 的建构与内存管理 ctor, push_back, push_front

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

总结

stack

stack 概述

stack 定义式完整列表

stack 没有迭代器

以 list做为 stack 的底层容器

迭代器（iterators）概念与traits 编程技法