《泛型编程与stl》

以下是STL六大组件(componments):
adapters  配接器 用来修饰其他组件。包括iterator adapters、function 
adapters、container adapters三大类。
allocators 配置器 用来分配空间。空间可来自于内存或磁盘--取决于配置器如何
实现。主要用来服务容器。
algorithms 算法 如sort,bineary search,permutation....
containers 容器 就是数据结构，用来存放元素。如vector,list,set,map,red
black tree,hashtalbe.
function object(functor) 函数对象（仿函数） 一种行为类似函数的东西。具体就是
重载了"function call"操作符的classes
iterators 迭代器 一种行为类似指针的东西。具体就是重载了++,--,->,*等操作
符的classes.


所有的STL算法亦都需要iterator，iterator的适用范围可以从普通的C指针，到（输出数据
流的外层包装，你可以将任何数据来源端的元素复制到任何数据目标端去。

STL包含各种泛型算法(algorithms)如sort,find和lexicographical_compare；泛型指针(it
erators)如istream_iterator和ostream_iterator；泛型容器(containers)如vector;
以及function objects如less和greater.

所谓使用STL，就是去扩充它。
STL的算法和容器是独立分离的。任何新增的算法并不要求你改写任何容器，我们可以随心
所欲地将任何算与任何容器匹配混用。
无须继承，STL便具备可扩充，可定制的特性。
抽象化并不意味效率低。

C语言中有三种不同种类的指针:
1、普通而有效的指针如&A[0]，可对它做提领动作；
2、非法指针如NULL（以称singular指针）
3、(past the end)指针，不可进行提领动作，但可用于指针运算。


C++的所有内建型别如int和void *都是default constructible.


所谓正规型别（regular type），是一种同时满足Assignable，Default Constructible,
Equality Comparable等条件的型别，亦即上述表达式都能以预期的方式进行。对于正规
型别，如果将X赋值给Y，那么X == Y必为真。
大多数基本的C++型别都是正规型别(int 就是本节提到的所有concepts的一个model），
STL定义的所有型别几乎也都是正规型别。


iterator对于泛型编程之所以重要，原因是它是算法与数据结构之间的接口。


input iterator携带的条件是功能需求最小集合，而input iterator的model则可能（而且
经常）超过这个最小集合。无论如何，一个可以和input iterator搭配的算法，不能有超
越input iterator所保证之最小功能集的任何要求。
只有single pass（单回）算法才能使用input iterator。(find)


input iterator是两个最弱的iterator concepts之一。许多算法要求获得的是其他类型的
iterators。许多算法无法单以input iterators完成。


input interator可以比较型别为iterator的两个对象的相等性，input iterator可以被复
制或被赋值(如find中first与last都是以值传入，这会调用Iterator的copy constructor)。
可以被提领，即表达式*p有定义。可以进行前置或后置的累加。


Output iterators所形成的区间都是以单独一个iterator再加上一个计量值来决定。
(copy)


ostream_iterator class是一个与istream_iterator反相的东西，同时也是一个最直觉的
output iterator.
ostream_iterator显示如何定义一个只写性质的iterator，也显示出为什么output iterator
的使用都必须是与copy相同形式的所谓single-pass算法。如果你将ostream_iterator牢记于
心，那么output iterator的限制就不会令你觉得那么怪异。


一个身为forward iterator model的型别，必然也是input interator model和output 
iterator model.(replace)
replace也是single pass算法，一次只作用一个元素。


copy是与输出输入皆有关的单回(single-pass)算法。


并非所有使用forward iterator的算法都会修改iterator所指之值。


和forward iterator(前向迭代器)一样，bidirectional iterator(双向迭代器)允许
multipass算法。而且它也可以是constant或mutable.


凡是forward iterator支持的行为，bidirectionary iterator也都支持，此外它还支持
operator--.(reverse_copy).


在此之前所提的四个iterators都只提供指针运算的一小部分子集:input iterator,
output iterator和forward iterator,只定义operator++，bidirectional iterator
也只不过增加了operator++。STL的最后一个iterator cconcept-Random Access
iterator 则涵盖其余所有指针运算:加法与减法(p+n,p-n)，下标(p[n])，两个iterator
相减(p1-p2)以及前后次序关系(p1<p2)。(sort)


Random Access Iterator对于sort这类算法很重要，因为排序算法必须有能力比对并交
换相隔甚远的元素（而非只是相邻元素）。


如果concept c2提供concept c1的所有功能，再加上其他可能的额外功能，我们便说
c2是c1的refinement(精炼，强化)，如bidirectional iterator与forward iterator
的关系。


如果concept c2是concept c1的一个refinement(强化),而某个算法要求其引数型别必
须是c1的model，那么你永远可以喂给它一个c2 model的引数型别。例如，以算法find
为例，它需要input iterator作为其template引数，而你已经知道，你可以将指针传给
find，因为指针是random access iterator的一个model.而random access iterator
是input iterator的一个refinement.


这些不同的iterator concepts提供了泛型算法一个自然分类法则。算法可以以其所采用
之iterator 


type inference(型别推论).
C++ template的引数推导过程"arguments deduction",只及于引数身上，不及于函数返回值
身上。


指针是个iterator，却不是个class.


template的特化分为全特化(full specialization,亦即为某型别如int *提供另一种定义)
和偏特化(partial specialization,亦即提供别一个定义，其自身亦为templated).


如果I是input iterator(当然亦包括input iterator的所有refinements),那么iterator_
traits<I>::value_type必须是I的value type。换言之当你定义新的iterator class时，
你必须确定你的class能够支持iterator_traits。最简单的方法便是：总是在你的class中
以嵌套型别定义value_type。这么一来你就不需要明白(explicitly)提到iterator_traits,
而定义于程序库内的iterator_traits class仍能正确运作。如果因为某种原因，使得你
无法或不方便使用现有的iterator_traits，你可以针对你的class，将iterator_traits特
化。
template <class Iterator>
struct iterator_traits{
typedef typename Iterator::value_type value_type;
};
我们可以这样的写法取用iterator I的value type:
typename iterator_traits<I>::value_type
另外，我们还需要将struct_traits特化来使它更加完整(一个是T*,另一个是const T*):
现在我们有了三种不同的iterator_traits版本:一个是针对型别为T的引数，一个是针对
型别为T*的引数，另一个是针对型别为const T*的引数。


STL已经建立了一些iterator_traits机制。


于是我们有了某种机制，让我们得以使用某个iterator的value type来撰写算法。如以下
的泛型函数用来计算nonempty range内的数值总和:
template <class InputIterator>
typename iterator_traits<InputIterator>::value_type
sum_nonempty(InputIterator first, InputIterator last)
{
typename iterator_traits<InputIterator>::value_type result = *first++;
for (; first != last; ++first)
result += *first;
return result;
}


当你定义新的iterator class时，你必须确定你的class能够支持iterator_traits。
最简单的方法便是:总是在你的class中以嵌套型别定义value_type。


Iterator Associated Types(迭代器的相关型别):value_type数值型别(sum_nonempty算法)，
difference_type差距型别(count算法)，reference引数型别，pointer指针型别。
这些associated type都定义在interator_traits之中。


iterator_traits最后定义的数个型别，更为抽象。我们要通过iterator和算法一起考虑。


如advance，其他STL算法会把它当作基本元素来使用。实际上它有三种不同的定义的
advance:一个针对input iterator(advance_II)，一个针对bidirectional iterators(
advance_BI)，一个针对random access iterator(advance_RAI).


operator->所提供的功能，不会超越我们在operator*上所定义的功能，表达式p->val
只是(*p).val的速写罢了。所有input iterators 都必须同时提供operator*和operator->
以下是advance_II的实现：
template<class InputIterator, class Distance>
void advance_II(InputIterator& i, Distance n)
{
for (; n > 0; --n, ++i){}
}


使用哪个版本的advance，我们不能在运行期才做选择，因为这样做实在是太慢了。我们必
须在编译期就选择。我们可以将advance函数重载(overloading)。只不过现在我们是对
concepts进行重载，而不是对types(型别)进行重载。
如果我们能够找出以C++型别系统(type system)来表示concepts的方法，我们就能够以一般
的函数重载来模拟concepts重载。


第一步是为每一个iterator concept定义一个专属型别，作为tag(标签)之用。
第二步将三个advance版本加以重载--以上述的标签型别(tag types)作为重载的识别凭借。
以下是advance_II的更好的实现：
template<class InputIterator, class Distance>
void advance(InputIterator& i, Distance n, input_iterator_tag)
{
// 实现代码同advance_II.
}
注意，这里也实现advance的forward iterator版本，其实现代码与input iterator相同。
最后，我们必须定出一个上层函数，由它来调用重载后的advance。此函数需要两个引数：
iterator i和距离n。它将这两个引数传给advance，并加上第三个引数:上述五个
tag types之一。因此，上层函数必须有能力推导出某个iterator type的tag type.


int *既是random access iterator的model，又是bidirectional iterator,forward iterator,
input iterator和output iterator的model，所以int *的分类是random_access_iterator_tag.


和其他associated type一样，iterator_category被定义为iterator_traits内的嵌套型别。
template <class InputIter, class Distance>
inline void advance(InputIter& i, Distance n)
{
advance(i, n, typename iterator_traits<InputIter>::iterator_category());
}
STL把这五个tag types 定义为空类。


只有当你需要定义自己的iterators或算法，你才需要担心这个机制。当你需要定义自己的算法时
以下两个理由是你可能需要用到iterator_traits：
1、你必须返回某值，或是声明临时变量，而其型别与iterator的value type或difference type
或reference type或pointer type一致。
2、你的算法类似advance。必须根据iterator的分类而决定不同的实现方法。


每当你定义一个新的iterator class I，你就必须在这个class中定义五个嵌套型别:
iterator_category,value_type,difference_type,reference和pointer.


STLe内含一个辅助类，base class iterator，它不包含任何member functions或member variables.
所以继承它不会招致任何额外开销。


iterator_traits class是颇为晚近的发明，HP原始版本的STL并未包含它。HP STL并没有value
types,difference types和iterator categories的概念，但它使用一组(较笨拙)的机制iterator
查询函数:distance_type,value_type和iterator_category.每个查询函数只需要一个引数，是个
iterator。


STL的设计允许我们加以扩充。你可以使用既有的STL算法，搭配新定义的iterators，或是使用
既有的iterators搭配新的算法。


iterators与算法都是根据iterators的条件而撰写的。


基本上，iterator必须做两件事:
1、它必须指向某物
2、它必须能够遍历任何一个有效区间。
一旦你定义了operator*与operator++，通常剩下的iterator的行为就很简单了。你必须确定
iterator被正确地定义为constant(不变的)或mutable(可变的)。这是常犯的错误之一。


STL定义了一些这种adapters，包括front_insert_iterator，back_insert_iterator和
reverse_iterator。


定义iterator时的建议:
1、注意iterator应该是constant或mutable。
2、确定iterator_traits能够正确作用于你的iterator身上，而最简单的做法就是以class
iterator作为你的base class.
3、尽可能提供较多的iterator操作行为。
4、而对forward iterator,你应该确实遵守所谓iterator相等(equality)的基本原则:只有当两个
iterators指向相同的对象，它们才被视为相等。


定义算法时的建议:
1、尽可能做最小的假设。
2、如果你能够将你的算法写成与input iterator搭配，但是另一个运用forward iterator的做
法更具效率，那么你不应该试着在效率与一般化之间做选择，你不应该放弃任何一个，你应使用
分派技术来解决这个问题。
3、当你测试你的算法时，应该尽可能使用与该iterator concept接近的具象型别，例如，如果
你写一个与input iterator搭配的算法，那么你应该使用istream_iterator来测试，而非使用
int *;
4、特别留意空区间，大多数算法将空区间视为合理。而且空区间是重要的测试条件。


STL内含许多事先定义的算法，所有STL算法都会作用在以iterator形成的range上；所有iterators
隶属于五个与指针极为类似的concepts家族。并非所有算法都可以和任何可想象的数据结构连接
搭配，例如，想要在单向链表上执行quicksort就绝对不可能。不过iterators自身提供有一种分
类方法，可以让使用者知道何种算法可用于何种数据结构。以外，某些算法会根据它所接获的
iterator的种类，分派(dispatch)给不同的实现代码处理。


function object（函数对象)
算法find只有查找与该引数相同的记录，而不能正确查找有关键它key的记录。这导致另一个
新算法find_if
template <class InputIterator, class Predicate>
InputIterator find_id(InputIterator first, InputIterator last,Predicate pred)
{
while (first != last && !pred(*first))
++first;
return first;
}
pred被声明为一个template参数predicate,即所谓的function object,而C中的习惯做法就将
pred声明为一个函数指针。


最简单的function object当推一般的函数指针(function pointer).


function call操作符operator()可以被重载，所以只要某个型别具有妥善定义的operator(),
你便可以将该对象传给find_if当作引数。这样，你可以将测试条件定义为一个class，而非
函数：
template <class Number> struct even
{
bool operator()(Number X)const {return (X & 1) == 0;}
};
需要注意的是：请尽可能将function object的operator()声明为const member function
因为如果你要以by const reference(而非by value)的方式传递function object，那么除
非operator()是个const member function，否则你就不能使用它。
find_if(first, last, even<int>());


C++函数对象:
struct last_name_is
{
string value;
last_name_is(const string& val):value(val){}
bool operator()(const Person& X)const
{
return x.last_name == value;
}
};
下面是使用这个function obectj的方法：
find_if(fist, last, last_name_is("Smith"));
上面的last_name_is class便是一个完全一般化的function object，它拥有局部状态，以及
一个constructor；而由于具有operator(),使得其对象看起来像个函数。


function object concepts:
任何function object concept的基本条件只是：如果f是个function object,我们可以将
operator()施于f身上。


单参与双参function objects:
STL内含两个版本的adjacent_find，严格地说其中只有一个版本才真正用到function object.


有的算法使用单一引数的的function obejct,有的算法使用两个引数的function object.
另有一些算法(如generate）使用的是不需要引数的function objects。


基本的function object concepts是generator,unary function,binary function。这些
concepts所描述的是能够以fun(),fun(x)和fun(x,y)调用的对象。


一元的函数对象unary function并不一定得返回true或false，它可以返回任何种类的数值。
只要其返回型别可以赋值assign给outputInterator即可。但返回bool值的function object
更常用。
单一引数并返回true或false的function objects，称为predicate,这是unary function的一
个强化(refinement)。而需要两个引数并返回true或false的function objects称为
binary predicate,是binary function的一个强化。


函数对象function object的相关型别associated type.是指其引数与其返回值的型别。
所以generator具有一个相关型别，即其返回型别。unary function具有两个型别，即其
引数与返回型别。binary function具有三个相关型，两个引数和返回型别。


就象iterator一样，我们也定义两个空的基类unary_function和binary_function，其中都
只有一些typedefs.


所以修改even<T>的方式有二，一是明白地声明出两个相关型别，要不就更简单地继承
unary_function：
template <class Number>
struct enen:public unary_function<Number, bool>
{
bool operator()(Number X)const{return (x&1)==0}
}
这不是完整的解决方案，因为它不能适用于一种很重要的function object身上：函数指针
(例如:bool (*)(int))。函数指针是内建型别，不是class，所以无法为它定义嵌套型别。


为此，STL把function objects和adaptable function objects区分开来。adaptable 
function object则会指明引数与返回型别为何，它会内含嵌套的typedefs，所以程序中可以
指定并使用那些型别。
STL提供两个基类unary_function和binary_function，这使得定义Adaptable Unary Function
和Adaptable Binary Function的工作简化许多。




Function Object Adapters函数对象配接器:
Adapter配接器是一种将某接口转换成另一接口的组件。上面讲到的reverse_iterator就是一
个iterator adapter，


你可以这样寻找某整数区间内的第一个偶数:
find_if(f, l, enen<int>());
但如果你要找某整数区间内的第一个奇数呢?你可能会想到再重新定义一个函数对象。
但我们应该重复运用代码，而非重复撰写代码.我们可以利用STL提供的function object
adapter: unary_negate


STL还定义有其他数个function object adapters。其中重要的是:1、binder1st与binder2nd,可
将adaptable binary function转换为unary function; 2、men_fun_t adapter及其变形，它们
除了作用于member function而非全局函数之外，极类似pointer_to_unary_function；
3、unary_compose,能将两个function objects f和g转换成单一一个function object使得h(x)
等于f(g(x))。




预定义的function objects:
STL所定义的基本数值运算是:plus,minus,multiplies, divides,modulus,negate。其中negate
是Adaptable Unary Function的一个model，其他都是Adaptable Binary Function的models。
基本的比较运算包括:equal_to,not_equal_to,greater,less,greater_equal和less_equal。
它们全都是adaptable binary function的models。其中最重要的是equal_to与less。它们都是
相应的缺省值。


一个对象是否小于另一个对象的测试行为是如此常见而重要，STL特别为它规范了一个专属概
念：strick weak ordering,这是binary predicate的一个强化refinement。
单独运用function object，用途并不大，function object通常只是小型的class,用来执行单一
而特定的行为。function object常常只有一个member function operator(),没有任何member 
function.
function objects，正如STL的大部分组件一样，作为作用于线性区间上的算法的附属品十分
好用。
const T*的value type是T，不是const T.


如果你想对struct初始化也像对数组做初始化动作一般（也就是在一对大括号内放置一串初值）
则你的struct必须符合某种特殊限制:struct不能拥有使用者声明的任何constructor，也不能
拥有任何private或protected members。block满足这些限制，所以我们可以像下面对数组一般
地声明一个block:
block<int, 6> A = {1, 2, 3, 4, 5, 6};
满足这些限制的型别，在C++ standard中称为aggregate type(聚合型别);


几乎所有的STL算法都可以作用于iterator所形成的range上。


所有的containers都定义有iterator和const_iterator两型别，两者都属于input iterator,
任何情况下，const_iterator一定是个constant iterator，而且我们一定可以将iterator
转换为const_iterator(但除非两型别一致，否则不能做逆向转换。是的，将const iterator
转换为mutable iterator，会严重违反const的正确性）。每个container都拥有member
function begin()和end()，而其所有元素都包含于range[begin(),end())之中。每一个
container也拥有一些辅助型别:value_type,pointer_type,const_pointer_type,
reference_type,const_reference_type,different_type和size_type。除了size_type,
它们都可以由iterator和const_iterator推导出来。


Container(Input Iterator)->Forward Container(Forward Iterator)->Reversible Container
(Bidirectional Iterator)->Random Access Container(Random Access Iterator)
STL预定义的所有container classes都是一种Forward Container，其中大多数甚至是
bidirectional container。另外一些则是Random 


下面是一个最简单的STL container,它是一个不包含任何东西的container：
template<class T>
struct trivial_container
{
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 value_type* iterator;
typedef const value_type* const_iterator;
typedef ptrdiff_t difference_type;
typedef size_t size_type;


const_iterator begin() const {return 0;}
const_iterator end() const {return 0;}
iterator begin() {return 0;}
iterator end() {return 0;}
size_type size() const {return 0;}
bool empty() const {return true;}
size_type max_size() const {return 0;}
void swap(trivial_contain &) {}
};
它正好展示了所有你必须满足的container条件。


STL定义两种大小可变的containers:
sequence container和associative container.


就像所有containers一样，sequence以严格线性顺序的range来呈现其元素。此外，你不但可
以取用任何元素，也可以在range的任意一个地点新增或删除元素。sequence都必须具有
member function insert与erase.如果S是Sequence而p是指向S内某个元素的iterator，
则S.erase(p)会移除并摧毁该元素。类似的，S.insert(p,x)会产生一个新对象，些对象是
X的一份副本，然后被安插于p所指元素之前。


STL包含三种sequence class:vector,list和deque，其中主要差异在于它们所提供的
iterator种类、iterator的无效语义（意指什么样的操作行为会造成先前取得的iterator无
效)以及insert与erase的复杂度。
vector具有Random Access Iterator性质，而且安插动作会使指向这个vector的其他iterator无效。
而list是以节点node为基础的container，其iterator属于bidirectional Iterator。安插新
元素到list之中并不涉及任何既有元素的搬移，也不会造成任何iterator无效。


sequence的insert与erase都是重载(overloaded)后的member functions。除了单元素版本之外，
还有其他版本可以一次安插或删除整个range。使用多元素版本会比多次调用单元素版本来得快
速许多，例如，如果V是个vector，L是个list，你可以将L的所有元素安插于V的开头，如下：
V.insert(V.begin(), L.begin(), L.end());
sequence的constructor亦具有多元素版本。


Front Insert Sequence具有三个特别的member functions:
1、front，返回container中的第一个元素
2、push_front,在开头安插新元素
3、pop_front，删除第一个元素
Back Insertion Sequence具有三个对应的member functions：
back, push_back, pop_back;


安插insert语义和覆盖overwrite语义:
请先看以下错误的STL写法:
int A[5] = {1, 2, 3, 4, 5};
vector<int> V;
copy(A, A+5, V.begin());
copy算法会从某个range复制元素到另一个range，它会复制range[A,A+5)到range[V.begin(),
V.begin()+5)。这意味着执行赋值动作*(V.begin()) = A[0], *(V.begin()+1) = A[1]....
但这么做不可能成功，因为vector V是空的，我们的赋值目标并不存在。


下面，让我们换个角度来看这个程序。copy没办法将新元素安插于V之中，因为copy永远看不到
V的整个本体，它只看到iterator。也就是说，复制到一个由V's iterator所形成的range,其
实这是一种覆盖overwrite语义。它会将新值赋于V的既有元素上，而非安插新的元素。要对V
安插新元素，你必须调用V的member function，而不是像现在这样调用泛型算法copy。


事实上，有办法让你以copy算法在sequence中安插新元素：利用所谓的insert_iterator adapter
或其他相关的adapters:front_insert_iterator,back_insert_iterator。


这些adapters使你得以通过iterator执行安插insert语义而非覆盖overwrite语义。
下面是以copy将新值安插到vector的正确写法:
int A[5] = {1, 2, 3, 4, 5};
vector<int> V;
copy(A, A + 5, back_inserter(V));
//back_inserter()是一种insert iterator adapter function,用来产生某个container的
back_insert_iterator;


5.3Associative Containers(关联式容器):
sequence并不强求特定顺序，你可以将一个元素安插于任意位置。另一种可变大小的container，
保证其元素总是会根据特定规则来排列。使用这种container，只要安插就好了，container自
动会将新元素安排在适当的位置。


和所有container一样，Associative Container也有value type,此外它更多了一个associated 
type,亦即其key type。


STL定义了两种Associative Container concepts，表现出两种value与key的关联方式。
一种是Simple Associative Container,其value_type和key_type相同，元素的key就是元素
自身。另一种是Pair Associative Container,其value_type的形式是pair<const key, T>.
Pair Associative Container的value是个pair,而其key则是这个pair的第一个字段。为什么是
pair<const key,T>而不是<key,T>?这和“不得将新元素安插于Associative container的任意
位置”是相同的道理，理改key会造成Associative Container前后不一致。


Muliple Associative Container允许有相同的key值，而Unique Associative Container不能
有相同的key值。


每个Associative Container内的元素都是根据key来排列。Associative Container至少有两个
不同的强化概念，分别以不同方式来组织元素。一是Hashed Associative Container,根据
hash table散列表来组织元素。它有一个嵌套型别，是个function object,作为散列函数之用。
二是Sorted Associative Container,它的元素一定以key的升幂顺序排列，也具有一个function
object嵌套型别---binary predicate,用来决定某个key是否小于另一个key。


以上三种差异具有正交性(orthogonal)。以STL的container class set为例，它属于sorted
associative container,unique associative container,Simple Associative Container.
即set的所有元素会形成一个升幂，元素之key即为该元素，不会有两个相同元素的range。




和sequence一样，associative container必须定义member function insert和erase。它也可以
一次安插（或删除）一个元素或整个range。真正差别在于:Sequence的member function insert
需要一个引数，指定安插位置，而associative container并不需要。例如若L是个list<int>下
面将L的所有元素安插于一个set内:
set<int> S;
S.insert<L.begin(), L.end());


Allocator并非sequence或associative container的需求条个的一部分。然而所有预定义的
STL container classes都允许以template参数指定其allocator。


一般的法则是，尽可能使用最简单的container class。如果你不想在container内频繁地做
安插动作，vector可能是取有效率的选择。如果你预期会频繁地执行安插动作，就应该使用
诸如list或slist之类的container.




第6章：基本概念(basic concepts):
所谓正规型别regular type，是同时兼具assignable,default constructible和equality
comparable的一个model。除非有合理的因素，否则任何使用者自定型别user_defined type
都应该是正规型别。




等价关系是数学中的基本概念，所谓等价关系是指满足reflexivity自反性，symmetry对称性
和transitivity传递性等恒长特性的关系 。


所有C++内建的数值与指针型别，都是equality comparable model。很多STL型别如
vector<int>也是。一般而言，当且仅当T是equality comparable，则vector<T>是equality
comparable。


所有C++内建的数值型别都是LessThan comparable model。指针型别也可以，但X与Y必须在
operator<domain之中。如指向同一数组的指针。


total ordering是一种特别的strict weak orderint。更明确地说，它的每个等价类(
equivalence class)只含单一数值。


所有C++内建的数值型别都是一种strict weakly comparable model。的确，整数的operator<
是total ordering,并非只是strict weak ordering。


Iterator相当重要，它让我们得以将容器container与作用其上的算法algorithm分离。大多
数的算法自身并不直接操作于container上，而是操作于iterators所形成的range上。由于所
有STL container都具有iterator，所以单一一个算法便可套用在许多不同的container types
上。container只要能够提供该iterators访问元素的方法就行了。


如果某个iterator所指位置超越container的最后一个元素，它就是所谓past_the_end。这种
iterator不但是nonsingular而且是nondereferenceable不可提领的。


dereferenceable iterator总是nonsingular，但nonsingular iterator不一定是dereferenceable.


C语言有个奇特语法：如果P是指针，则P[n]等价于n[P]。然而，一般的Random Access Iterator
不需保证支持此一性质，它只须支持i[n]就好了。


function pointer函数指针
function pointer函数指针是一种function object。所有具备operator() member function的
objects也是function object。


generator，unary function和binary function是基本的function object concepts:这些objects
分别能够以f()，f(x)和f(x,y)的形式被调用。
function objects之中无参数而返回bool者称为generator,返回bool之unary function称为
unary predicate,返回bool之binary function称为binary predicate。


function objects和adaptable function objects之间有一个重要而有点微妙的差异。
一般而言，function objects的引数型别受到限制，型别限制不一定是很单纯的，例如operator()
可能被重载，也可能是个member template,亦或两都都是。
adaptable function object可以指定引数及返回值型别，而且可以包含嵌套型别nested type
声明，好让这些型别可以被命名以及被程序使用。例如，如果F2是adaptable binary generator
的一个model，那么它必须定义嵌套型别F2::first_argument_type,F2::second_argument_type
和F2::result_type。


9.containers容器
所谓container是一种object，可以包含并管理其他objects，并提供iterators用以定址其所包含
之objects。
STL的container concepts可归属为三种广泛类型：container concept,sequence concept,
associative container concept.
某些container 以其内存分配方式作为参数，其中很多使用allocator concept。allocator并
不是container的强化refinement。


每一个container model都具有一个相关的iterator型别，可用来遍历元素。通过iterators所
形成的range，可以访问container中的所有元素。


9.2 sequence序列
所谓sequence是一种可变大小的container，其元素系以strict linear order严格线性次序加以
排列。sequence concept导入许多新的member functions,用来安插或删除任意位置上的单个元素
或某区间内的元素。




Insert(安插)
a.insert(p, t);
返回X::iterator,p是a中有效的iterator。作用，将t复制品安插于p之前。有两个重要的特案:
a.insert(a.begin(),t)将t安插于开头(第一个元素之前),a.insert(a.end(),t)将t附加于尾端。
结果:a.size()增加1。*(a.insert(p,t))是一个t复制品。但不非表示a之中的某个有效的iterator
在安插与删除之后还保证有效。其间细节根据不同的sequence class而有所不同。


Fill Insert(安插并充填)
a.insert(p, n, t);
返回void,p是a中一个有效的iterator。n>=0,a.size()+n <= a.max_size();
语义:将n个t复制品安插于p之前，


Range Insert(安插并充填一个区间)
a.insert(p, i, j);
返回void,i,j都是input iterators.
语义:将range[i,j)之复制品安插于p之前。


Erase(抹除)
a.erase(p);
返回interator,
语义:将p所指的元素析构掉，并将它从sequence中移除。返回值是个iterator,指向被移除元素的
下一个紧邻元素。如果没有这样的元素，则返回a.end();


Range erase(抹除某个区间)
a.erase(p, q);
[p, q)是a中有效的range。
将range[p, q)中的所有元素析构掉，并将它们从sequence中移除。返回值是个iterator，指向
被移除的元素群的下一个紧邻元素，如果没有这样的元素，返回值将是a.end().


Front(返回开头元素)
a.front();
如果a是可变的，返回reference,否则返回const_reference。先决条件,!a.empty();
等价于*(a.begin());


其中有两个表达式涉及一般性input iterators所形成的ranges，所以你可以将list<>内的所有
元素安插到vector<>内，像这样:
V.insert(V.begin(), L.begin(), L.end());
由于这对于任何input iterator types都必须成立，所以insert必须是个member template，换
句话说它必须是一个template形式的member function.




STL containers如vector.deque,list,slist，都是sequence的model。它们之间的差别主要在于
其iterators(vector和deque提供random access iterators,list提供bidirectional iterators,
slist提供forward iterators),以及insert/erase的运行期复杂度。


vector通常是最好的选择，它是STL containers中最为简单的一个，因些对于iterators以及元素
访问，具有最小的时间（速度）负担。然而，由于将元素安插至vector的复杂度与安插点至尾
端的元素个数成线性关系，如果安插动作频繁，其他sequences可能比较适合。如果你常在开头
或尾端执行许多安插动作，deque可能是个好选择，如果常在sequence两端之间执行许多安插动作
那么list或slist可能比较理想。




9.2.2 Front Insertion Sequence
所谓Front Insertion Sequence是一种Sequence，可以在amortized constant time内将元素安插
于起始点或取得起始位置的元素。Front insertion Sequence拥有一些特别member functions以
实现上述行为。


Front(取出起始元素)
a.front();
返回:如果a是可变的mutable就返回reference，否则返回const_reference。
先决条件:!a.empty(); 等价于*(a.begin());


Push_front(前端推入)
a.push_front(t);
返回void,等价于a.insert(a.begin(), t);


Pop front(前端取出)
a.pop_front();
返回void,等价于a.erase(a.begin());


上面的front实际上定义于sequence之中，因为它总是能够在amortized constant time内完成。


STL containers中的list,slist和deque都是Front Insertion Sequence的model,vector就不是。
vector拥用front，但不具备push_front和pop_front。在vector的起始处进行安插或删除动作，
不是一种constant time行为。


Back Insertion sequence
所谓back insetion sequence是一种sequence，可以在amortized constant time内将元素安插
于尾端，或是取出最后元素。back insertion sequence拥有某些特别的member functions,用
以实现上述行为。


Back(取出最后一个元素)
如果a可变mutable就返回reference，否则返回const_reference。先决条件:!a.empty();
等价于*(--a.end());


Push back(尾端推入)
a.push_back(t);
返回void,等价于a.insert(a.end(), t);


Pop back(尾端取出)
a.pop_back();
返回void.等价于a.erase(a.end());


STL containers中的vector,list,deque都是back insertion sequence的model，slist就不是
slist拥有back，但不具备push_back和pop_back,它是单向链表，供应的是froward iterators
而非bidirectional iterators，而且访问slist的最后一个元素并不是一种constant time行为。




9.3 associative containers关联式容器
所谓associative container是一种可变大小的container,它支持以key键值为基础，有效率地
取出元素的方法。它也提供安插与移除动作，但与sequence不同的是，它并不允许将元素安插于
特定位置。
不具有上述机制的原因是，在associative container中，元素的排列方式对class而言是一种
不变性，以sorted associative container为例，元素总是以递增次序来存储，而在hashed
associative container之中元素总是根据hash function来存储。因此，在任意位置上安插元素
是不合理的。
如同所有containers,associative container内含型别为value_type的元素，此外每个元素具
有一个型别为key_type的key键值。在某些associative containers之中，例如simple 
associative containers，其value type与key type相同，元素自身就是key。在其他associative 
containers中key键值是value实值的特定部分。由于元素的存储与其key有关，所以基本上每个元
的key是不能改变的。这表示你一旦将元素放入simple associative container内，就再也不能改
变它了，而其他的associative containers，例如pair associative container，其元素自身可
变，但作为key的那一部分不能改变。


由于associative container的元素不能任意更改，所以associative container可以不具有
mutable iterators，mutable iterators必须允许赋值动作，亦即支持表达式*i = t,但这样
会侵犯到key的不可变动性。


在simple associative container之中，元素自身就是它自己的key，因此嵌套型别iterator
和const_iterator在功能上完全相同，而且可能有相同的型别。你可以移除simple associative
container的某个元素，但无法更改其内容。其他的associative container具有可改变的元素，
而且提供某种iterator，可通过它来改变元素。你可以改变元素值，只要不要更改其key就行了。
以pair associative container为例，它具有两个不同的嵌套型别:iterator和const_iterator。
其实这里的iterator并非是个mutable iterator,因为你不能写出*i = t。但它也不完全是
constant iterator，因为如果i的型别map<int,double>::iterator,你可以写i->second = 3。


至于所谓的unique associative container,保证没有两个元素具有相同的key，multiple 
associative container则允许多个元素具有相同的key.


有很多不同的方法，可以将元素组织于数据结构中，使我们得以简单地藉由key来查询某个元素。
其中两个特别重要的数据结构是二分查找树(binary search tree)和散列表(hash table)。


associative container提供的方法:
Find(查找):
a.find(k);
如果a是可变的mutable就返回iterator,否则返回const_iterator。
语义：返回一个iterator，指向一个键值key为k的元素，这样的元素可能超过一个，若是如此
返回值所指元素并不明确，如果不存在这样的元素，返回值为a.end();


Count(计数):
a.count(k);
返回size_type。语义:返回键值key为k的元素个数
返回值不为负数，并且一定<=a.size()。对unique associative container而言，返回值非0
即1。


Equal range(找出某个等值区间):
a.equal_range(k);
如果a是可变的mutable，返回pair<iterator, iterator>，否则返回pair<const_iterator,
const_iterator>。
语义:返回所有键值key为k的元素。返回的是一个pair p，[p.first, p.second)内含所有键值
key为k的元素，注意这个member function带来的暗示:
如果两个元素的key相同，它们之间必不夹杂key不相同的其他元素。key相同的各个元素必须
连续存储在一起，这一条件正是associative container的恒长特性之一。如果a并未含有任何
符合条件的元素，就返回一个空range。
必然结果:distance(p.first, p.second) == a.count(k)。如果p是[p.first, p.second)中
的某个可提领dereferenceable iterator，则p指向某个键值key为k的元素。如果q是a中某个可
提领的dereferenceable iterator，而且q不在range[p.first, p.second)之中，那么q所指
元素的键值key就不是k。


Erase key(删除键值):
a.erase(k);
返回void,将键值key为k的所有元素析构掉，并将它们移出container。


Erase element(删除元素):
a.erase(p);
返回void，p是a中的一个dereferenceable iterator。析构p所指的元素，并将它从a中移出。


Erase range（删除某个区间):
a.erase(p,q);
返回void,[p, q)是a中一个有效的range。将range[p, q)中的元素全部析构，并将它们从a中
移出。
以上包含了元素的查询和删除方法，安插动作对unique associative container和multiple
associative container有截然不同的意义。


复杂度保证complexity guarantees:
1、Find和Equal range的平均复杂度至多是对数等级logarithmic。
2、Count的平均复杂度至多是O(log(size()) + count(k))。
3、Erase key的平均复杂度至多是O(log(size()) + count(k))。
4、Erase element的平均复杂度为amortized constant time。
5、Erase range的平均复杂度至多是O(log(size()) + N)，N代表range中的元素个数。
注意，这些都是平均复杂度，并非最坏情况。


恒长特性invariants:
1、连续存储(contiguous storage):
键值key相同的所有元素必须互相邻接。也就是说如果p和q指向具有相同键值的元素，而且p在
q之前，那么range[p, q)中的每个元素都具有相同的键值。
2、键值key的不可改变性immutability:
associative container的每一个元素，其键值key都不可改变。你可以安插或删除元素，但是
无法改变任何元素的键值key。


9.3.2 unique associative container:
所谓unique associative container是一种associative container，具有container中的每一个
key都独一无二的性质。unique associative container之中没有两个元素具有相同的key。
这意味着将元素安插于unique associative container之中需要某种先决条件:如果t的key已存
在于container中，t就无法被安插进去。


Range Constructor(区间构造函数):
X(i, j);
X a(i, j);
i和j是input iterators,其value type可转换成T。语义:产生一个associative container,内
含[i, j)的所有元素，每个元素具有独一无二的key。必然结果:size()<=distance(i, j)。
这是因为[i, j)之中可能有一些元素的key相同，果真如此便只会安插这些元素中第一个元素。


Insert element(安插元素):
a.insert(t);
返回pair<X::iterator, bool>
语义:当且仅当if and only if a没有任何一个元素与t的键值冲突，则将t安插于a。返回值是
pair p，其第二个元素的型别为bool。如果a的某个元素与t的键值冲突，则p.first指向该元素
p.second为false，如果a并未含有这样的元素，则p.first指向新插入的元素并且p.second为
true。也就是说，当t实际被安插于a之中，p.second便为true.


Insert range(安插某个区间):
a.insert(i, j);
i, j都是input iterators，其value type可转换为T。
返回void，相当于对rang[i,j)中的每个元素t做a.insert(t)动作。也就是说，只要a的元素和
range内的元素不产生键值冲突的情况，整个range便都可以安插进入a.




unique associative container不可能有两个元素具有相同的key。换句话说对于每个型别为
key_type的k,a.count(k)非0即1.


下列STL container classes都是unique associative container的models:
set, map, hash_set, hash_map






multiple associative container可内含具有相同键值key的元素，将元素安插到multiple 
associative container之中，就像将元素安插到sequence一般，并不需要什么特别条件。安
插时，insert不会检查container之中是否已具备键值相同的元素。


Range Constructor(区间构造函数):
X(i, j);
X a(i, j);
i和j是input iterators，其value type可转换成T。
语义:产生一个associative container，其内包含[i, j)内的所有元素。
container的元素个数等于distance(i, j)。range[i, j)中的每个元素都会出现在container
之中。


Insert element(安插元素):
a.insert(t);
返回X::iterator,语义:无条件安插t于a中，返回一个iterator，指向新插入的元素。


Insert range(安插某个区间):
a.insert(i, j);
i和j都是input iterators，其value type可转换为T.
返回void,等价于对range[i, j)中的每一个元素t做a.insert(t)动作。也就是说range内的每个
元素都会被安插于a.


下列STL containers classes都是multiple associative container的models:
multiset,multimap,hash_multiset,hash_multimap。


Simple Associative Container
其元素自身就是key，而非key再加上某些额外数据。key_type与value_type两型别必须相同。
型别X::iterator与X::const_iterator必须具有相同行为，甚至两都完全相同。Simple associative
container并不提供mutable iterators，这是因为associative container的key一定不可改变。
Simple associative container的元素不可改变，你可以安插或删除元素，但是元素值绝不能改变
。每个associative container具有不可改变的key。


下列STL container classes都是simple associative container的models:
set, multiset, hash_set, hash_multiset




Pair Associative Container:
它将key与某些objects产生关联。其value type形式为pair<const key_type, mapped_type>


以下STL container classes都是pair associative container的models:
map, multimap, hash_map, hash_multimap






Sorted Associative Container:
针对key做Strict Weak Ordering递增排序，来排列各个元素。


Default constructor(缺省构造函数):
X()
X a;
产生一个以key_compare()作为比较函数的空的container。


Default constructor with compare(夹带比较准则的缺省构造函数):
X(c);
X a(c);
产生一个以c作为比较函数的空的container。


Range construct(区间构造函数):
X(i, j);
X a(i, j);
i和j为input iterators，其value type可转换为T。等价于X a; a.insert(i, j);
insert所带来的影响（亦即它究竟会安插[i, j)的所有元素或只是单一元素),取决于X为multiple
associative container或是unique associative continer的model。


Range constructor with compare(夹带比较准则的区间构造函数):
X(i, j, c);
X a(i, j, c);
i和j为input iterators,其value type可转换为T。等价于X a(c); a.insert(i, j);


Key comparison(键值比较):
a.key_comp();
返回key_compare,返回a的key comparison object。后者在a构造时设定，之后便不能改变了。


Value comparison(实值比较):
a.value_comp();
返回value_compare，返回a之key comparison object所导出的value comparison object。
如果t1和t2是value_type objects,而k1和k2是其相应键值，那么a.value_comp(t1, t2)
等价于a.key_cmop(k1, k2);


Lower bound(下界):
a.lower_bound(k);
如果a可变mutable就返回iterator,否则返回const_iterator。
语义：返回一个iterator,指向第一个键值不小于k的元素。若无此等元素存在，就返回a.end()。




Upper bound(上界):
a.upper_bound(k);
如果a可变mutable，就返回iterator，否则返回const_iterator。
语义:返回一个iterator,指向第一个键值大于k的元素。若无此等元素存在，就返回a.end();




Equal range(等值区间):
a.equal_range(k);
如果a可变mutable，返回pair<iterator, iterator>,否则返回pair<const_iterator, const_iterator>.
语义:返回pair p，使得p.first为a.lower_bound(k),且p.second为a.upper_bound(k)。这个定义
符合associative container条件中所描述的语义，但更严格。如果a不包含任何键值为k的元素，
则a.equal_range(k)返回一个empty range，用来表示如果这些元素存在，它们应该放置何处。
然而associative container仅仅要求在这种状况返回值是任意的empty range。
必然结果是所有与k相等的key都包含于range[p.first, p.second)中。


Insert with hint(夹带提示的安插行为):
a.insert(p, t);
返回iterator，p是a的一个nonsingular iterator。
语义:与a.insert(t)相同。如果X是multiple associative container的一个model,就做无条件
安插动作，返回值（一个iterator)指向新安插的元素。如果X是unique associative container
的一个model，那么当尚未存在键值相同的元素时，t才会被安插。返回值是个iterator，指向新
安插的元素(如果有被安插的话),或是指向键值与k相同的元素。引数p作为提示用，应该指向t
打算被安插的位置。这个提示不会影响正确性，只会影响性能。


Sorted associative container内的元素一定根据key做递增次序排列。如果a是一个sorted
associative container，则
is_sorted(a.begin(), a.end(), a.value_comp());
必定为true。


下列STL container classes都是Sorted associative container的models:
set, map, multiset, multimap




Hashed associative container:
是一种associative container，以hash table(散列表)实现完成。Hashed associative contaienr
的元素并不保证具有任何富含意义的次序。更明确地说它们并不做排序动作。大部分hashed associative
container的操作行为，在最坏情况下，其复杂度与container的大小成线性关系。平均复杂度则
是constant time,这意味着对于只是单纯地存储与取出数值，次序并不重要的应用而言，hashed 
associative container往往比sorted associative container快上许多。


hashed associative container X的hash function散列函数是一种unary function,其引数型别
为X::key_type，其返回值型别为size_t。hash function必须具备注定性deterministic，意思是
当我们以相同的引数调用它，它一定得返回相同的值。但其返回值应该尽可能均匀uniform。理
想情况下，不会有两个键值hash出相同的实值value.


hashed associative container的元素会分组成一个个的buckets(桶子)。hashed associative
container利用hash function的值来决定将元素赋值给那一个bucket。


hashed associative container的元素个数除以buckets个数，称为load factor负载因子，一般来
说，load factor较小者其执行速度比load factor较大者快速。




Default constructor(缺省构造函数):
X();
X a;
语义:产生一个空的container，以hasher()作为hash function，并以key_equal()作为key equality
function。
结果:container大小为0。buckets数量是个未明定的缺省值。hash function是hasher()，而
key equality funciton是key_equal()。


Default constructor with bucket count(接受bucket数量之缺省构造函数):
X(n);
X a(n);
语义:以hasher()作为hash function，并以key_equal()作为key equality function，产生一个至
少具有n个buckets的空container。结果:container大小为0，buckets数量大于等于n。hash 
function是hasher()，key equality function是key_equal()。


Default constructor with hash function(接受hash function之缺省构造函数):
X(n, h);
X a(n, h);
语义:以h为hash function并以key_equal为key equality function，产生一个最少个有n个buckets
的空container。结果，container大小为0，buckets数量大于等于n。hash function是h，key
equality function是key_equal();


Default constructor with key equality(接受key equality function之缺省构造函数):
X(n, h, k);
X a(n, h, k);
语义:以h为hash function并以k为key equality function，产生一个最少具有n个buckets的空
container。结果:container大小为0。buckets数量大于等于n。hash function为h，key 
equality function为k。


Range construct(以某区间为初值的构造函数):
X(i, j);
X a(i, j);
i和j皆为input iterators,其value type可转换为T。等价于X a; a.insert(i, j);insert动
作带来的影响，也就是说它是否会将[i, j)的所有元素安插进去，抑或只是单一元素，取决于
x是multiple associative container或是unique associative container的model。


Range constructor with bucket count(接受bucket数量之区间构造函数):
X(i, j, n);
X a(i, j, n);
i和j皆为input iterators，其value type可转换为T。等价于X a(n); a.insert(i, j);


Range constructor with hash function(接受hash function之区间构造函数):
X(i, j, n, h);
X a(i, j, n, h);
i和j皆为input iterators,其value type可转换为T。等价于X a(n, h); a.insert(i, j);


Range constructor with key equality(接受key equality function之区间构造函数):
X(i, j, n, h, k);
X a(i, j, n, h, k);
i和j皆为input iterator,其value type可转换为T。等价于X a(n, h, k); a.insert(i, j);


Hash function(散列函数):
a.hash_funct();
返回X::hasher,语义：返回a的hash function。


Key equality(键值相等检验函数):
a.key_eq();
返回X::key_equal,语义:返回a的key equality function..


Bucket count(Bucket计数):
a.bucket_count();
返回X::size_type，返回a的buckets数量。


Resize(重定大小):
a.resize(n);
增加a的bucket数量。
必然结果:a的bucket数量至少为n。指向a内元素的所有iterators都仍有效。注意，虽然resize并
不造成iterators失效，但通常它会改变iterators间的次序关系。如果i和j是指向hashed associative
container的iterators，而且j在i之后，则resize完成后并不保证j还是在i之后。关于次序问题，
唯一保证的是连续存储性:键值key相同的元素一定紧邻。
作为一个一般性规则，hashed associative container尝试将其load factor维护于某个相当狭窄
的区间内（这必须满足复杂度限制。如果load factor允许无限成长，则hashed associative 
container会在元素个数成长时拙劣地扩充。
当你将元素安插于hashed associative container时，你可能会触发auto resizing机制。它会像
resize动作一样地对iterators和ranges造成影响。它会保留iterators的有效性，但不保留
iterators之间的次序关系。当然，这是resize的生存理由之一，也就是为什么会有constructor
可让你指定bucket数量的原因，如果你事先知道一个hashed associative container会成长到多
大，那么趁着container还是空的时候就设定bucket数量，会比较有效。


下列STL container classes都是hashed associative container的models:
hash_set, hash_map.




9.4 Allocator空间配置器:
Allocator是一个class，用来封装内存分配与归还的某些细节。STL预定义的所有containers
都使用Allocator来做内存管理。


关于Allocator,有三个事实比任何技术细节都来得重要:


第一，同时也是最重要的，你或许丝毫不必知道Allocator的任何事。使用STL预定义的container
时，你不需要知道Allocator的存在，因为这些container classes使用缺省的template参数
来隐藏对Allocator的使用。例如缺省情况下vector<int>意味着vector<int, alloctor<int>>。
你甚至不必知道Allocator便可以撰写新的container class。container class不必使用精致
复杂的内存管理技术。


第二，allocator是STL之中最不具移植性的一个主题。


第三，虽然container以allocator作为参数之一，但这并不表示你得以控制每一个想像可及的
内存管理层面。Allocator concept与以下各点毫无关系:deque节点中包含多少元素、container
的元素是否连续存储、vector重新分配时如何增长内存。




第10章 基本组件basic components:
pair<T1, T2>:
Class pair<T1, T2>是一个可拥有不同成分的数对，当pair自身被析构时，元素也会被析构，但
它其实并非是container的一个model，因为它并没有支持container的元素标准访问法。例如iterator.
几是需要返回两个值的函数，通常可以利用pair。
样例:
pair<bool, double> result = do_a_calculation();
if (result.first)
do_something_more(result.second);
else
report_error();
在早期的HP实现品中，pair定义于头文件<pair.h>中，但在C++ standard中它被定义于头文件
<utility>。
bool operator<(const pair& x, const pair& y);
比较操作符。如果x.first小于y.first或(x.second小于y.second且x.first与y.first相等)，则表
达式x<y为true。
template <class T1, class T2>
pair<T1, T2>::make_pair(const T1& x, const T2& y);
辅助函数，用来产生一个pair。等价于pair<T1, T2>(x, y),但比较方便。




10.2 Iterator基本要素iterator primitives:
10.2.1 iterator_traits
iterator_traits<Iterator>
所有iterators都具有相关型别(associated types),如value type, difference type等
作为iterator需求条件的一部分，STL定义了一个机制，用来取得这些相关型别。例如，假设I1
是input iterator的一个model，其value type将是iterator_traits<I1>::value_type。STL预定
义的iterator藉由三个class template iterator_traits版本，满足上述需求:1,一般版；2，指
针特殊版；3，const指针特殊版；
样例:
下面这个泛型函数用来返回nonempty range中的最后一个元素。你不可能根据旧有的value_type函数 
定义一个如此的函数，因为这个函数的返回型别必须声明为iterator的value type:
template <class InputIter>
typename iterator_traits<InputIter>::value_type
last_value(InputIter first, InputIter last){
typename iterator_traits<InputIter>::value_type result = *first;
for (++first; first != last; ++first)
result = *first;
return result;
}
iterator_traits并不在HP的实现中。根据C++ standard，它声明在头文件<iterator>中。


成员:
iterator_traits的所有成员都是一些嵌套定义nested typedef:


iterator_traits::iterator_category:
返回以下五者之一:input_iterator_tag,output_iterator_tag,forward_iterator_tag,
bidirectional_iterator_tag,random_access_iterator_tag。所谓iterator category
是指最明确的那个iterator concept，本iterator即为该concept的一个model。


iterator_traits::value_type:
iterator_traits::difference_type:
iterator_traits::pointer:
iterator_traits::reference:
正如定义于input iterator需求条件中的一样。注意，只有当
Iterator是input iterator的一个model时才可以使用之。output iterator不必具有。


10.2.2 Iterator Tag Classes
这五个iterator tag classes完全是空的。它们不具有任何member functions,member variables
或nested types。正如其名，它们仅仅被当作tag标签之用。用来表示C++型别系统中的五种iterator
concepts。




10.2.5 Iterator Base Class
iterator<Category, T, Distance, Pointer, Reference>
iterator class是个空的class,不具备任何member function或member variable，只有一些nested
typedef。
样例:
class my_forward_iterator:
public std::iterator<forward_iterator_tag, double>
{
...
};
这会令my_forward_iterator为一个forward iterator,其value type为double,difference type
为ptrdiff_t,而pointer和reference type分别为double *和double &;
不使用iterator一样可以做到相同的事，只要为my_forward_iterator定义一些嵌套型别即可:
class my_forward_iterator
{
public:
typedef forward_iterator_tag iterator_category;
typedef double value_type;
typedef ptrdiff_t difference_type;
typedef double *pointer;
typedef double& reference;
...
};
这样明白的定义出嵌套型别有时效率会更好，因为在很多编译器上，空的base class需要某些
额外空间。


10.3 allocator
allocator<T>
几乎没有什么理由需要直接用到allocator class。
STL事先定义的所有containers都具有一个身为allocator model的template参数，缺省值为
allocator。例如vector<int>就等于vector<int, allocator<int>>。


本节三个最重要的算法是uninitialized_copy,uninitialized_fill和uninitialized_fill_n。
它们和算法copy,fill,fill_n关系十分密切。两者间的唯一真正差别在于，copy,fill和fill_n
会赋值于已存在的objects身上，而低阶算法uninitialized_copy,uninitialized_fill和
uninitialized_fill_n会构造出新的objects。


10.4.1 construct
template<class T1, class T2>
void construct(T1 *p, const T2& value);
在C++中，new操作符首先分配object的内存，然后调用构造函数在该内存位置上构造object。




第11章 不改变操作对象之内容的算法nonmutating algorithms
本章叙述STL的基本算法，它们作用于iterators所形成的range之上，但不会更改这些iterators
所指元素的内容。这些算法返回range所含元素的某种信息，它们主要用于审阅，而非用来更改
内容。


11.1线性查找linear search
11.1.1 find
template <class InputIterator, class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last, 
const EqualityComparable& value);
算法find会在iterators range内执行线性查找，寻找指定之值value。更明确地说，它会返回在
[first, last)中第一个满足[*i = value]的iterator i。如果没有这样的iterator，就返回last。


11.1.2 find_if
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
如同find，算法find_if能在iterators range内执行线性查找。两者的差别在于find_if更为一般
化。它并不查找某特定值，而是查找满足某种条件的元素。它会返回range[first, last)之间第
一个满足[pred(*i)为true]的iterator i，如果没有这样的iterator存在，就返回last。
注意，你可以利用find_if来寻找第一个等于某特定值的元素。毕竟function object pred可以
测试其引数是否等于该值。即find_if可用来做与find相同的事情，但如果这样做，就不是那么有
价值了，有一个十分常见的行为是:查询具有某特定键值key的元素，例如以姓查询某人，或以
process ID查询操作系统中的某个process。而你不能用find来做这件事，因为它只能测试object
的相等性。那为什么不将find与find_if进行重载？这纯粹是技术上的原因，两个算法都具有相同
个数的引数，而且其第三个引数都是template参数，因此，编译器便无法正确调用它们。


以下找寻键值为2的第一个元素。此例中的元素是pair,而pair的第一元素便视为key。更一般化
的情况下，你可以将任何数据结构的字段视为key，你所要做的就是让function object能够将
该字段抽取出来。
int main()
{
typedef pair<int, char*> Pair;
vector<Pair> V;
V.push_back(Pair(3, "A"));
V.push_back(Pair(7, "B"));
V.push_back(Pair(2, "C"));
V.push_back(Pair(0, "D"));
V.push_back(Pair(6, "E"));

vector<Pair>::iterator p = 
find_if(V.begin(), V.end(),
compose1(bind2nd(equal_to<int>(), 2), selectlst<Pair>()));
cout<<"Found:"
   <<"<"<<(*p).first<<","<<(*p).second<<">"<<endl;
}


11.1.3 adjacent_find
(1)
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);


(2)
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
BinaryPredicate bindary_pred);
如同find,adjacent_find算法会在iterators range中执行线性查找。两者间的差异在于find是针
对单个元素查找，adjacent_find却是针对两个相邻元素查找。
adjacent_find有两个版本。版本一查找两个相等的紧邻元素。版本二则更一般化，查找两个紧邻
元素是否满足某种条件，该条件系以Binary Predicate定义。
adjacent_find第一版本返回[first, last)内第一个满足[i和i+1都有效，且*i == *(i+1)]的i。
如果没有这样的iterator存在，就返回last。
第二个版本返回[first, last)中第一个满足[binary_pred(*i, *(i+1))为true]的i。如果没有
这样的iterator存在，就返回last.


以下找寻第一个大于其后继都的元素---也就是寻找range之内不以递增次序排列的第一个元素位
置。本例运用第二版本:
int main()
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
const int N = sizeof(A) / sizeof(int);
const int* p = adjacent_find(A, A + N, greater<int>());
if (p == A + N)
cout<<"The range is sorted in ascending order."<<endl;
else
cout<<"Element "<<p - A<<"is out of order: "<<*p
<<">"<<*(p+1)<<"."<<endl;
}


11.1.4 find_first_of
(1)
template <class InputIterator, class ForwardIterator>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2);


(2)
template <class InputIterator, class ForwardIterator,
class BinaryPredicate>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator frist2, ForwardIterator lastr2,
BinaryPredicate comp);
算法find_first_of极类似find。它会在input iterator range内执行线性查找。两者间的差
异在于find查找某个特定值，而find_first_of可查找任何数量的值。更明确地说，find_first_of
会在range[first1, last1)内查找任何出现于[first2, last2)内的元素。
如果find类似c标准函数库中的strchr，那么find_first_of就有如strpbrk。
同样find_first_of有两个版本,差别在于它们比较元素否相等的方式。第一版本采用operator==，
第二版本采用外界提供的function obejct comp。


样例:
就像strpbrk一样，find_first_of的某个用途是拿来寻找字符串中的whitespace字符。不论space
空格，tab跳格定位或newline新行都是whitespace字符。
int main()
{
const char *WS = " \t\n";
const int n_WS = strlen(WS);
char* s1 = "This sentence contains five words.";
char* s2 = "OneWord";
char* end1 = find_first_of(s1, s1 + strlen(s1),
WS, WS+n_WS);
char* end2 = find_first_of(s2, s2 + strlen(s2),
WS, WS+n_WS);
printf("first word of S1:%.*s\n", end1-s1, s1);
printf("first word of s2:%.*s\n", end2-s2, s2);
}


11.2 子序列匹配subsequence matching
11.2.1 search
(1)
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 frist1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);


(2)
template <class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 frist1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate binary_pred);
算法search和find，find_if类似，可以在某个range内做查找动作，不同的是find和find_if企
图查找单个元素，而search则是企图查找整个subrange子区间，它试图在[first1, last1)内寻找
[first2, last2)。也就是说search会寻找[first1, last1)的某个子序列，使得该子序列与
[first2, last2)进行元素的一一比较时是相同的。search返回一个iterator，指向该子序列的开
头，如果这样的子序列不存在，就返回last1。


以下找寻三数形成的子序列，三数的最末一个阿拉伯数字分别为1,2,3。
template <calss Integer>
struct congruent
{
congruent(Integer mod):N(mod){}
bool operator()(Integer a, Integer b) const
{
return (a - b) % N == 0;
}
Integer N;
};


int main()
{
int A[10] = {23, 46, 81, 2, 43, 19, 14, 98, 72, 51};
int digits[3] = {1, 2, 3};
int* seq = search(A, A+10, digits, digits+3,
congruent<int>(10)); 

if (seq != A + 10){
cout<<"subsequence: ";
copy(seq, seq+3, ostream_iterator<int>(cout, ""));
cout<<endl;
}
else
{
cout<<"subsequence not found"<<eendl;
}
}
输出结果为:81 2 43


11.2.2 find_end
(1)
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);


(2)
template <class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate binary_pred);
find_end的名字是个错误。它其实比较像search而非find。比较精确的名称应该是search_end.
和search一样，find_end会在[first1, last1)之中查找与[first2, last2)相同的子序列。它们
的差异在于search找寻的是第一个这样的子序列。find_end找寻的是最后一个这样的子序列。它
返回一个iterator,指向该子序列的头。如果不存在这样的子序列，就返回last1。




11.2.3 search_n
(1)
template <class ForwardIterator, class Integer, class T>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
Integer count, const T& value);


(2)
template <class ForwardIterator, class Integer, class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
Integer count, const T& value,
BinaryPredicate binary_pred);
算法search_n查找[first, last)之中由count个相邻元素形成的子序列，其中所有元素都等于value
它返回一个iterator，指向这个子序列的起始点。如果这样的子序列不存在，就返回last。
注意,count允许为0，0个元素的子序列有其明确定义。如果调用search_n时指定count为0，查找
动作一定成功且返回值一定是first。
同样，search_n有两个版本，其间差异在于两个元素是否相等的判断方法。版本一采用operator==,
版本二采用外界提供的function object binary_pred。




11.3 计算元素个数counting elements
11.3.1 count
(1)
template <class InputIterator, class EqualityComparable>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last,
const EqualityComparable & value);


(2)
template <class InputIterator, class EqualityComparable, class Size>
void count(InputIterator first, InputIterator last,
const EqualityComparable & value,
Size & n);
算法count可以计算[first, last)之中与value相等的元素个数。
C++ standard只包含版本一，目前某些STL实现品只包含第一个版本，某些只包含第二个版本，
某些则是两个都包含。




11.3.2 count_if
(1)
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last,
Predicate pred);


(2)
template <class InputIterator, class Predicate, class Size>
void count_if(InputIterator first, InputIterator last, Predicate pred, Size &n);
算法count_if很类似count，但却更一般化。它不再是计算与某特定值相等的元素个数，而是计算
在[first, last)内满足某种条件的元素个数。该条件由外界提供的function object pred来表
现。


和find_if的情况一样，计算与某值相等之元素个数，具有更令人感兴趣的一般性:计算某些键值
与某值相等的元素个数。下面这个例子的元素是pair。pair的第一个元素被视为key。
int main()
{
typedef pair<int, char *> Pair;
vector<Pair> V;
V.push_back(Pair(3, "A"));
V.push_back(Pair(7, "B"));
V.push_back(Pair(2, "C"));
V.push_back(Pair(3, "D"));
V.push_back(Pair(0, "E"));
V.push_back(Pair(6, "E"));


cout<<"Number of elements with key equal to 3:"
<<count_if(V.begin(), V.end(),
compose1(bind2nd(equal_to<int>(), 3),
select1st<Pair>()))
<<endl;
}


以下计算range内的偶元素个数:
int main()
{
int A[] = {2, 0, 4, 6, 0, 3, 1, -7};
const int N = sizeof(A) / sizeof(int);
cout<<"Number of event element:"
<<count_if(A, A+N, 
compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)))
<<endl;
}




11.4 for_each
template <class InputIterator, class UnaryFunction>
UnaryFunction for_each(InputIterator first, InputIterator last,
UnaryFunction f);
算法for_each将function object f套用于[first, last)内的每个元素上，并忽略f的返回值（如
果有的话）。套用动作是向前进行的，也就是说是从first到last。返回值是套用于每个元素身上
的那个function obejct。
样例：
以下打印一系列元素,用的是一个能够打印其引数的unary function object。
template <class T> 
struct print:public unary_function<T, void>
{
print(ostream &out):os(out), count(0){}
void operator()(T x)
{
os<<x<<" ";
++count;
}
ostream &os;
int count;
};


int main()
{
int A[] = {1, 4, 2, 8, 5, 7};
const int N = sizeof(A) / sizeof(int);
print<int> P = for_each(A, A+N, print<int>(cout));
cout<<endl<<p.count<<" object printed."<<endl;
}
我们还可以利用C标准函数库中的system函数，依序执行操作系统指令。这种情况下，我们传给
for_each的function object是一个函数指针。


11.5 比较两个Ranges
11.5.1 equal
(1)
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 frist1, InputIterator1 last1,
InputIterator2 first2);


(2)
template <class InputIterator1, class InputIterator2,
class BinaryPredicate>
bool equal(InputIterator1 frist1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate binary_pred);


如果将[first1, last1)和[first2, first2+(last1-first1))内的元素一一比较，结果都相等的
话，equal便返回true。否则返回false。
同样，equal有两个版本，差别在于第一个版本采用operator==来比较元素，第二版本采用外界
提供的function obejct binary_pred。
以下比较两个ranges是否相等，大小写不论。
inline bool eq_nocase(char c1, char c2)
{
return toupper(c1) == toupper(c2);
}


int main()
{
const char *s1 = "This is a test";
const char *s2 = "This is a Test";
const int N = strlen(s1);


if (equal(s1, s1+N, s2, eq_nocase));
{
cout<<"Equal"<<endl;
}
else
{
cout<<"Not equal"<<endl;
}
}


11.5.2 mismatch
(1)
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 frist2);


(2)
template <class InputIterator1, class InputIterator2,
class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2,
BinaryPredicate binary_pred);
算法mismatch返回[first1, last1)与[first2, frist2+(last1-first1))之间第一个元素
值不同的位置。该位置可由[first1, last1）的一个iterator和[first2, first2+(last1
-first1))的一个iterator描述之，mismatch返回的便是一个pair，包含这两个iterators。
注意，这和equal多么类似啊，唯一差异在于当两个ranges不同时所发生的事情:equal只会返回
一个bool，但mismatch会告知它们哪里不同。表达式equal(f1, 11, f2)等价于表达式
mismatch(f1, 11, f2).first == 11，而这正是equal的一个合理实现方式。


以下找寻两个字符串中第一个字符不相同的位置，大小写不论。
inline bool eq_nocase(char c1, char c2)
{
return toupper(c1) == toupper(c2);
}


int main()
{
const char *s1 = "This is a Test";
const char *s2 = "This is a test";
const int N = strlen(s1);
pair<const char *, const char*>result =
mismatch(s1, s1+N, s2, eq_nocase);
if (result.first == s1 + N)
cout<<"The two strings do not differ"<<endl;
else
{
cout<<"Ths strings differ starting at character"
<<result.first - s1<<endl;
cout<<"Trailing part of s1: "<<result.first<<endl;
cout<<"Trailing part of s2: "<<result.second<<endl;
}
}




11.5.3 lexicographical_compare
(1)
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 frist2, InputIterator2 last2);


(2)
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
InputIterator2 frist2, InputIterator2 last2,
BinaryPredicate comp);
若以字典排序法做比较，[first1, last1)小于[first2, last2)的话，算法lexicographical_
compare返回true，反之返回false。
如果第一range内每个元素都相等于第二range内的相对元素，但第二range包含更多元素，那么
第一range被视为小于第二range。


[first1, last1)和[first2, last2)不必具有相同的元素个数。这很罕见，因为大部分作用于
两个range身上的STL算法，例如equal和copy，都要求两个ranges的长度必须相同。大部分算法
以三个iterators来指示两个ranges，但lexicographical_compare却使用四个iterators。




11.6 最大值与最小值
11.6.1 min
(1)
template <class LessThanComparable>
const LessThanComparable &min(const LessThanComparable &a,
const LessThanComparable &b);


(2)
template <class T, class BinaryPredicate>
const T&min(const T& a, const T& b, BinaryPredicate comp);
大多数STL算法都作用于元素所形成的ranges身上，min是少数作用在以引数传入之单一objects
身上的算法之一。min返回两个引数中较小的一个，如果比不出大小，就返回第一引数。




11.6.2 max
(1)
template <class LessThanComparable>
const LessThanComarable &max(const LessThanComparable &a,
const LessThanComparable &b);


(2)
template <class T, class BinaryPredicate>
const T& max(const T& a, const T& b, BinaryPredicate comp);
大多数STL算法都作用于元素所形成的ranges身上，max是少数作用在以引数传入之单一objects
身上的算法之一。max返回两个引数中较大的一个，如果比不出大小，就返回第一引数。


11.6.3 min_element
(1)
template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);


(2)
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
BinaryPredicate comp);
算法min_element寻找[first, last)内的最小元素，它返回[first, last)之内第一个满足range
之内再没有其他iterator所指之值小于*i的iterator i。如[first, last)是空的，返回值为
last。这是因为最小元素可能不只一个，所以min函数返回最小元素范围内的第一个iterator.




11.6.4 max_element
(1)
template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);


(2)
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
BinaryPredicate comp);
同min_element。






第12章 会改变操作对象之内容的算法basic mutating algorithms
本单所叙述的基本算法会更改某些iterators所指的元素。这些算法包括:(1)从某个range复制
元素至另一个range；(2)为range中的每个iterators赋值;(3)将某个值覆盖为另一个值。
本章的算法有一个相同的特质:它们更改的是iterator所指之值，而非iterator自身。或者说
这些算法会更改元素所形成的range，而非iterator range。
本章中的某些算法如partition,系作用于单一range身上。其他算法如copy，作用于两个不同的
ranges身上，一个是input range，其值不会被更改，另一个是output range,那是算法赋值结‘
果的地方。


有时候，STL对于相同的算法会提供两种形式。例如reverse会将某个range反转reverse后取而
代之，reverse_copy则会将inpu range以相反方向复制到output range上，命名原则有其一致
性:以X_copy为名的算法是以X为名的算法的复制形式。


12.1 拷贝某个区间 copying ranges
12.1.1 copy
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result);
copy只会更改[result, result+(last-first))之中的iterator所指值，而非iterator自身。它
会为output range内的元素赋予新值，而不是产生新的元素。因此，copy不能直接用来将元素安
插于空的container之中。
如果你想要将元素安插于sequence，要不就使用其insert member function,要不就使用copy
并搭配insert_iterator adapter.


注意，如果input range和output range重叠，赋值顺序需要多加讨论。当result位于[first, last)
之内，也就是说如果output range的开头与input range重叠，我们便不能使用copy。但如果output
range的尾端与input range重叠，就可以使用copy。copy_backward的限制恰恰相反。如果两个ranges
完全不重叠，当然毫无问题地两个算法都可以用。如果result是个ostream_iterator或其他某种[其语
义视赋值顺序而定]的iterator，那么赋值顺序一样会成为一个需要讨论的问题。


以下将vector的元素复制到slist身上。下面我们明白产生出一个slist，令它足以容纳vector的
所有元素。
int main()
{
char A[] = "ABCDEF";
vector<char> V(A, A + strlen(A));
slist<char> L(V.size());
copy(V.begin(), V.end(), L.begin());
assert(equal(V.begin(), V.end(), L.begin()));
}


以下将vector的元素填满空的list。由于不能直接复制到list(因为这个list之中没有任何可以
被赋值的元素），因此我们搭配output iterator adapter来使用copy，使元素得以附加于这个
list身上。
int main()
{
char A[] = "ABCDEF";
vector<char> V(A, A+strlen(A));
list<char> L;
copy(V.begin(), V.end(), back_inserter(L));
assert(equal(V.begin(), V.end(), L.begin()));
}


以下使用ostream_iterator，将list内的所有元素复制到标准输出设备上。
int main()
{
list<int> L;
L.push_back(1);
L.push_back(3);
L.push_back(5);
L.push_back(7);


copy(L.begin(), L.end(), ostream_iterator<int>(cout, "\n"));
}


12.1.2 copy_backward
template <class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
它会执行赋值动作*(result-1) = *(last-1),*(result-2) = *(last-2)....依次类推。
copy_backward则以iterator result代表其output range的尾端。这种表示法并不常见。在所有
STL算法中，这是唯一一个以指向range尾端之单iterator来表示某个range者。


12.2 互换元素swapping elements
12.2.1 swap
template <class Assignable>
void swap(Assignable &a, Assignable &b);
swap是少数作用于个别objects而非range之上的算法。swap是其他很多算法所使用的基本函数。
STL对于所有的container class,都提供特化版本的swap。因此，使用者自订型别也应该提供swap
的特代版本。


12.2.2 iter_swap
template <class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
如果a和b是iterators，那么iter_swap(a, b)等价于swap(*a, *b);
但iter_swap几乎很少被使用，你应该改用swap。




12.2.3 swap_ranges
template <class ForwardIterator1, class ForwardIterator2>
swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
算法swap_ranges可将大小相同的两个ranges的内容互换。它会将*(first1+n)与*(first2+n)互
换。返回值是first2+(last1-first1);




12.3 transform
(1)
template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryFunction op);


(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryFunction>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
InputIterator first2, OutputIterator result,
BinaryFunction binary_op);
算法transform非常类似于for_each，可在搭配一个function object后对range内的objects执行
某种运算。两者的差别在于for_each不在意function object的返回值，但transform会将该返回
值复制到另一个range中。这么做的理由正如transform的名字所暗示:它在range内的各元素身上
执行某种运算，以便将某个range转换成另一个range。
transform有两个版本。一个版本将Unary Function套用于单一input range身上，另一个版本则
是将Binary Function套用于两个大小相等的input ranges身上。


版本一执行*(result+n) = op(*(first+n))。返回值是result+(last-first)。
版本二执行*(result+n) = op(*(first1+n), *(first2+n))。返回值是result+(last1-first1)。


注意，transform可以被用来就地inplace更改序列。是的，它允许first和result是同一个
iterator。但result只能与first相同，不能与[first,last)中的其他iterator相同。


transform的第二个版本作用于两个不同的input ranges身上。既然如此，我们可利用它来计算一
个vector与一个数组的总和。Output range不一定得是list或vector，可以是任何种类的Output
iterator，甚至包括根本不与任何container相关联的Output Iterator。


int main()
{
const int N = 10;
vector<int> V(N);
fill(V.begin(), V.end(), 75);
int A[N] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
transform(V.begin(), V.end(), &A[0],
ostream_iterator<int>(cout, "\n"),
plus<int>());
}




12.4 替换元素replacing elements
12.4.1 replace
template <class ForwardIterator, class T>
void replace(ForwardIterator first, FrowardIterator last,
const T& old_value, const T&new_value);
算法replace会审阅range中的每个元素，几old_value出现之处，便改为new_value。与old_value
不相等的元素不会受到影响。


replace有个明显的一般化版本。此版本不再测试元素是否等于old_equal，而是让使用者控制
测试行为:由他们提供更一般化的Predicate。由于技术因素，这个一般化版本不能够也命名为
replace，因为两个版本具有相同的引数，而且两者都是template functions。这个一般化版
本必须有不同的名字:replace_if


样例:
以下将apples替换为oranges。
int main()
{
vector<string> fruits;
fruits.push_back("cherry");
fruits.push_back("apple");
fruits.push_back("peach");
fruits.push_back("plum");
fruits.push_back("pear");


replace(fruits.begin(), fruits.end()
string("apple"), string("oragne"));
copy(fruits.begin(), fruits.end(),
ostream_iterator<string>(cout, "\n"));
}




12.4.2 replace_if
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
Predicate pred,
const T& new_value);
算法replace_if是replace的一般化版本。它会审阅range中的每个元素，将每一个使predicate 
pred返回true的元素替换为new_value。


很多STL算法都具有两种版本，版本一执行缺省行为，版本二执行使用者指定操作行为。通常
这样的两个版本具有相同名称。算法replace和replace_if名称不同，单纯只是技术上的因素:
两个都是template functions，而且具有相同的引数个数。


样例:
replace_if的一个常见用途是确保range中的所有元素都遵循某种限制。未能遵循的元素则以
能够遵循的值取代之，下面的例子，所有负值都以0取代。
int main()
{
vector<double> V;
V.push_back(1);
V.push_back(-3);
V.push_back(2);
V.push_back(-1);
replace_if(V.begin(), V.end(),
bind2nd(less<double>(), 0),
0);
}




以下例子将长度超过6的所有字符串以字符串"******"取代之。
struct string_length_exceeds
{
string_length_exceeds(int n):limit(n){}
bool operator()(const string &s) const
{
return s.size() > limit;
}
int limit;
};


int main()
{
string A[5] = {"oxygen", "carbon", "nitrogen", "iron",
"hydrogen"};
replace_if(A, A+5,
string_length_exceeds(6),
"******");
copy(A, A+5, ostream_iterator<string>(cout, "\n"));
}




12.4.3 replace_copy
template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& old_value,
const T& new_value);
算法replace_copy可将[first, last)的元素复制到[result, result+(last-first))中，复制过
程中以new_value,取代old_value。[first, last)不会被更改。


12.4.4 replace_copy_if
template <class InputIterator, class outputIterator,
class Predicate, class T>
OutputIterator replace_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred,
const T& new_value);
算法replace_copy_if是replace_if的复制形式，就像算法replace_copy是relace的复制式一般。
样例:
以下将vector内的元素复制到标准输出设备，并将所有负值取代为0.
int main()
{
vector<double> V;
V.push_back(1);
V.push_back(-1);
V.push_back(-5);
V.push_back(2);
replace_copy_if(V.begin(), V.end(),
ostream_iterator<double>(cout, "\n"),
bind2nd(less<int>(), 0), 0);
}




12.5 充填整个区间(Filling Ranges)
12.5.1 fill
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);
算法fill将某值赋值给[first, last)中的每个元素。换句话说对于[first,last)中的每个
iterator i，执行*i = value。




12.5.2 fill_n
template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T&value);
算法fill_n将数值value赋值给[first, first+n)内的每一个元素。返回值为first+n。


样例:
制作三个137副本，添加于vector尾端:
int main()
{
vector<int> V(2, 128);
fill_n(back_inserter(V), 3, 137);
}




12.5.3 generate
template <class ForwardIterator, class Generator>
-void generate(ForwardIterator first, ForwardIterator last,
Generator gen);
算法generate会调用gen(一个不需任何引数的function object），并将其结果赋值给[first,
last)中的每个元素。即针对[first, last)中的每个iterator i,执行*i = gen();
针对[first, last)内的每一个iterators，gen都会被调用一次，而非只在循环外调用一次。这
一点很重要，因为Generator不一定会在每次调用时都返回相同结果。因此generate允许从文件
读入，取局部状态的值并更改....


如果你只想调用function obejct一次，然后将其结果赋值给range内的每个元素，可以使用fill。


12.5.4 generate_n
template <class OutputIterator, class Size, class Generator>
OutputIterator generate_n(OutputIterator first, Size n, const Generator gen);
算法generate_n会将gen(一个不需引数的function object）所得结果赋值给[first, first+n)
中的每个元素。




12.6 移除元素 Removing Elements
12.6.1 remove
template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
算法remove会将数值value从[first, last)中移除。
移除的意义有点微妙。其关键重点在于:本章之中任何一个会改变操作目标物内容的算法mutating
algorithm，包括现在所谈的remove，都不可能摧毁任何iterator或中改变first与last之间距
离。例如，假设A是个int[10]数组，如果你写remove(A, A+10, 3),实际上remove不会改变A的元
素个数，因为C语言的数组不能重定大小。
由于本章的各个算法并非作用于range身上，而是作用于iterator身上，所以移除动作removal
实际上并不会改变container的大小:它们除了对iterator所指元素赋值之外，就无法做什么了。
本书之中，移除动作的实际意思是:remove会返回一个iterator new_last,使得[first,new_last)
内的元素都不等于value。也就是说，value在[first, new_last)区间内被移除出去了。我们说
remove动作是稳定的stable，意思是区间左端的元素的相对位置不变。而[new_last, last)中的
iterators仍然可提领。
如果你从一个sequence中移除元素，你可以大大方方地将new_last之后的元素抹除掉erase。
真正抹除它们并改变sequence大小的一个做法是:
S.erase(remove(S.begin(), S.end(),x), S.end());


样例:
将vector内其值为1的元素移除。注意，调用remove之后，vector的大小仍然不变。在此程序中，
紧接着remove之后第二次打印vector，仍有九个元素。不过[V.begin(), new_end)内绝不会再
有等于1的元素。
vector的大小不会改变，直到明白调用member function erase().
template <class Container>
void print_container(const Container& C)
{
cout<<C.size()<<" elements: ";
copy(C.begin(), C.end(), 
ostream_iterator<typename Container::value_type>(cout, ""));
cout<<endl;
}


int main()
{
const int A[9] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
vector<int> V(A, A+9);
print_container(V);

vector<int>::iterator new_end = remove(V.begin(), V.end(), 1);
print_container(V);
V.erase(new_end, V.end());
print_container(V);
}

12.6.2 remove_if
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
remove_if之于remove就好比replace_if之于replace一样。remove和remove_if之所以名称不同，
纯粹是技术上的因素。因为两者都是template functions，而且具有相同的引数个数。




12.6.3 remove_copy
template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator frist, InputIterator last,
OutputIterator result, const T& value);
算法remove_copy可从[first, last)中将元素复制至以result开头的range身上，但不会复制与
value相等的元素。返回值是用来安放执行结果之range的尾端。如果[first, last)内有n个元素
不等于value，则返回值为result+n。
样例:
将vector内的所有非空符串打印出来:
int main()
{
vector<string> V;
V.push_back("one");
V.push_back("");
V.push_back("four");
V.push_back("");
remove_copy(V.begin(), V.end(),
ostream_iterator<string>(cout, "\n"),
string(""));
}




}


12.6.4 remove_copy_if
template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator remover_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
样例:
将vector内的非负元素填到另一个vector中。
int main()
{
vector<int> V1;
V1.push_back(-2);
V1.push_back(0);
V1.push_back(-1);
V1.push_back(0);
V1.push_back(1);
V1.push_back(2);

vector<int> V2;
remover_copy_if(V1.begin(), V1.end(), back_inserter(V2),
bind2nd(less<int>(), 0));
}
很多人建议STL应该包含算法copy_if，作为remove_copy_if的相反动作。remover_copy_if用
来复制不满足某个条件的所有元素，copy_if则用来复制满足某个条件的所有元素。
根据remove_copy_if实现copy_if是很简单的事。
template <class InputIterator, class OutputIterator, class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred)
{
return remove_copy_if(first, last, result, not1(pred));
}




12.6.5 unique
(1)
template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);


(2)
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate binary_pred);
算法unique能够移除重复元素。每当在[first, last）内遇到相连重复元素群出现，unique便
会移除该群中第一个以外的所有元素。
注意，unique只移除相邻的重复元素。如果你想要移除所有重复元素，你必须确定所有重复元素
都相邻。基于这个理由，unique和sort搭配特别管用。正如本章涵盖的所有算法一样，unique
实际上并不会改变[first, last)的元素个数。


12.6.6 unique_copy
(1)
template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result);


(2)
template <class InputIterator, class OutputIterator,
class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result,
BinaryPredicate binary_pred);






12.7 排列算法 Permuting Algorithms
所谓range元素的排列permutation，就是将range中的元素重定顺序。它不会删除或新增任何元素
只是将元素值以不同的顺序放入input range内。作用于range身上的许多重要算法都属于这一类
例如sorting(排序)就是其一。


12.7.1 reverse
template <class BidirectionalIterator>
void reverse(BidirectionalIterator frist, BidirectionalIterator last);
算法reverse会将range的内容就地反转，即它会将*(first+n)与*(last-(n+1))互换。




12.7.2 reverse_copy
template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result);
返回值为新产生之range尾端:result+(last-first)。
其效果相同于先copy再reverse。




12.7.3 rotate
template <class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last);
算法rotate将range内元素加以旋转rotate:它会将[first, middle)与[middle, last)互换。
rotate的用途之一是以swap_ranges所无法达到的方式来交换swap两个ranges。你可以用
swap_ranges来交换两个长度相同的ranges。但你可以用rotate来交换两个长度不同的相邻
ranges。


12.7.4 rotate_copy
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result);
算法rotate_copy是rotate的复制版本。它像是先copy然后再rotate。返回值为output range的
尾端:result+(last-first)。
样例：
数组A由一连串1接着一连串2构成。我们将这两部分以相反的次序复制到标准输出设备。
int main()
{
int A[] = {1, 1, 1, 2, 2, 2, 2};
const int N = sizeof(A) / sizeof(int);
rotate_copy(A, A+3, A+N, ostream_iterator<int>(cout, " "));
cout<<endl;
//输出2 2 2 2 1 1 1
}




12.7.5 next_permutation
(1)
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, 
BidirectionalIterator last);


(2)
template <class BidirectionalIterator, class StrictWeakOrdering>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last,
StrictWeakOrdering comp);
算法next_permutation会将元素所形成的range[first, last)转换为表格中的下一个排列顺序---
也就是字典排序方式中的下一个较大排列顺序。
若有这样的排列顺序存在，next_permutation便将[first, last)转换为该排列顺序，并返回true
否则就将[first, last)转换成词汇编纂方式下的最小排列顺序(根据定义，那便是以递增顺序排
列的一种排列排序)，并返回false。
当且仅当if and only if返回值为true，其必然结果是:元素的新排列顺序在字典排序方式下(以
lexicographical_compare判断)一定大于旧者。


12.7.6 prev_permutation




12.7 分割 partitions
12.8.1 partition
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
算法partition会依据function object pred重新排列[first, last)的元素，使满足pred的元素
排在不满足pred的元素之前。
partition的必然结果是:[first, last)内会存在某个iterator middle，使得[first, last)内
的每个iterator i都导致pred(*i)为true，并使得[middle，last）内每个iterator i都导致
pred(*i)为false。注意,partition不必保存元素原来的相对位置。它会保证[first, middle)
中的元素都满足pred而[middle,last)中的元素都不满足pred，但不对[first, middle)与[middle,
last)中的元素顺序做任何保证。相较之下，另一个算法stable_partition就会保持原来的相对
顺序。返回值为iterator middle。


样例:
int main()
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A+N, 
compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)));
copy(A, A+N, ostream_iterator<int>(cout, " "));
//输出 "10 2 8 4 6 5 7 3 9 1"
}


12.8.2 stable_partition
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(
ForwardIterator first, ForwardIterator last,
Predicate pred);
算法stable_partition与partition类似。它依据function object pred重新排列[first, last)
中的元素，使得满足pred的元素排在不满足pred的元素前。返回值也为iterator middle。
算法partition和stable_partition的不同点在于,stable_partition能够保持元素的相对顺序。
但partition执行速度较快，所以除非稳定性stability对你而言很重要，否则你不应该使用
stable_partition。


和partition不同，stable_partition是一个adaptive算法:它会试图分配临时内存缓冲区，而其
运行期复杂度取决于缓冲区中有多少内存。最坏情况下（没有配得任何内存)至多调用swap共
Nlog(N)次，其中N为first-last。最好情况下(缓冲区中有足够的内存)与N呈线性关系。


样例:
重新排列一个序列，使偶数排在奇数之前。序列初值已经过排序。对它进行分割后，偶数与奇数
仍然排过序。这是因为stable_partition会保持元素的相对顺序，这一点和partation不同。
int main()
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A) / sizeof(int);
stable_partition(A, A+N, compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)));
copy(A, A+N, ostream_iterator<int>(cout, " "));
//输出"2 4 6 8 10 1 3 5 7 9"
}


12.9 随机重排与抽样(random shuffling and sampling)
本节所列的第一个算法random_shuffle，和12.7节所列的一样都属于排列算法。它会在保持原初
始值的情况下重新排列range中的数值。本节的另两个算法就不是排列算法，它们并不随机重排
range，其执行动作与从input range中选择一个随机子集有十分密切的关联。


12.9.1 random_shuffle
(1)
template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator & rand);
算法random_shuffle随机重排[first, last)的顺序。N个元素的序列，其排列方式共有N!种，
也就是说它在N!种可能的元素排列顺序中随机选出一种，此处N为last-first。


random_shuffle有两个版本，其差别在于乱数的取得。版本一使用内部乱数产生器，版本二
使用random Number Generator，那是一种特别的function object,被当成引数传递进来，传
递方式是by reference而非by value。


使用乱数时，能够明白设定该乱数产生器的种子seed有时候是很重要的。如果这样的控制对你
的程序的确很重要，你就必须使用第二版本。




样例:
int main()
{
const int N = 8;
int A[] = {1, 2, 4, 5, 6, 7, 8};
random_shuffle(A, A + N);
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout<<endl;
//结果可能是7 1 6 3 2 5 4 8 
//或40319种其他可能性之一。
}


12.9.2 random_sample
(1)
template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator random_sample(InputIterator first, InputIterator last,
RandomAccessIterator ofirst, RandomAccessIterator olast);


(2)
template <class InputIterator, class RandomAccessIterator,
class RandomNumberGenerator>
RandomAccessIterator random_sample(InputIterator first, InputIterator last,
RandomAccessIterator ofirst, RandomAccessIterator olast,
RandomNumberGenerator &rand);
算法random_sample会随机地将[first, last)内的一个取样结果复制到[ofirst, olast)中。它会
复制n个元素，此处n为min(last-first, olast-ofirst)。返回值为ofirst+n。
同样，random_sample有两个版本，其差别在于乱数的取得。第一个版本使用内部乱数产生器，
第二个版本使用random Number Generator，那是一种特殊的function object，被当成引数传递
进来。
如果你的程序需要保持input range中的元素的相对顺序，你应该改用random_sample_n。


12.9.3 random_sample_n
(1)
template <class ForwardIterator, class OutputIterator, class Distance>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
OutputIterator out, Distance n);


(2)
template <class ForwardIterator, class OutputIterator, class Distance,
class RandomNumberGenerator。
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
OutputIterator out, Distance n,
RandomNumberGenerator &rand);
算法random_sample_n能够随机地将[first, last)中的某些元素复制到[out, out+n)中。它
会复制m个元素，此处m为min(last-first, n).返回值为ofirst+m。
random_sample_n与random_sample之间一个重要差别在于，random_sample_n会保持元素在input
range中的相对顺序，而random_sample不会。random_sample_n还必须保证有足够大的空间容纳
所有被复制的元素。


样例:
int main()
{
const int N  = 10;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
random_sample_n(A, A+N, ostream_iterator<int>(cout, " "), 4);
cout<<endl;
//打印结果可能是3 5 6 10
//或209种可能性中的任何一种
}




12.10 一般化之数值算法(Generalized Numeric Algorithms)
12.10.1 accumulate
(1)
template <class InputIterator, class T>
T accumulate<InputIterator first, InputIterator last, T init);


(2)
template <class InputIterator, class T, class BinaryFunction>
T accumulate<InputIterator first, InputIterator last, T init,
BinaryFunction binary_op);
算法accumulate为总和运算的一般型。它可以计算init和[first, last)内的所有元素的总和
或其他双参运算。
注意，accumulate的接口有点笨拙。你一定得提供一个初始值init（这么做的原因之一是当
[first, last)为空时仍获一个明确定义的值。）如果你希望计算[first, last)中所有数值
的总和，你应该将init设为0。
式中的双参操作符不必具备交换性commutative和结合性associative。所有的accumulate运算
行为的顺序都有明确设定:首先将init初始化，然后针对[first, last)之每一个iterator i，
由起头到结尾，执行result = result + *i版本一或result = binary_op(result, *i)版本二。


样例:
计算range内所有元素的总和以及乘积。本例同时示范accumulate两个版本的用法。由于加法与
乘法具有不同的证同元素(identity element)，所以计算总和时，提供0为初始值，计算乘积时
则以1为初始值。
int main()
{
int A[] = {1, 2, 3, 4, 5};
const int N = sizeof(A)/sizeof(int);
cout<<"The sum of all elements in A is "
<<accumulate(A, A+N, 0)<<endl;
cout<<"The product of all elements in A is "
<<accumulate(A, A+N, 1, multiplies<int>())<<endl;
}




12.10.2 inner_product
(1)
template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2,
T init);


(2)
template <class InputIterator1, class InputIterator2, class T,
class BinaryFunction1, class BinaryFunction2>
T inner_product(InputIterator1 frist1, InputIterator1 last1,
InputIterator2 frist2, T init,
BinaryFunction1 binary_op1,
BinaryFunction2 binary_op2);
算法inner_product能够计算[first1, last1)和[first2, frist2+(last1-first1))的一般化
内积generalized inner product。如果你想计算两个vectors的一般内积，应该将init设为0.


第一个版本会将两个ranges的内积结果加上init。也就是说先将结果初始化为init。然后针对
[first1, last1)的每一个iterator i，由起头到结尾，执行result = result+(*i)*(first2+
(i-first1));


第二个版本与第一个版本的唯一差异是以外界提供之function object来取代operator+和
operator*，也就是说，首先将结果初始化为init，然后针对[frist1, last1)的每个iterator i
由起头到结尾，执行result = binary_op1(result, binary_op2(*i, *(first2+(i-first1))))。
样例:
int main()
{
int A1[] = {1, 2, 3};
int A2[] = {4, 1, -2};
const int N = sizeof(A1)/sizeof(int);
cout<<"The inner product of A1 and A2 is "
<<inner_product(A1, A1+N1, A2, 0)
<<endl;
}




12.10.3 partial_sum
(1)
template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
OutputIterator result);


(2)
template <class InputIterator, class OutputIterator,
class BinaryFunction>
OutputIterator partial_sum(InputIterator first, InputIterator last,
OutputIterator result,
BinaryFunction Binary_op);
算法partial_sum用来计算部分总和partial sum。它会将*first赋值给*result，将*first和
*(first+1)的和赋值给*(result+1)，依次类推。注意，result可以等于iterator frist。这对
于就地in place计算部分总和很有帮助。本算法返回output range尾端,result+(last-first)。


样例:
int main()
{
const int N = 10;
int A[N];
fill(A, A+N, 1);
cout<<"A: ";
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout<<endl;

cout<<"Partial sums of A: ";
partial_sum(A, A+N, ostream_iterator<int>(cout, " "));
cout<<endl;
//输出:1, 2, 3, 4, 5 ,6 ,7 ,8 9, 10
}


12.10.4 adjacent_difference
(1)
template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
OutputIterator result);


(2)
template <class InputIterator, class OutputIterator,
class BinaryFunction>
OutputIterator adjacent_difference(InputIterator first, InputIterator last,
OutputIterator result,
BinaryFunction binary_op);
算法adjacent_difference可用来计算[first, last)中相邻元素的差额。也就是说它将*first赋
值给*result，并针对[first+1, last)内的每个iterator i，将*i与*(i-1)之差值赋值给
*(result+(i-first))。
注意:result可以等于iterator first。因此你可以利用adjacent_difference就地inplace计
算差额。




第13章 排序和查找 Sorting and Searching
本章将描述STL的排序算法（可作用于整个range或部分range),以及作用于已序sorted的ranges
身上的算法。本章所提的已序是指以递增顺序排列的range。由于range可能内含重复duplicate
元素，所以更精确地说它是一种以非递减顺序排列的range。不过本章的所有算法都已完全一般
化，都具有一个接受function objects作为参数的版本，所以你一定可以根据你的应用，完成
适当的排序方式。


13.1 对某个区间排序(sorting ranges)
除了本章所列的算法，STL还包含三种其他形式的排序法:第一，containers list和slist都拥
有member function sort，可用来对整个container排序；第二，Sorted Assocative Containers
的元素一定自动处于已序状态；第三，你可以使用heap sort算法来对任何range排序:首先调用
make_heap构造一个heap，然后调用sort_heap将这个heap转换成一个已序的range。


没有任何一种排序算法在各种情况下永远是最好的，所以你应该小心选择你的排序算法,通常sort
是个好选择，但有时候其他方法也许更恰当。


13.1.1 sort
(1)
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
算法sort可以将[first, last)中的元素以递增顺序(或更严格地说是非递减顺序）排序。sort不
一定是个稳定stable排序算法。


当你要对多字段数据进行排序的时候，稳定性stability会有举足轻重的影响。你可能想要先以
某个字段排序，再以另一个字段排序，这种情况下第二个排序行为是否稳定stable就相当重要了
算法stable_sort能够保持等价元素间的相对顺序。


sort有两个版本，其间差异在于如何定义某元素是否小于另一元素。第一版本采用operator<
来比较，第二版本采用function object comp做比较。第一版本必导致is_sorted(first, last)
为true。第二版本必导致is_sorted(first, last, comp)为true.
根据C++ standard的要求,sort平均执行O(NlogN)个比较动作，最坏情况下的复杂度O(N^2)。


早期的sort版本之所以有二次方quadratic最坏情况，因为它们通常都使用quicksort算法。
Quicksort的平均复杂度为O(NlogN)，最坏情况之复杂度则为O(N^2）。
近来的sort版本使用introsort算法，使其最坏情况下的复杂度进步到O(NlogN).


我们调用sort(A, A+N);就可将一个整数range做递增顺序排序。以递减顺序排序也是一样简单:
我们可以传入适当的function object给sort和第二版本。Function object greater是一种
Strict Weak Ordering。如下所示:
int main()
{
vector<string> fruits;
fruits.push_back("apple");
fruits.push_back("pera");
fruits.push_back("peach");
fruits.push_back("orange");
fruits.push_back("banana");
fruits.push_back("watermelon");
fruits.push_back("mango");


sort(fruits.begin(), fruits.end(),
greater<string>());
assert(is_sorted(fruits.begin(), fruits.end(), greater<string>()));
copy(fruits.begin(), fruits.end(),
ostream_iterator<string>(cout, "\n"));
}



13.1.2 stable_sort
(1)
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
和sort不同，stable_sort是一种adaptive算法。它会试图分配临时内存缓冲区，而其运行期复
杂度取决于究竟分配了多少内存。在没有分配到任何辅助内存的最坏情况下，将执行O(N(logN)^2)
个比较动作，此处的N为last-first。最好情况下（分配了足够内存)为O（N(logN)).sort和
stable_sort两者都是O(N(logN))，但sort会快上某个常量倍。


样例:
试排序一个字符序列，并忽略其中的大小写。
inline bool lt_nocase(char c1, char c2)
{
return tolower(c1) < tolower(c2);
}
int main()
{
char A[] = "fdBeACFDbEac";
const int N = sizeof(A) - 1;
stable_sort(A, A+N, lt_nocase);
cout<<A<<endl;
//输出: AaBbCcdDeEfF
}


13.1.3 partial_sort
(1)
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
RandomWeakOrdering comp);
算法partial_sort可重新安排[first, last)，使其中middle-first个最小元素以递增顺序排列。
并包含于[first, middle)内，其余的last-middle个元素安置于[middle,last)中，无任何特定
顺序。
partial_sort内部系采用heapsort来实现。
不过middle==first和middle==last是两个明显特例。
如果middle==first，partial_sort唯一保证的便是将[first, last)以未定顺序重新排列过。
如果middle==last，partial_sort会对整个[first, last)重新以递增方式排序。
如果你使用某个版本的STL sort，而该sort系以introsort实现出来，那么没有任何理由用
partial_sort的这种排序方式来取代sort。在这种情况下，sort与partial_sort都是O(NlogN)
但通常sort会快上两倍。
但如果你使用旧版本的STL sort,而该sort系以quicksort实现出来，那么有些情况你应该考虑以
partial_sort取代sort来对整个range排序。因为虽然quicksort通常是O(NlogN)，但在极少情况
下会是O(N^2)。




13.1.4 partial_sort_copy
(1)
template <class InputIterator, class RandomAccessIterator>
void partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);


(2)
template <class InputIterator, class RandomAccessIterator,
class StrictWeakOrdering>
void partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
StrictWeakOrdering comp);
partial_sort_copy会从[first, last)内复制前N个最小元素到[result_first, result_first+N)
之中，这里的N是last-first和result_last-result_first两者中的最小值，被复制过去的元素
系以递增顺序排序。返回值为result_first+N。


样例:
试将整数数组中的前4个最小值复制到另一个vector内。不可使用partial_sort_copy将结果
直接复制到标准输出设备上，因为partial_sort_copy要求其output range必须由Random
Access Iterators组成。
int main()
{
int A[] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};
const int N = sizeof(A) / sizeof(int);
vector<int> V(4);
partial_sort_copy(A, A+N, V.begin(), V.end());
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
//输出1 2 3 4
}




13.1.5 nth_element
(1)
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);
就像partial_sort一样，算法nth_element也会对range内的元素进行部分排序。它会重新排列
[first, last),也可作为分割(partition)之用:它保证[nth, last)内没有任何一个元素小于
[first, nth)内的元素。
与partial_sort不同之处在于，nth_element并不保证[first, nth)或[nth, last)都会被排序。
它只保证[first, nth）内元素都小于（或者精确地说是不大于)[nth,last）内的元素。因此
nth_element更类似于partition而非sort或partial_sort。
平均复杂度与last-first成线性关系。大大低于partial_sort的运行期复杂度。除非partial_sort
的其他保证对于你的应用程序很重要，否则你应该尽量以nth_element取代partial_sort。


13.1.6 is_sorted
(1)
template <class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last);


(2)
template <class ForwardIterator, class StrictWeakOrdering>
bool is_sorted(ForwardIterator first, ForwardIterator last,
StrictWeakOrdering comp);
is_sorted不会对range进行排序，只是用来测试某个range是否已经按从小到大的顺序排序过了。
如果[first, last)已排序，is_sorted返回true，否则返回false。
同样，is_sorted有两个版本，其差异在于如何定义某个元素小于另一个元素。第一个版本使用
operator<来进行比较，第二个版本使用function object comp来进行比较。空的range被视为
已排序。




13.2 sorted ranges上的操作行为
排序算法之所以重要，原因之一是有很多算法必须输入已排序的ranges。range一旦排序，查找
特定值，与其他已排序之range结合等等动作便会简单许多。


13.2.1 二分查找法 binary search
STL包含四种不同的二分查找算法，因为执行二分查找法时你可能想要解决不同的问题。其中最
基本（但事实上不是最有用）的问题是：某元素是否包含于某个range之中。这个问题对应到
binary_search算法。
但是通常解决这个问题还不够，如果该元素已确定包含于某range之中，你可能希望知道它的位置
如果它不在该range之中，你可能想要知道如果它在其中的话，它应该在哪里。
这便是lower_bound,upper_bound,equal_range三个算法的一般基本。之所以有三个算法，原因是
你要找寻的元素在某个range中可能不只存在一份。假设序列中有四个17，算法该给你哪一个呢？
第一个？最后一个？或是给你整个17所形成的range？这三者分别相应于lower_bound,upper_bound
equal_bound。大部分情况下，lower_bound似乎最方便。


13.2.1.1 binary_search
(1)
template <class ForwardIterator, class StrictWeaklyComparable>
bool binary_search(ForwardIterator first, ForwardIterator last,
const StrictWeaklyComparable &value);


(2)
template <class ForwardIterator, class T, class StrictWeakOrdering>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value,
StrictWeakOrdering comp);
算法binary_search是二分查找法的一个版本。它试图在已排序的[first, last)中寻找元素value.
如果[first, last)内有等价于value的元素，它会返回true，否则返回false。


样例:
试在已排序的整数数组中查找元素:
int main()
{
int A[] = {1, 2, 3, 3, 3, 5, 8};
const int N = sizeof(A) / sizeof(int);
for (int i = 1; i <= 10; ++i)
{
cout<<"Searching for "<<i<<" : "
<<(binary_search(A, A+N, i)?"present":"not present")
<<endl;
}
}


13.2.1.2 lower_bound
(1)
template <class ForwardIterator, class StrictWeaklyComparable>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const StrictWeaklyComparable &value);


(2)
template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, StrictWeakOrdering comp);
算法lower_bound是二分算法的一种版本。它试图在已排序的[first, last)中寻找元素value.
如果[first, last)具有等价于value的元素，lower_bound返回一个iterator指向其中第一个
元素。也就是说它会返回一个iterator，指向一个不小于value的元素。如果value大于[first,
last)的任何一个元素，则返回last。你可以认为其返回值是在不破坏顺序的原则下，第一个
可安插value的位置。


算法lower_bound很类似C函数库的bsearch函数。其中最主要的差别在于，当你查找某值却找不
到时，lower_bound返回如果该值存在，会出现在的那个位置。而bsearch返回null指针，表示
找不到。




13.2.1.3 upper_bound
(1)
template <class ForwardIterator, class StrictWeaklyComparable>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const StrictWeaklyComparable &value);


(2)
template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T&value, StrictWeakOrdering comp);
算法upper_bound也是二分查找法的一个版本。它会返回在不破坏顺序的情况下，可安插value的
最后一个合适位置。




13.2.1.4 equal_range
(1)
template <class ForwardIterator, class StrictWeaklyComparable>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const StrictWeaklyComparable &value);


(2)
template <class ForwardIterator, class T, class StrictWeakOrdering>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value,
StrictWeakOrdering comp);
算法equal_range也是二分查找法的一个版本，equal_range的返回值本质上结合了lower_bound
和upper_bound两者的返回值。其返回值是一对iterator i和j，其中i是在不破坏顺序的前提下
value可安插的第一个位置，j则是在不破坏顺序的前提下value可安插的最后一个位置。因此可
以得到[i, j）之间的每个元素都等价于value。


因此，我们可以这样看equal_range，我们可把它想成是[first, last)内与value等价之所有元素
所形成的range。而算法lower_bound返回该range的第一个iterator,算法upper_bound返回该range
的past-the-end iterator，算法equal_range则是以pair的形式将两者都返回。
即使[first, last)并未含有与value等价之任何元素，以上叙述仍然合理。这种情况下与value
等价之所有元素所形成的，其实是个空的range。在不破坏range顺序的前提下只有一个位置可
以安插value。而equal_range所返回的pair，其第一与第二元素iterator皆指向该位置。




13.2.2 合并Merging两个Sorted Ranges
13.2.2.1 merge
(1)
template <class InputIterator1, class InputIterator2, 
class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);


(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator,
class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, StrictWeakOrdering comp);
算法merge可将两个已排序的ranges合并成单一一个已排序的range。这个动作属于稳定stable行为
对于两个input range中等价的元素，从第一range来的元素会排在第二range来的元素之前。


请注意，算法merge和set_union十分类似，两个算法都可以由两个已排序之ranges所含元素中构
造出一个已排序的range。差别在于两个input ranges含有相同的值时的处理方式:set_union会
剔除重复元素，而merge不会。因此，merge会导致以下必然结果:output range的长度等于两个
input ranges的长度总和。相较之下set_union只保证output range的长度小于或等于input
ranges的长度总和。
样例:
int main()
{
int A1[] = {1, 3, 5, 7};
int A2[] = {2, 4, 6, 8};
const int N1 = sizeof(A1)/sizeof(int);
const int N2 = sizeof(A2)/sizeof(int);
merge(A1, A1+N1, A2, A2+N2,
ostream_iterator<int>(cout, " "));
cout<<endl;
//输出1 2 3 4 5 6 7 8
}




13.2.2.2 inplace_merge
(1)
template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);


(2)
template <class BidirectionalIterator, class StrictWeakOrdering>
inline void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last,
BidirectionalIterator comp);
如果在一个range内，[first,middle)和[middle, last)都已排序（本书中的排序都是指已递增
排序)，那么inplace_merge可将它们结合成单一已序range。和merge一样，inplace_merge也是
稳定stable操作。
算法inplace_merge是一种adaptive算法，它会试图分配内存，最坏情况下其复杂度为O(NlogN),
最好情况下最多需要N-1次比较动作。


由于将[两个连续且已排序的ranges合并的效率相当好]。所以我们可以利用[先分剖再征服(
divide and conquer)]的方法来对一个range排序:先将range对半分开，分别对各半部排序，
然后再利用inplace_merge构造出一个已排序的range。


template <class BidirectionalIter>
void mergesort(BidirectionalIter first, BidirectionalIter last)
{
typename iterator_traits<BidirectionalIter>::difference_type n
  = distance(first, last);
if (n == 0 || n == 1)
return;
else
{
BidirectionalIter mid = first + n / 2;
mergesort(first, mid);
mergesort(mid, last);
inplace_merge(first, mid, last);
}
}
这就是所谓的merge sort算法，事实上stable_sort正是以这种方式实现出来的。


13.2.3 在Sorted Ranges身上执行集合set相关操作
在抽象数学中，集合无序可言，然而在计算机程序中，我们必须选择某种方式来使集有序。
本节的算法将集合运行行为实现成sorted range上的操作行为.
除了这些算法，STL还包含一种container class,称作set。如果你希望在本节执行各种集合算法，
set是一种十分合宜的元素聚集方式。set内的元素独一无二，并且自动形成一个sorted range。
本节算法所操作的集合是以sorted ranges表示，某特定值可以不只一次地出现在sorted range中


13.2.3.1 includes
(1)
template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);


(2)
template <class InputIterator1, calss InputIterator2,
class StrictWeakOrdering>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
StrictWeakOrdering comp);
算法includes可测试某个集合是否为另一集合的子集，此处两个集合都以sorted ranges来表示。
也就是说，当且仅当[first2, last2)中的每个元素在[first1, last1)中存在等价元素，那么
includes便返回true。
样例:
int main()
{
int A1[] = {1, 2, 3, 4, 5, 6, 7};
int A2[] = {1, 4, 7};
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);


cout<<"A2 contained in A1: "
<<(includes(A1, A1+N1, A2, A2+N2)? "true" : "false")
<<endl;
}
//输出为:
A2 contained in A1: true




13.2.3.2 set_union
(1)
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);


(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator,
class StrictWeakOrdering>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
StrictWeakOrdering comp);
算法set_union可构造出两集合之联集。如果某个值在[first1, last1)出现n次，同样的值在
[first2, last2)出现m次，那么该值在output range中会出现max(m, n)次。




13.2.3.3 set_intersection
(1)
template <class InputIterator1, class InputIterator2, 
class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);


(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator,
class StrictWeakOrdering>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 frist2, InputIterator2 last2,
OutputIterator resutl,
StrictWeakOrdering comp);
算法set_intersection可以构造出两集合的交集。也就是说，它能构造出集合S1∩S2，包含每一
个在S1且在S2中出现的元素。S1, S2及其交集都以sorted ranges表示。返回值为output range
的尾端。[first1 last1)或[first2, last2)内的元素并不一定得独一无二。如果某值在[first1,
last1)出现n次，在[first2, last2)出现m次，那么该值会在output range中出现min(m, n)次。
交集属于稳定stable操作，意思是元素都是从第一个ranges复制过来，而且output range内的元素
相对顺序一定和第一个input range的相对顺序相同。


13.2.3.4 set_difference
(1)
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);


(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator,
class StrictWeakOrdering>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result,
StrictWeakOrdering comp);
算法set_difference可构造出两集合之差。也就是说，它能构造出集合s1-s2，其中包含出现于
S1但不出现在S2内的每个元素。S1, S2及其差集都以sorted ranges表示。返回值为output range
尾端。如果某值在[first1, last1)出现n次，在[first2, last2)出现m次,那么该值在output 
range中会出现max(n-m, 0)次。它同样是稳定操作stable。意味着元素都复制自第一个range而
非第二个range。


13.2.3.5 set_symmetric_difference
(1)
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);


(2)
template <class InputIterator1, class InputIterator2,
class OutputIterator,
class StrictWeakOrdering>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result,
StrictWeakOrdering comp);
算法set_symmetric_difference可构造出两集合之对称差。即出现于S1但不出现于S2内的所有元
素以及出现于S2但不出现于S1内的所有元素。S1,S2及其对称差集都以sorted ranges表现，返回
值为output range的尾端。如果某值在[first1, last1)出现n次，在[first2, last2)出现m次，、
那么该值在output range中会出现|n-m|次。




13.3 堆的相关操作 heap operations
堆heaps并不是sorted ranges。堆中的元素并不会以递增顺序排列，而是以一种更复杂的方式排列。
堆内部事实上是以树状方式来表现一个sequential range，该树状结构系以每个节点小于或等于
其父节点的方式构造。


由于三个理由，使得堆和sorted ranges有密切关系。第一，和sorted ranges一样，堆提供高
效率的方式来取得其最大元素。如果[first,last)是一个堆，那么*first便是堆中的最大元素。
第二，我们可以在对数logarithmic时间内以push_heap为堆增加新元素，或以pop_heap为堆移除
某元素。第三，有一种简单而有效率的算法，称作sort_heap，可将堆转成sorted range。


堆是一种表现priority queues的方便法门，后者的每一个元素都以任意顺序安插，但移除的
顺序是由最大到最小。例如STL有一个container adapter priority_queue就是以堆实现出来。


13.3.1 make_heap
(1)
template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,\
StrictWeakOrdering comp);
算法make_heap可将任意的range[first,last)转换成一个堆。


13.3.2 push_heap
(1)
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
算法push_heap可以为堆heap增加新元素。其接口有点特别:堆以[first, last-1)表示，新增元素
为*（last-1)。


13.3.3 pop_heap
(1)
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
算法pop_heap可移除堆[first, last)内的最大元素，即移除*first。




13.3.4 sort_heap
(1)
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
算法sort_heap可将堆[first, last)转换为sorted range。这并不是个稳定stable排序法。




13.3.5 is_heap
(1)
template <class RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last);


(2)
template <class RandomAccessIterator, class StrictWeakOrdering>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);
如果[first, last)是一个堆，算法is_heap返回true，否则返回false。

第14章 Iterator classes迭代器类
每个STL container都拥有嵌套的nested iterator classes，这是它之所以被称为"container"
的部分原因。此外，STL亦包含一些独立运作的iterator classes,其中大部分是iterator 
adapters。
C++ standard规定，所有标准的iterator classes都得继承自base class iterator。但你应该
记住，这纯粹只是实现上的细节。真正重要的是，如果一个iterator class希望内含iterator_
traits所要求之各种嵌套型别，继承自iterator只不过是可行方法之一，而且并不一定是最简单
的方法。从template base classes身上继承而来的型别声明，有着某种复杂技术限制:明白提供
嵌套的typedefs通常才是比较简单的做法。


14.1 insert Iterators
14.1.1 front_insert_iterator
front_insert_iterator<FrontInsertionSequence>
class front_insert_iterator是具有Output iterator功能的一个iterator adapter。通过
front_insert_iterator完成的赋值动作，可将object安插于Front Insertion Sequence中的
第一个元素之前。
注意，Front Insertion Sequence自身已经具备iterators，毕竟它是一个container，而所有
的containers都定义有它们自已的iterators。那么我们为什么还需要为Front Insertion 
Sequence定义另一种iterator呢？
是的，我们必须这么做，因为其行为和sequence's iterators有很大的差别。假设seq是个
Front insertion sequence，那么seq::iterator就具有覆盖overwrite语义，而front_
insert_iterator<seq>具有安插insertion语义，如果i是一个有效的seq::iterator，指向某
序列S中的某个元素，那么表达式*i = t会将该元素以t取代，但不改变S的元素的总个数，如
果ii是一个有效的front_insert_iterator<seq>，那么*ii = t就相当于seq.push_front(t)，会
为S增加新元素，而非覆盖S中的任何既有元素。


样例:
int main()
{
list<int> L;
L.push_front(3);
front_insert_iterator<list<int>> ii(L);
*ii++ = 0;
*ii++ = 1;
*ii++ = 2;
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
//打印结果为2 1 0 3
}
每个通过ii的赋值动作会将元素新增于L开头处。


template <class FrontInsertionSequence>
front_insert_iterator<FrontInsertionSequence>
front_inserter(FrontInsertionSequence &S);
等价于front_insert_iterator<FrontInsertionSequence>(S).这个辅助函数之所以存在，主要是
为了便利性:它是一个非成员函数，所以template参数可被推导出来，而且无须明白声明型别
front_insert_iterator。




14.1.2 back_insert_iterator
back_insert_iterator<BackInsertionSequence>
class back_insert_iterator是一种iterator adapter,通过back_insert_iterator，赋值动作可
将object安插于back insertion sequence的最后一个元素之后。
与front_insert_iterator一样，back_insert_iterator同样也存在一个辅助函数back_inserter


14.1.3 insert_iterator
insert_iterator<container>
class insert_iterator是一种iterator adapter,功能如同output iterator。通过insert_iterator
赋值动作可将object安插于container之中。如果ii是个insert_iterator,那么ii会持续追踪一个
container C和一个安插点p，表达式*ii = t将执行安插动作c.insert(p, t)。


在每个container都已拥有iterator的情况下，insert_iterator之所以存在，原因是insert_iterator
提供安插语义而非覆盖语义。如果i一个有效的C::iterator，指向container C内的某个元素，
表达式*i = t会将该元素以t取代，但不改变c的元素总个数。但如果ii是个insert_iterator<C>,
*ii = t就相当于c.insert(p, t)，它会为c新增元素，而非覆盖C内的任何既有元素。
你可以拿insert_iterator搭配任何container，只要后都对表达式c.insert(p, t)有所定义。
sequence和sorted associate container都定义有这种表达式。
对sequence S而言，表达式S.insert(p, x)表示将数值x安插于紧邻iterator p之前。
sorted associate container的元素一定以key的递增顺序出现。sorted associate container虽
定义有带两个引数的insert版本，但只是作为优化之用:第一个引数只是个提示，指向查找起始
位置。
注意，output Iterator的定义只要求*ii = t需为有效表达式。


14.2 Stream Iterators
STL事先定义的iterators大多都能迭代于container元素之中，但这并非必要条件。


14.2.1 istream_iterator
istream_iterator<T, char T, traits, Distance>
istream_iterator是一种input iterator，它能为来自某个basic_istream的object执行格式化
输入动作。一旦stream结束，istream_iterator便呈现一个特别的stream终结值，此值为
past-the-end iterator。input iterator的所有限制都必须被遵守，包括operator*和
operator++操作顺序上的限制。
在最初的C++ stream I/O版本中，istream是一个由某输入设备读入char的class。然而C++ 
standard中的istream并非是个class，而是一个typedef。它是basic_istream<char, 
char_traits<char>>的别名。此处的class basic_istream是个template,可为一般化的字符执行
格式化输入。


样例:
int main()
{
vector<int> V;
copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(V));
}
HP STL将istream_iterator定义于头文件<iterator.h>。c++ standard将它声明于<iterator>。


istream_iterator::istream_iterator(istream_type &s)
这是constructor。产生一个可从input stream读取数据的istream_iterator。当s到达stream
终点，这个iterator和end_of_stream iterator相比较的结果会相等。end-of-stream iterator
由default constructor产生出来。


istream_iterator::istream_iterator()
这是default constructor。产生一个end_of_stream iterator,那是个past_the_end（最后元素
的下一位置）iterator，可于构造某个区间range时派上用场。




14.2.2 ostream_iterator
ostream_iterator<T, charT, traits>
ostream_iterator是一种output iterator，它能将一个T objects格式化输出到某个特定的
basic_ostream中。Output iterator的所有限制都必须被遵守，包括operator*和operator++
操作顺序上的限制。 


样例:
以相反的顺序，将一个vector复制到标准输出设备上，一个元素占一行。此例之中，我们所使用的
ostream_iterator constructor需要两个参数。第二个参数是个字符串，会在每个元素打印之后
被打印。
int main()
{
vector<int> V;
for(int i = 0; i < 20; ++i)
V.push_back(i);
reverse_copy(V.begin(), V.end(), ostream_iterator<int>(cout, "\n");
}


ostream_iterator::ostream_iterator(ostream_type &s)
这是constructor。此式产生一个ostream_iterator，使得通过它所进行的赋值动作犹如s<<t。
ostream_iterator::ostream_iterator(ostream_type &s, const charT* delim)
这是具定界符号delimiter的constructor，此式产生一个ostream_iterator,使得通过它所进行
的赋值动作犹如s<<t<<delim。




14.2.3 istreambuf_iterator
istreambuf_iterator<charT, traits>
istreambuf_iterator和istream_iterator非常相似，但它并不执行任意型别的一般格式化输入
而是从input stream读入单字符。这是一种input iterator，并且就像istream_iterator一样
在遇到stream终结时，会以一个特别的past-the-end值表示之。


样例:
将标准的input stream中剩余的所有字符读进一个缓冲区内。
int main()
{
istreambuf_iterator<char> first(cin);
istreambuf_iterator<char> end_of_stream;
vector<char> buffer(first, end_of_stream);
...
}


istreambuf_iterator::istreambuf_iterator(istream_type &s)
这是constructor。它会产生一个istreambuf_iterator。可藉此从input stream s中读值。一
旦遇到stream终结点，这个iterator与default constructor所产生之end-of-stream iterator
相比较的结果必为相等。


istreambuf_iterator::istreambuf_iterator(istreambuf_type *s)
这是constructor。它会产生一个istreambuf_iterator。可藉此从streambuf *s中读值。一
旦遇到stream终结点，这个iterator与default constructor所产生之end-of-stream iterator
相比较的结果必为相等。如果s是null指针，这个constructor等价于default constructor。


istreambuf_iterator::istreambuf_iterator()
这是default constructor。它会构造出一个end-of-stream iterator,这是一个past-the-iterator
当我们需要构造一个range时，它很管用。




14.2.4 ostreambuf_iterator
ostreambuf_iterator<charT, traits>
ostreambuf_iterator是一种output iterator，可将字符写入一个output stream之中。它和
ostream_iterator很相似，但不会执行任意型别的一般格式化输出，而是利用streambuf class
的sputc member function输出单个字符。




14.3 reverse_iterator
reverse_iterator<Iterator>
class reverse_iterator是一种iterator adapter,能够在range上逆向移动。在reverse_iterator
<Iter> object上执行operator++和在Iter object上执行operator--的结果是相同的。


14.4 raw_storage_iterator
raw_storage_iterator<ForwardIterator, T>
class raw_storage_iterator是一种adapter，可以让STL算法与低阶内存操作彼此结合起来。当
你有必要将内存的分配与对象的构造分开处理时，它就可以派上用场。


raw_storage_iterator<Iter> r与其底部underlying iterator i指向同一块内存。表达式
*r = x等价于表达式construct(&*i, x);
除非你打算撰写一个container或是一个adaptive算法，否则不应该用到raw_storage_iterator
adapter。事实上你或许根本就不该用它:直接使用construct或其他得以将某个range中的所有
成员都初始化的算法几乎总是比较好的选择。






第15章 Function object classes 函数对象类
就像第8章所讨论的，很多STL算法会利用function object将执行动作参数化。STL含有大量事
先定义好的function object，可执行基本的数值运算和逻辑运算。
STL事先定义的所有function object都隶属于Adaptable Unary Function或Adaptable Binary
Function,意味着它们都声明有嵌套型别，用以描述其引数型别和返回值型别。如果你要自行实
现一个function object，有一种方法可以提供这些嵌套型别（但此法并非唯一，也不见得最好）
就是继承自一个空的base classes unary_function或binary_function。有时你可能会发现，直
接以typedefs定义这些嵌套型别会比较简单，因为在C++语言中，从一个template base class
继承型别的声明，有相当复杂的技术限制。


C++ standard规定所有标准的function object classes都必须继承自unary_function或
binary_function，但你应该记住这纯粹只是实现细节。真正的重点是，它们必须具备Adaptable
Unary Function与Adaptable Binary  Function这两个concepts所要求的嵌套型别。


15.1 Function Object Base Classes
15.1.1 unary_function
unary_function<Arg, Result>
unary_function是一个空的base class，其中没有任何member functions或member variables，
只有型别信息。它的存在是为了让Adaptabel Unary Function models的定义更方便些。是的，
Adaptable Unary Function的models都必须内含嵌套型别的声明，而继承unary_function则是
获得这些嵌套型的方便法门。


样例:
struct sine: public unary_function<double, double>
{
double operator()(double x) const{return sin(x);}
};
HP STL将unary_function声明于头文件<function.h>,C++ standard将它声明于functional>




15.1.2 binary_function
binary_function<Arg1, Arg2, Result>
binary_function class是一个空的base class，不含任何member functions或member variables
只含型别信息。它的存让Adaptable Binary Function models的定义变得更方便些。Adaptable
Binary Function的任何models都必须包含嵌套型别声明，而继承base class binary_function
就是获得这些typedefs的一种方便法门。


样例:
struct exponentiate: public binary_functin<double, double, double>
{
double operator()(double x, double y) const {return pow(x, y);}
};




15.2 算术运算 Arithmetic Operations
15.2.1 plus
plus<T>
class plus<T>是一种Adaptable Binary Function，如果f是class plus<T>的一个object,而
且x和y都是型别为T的值，则f(x, y)返回x+y;


样例:
令V3内的每个元素是V1和V2内对应元素之和:
int main()
{
const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

generate(V1.begin(), V1.end(), rand);
fill(V2.begin(), V2.end(), -RAND_MAX / 2.0);

transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), plus<doulbe>());

for (int i = 0; i < N; ++i)
assert(V3[i] == V1[i] + V2[i];
}




15.2.2 minus
minus<T>
Class minus<T>是一种Adaptable Binary Function。如果f是class minus<T>的一个object，而
且x和y都属于T型别，则f(x, y)返回x-y。


样例:
v3内的每个元素都是v1和v2内对应元素之差。
int main()
{
const int N = 1000;
vector<double> v1(N);
vector<double> v2(N);
vector<double> v3(N);


generate(v1.begin(), v2.end(), rand);
fill(v2.begin(), v2.end(), -RAND_MAX / 2.0);

transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), minus<double>());


for (int i = 0; i < N; ++i)
assert(v3[i] == v1[i] - v2[i]);
}




15.2.3 multiplies
multiplies<T>
class multiplies<T>是一种Adaptable Binary Function。如果f是class mutiplies<T>的一个
object，且x和y都属于T型别，则f(x, y)返回x * y;


样例:
将1!至20!的值填入一个表格中。
int main()
{
const int N = 20;
vector<double> v(N);
for (int i = 0; i < N; ++i)
v[i] = i + 1;
partial_sum(v.begin(), v.end(), v.begin(), multiplies<double>());
copy(v.begin(), v.end(), ostream_iterator<double>(cout, "\n");
}




15.2.4 divides
divides<T>
class divides<T>是一种Adaptable Binary Function。如果f是class divides<T>的一个object
且x和y都属于型别T，则f(x, y)返回x/y。


样例:
将vector内的每个元素都除以某个常量。
int main()
{
const int N = 1000;
vector<double> v(N);
generate<v.begin(), v.end(), rand);
transform(v.begin(), v.end(), v.begin(),
bind2nd(divides<double>(), double(RAND_MAX)));

for (int i = 0; i < N; ++i)
assert(0 <=  v[i] && v[i] <= 1.);
}




15.2.5 modulus
modulus<T>
class modulus<T>是一种Adaptable Binary Function。如果f是class modulus<T>的一个object
且x和y都属于型别T，则f(x, y)返回x % y;


样例:
将vector内的每一个元素都以其最后一个阿拉伯数字取代之。
int main()
{
const int N = 1000;
vector<int> v(N);

generate(v.begin(), v.end(), rand);
transform(v.begin(), v.end(), v.begin(),
bind2nd(modulus<double>(), 10
for (int i = 0; i < N; ++i)
assert(0　<= v[i] && v[i] <= 10);
}




15.2.6 negate
negate<T>
class negate<T>是一种Adaptable Unary Function,是一个单引数function object。如果f是
class negate<T>的一个object，且x属于型别T，则f(x)返回-x。


样例:
构造一个vector v2，使其每个元素都是v1相对元素的负值。
int main()
{
const int N  = 1000;
vector<double> v1(N);
vector<double> v2(N);

generate(v1.begin(), v1.end(), rand);
transform(v1.begin(), v1.end(), v2.begin(), negate<double>());

for (int i = 0; i < N; ++i)
assert(v2[i] + v1[i] == 0);


}




15.3 大小比较 Comparisons
15.3.1 equal_to
equal_to<T>
class equal_to<T>是一种Adaptable Binary Predicate，这表示它可用来验证某条件的真或伪。
如果f是class equal_to<T>的一个object，且x与y为型别T之值，则只有在x==y时f(x, y)才会
返回true。


样例:
重新安排一个数组，将等于零的所有元素排在不等于零的所有元素之前:
int main()
{
const int N = 20;
int A[N] = {1, 3, 0, 2, 5, 9, 0, 0, 6, 0};

partition(A, A+N, bind2nd(equal_to<int>(), 0));
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout<<endl;
}


15.3.2 not_equal_to
not_equal_to<T>
class not_equal_to<T>是一种Adaptable Binary Predicate,这表示它可用来验证某条件之真伪
如果f是class not_equal_to<T>的一个object而且x和y都为型别T之值，则只有在x!=y的时候
f(x, y)才返回true。


样例:
在list之中找寻第一个非零元素:
int main()
{
const int N = 9;
int A[N] = {0, 0, 0, 0, 1, 2, 4, 8, 0};
list<int> L(A, A+N);

list<int>::iterator i = find_if(L.begin(), L.end(),
bind2nd(not_equal_to<int>(), 0));
cout<<"Elements after initial zeros (if any): ";
copy(i, L.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
}




15.3.3 less
class less<T>
class less<T>是一种Adaptable Binary Predicate,这表示它可以用来验证某条件之真伪。如
果f是class less<T>的一个object而且x和y都是型别T之值，则只有当x<y时f(x, y)才返回true.
STL的许多classes及algorithm都需要用到比较函数，例如sort,set,map。less是其典型的缺
省值。


样例:
重新排列一个数组，使所有负数排在非负数之前。
int main()
{
const int N  = 10;
int A[N] = {1, -3, -7, 2, 5, -9, -2, 1, 6, -8};

partition(A, A+N, bind2nd(less<int>(), 0));
copy(A, A+N, ostream_iterator<int>(cout, " "));
cout<<endl;
}




15.3.4 greater
greater<T>
class greater<T>是一种Adaptable Binary Predicate，这表示它可用来验证某条件之真伪，
如果f是class greater<T>的一个object而且x和y都是型别T之值，则只有当x>y时f(x, y)才
返回true。


样例:
将一个vector以递减顺序而非递增顺序做排序。
int main()
{
const int N = 10;
int A[N] = {1, -3, -7, 2, 5, -9, -2, 1, 6, -8};
vector<int> v(A, A+N);


sort(v.begin(), v.end(), greater<int>());
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
}




15.3.5 less_equal
less_equal<T>
class less_equal<T>是一种Adaptable Binary Predicate,这表示它可以用来验证某条件之真
伪。如果f是class less_equal<T>的一个object而且x和y都是型别T之值，则只有当x<=y时，
f(x, y)才返回true。


样例:
产生一个list,令其元素为某个range之内的所有非正数值。
int main()
{
const int N = 10;
int A[N] = {3, -7, 0, 6, 5, -1, -3, 0, 4, -2};

list<int> L;
remove_copy_if(A, A+N, back_inserter<L>, 
bind2nd(less_equal<int>(), 0));
cout<<"Elements int list: ";
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
}




15.3.6 greater_equal
greater_equal<T>
class greater_equal<T>是一种Adaptable Binary Predicate，这表示它可用来验证某条件之真
伪。如果f是class greater_equal<T>的一个object，而且x和y都是型别T之值，则只有当
x>=y时，f(x, y)返回true;


样例:
找寻vector中第一个不为负的值。
int main()
{
const int N = 10;
int A[N] = {-4, -3, 0, -6, 5, -1, -3, 0, 4, -2};

int *p = find_if(A, A+N, bind2nd(greater_equal<int>(), 0));
cout<<*p<<endl;
}


15.4 逻辑运算 logical operations
逻辑运算logical function objects和算术运算arithmetic function object很相似:它们执行
的是诸如x||y和x&&y这类操作。
logical_and和logical_or自身并不很有用，它们主要的用途在于与function object adapter
binary_compose结合，这样它们便可以在其他function objects身上执行逻辑运算。


15.4.1 logical_and
logical_and<T>
class logical_and<T>是一种Adaptable Binary Predicate，这表示它可以用来验证某条件之真伪
如果f是class logical_and<T>的一个object而且x和y都是型别T之值，T可转换为bool,则只有
当x和y皆为true时f(x, y)才返回true.


样例:
找寻list之内第一个介于0...10的元素。
int main()
{
list<int> L;
generate_n(back_insert(L), 10000, rand);

list<int>::iterator i = 
find_if(L.begin(), L.end(),
compose2(logical_and<bool>(),
bind2nd(greater_equal<int>(), 1),
bind2nd(less_equal<int>(), 10)));


assert(i == L.end() || (*i >= 1 && *i <= 10));
}




15.4.2 logical_or
class logical_or<T>是一种Adaptable Binary Predicate，这表示它可用来验证某条件之真伪，
如果f是class logical_or<T>的一个object，而且x和y都是型别T之值，T可转换为bool，则只有
当x或y有一个为true时f(x, y)才返回true。


样例:
找寻字符串中第一个' '字符或'\n'字符。
int main()
{
char str[] = "The first line\nThe second line";
int len = strlen(str);

const char* wptr = find_if(str, str + len,
compose2(logical_or<bool>(),
bind2nd(equal_to<char>(), ' '),
bind2nd(equal_to<char>(), '\n')));
assert(wptr == str + len || *wptr == ' ' || *wptr == '\n');
}




15.4.3 logical_not
logical_not<T>
class logical_not<T>是一种Adaptable Predicate，这表示它可以用来验证某条件的真或伪，而
且只需单一引数。如果f是class logical_not<T>的一个object而且x是型别T之值，T可转换为bool
则只有当x为false时f(x)才返回true。


样例:
将一个bit vector转换为其逻辑补数logical complement
int main()
{
const int N = 1000;
vector<bool> v1;
for (int i = 0; i < N; ++i)
v1.push_back(rand() > (RAND_MAX / 2));
vector<bool> v2;
transform(v1.begin(), v1.end(), back_inserter(v2),
logical_not<bool>());
for (int i = 0; i < N; ++i)
assert(v1[i] == !v2[i]);
}




15.5 证同Identity与投射projection
本节所有的function objects，以某种观点来看，都只是将其引数值原封不动地返回，基本的
identity function object为identity，其他function objects都是其一般化形式。


C++ standard并未涵盖任何identity和projection操作行为，不过它们常常存在于各个实现品中
作为一种扩充性产品。


15.5.1 identity
identity<T>
class identity是一种Unary Function，表示证同函数identity function,它需要一个引数x，返回
的是未经任何改变的x。


样例:
int main()
{
int x = 135;
identity<int> id;
assert(x == id(x));
}




15.5.2 project1st
project1st<Arg1, Arg2>
class project1st接受两个引数，返回第一个引数，并忽略第二引数。本质上它是Binary Function
情况下的identity一般化形式。
样例:
int main()
{
vector<int> v1(10, 137);
vector<char *> v2(10, (char *)0);
vector<int> result(10);

transform(v1.begin(), v1.end(), v2.begin(), result.begin(),
project1st<int, char *>());
assert(equal(v1.begin(), v1.end(), result.begin()));
}




15.5.3 project2nd<Arg1, Arg2>
class project2nd接受两个引数，返回第二个引数，并忽略第一个引数。本质上它是Binary
Function情况下的identity一般化形式。
同project1st。




15.5.4 select1st
select1st<pair>
class select1st接受单一引数，此引数是个pair或与pair相同接口的class，并返回该pair的第
一个元素。


样例:
map的元素都是pairs，所以我们可以利用select1st取出及打印map的所有键值keys
int main()
{
map<int, double> M;
M[1] = 0.2;
M[47] = 0.8;
M[33] = 0.1;


transform(M.begin(), M.end(), ostream_iterator<int>(cout, " "),
select1st<map<int, double>::value_type>());
cout<<endl;
//输出为1 33 47
}




15.5.5 select2nd
select2nd<pair>
class select2nd接受单一引数，此引数是个pair或与pair相同接口的class，并返回该pair的第
二个元素。




15.6 特殊的Function objects
15.6.1 hash
hash<T>
class hash<T>是一种Hash Function。STL内所有Hashed Associate Container把它拿来当作缺
省的hash function。
template hash<T>只针对template引数型别为char *,const char *, string以及内建整数integral
而定义。如果你要搭配不同引数型别之Hash Function,你就必须提供自己的template specialization
或是提供一个新的Hash Function class。


样例:
int main()
{
hash<const char *> H;
cout<<"foo -> "<<H("foo")<<endl;
cout<<"bar -> "<<H("bar")<<endl;
}




15.7 Member Function Adapters
所谓member function adapters是一群小型的classes，让你能够将member functions当作function
objects来调用。每一个adapter需要一个型别为X*或X&的引数，可通过该引数调用X的一个member
function----如果那是一个virtual member function，那么便是一个多态函数调用polymorphic
function object，因此,member function adapters是面向对象编程与泛型编程之间的桥梁。
Member function adapters数量之多令人却步，但它们都遵循系统化的命名格式。三个不同的
特点形成了共2^3 = 8种adapters:


1、这个adapters接受型别为X*或X&的引数吗？如果是后者，其名称有"_ref"后缀词。
2、这个adapters封装的是无引数的或单一引数的member function?如果是后者，其名称有'1'
后缀词。
3、这个adapters封装的是non_const或const member function?（C++的型别声明语法无法以
同一个class处理两种情况)如果是后者，其名称会冠上"const_"前缀词。


以上的复杂度在一般使用情况下多隐匿无形。通常构造一个function object adapter的方式是
使用辅助函数helper function而非直接调用其constructor。由于辅助函数被重载overload，所
以只需记住两个名称就好:mem_fun和mem_fun_ref。


15.7.1 mem_fun_t
mem_fun_t<R, X>
class mem_fun_t是一种member function adapter。如果X是个class，具有member function 
R X::f()亦即无任何引数，返回型别为R，那么mem_fun_t<R, X>便成为一个member object
adapter,使得以一般函数（而非member function)的方式来调用f()。
如同其他众多adapters一样，直接使用mem_fun_t constructor是很不方便的。使用辅助函数
mem_fun来代替往往是比较好的做法。
如果F是一个mem_fun_t，并且X是一个指针，型别为X*，那么表达式F(X)等价于表达式X->f().


样例:
struct B{
virtual void print() = 0;
};


struct D1: public B{
void print(){cout<<"I'm a D1"<<endl;}
};


struct D2: public B{
void print(){cout<<"I'm a D2"<<endl;}
};


int main()
{
vector<B*> V;
V.push_back(new D1);
V.push_back(new D2);
V.push_back(new D2);
V.push_back(new D1);

for_each(V.begin(), V.end(), mem_fun(&B::print));
}




15.7.2 mem_fun_ref_t
mem_fun_ref_t<R, X>
如果F是一个mem_fun_ref_t，以member function X::f构造出来，并且X是一个型别为X的object
那么表达式F(X)等价于表达式X.f()。两者的差别在于语法层面:F支持Adaptable Unary Function
接口。
如同其他众多adapters一样，直接使用mem_fun_ref_t constructor是很不方便的。使用辅助函数
mem_fun_ref来代替往往是比较好的做法。
样例:
struct B{
  virtual void print() = 0;
};


struct D1: public B{
void print(){cout<<"I'm a D1"<<endl;
};


struct D2: public B{
void print(){cout<<"I'm a D2"<<endl;
};


int main()
{
vector<D1> V;
V.push_back(D1());
V.push_back(D1());

for_each(V.begin(), V.end(), mem_ref_t(&B::print));
}




15.7.3 mem_fun1_t
mem_fun1_t<R, X, A>
如果F是一个mem_fun1_t，并以member_function X::f构造出来，X是一个指针，型别为X*，a是
型别A的值，那么表达式F(X, a)等价于表达式X->f(a)。两者差别在于语法层面上:F支持
Adaptable Binary Function的接口。
和其他众多adapters一样，直接使用mem_fun1_t的constructor并不方便。以辅助函数
mem_fun代替是比较好的做法。
样例:
struct Operation{
virtual double eval(double) = 0;
};


struct Square: public Operation{
double eval(double x){return x*x;}
};


struct Negate: public Operation{
double eval(double x){return -x;}
};


int main()
{
vector<Operation *> operations;
vector<double> operands;


operations.push_back(new Square);
operations.push_back(new Square);
operations.push_back(new Negate);
operations.push_back(new Negate);
operations.push_back(new Square);


operands.push_back(1);
operands.push_back(2);
operands.push_back(3);
operands.push_back(4);
operands.push_back(5);


transform(operations.begin(), operations.end(),
operands.begin(), 
ostream_iterator<double>(cout, "\n"),
mem_fun(&operation::eval));
}




15.7.4 mem_fun1_ref_t
mem_fun1_ref_t<R, X, A>
如果F是一个mem_fun1_ref_t，并以member function X::f构造出来，X是型别为X的object，a是
型别为A的值，则表达式F(X, a)等价于表达式X.f(a)，两者差别在于语法层面:F支持Adaptable
Binary Function接口。
使用mem_fun_ref来代替mem_fun1_ref_t通常是比较好的做法。
样例:
int main()
{
int A1[5] = {1, 2, 3, 4, 5};
int A2[5] = {1, 1, 2, 3, 5};
int A3[5] = {1, 4, 1, 5, 9};

vector<vector<int>> V;
V.push_back(vector<int>(A1, A1+5));
V.push_back(vector<int>(A2, A2+5));
V.push_back(vector<int>(A3, A3+5));

int indices[3] = {0, 2, 4};

int &(vector<int>::*extract)(vector<int>::size_type);
extract = &vector<int>::operator[]; //指向模板函数的成员函数的函数指针
transform(V.begin(), V.end(), indices,
ostream_iterator<int>(cout, " "),
mem_fun_ref(extract));
cout<<endl;
}
输出为
1 2 9




15.7.5 const_mem_fun_t
样例:
int main()
{
vector<vector<int>*> V;

V.push_back(new vector<int>(5));
V.push_back(new vector<int>(3));
V.push_back(new vector<int>(4));

transform(V.begin(), V.end(),
ostream_iterator<int>(cout, " "),
mem_fun(&vector<int>::size));
cout<<endl;
//输出为 5 3 4
}




15.7.6 const_mem_fun_ref_t
const_mem_fun_ref_t<R, X>


15.7.7 const_mem_fun1_t
const_mem_fun1_t<R, X, A>


15.7.8 const_mem_fun1_ref_t
const_mem_fun1_ref_t




15.8 其他的Adapters
15.8.1 binder1st
binder1st<BinaryFun>
Class binder1st是一种function object adapter。可用来将Adpatable Binary Function转换
成Adaptable Unary Function，如果F是class1st<BinaryFun>的object,则f(x)返回F(c,x)，其
中F为BinaryFun Object，c为一常量，F和c都会被当作引数，传给binder1st的constructor。
你可以理解为是将一个双参函数的第一引数设定为某个常量，因而形成一个单参函数。要产生
一个binder1st，最简单的是使用辅助函数bind1st。
样例:
在键表之中寻找第一个不为零的元素。
int main()
{
list<int> L;
for(int i = 0; i < 20; ++i)
L.push_back(rand() % 3);

list<int>::iterator first_nonzero = 
find_if(L.begin(), L.end(),
bind1st(not_equal_to<int>(), 0));
cout<<*first_nonzero<<endl;
}




15.8.2 binder2nd
binder2nd<BinaryFun>
class binder2nd是一种function object adapter。可用来将Adaptable Binary Function转换成
Adaptable Unary Function。如果f是class binder2nd<BinaryFun>的object，则f(x)返回F(x,c)
其中c为一常量。F和c都会被当作引数，传给binder2nd的constructor。
该adapter会将一个双参函数的第二引数设定为某个常量，因而形成一个单参函数。我们可以使用
辅助函数bind2nd来代替binder2nd。




15.8.3 pointer_to_unary_function
pointer_to_unary_function<Arg, Result>
class pointer_to_unary_function是一种function object adapter,允许将函数指针Result
(*f)(Arg)视为一个Adaptable Unary Function。如果F是一个pointer_to_unary_function
<Arg, Result> object，而且以一个型别为Result(*)(Arg)的函数指针f作为初值，那么F（x)
会调用函数F(x)。
型别为Result(*)(Arg)的那个函数指针，就自身条件而言已经是一个相当不错的Unary Function
object，它可以传入任何需要以Unary Function为引数的STL算法中。pinter_to_unary_function
的唯一使用时机，是当你希望在需要Adaptable Unary Function的情况下使用一般函数指针，例如
以它作为某个function object adapter的引数。
我们一般使用其辅助函数ptr_fun来代替pointer_to_unary_function。


样例:
以标准库中的fabs，将某个range内的数值以其绝对值取代。这不需要用到pointer_to_unary_function
adapter，因为我们只要将fabs直接传给transform即可:
transform(first, last, first, fabs);


底下这段代码则是将某个range内的数值以其绝对值的负数取代。我们需要将fabs与negate组合
起来，因此fabs必须被视为一个Adaptable Unary Function，此时我们必须使用pointer_
to_unary_function:
transform(first, last, first, compose1(negate<doulbe>(), ptr_fun(fabs)));




15.8.4 pointer_to_binary_function
pointer_to_binary_function<Arg1, Arg2, Result>
class pointer_to_binary_function是一种function object adapter，允许将函数指针result
(*f)(Arg1, Arg2)视为一个Adaptable Binary Function。


型别为Result(*)(Arg1， Arg2)的那个函数指针，就自身条件而言已经是一个相当不错的Unary
Function object，它可以传入任何需要以Unary Function为引数的STL算法中。
pinter_to_unary_function的唯一使用时机，是当你希望在需要Adaptable Unary Function的
情况下使用一般函数指针，例如以它作为某个function object adapter的引数。
我们一般使用其辅助函数ptr_fun来代替pointer_to_unary_function。


样例:
以下程序片段能在链表之中找寻与"ok"相等的字符串。由于欲使用标准函数库函数strcmp作
为function object adapter的引数，所以必须先使用pointer_to_binary_function adapter
以提供Adaptable Binary Function的接口给strcmp。
list<char*>::iterator item = 
find_if(L.begin(), L.end(),
notl(binder2nd(ptr_fun(strcmp), "ok")));






15.8.5 unary_negate
unary_negate<Predicate>
class unary_negate是一种Adatable Predicate，用来表示其他某个Adaptable Predicate的逻辑
负值logical negation。如果f是一个unary_negate<Predicate> object，构造时以pred作为其
底部的一个function object，那么f(x)会返回!pred(x)。严格来说unary_negate有点多余，因为
它可以用function object logical_not与adapter unary_compose构造出来。
一般使用其辅助函数not1来代替unary_negate.
样例:
试着在链表中找出第一个落于1...10以外的元素。
int main()
{
list<int> L;
generate_n(back_inserter(L), 10000, rand);


list<int>::iterator i = 
find_if(L.begin(), L.end(),
not1(compose2(logical_and<bool>(),
bind2nd(greater_equal<int>(), 1),
bind2nd(less_equal<int>(), 10))));
assert(i == L.end() || !(*i >= 1 && *i <= 10));
}




15.8.6 binary_negate
binary_negate<BinaryPredicate>
class binary_negate是一种Adaptable Binary Predicate。用来表示其他某个Adaptable Binary
Predicate的逻辑负值logical negation。如果f是一个binary_negate<Predicate> object，构造
时以pred作为其底部的一个function object，那么f(x, y)会返回!pred(x, y)。
一般使用not2来代替binary_negate。
样例:
在字符串中找出第一个不为' '或'\n'的字符:
char str[MAXLEN];
...
const char *wptr = find_if(str, str + MAXLEN,
compose2(not2(logical_or<bool>()),
bind2nd(equal_to<char>(), ' '),
bind2nd(equal_to<char>(), '\n')));
assert(wptr == str + MAXLEN || !(*wptr == ' ' || *wptr == '\n'));




15.8.7 unary_compose
unary_compose<Function1, Function2>
class unary_compose是一种function object adapter。如果f和g都是Adaptable Unary 
Functions而且g的返回型可转换为f的引数型别，那么unary_compose可被用来产生一个
function object h，使h(x)相同于f(g(x))。
这样的行为称为函数合成function composition。通常它用来表示数学运算fog,也就是产出一
个函数，使(fog)(x)即为f(g(x))。函数合成是代数上的一个重要观念，可以利用其他组件来
构造组件，因为这使我们得以单纯的function objects任意构造出复杂的function objects。
一般我们使用其辅助函数compose1来代替unary_compose。
样例:
计算vector中的所有元素之正弦值sins的负数。每个元素代表一个角度degrees。由于C函数库的
sin需要的引数是以弧度radians为单位，所以整个运算由三个行为合成:角度转换为弧度、取正
弦值、取负值。


vector<double> angles;
vector<double> sines;
const double pi = 3.14159265358979323846;
...
assert(sines.size() >= angles.size());
transform(angles.begin(), angles.end(), sines.begin(),
compose1(negate<double>(),
compose1(ptr_fun(sin),
bind2nd(multiplies<double>(), pi/180.0))));



15.8.8 binary_compose
binary_compose<BinaryFunction, UnaryFunction1, UnaryFunction2>
class binary_compose是一种function object adapter。如果f是Adaptable Binary Functions,
g1和g2都是Adaptable Unary Functions，而且g1和g2的返回型别皆可转换为f的引数型别，那么
binary_compose可被用来产生一个function object h，使h(x)相同于f(g1(x), g2(x))。
样例:
找出链表之中第一个落在1...10区间内的元素。
list<int> L;
...
list<int>::iterator in_range = 
find_if(L.begin(), L.end(),
compose2(logical_and<bool>(),
bind2nd(greater_equal<int>(), 1),
bind2nd(less_equal<int>(), 10)));
assert(in_range == L.end() || (*in_range >= 1 && *in_range <= 10));
以下试针对某区间内的每个元素x，计算sin(x) / (x+DBL_MIN)。
transform(first, last, first,
compose2(divides<double>(),
ptr_fun(sin),
bind2nd(plus<double>(), DBL_MIN)));




第16章
Container Classes容器类
STL定义的所有container classes都是Sequence或Associate Container的models。它们都是
templates，可被具现化以包含任何型别的objects。例如，你可以像使用普通C数组一样地使用
vector<int>，它使你得以免除内存管理之类的琐事。
除了序列式containers和关联式containers，STL还定义了三种container adapters。它们自身
并不是containers，它们不是container的models，它们刻意提供受限的功能。




16.1 序列Sequences
C++ standard定义了三种序列:
1、vector: 一种简单的数据结构，提供元素的快速随机访问能力；
2、deque: 一种较为复杂的数据结构，允许高效地在container两端安插及移除元素；
3、list: 双向连接链表。


vector是STL container classes当中最简单的一个，通常也是最好的选择。
C++ standard并未提供单向链表，SGI STL就实现有一个单向链表slist。


16.1.1 vector
vector<T, Allocator>
vector是一种Sequence，支持随机访问元素、常量时间内在尾端安插和移除元素，以及线性时间
内在开头或中间处安插或移除元素。vector的元素个数能够动态变更，其内存管理行为完全自动
通常它的实现方式是把元素安排在连续的存储块中，这使得vector的iterators可以是一般指针。
vector的大小(size,其所包含的元素个数)与容量(capacity,其内存所能容纳的元素个数)之间
有很重要的差别。我们以实现角度来看。vector会管理其内存，并在内存的开头处构造元素。
典型的vector的三个member variables。三个都是指针:start,finish和end_of_storage。
vector的所有元素位于[start, finish)之中，而[finish，end_of_storage)则包含了未初始化
的存储空间。vector的大小是finish-start，容量为end_of_storage-start。当然，容量一定
大于等于其元素个数。
当你要将元素安插于vector内，如果vector的大小等于其容量（亦即这个vector已经没有未初
始化的存储空间了），安插新元素的唯一方法就是增加这个vector的内存总是不量。这意味得
分配一块新的而且更大的内存，再将旧内存块的内容复制到新内存块中，然后归还旧内存块。
一旦vector的内存重新分配，其iterators便失效了。此外，在vector中间安插或删除元素，也会
使指向该安插点或删除点之后元素的所有iterators都失效。这表示如果所有安插或删除动作都在
vector尾端进行，那么你就可以使用vector的iterators不失效。


样例:
以vector作为临时存储体，从标准输入设备读入一些数值，然后打印这串数值的中间值。因为
vector可以由任何种类的input iterators range构造出来。本例是由型别为istream_iterator
的range构造出来。这也说明vector提供Random Access Iterators。
vector自动执行内存重新分配动作时，通常以2为因数factor来增加容量。因此容量的增加与目前
容量成比例，而不是一个固定常量。
int main()
{
istream_iterator<double> first(cin);
istream_iterator<double> end_of_file;;
vector<double> buf(first, end_of_file);
nth_element(buf.begin(), buf.begin() + buf.size()/2, buf.end());
cout<<buf[buf.size()/2]<<endl;
}
你可以使用member function reserve来增加vector的容量，但没有任何一个member function可
以为我们缩小容量。因为不需要任何特别的member functions我们就可以缩小vector的容量。
vector中的部分成员函数
size_type vector::capacity() const
返回vector的容量，亦即分配获得之内存所能容纳的元素个数。容量总是大于等于其大小。如果
这个vector的内存重新分配，则会造成任何指向此vector的iterators失效。
void vector::swap(vector &)
将两个vectors的内容互换。
void vector::reserve(size_type n)
增加vector的容量。如果n小于等于capacity()，则此函数不带来任何影响。否则它会要求分配
额外内存。如果成功，capacity()会大于或等于n，而指向此vector的任何iterators都将失效
vector的大小以及元素内容都维持不变。
使用reserve()的理由主要是为了效率。如果你知道vector最后会增长到多大的容量，那么一次
就把所有内存分配好，可比依赖内存自动分配机制更有效率多了。
reference vector::front()
返回第一个元素。
reference vector::back()
返回最后一个元素。
void vector::push_back(const T& x)
在vector尾端添加x。
void vector::pop_back()
移除最后一个元素。
iterator vector::insert(iterator pos, const T& x)
在pos之前一个位置安插x。指向此vector的所有iterators都可能因此失效。
template <class InputIterator>
void vector::insert(iterator pos, InputIterator f, InputIterator l)
在pos之前一个位置安插[f,l)。指向此vector的所有iterators都可能因此失效。
void vector::insert(iterator pos, size_type n, const T& x)
在pos之前一个位置安插n个x复制品。指向此vector的所有iterators都可能因此失效。
iterator vector::erase(iterator pos)
删除pos所指的元素。pos之后的任何iterators都将因此失效。
iterator vector::erase(iterator first, iterator last)
删除[first, last)内的元素。此range之后的任何iterators都将因此失效。
void vector::clear()
删除vector的所有元素。
void vector::resize(size_type n, const T& t = T())
将vector的大小改变为n。
template <class InputIterator>
void vector::assign(InputIterator first, InputIterator last)
相当于删除*this中的所有元素，再以[first, last)内的元素取而代之。
void vector::assign(size_type n, const T&x)
相当于删除*this中的所有元素，再以n个x复制品取而代之。






16.1.2 list
list<T, Allocator>
list是一种双向链表，其中每个元素都有一个前承元素predecessor和一个后继元素successor。
也就是说它是一种Sequence，支持前后两种移动方向，并能以amortized const time在任意位置
安插及移除元素。list有一个重要性质:安插与接合splicing动作不会造成指向list的iterators
失效，即使是删除动作，也只会令指向被删除元素的那个iterator失效。
list和vector的比较深具启发意义。假设i是型别为vector<T>::iterator的一个有效iterator，
当我们在i之前一个位置安插或移除一个元素，i会因此指向不同的元素，或者i根本完全失效。
另一方面，假设i和j都是指向vector的iterators，存在某个整数n，使得i == j + n。这个情
况下即使元素被安插在vector之中且i和j指向不同元素，两个指针的相互关系仍然维持不变。
list正好相反。其iterators不会被无效化，也不会指向不同元素，但iterators的前承元素与
后继元素的关系不会维持不变。


样例:
产生两个空的list，为它们新增元素，然后对它们排序，然后将这两个lists合并成单个list。
int main()
{
list<int> L1;
L1.push_back(0);'
L1.push_front(1);
L1.insert(++L1.begin(), 3);


list<int> L2;
L2.push_back(4);
L2.push_front(2);

L1.sort();
L2.sort();
L1.merge(L2);
assert(L1.size() == 5);
assert(L2.size() == 0);
L1.reverse();
copy(L1.begin(), L1.end(), ostream_iterator<int>(cout, " "));
cout<<endl;
}
输出
4 3 2 1 0




16.1.3 slist
slist<T, Allocator>
slist是一种单向连接链表。就像list一样，slist具有一个重要性质:安插与接合splicing动作不
会造成slist iterators失效。
还有一个重要点是，如同其他Sequences一样，slist定义了member functions insert与erase。
如果不是很谨慎地使用这些member functions，你的程序执行起来可能会严重变慢。问题在于
安插与删除都会用到前一个结点的next指针，即必须找到pos之前的那个iterator。由于
Bidirectional iterators的缘故，list只需耗用常量时间就可以完成了，但slist就必须从链表
头部开始移动。
slist提供insert_after和erase_after，这是常量时间的操作行为，你应该尽可能以这些函数取
代insert和erase。如果它们不能满足你的需求，而常常必须使用insert和erase，那么你可能
应该使用list而非slist。
样例:
产生一个slist，并安插一些元素进去。
int main()
{
slist<int> L;
L.push_front(0);
L.push_front(1);
L.insert_after(L.begin(), 2);
copy(L.begin(), L.end(), 
ostream_iterator<int>(cout, " "));
cout<<endl;
}
输出:
1 2 0
slist提供了push_front，但并没有提供push_back。因此，这会造成slist中的元素以相反于新
增元素的顺序排列。如果你想要让元素次序和新增元素的顺序相同，有两种选择。第一，你可以
在元素全部加入之后，使用member function reverse。第二，你可以运用LISP程序普遍使用的
技巧:维护一个iterator，指向最后元素。如下例所示:
int main()
{
slist<double> L;
double x = 1;
L.push_front(x);
slist<double>::iterator back = L.begin();
while(x < 10000.0)
{
back = L.insert_after(back, x *= 2);
}
copy(L.begin(), L.end(),
ostream_iterator<double>(cout, " "));
}




16.1.4 deque
deque<T, Allocator>
deque类似vector。它支持元素的随机访问、常量时间内于尾端安插或移除元素、线性时间内于中
间处安插或移除元素。
deque和vector的差异在于。deque另外还提供常量时间内于序列开头新增或移除元素。在deque
开头或尾端安插一个元素，是常量时间。在中间安插元素的复杂度则与n成线性关系，此处n
是安插点距离deque开头与尾端的最短距离。
另一个差异是deque不具备类似vector的capacity()和reserve()之类的member functions。
一般来说，insert(包括push_front与push_back)会造成指向deque的所有iterators失效。对
deque中段调用erase亦会造成指向deque的所有iterators失效。至于对着deque的开头或尾端
调用erase(包括pop_front与pop_back)，则只会造成被移除元素的iterator失效。
通常，deque系以动态区段化dynamic segmented的数组实现出来。deque通常内含一个表头，指向
一组节点nodes。每个节点包含固定数量并连续存储的元素。当deque增长时便增加新的节点。
deque的内部细节对你并不重要，重要的是你能够认知到deque远比vector复杂。对一个deque
iterator做累加动作，并非只是单纯的指针累加；必须包括至少一次比较动作。所以，尽管
vector与deque都提供Random Access Iterators，但deque iterator上的任何操作行为都要比
vector iterator上的相同行为慢许多。
所以除非你需要的功能只有deque才提供，如在常量时间内于开头做安插或移除动作。否则应该
尽量使用vector。同样，对deque进行排序几乎不会是个好主意，你应该将此deque的元素复制
到一个vector，然后再对此vector排序，再将所有元素复制回deque，这样会比较快。
样例:
int main()
{
deque<int> Q;
Q.push_back(3);
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
Q[2] = 0;
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
}




16.2 Associative Containers 关联式容器
C++ standard提供四种Associative Container Classes:set, map, multiset和multimap。
这四个classes都是Sorted Associative Container的models。
C++ standard并未包含Hashed Associative Containers。


16.2.1 set
set<Key, Compare, Allocator>
set是一种Sorted Associative Container，能够存储型别为key的objects。这是一种Simple 
Associative Container，意指其value type与其key type都是key。它同时也是Unique 
Associative Container，表示没有两个元素相同。
和list一样，set具有数个重要性质:新元素的安插并不会造成既有元素的iterators失效，
从set中删除元素也不会令任何iterators失效----当然被移除元素的iterator除外。




16.2.2 map
map<Key, T, Compare, Allocator>
map是一种Sorted Associative Container，可将型别为key的objects与型别为T的objects系
结在一起。它是一种Pair Associative Container，表示其value type的pair<const key, T>
它同时也是Unique Associative Container，意指没有两个元素具有相同的key。
map与set很类似。主要的差别在于set是一种Simple Associative Container其value type与
key type相同，而map是一种Pair Associatve Contianer其value type就是其key type。正是
因为这种差异造成set无法区分iterator与const_iterator，而map却能够。
和list一样，新元素的安插不会造成既有元素的iterators的失效。自map中删除元素也不会造成
任何iterators失效，除了被移除元素的iterator外。


样例:
struct ltstr
{
bool operator()(const char *s1, const char *s2) const
{
return strcmp(s1, s2) < 0;
}
};


int main()
{
map<const char*, int, ltstr> days;
days["january"] = 31;
days["february"] = 28;
days["march"] = 31;
days["april"] = 30;
days["may"] = 31;
days["june"] = 30;
days["july"] = 31;
days["august"] = 31;
days["september"] = 30;
days["october"] = 31;
days["november"] = 30;
days["december"] = 31;


cout<<"june-> "<<days["june"]<<endl;
map<const char*, int, ltstr>::iterator cur = days.find("june");
map<const char*, int, ltstr>::iterator prev = cur;
map<const char*, int, ltstr>::iterator next = cur;
++next;
--prev;
cout<<"Previous(in alphabetical order) is "
<<(*prev).first<<endl;
cout<<"Next(in alphabetical order) is "
<<(*next).first<<endl;
}


pair<iterator, bool> map::insert(const value_type& x)
将x安插到map之中。如果x的确被安插了，返回值pair的第二部分为true，如果x已存在所以没有
被安插，返回值pair的第二部分为false。
样例:
int main()
{
map<string, ing> M;
M.insert(make_pair("A", 17));
M.insert(make_pair("B", 74));

if (M.find("Z") == M.end())
cout<<"Not found: Z"<<endl;

//安插新值于此map中
pair<map<string, int>::iterator, bool> p = M.insert(make_pair("C", 4));
assert(p.second);

//试着再安插一个新值，这次不会成功
//因为map已经拥有一个元素其键值为"B"。
p = M.insert(make_pair("B", 3));
assert(!p.second);

//改变与B关联的值
cout<<"Value associated with B: "<<p.first->second<<endl;
p.first->second = 7;
cout<<"Value associated with B: "<<p.first->second<<endl;
}




16.2.3 multiset
multiset<Key, Compare, Allocator>
multiset是一种Sorted Associative Container.能够存储型别为Key的objects。它是一种Simple
Associative Container，意指其value type与其key type都是key。它同时也是multiple 
Associative Container,表示可以容纳两个或更多个相同元素，这是set与multiset唯一不同之处
和list一样，multiset具有数个重要性质：新元素的安插并不会造成既有元素的iterators失效，
从set中删除元素也不会令任何iterators失效---当然被移除元素的iterator除外。






16.2.4 multimap
multimap<Key, T, Compare, Allocator>
multimap是一种Sorted Associative Container，可将型别为Key的objects与型别为T的objects
系结在一起。它是一种Pair Associative Container，表示其value type为pair<const Key, T>
同时也是Multiple Associative Container，意指可容纳两个或更多的相同元素（这是map与
multimap唯一不同之处）。也就是说，multimap并非将型别为key的键值




16.2.5 hash_set
hash_set<Key, HashFun, EqualKey, Allocator>
hash_set是一种Hashed Associative Container，它同是也是一种Simple Associatve Container
和Unique Associative Container。
在重视快速查找的应用程序中，hash_set class很有用。然而如果元素必须以特定顺序排列的话
那么set比较适合。
样例:
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};


void lookup(const hash_set<const char*, hash<const char*>, eqstr>& Set,
const char* word)
{
hash_set<const char*, hash<const char*>, sqstr>::const_iterator it
= Set.find(word);
cout<<" "<<word<<" : "
<<(it != Set.end()? "present" : "not present")
<<endl;
}


int main()
{
hash_set<const char*, hash<const char*>, eqstr> Set;
Set.insert("kiwi");
Set.insert("plum");
Set.insert("apple");
Set.insert("mango");
Set.insert("apricot");
Set.insert("banana");

lookup(Set, "mango");
lookup(Set, "apple");
lookup(Set, "durian");
}
输出为:
mango: present
apple: present
durian: not present




16.2.6 hash_map
hash_map<Key, T, HashFun, EqualKey, Allocator>


16.2.7 hash_multiset
hash_multiset<Key, HashFun, EqualKey, Allocator>


16.2.8 hash_multimap
hash_multimap<Key, T, HashFun, EqualKey, Allocator>
样例:
struct eqstr
{
bool operator()(const char*s1, const char*s2)const
{
return strcmp(s1, s2) == 0;
}
};


typedef hash_multimap<const char*, int, hash<const char*>, eqstr>
map_type;



void lookup(const map_type*Map, const char*str)
{
cout<<" "<<str<<" :";
pari<map_type::const_iterator, map_type::const_iterator> p = 
Map.equal_range(str);
for (map_type::const_iterator i = p.first; i != p.second; ++i)
cout<<(*i).second<<" ";


cout<<endl;
}


int main()
{
map_type M;

M.insert(map_type::value_type("H", 1));
M.insert(map_type::value_type("H", 2));
M.insert(map_type::value_type("C", 12));
M.insert(map_type::value_type("C", 13));
M.insert(map_type::value_type("O", 16));
M.insert(map_type::value_type("O", 17));
M.insert(map_type::value_type("O", 18));
M.insert(map_type::value_type("I", 127));


lookup(M, "I");
lookup(M, "O");
lookup(M, "Rn");
}


hash_multimap::value_type
存储于此hash_multimap之内的object型别，亦即pair<const Key, T>






16.3 Container Adapters
stack, queue和priority_queue等classes并非containers，它们只提供container操作行为的有
限子集。例如stack只允许你安插、移除或检查栈stack顶端的元素。这些classes被称为adapters
因为它们系根据底部的underlying container为实现基础。
stack栈、queues队列和priority queues带优先权的队列都是常见的数据结构。但相应的container
adapters的接口可能令人感到陌生。这三种classes都具有member function pop,可移除最顶端
元素，而且不返回任何值。




16.3.1 stack
stack<T, Sequence>
stack是一种adapter，提供container功能子集。它允许安插、移除及审查stack最顶端元素。这
是一种后进先出LIFO的数据结构，stack最顶端元素即是最后新增元素。
除了最顶端元素外，没有任何方法能够访问栈stack的其他元素:stack不允许遍历其元素。这项
限制是stack存在的唯一理由，因为任何Front Insertion Sequence或Back Insertion Sequence
都足以胜任stack的要求。例如，以vector而言，栈的行为是member functions back,push_back
和pop_back。使用container adapter stack而不直接使得Sequence的唯一理由是，让你清楚知道
你正在执行栈的行为。
由于stack是一个container adapter，它实现于某个底部的container之上，缺省的底部型别是
deque，但也可以明确指定不同的底部型别。
样例:
int main()
{
stack<int> S;
S.push(8);
S.push(7);
S.push(4);
assert(S.size() == 3);
assert(S.top() == 4);
S.pop();
assert(S.top() == 7);
S.pop();
assert(S.top() == 8);
S.pop();
assert(S.empty());
}




16.3.2 queue
queue<T, Sequence>
queue是一种adapter,提供Container功能子集。这是一种先进先出式的数据结构。也就是说允许
在queue的尾端新增元素，并在queue的前端将该元素移除。Q.front()返回的是最早被加入
queue内的元素。
除了queue的前端和尾端，没有任何方式能够访问queue的其他元素；queue并不具有iterators.
这项限制是queue存在的唯一理由，因为任何container如果隶属于Front Insertion Sequence
且为Back Insertion Sequence，便足以胜任队列queue的要求。例如，deque和list都拥有
member functions front、back、push_front、push_back、pop_front、pop_back。


由于stack是一个container adapter，它实现于某个底部的container之上，缺省的底部型别是
deque，但也可以明确指定不同的底部型别。


样例:
int main()
{
queue<int> Q;
Q.push(8);
Q.push(7);
Q.push(6);
Q.push(2);

assert(Q.size() == 4);
assert(Q.back() == 2);

assert(Q.front() == 8);
Q.pop();

assert(Q.front() == 7);
Q.pop();


assert(Q.front() == 6);
Q.pop();

assert(Q.front() == 2);
Q.pop();

assert(Q.empty());
}




16.3.3 priority_queue
priority_queue<T, Sequeue, Compare>
priority_queue是一种adapter，提供Container功能子集。它提供安插、审视、移除最顶端元素
的功能。没有任何机制可以更改priority_queue的任何元素，或是遍历这些元素。
priority_queue的最顶端元素一定是元素中的最大值。


由于priority_queue是一个container adapter，它实现于某个底部的container之上。缺省的底
部型别是vector，但也可以明确指定不同的底部型别。


带优先权的队列priority_queue是标准的数据结构，可以以不同方式实现出来。通常priority
_queue是以heap来实现，并以算法make_heap、push_heap和pop_heap来维护heap的状态。


样例:
int main()
{
priority_queue<int> Q;
Q.push(1);
Q.push(4);
Q.push(2);
Q.push(8);
Q.push(5);
Q.push(7);

assert(Q.size() == 6);
while (!Q.empty())
{
cout<<Q.top()<<" ";
Q.pop();
}
cout<<endl;
//输出为 8 7 5 4 2 1 
}


上个例子中的priority_queue，其最顶端元素一定是数值最大的元素。元素次序关系可由指定
之function object决定，所以轻易就能产生一个priority_queue，使其最顶端元素为数值最小
之元素。
int main()
{
priority_queue<int, vector<int>, greater<int>> Q;
Q.push(1);
Q.push(4);
Q.push(2);
Q.push(8);
Q.push(5);
Q.push(7);

assert(Q.size() == 6);
while (!Q.empty())
{
cout<<Q.top()<<" ";
Q.pop();
}
cout<<endl;
//输出为 1 2 4 5 7 8
}






可移植性与标准化
C++ standard与ARM之间的差异，就像ANSI C standard与The C Programming Language之间的差
异一样。几乎所有C++编译器所实现出来的，都介于ARM C++与standard C++之间。
STL的情况也很类似。仍然没有一个STL实现品完全符合Stepanov--Lee的原始定义，或是符合C++
standard的定义。第二个问题是，即使到了今天，也没有任何一个C++编译器支持STL所用到的每
一个语言特性。


A.1 语言上的变动
A.1.1 Template编译模型(Compilation Model)
自从C++增加template特性之后，template分离式编译(separate compilation)就成了语言的一
部分。其目的在于让function templates和class templates可以如同一般functions和classes
一样地被使用。也就是说你可以在某个源代码文件中声明一个函数，然后在不同的源代码文件中
使用这个函数。这两个文件可以分开编译，只要最后两个目标文件object files被连接linked
起来即可。
ARM和C++ standard都要求templates分离式编译。但很多编译器根本就不具有任何templates
分离式编译能力。


目前唯一具可移植性的解决方案就是，遵循一个规则:function templates和class templates
必须定义在头文件中，而你必须含入适当的头文件，才能使用某个template。这就是为什么现
有的所有STL实现品大部分（甚至全部)都是一些头文件的原因。


A.1.2 带缺省值的Template参数(Default Template Parameters)
就你C++函数的参数可具有缺省值，class templates也一样。假设你声明一个class template
如下:
template <class A, class B = A>
class X{
...
};
那么当你具现化instantiated X时，可以不指定第二个template参数。这么一来便会采用缺省值
A。是的，型别X<int>与型别X<int, int>完全相同。
所有的STL container classes都使用带缺省值的template参数。例如，vector就具有两个
template参数，第一个表现出vector的元素型别，第二个表现allocator，用来参数化vector
的内存分配策略。第二个template参数便带有缺省值，因为大部分的vector使用时机都没有理
由使用非标准的内存分配策略。
目前，并非所有的C++编译器都完全支持带缺省值的template参数。




A.1.3 Member Templates
templates最初加入C++语言时，只有两种东西可以是template:全局的classes和全局的functions
也就是说，template声明式不能在class scope内发生。这意味着member functions不能是
function template。
如今C++ standard已允许non-virtual member functions可以成为function templates。
Member function templates的调用方式和一般的function templates一样。编译器可以由函数
调用所给定的引数推导出template参数，并自动产生该member function的适当实体instance。


class's constructor是一个member function，所以如同其他member functions一样，它可以
成为一个template。这个结果导致member templates最重要的用途之一。例如class pair
便拥有一个经过泛化的copy constructor:
template <class T1, T2> template <class U1, class U2>
pair<T1, T2>::pair(const pair<U1, U2> &);
此式允许以任何pair<U1, U2>构造出任何一个pair<T1, T2>，只要U1可转换为T1,且U2可转换为
T2。关键字template必须出现两次，因为此处有两个template参数列，一个针对pair template
自身，另一个针对member template constructor。


STL container classes大量使用member templates。让我再说一次，其主要用途之一是在
constructors。你可以根据一个iterator range构造出一个container，member template
允许该range所含之型别为任何input Iterator之model。例如你可以这样产生一个vector V,让
它和list L包含相同的元素:
vector<T> V(L.begin(), L.end());
只要L的value type可转换为T，这种写法就有效。同样地，container的insert member functions
也可以藉由member template技术，接受一个iterators range。


class pair的member template constructor不完全是方便性的问题。例如，标准的container
map是一个Associative Container，其元素型别为pair<const Key, Data>。和其他Associate
Container一样，map有一个member function。可让你将单个元素安插到container内，当你写:
M.insert(p);
此处p的型别相同于M的元素型别，也就是说p的型别是pair<const Key, Data>。问题在于如何
构造出object p。
如果使用member template constructor,你可以不必写出pair constructor就将一个元素安插
到map:
M.insert(make_pair(k, d));
这会产生pair<Key, Data> object，然后将该object转为pair<const Key, Data>，然后将它安插
到map中。如果没有member template constructor，便没有这种转换行为。一旦缺少member 
templates的支持，你就必须使用较不方便的形式:
M.insert(pair<const Key, Data>(k, d));




A.1.4 偏特化Partial Specialization
class templates的特化如今进展到了所谓的偏特化partial specialization，如下，你可以针对
整个型别类属entire category of types，而非只针对单一型别，给予template一份不同的定义:
template <clas T> class X
{
//版本1:最一般化(泛化)
};


template <class T> class X<T *>
{
//版本2:针对普通指针、
};


template <> class X(void *)
{
//版本3: 针对某种特定指针
};


全特化与偏特化并不使用相同的语法。这是C++标准化过程中的一项改变。
如果你所使用的编译器遵循C++ standard，你必须写
template <> class X<void>
如果你使用的编译器比较旧，你得这么写:
class X<void *>
这个式子并未使用关键字template。除了使用预处理器pre-processor所提供的宏，否则再没有其
他方法可以写出符合新旧规格的全特化语法。




偏特化对于优化常常很有用途。此外，偏特化使得某种程序设计技术变得可能，而STL正是架构于
这些技术之上。


第一，为了存储效率，STL内含一个特化版本的vector container class:vector<bool>。乍见
之下这不像一个偏特化的例子，但它的确是：就像所有的STL序列一样，vector具有两个template
参数:一个是value type，一个是allocator。vector<bool> class是一个偏特化版本，因为它
给予第一个template参数一个特别型别，而让allocator完全泛化。在不支持偏特化的编译器上，
STL实现品通常会声明一个class bit_vector取而代之。




函数的偏特化partial specialization of functions
Template函数，如同其他函数一样，是可被重载的overloaded。这提高了面对一个函数调用时有
多个版本能够精确吻合exact match的几率。假设你声明了两个function templates:
template <class T> void f(T)
template <class U> void (U* );
当你写下f((int *)0)，你会调用哪个版本?该调用动作吻合第一版本（当T为int *)或第二版本
(当U为int)。
在template初被引进之际，这类函数调用是一合法的，因为它精确吻合了一个以上的函数。但是
新规则已经放宽了这项限制。每当某个函数调用动作可匹配多个重载的function templates时，
编译器会选择其中最特化most specialized的一个。此例之中f的第二版本比第一版本更特化。
是的，第一版本能匹配任何型别，但第二版本只能匹配指针。


STL只在一个地方使用函数的这种偏序partial ordering关系。它有一个swap函数，可交换任何
两个变量的内容。STL针对所有的container classes定义了特化的swap版本。当你写下
swap(v1, v2)，如果v1和v2都是vector &，你会调用以下函数:
template<class T, class Allocator>
void swap(vector<T, Allocator> &, vector<T, Allocator> &)
而非更一般化的版本:
template <class T> void swap(T&, T&)




A.1.5 新加入的关键字
C++语言新增了许多关键字，这些关键字是ARM发行之时所没有的。对于STL以及运用templates的
程序而言，有两个关键字特别重要，那就是explicit和typename。


关键字explicit
explicit用来抑制某种自动型别转换功能。通常，如果class X具有一个constructor可接受型别
为T的单一引数，C++编译器便会自动以该constructor将型别为T的值转换成型别为X的值。C++
standard将大多数containers的单引数constructors都声明为explicit。


关键字typename
C++有一个非常简单的规则来决定是否要将X::T视为型别:如果某个名称可能代表型别或代表其他
某物，则除非你以别种方式明确告知编译器，否则编译器总是假设该名称不代表某个型别。
typename关键字就是用来告知编译器应该将某特定名称视为一个型别。
注意，每当要代表一个型别时，你都必须使用typename，也就是说你必须写出:
template <class X> void g1(x)
{
typename X::T t;
typename X::T *pt;
}
第二个typename也是必要的。


如果某个名称符合以下条件，你就必须使用typename:
1、它是一个资格受限的名称qualified name，亦即其他型别中的嵌套型别。
2、它取决于template参数，也就是取决于template被具现化后的template引数。
例如，函数g内的X::T是一个资格受限的名称（以X::加以限制),并取决于template参数X。


这也意味着，不管你自己正在撰写新的STL组个，或都使用别人所定义的组件，你得使用很多
typename。例如，撰写一个作用于vector<T>身上的template function而且必须取用该vector
的iterator:
template <class T>
void f(vector<T>& V)
{
typename vector<T>::iterator i = V.begin();
...
}
这虽然看起来很奇怪，但此地的确需要typename。在你看来，很显然vector<T>::iterator一定是
取用vector的嵌套的iterator type，但对编译器而言，那只是一种取决于template参数的资格受
限名称。除非你明白告知编译器vector<T>::iterator是个型别名称，否则编译器无法知道。


因此，typename造成了可移植性的问题。符合C++ standard之编译器需要它，但其他更早（尚
未加入关键字typename）之前的编译器却不认识它。
唯一可以通吃上述两种编译器的做法，就是利用预处理器技巧，你可以定义一个宏TYPENAME，让
它在某些编译器中展开为typename，在另一些编译器下则什么也没展开。




A.2 程序库的变动
A.2.1 Allocators
STL containers都将其内存分配方法参数化了。这种做法有时候很有用，但从历史的角度来看，
它却成为STL最不稳定的一部分。目前大家常用的有四种不同的allocator设计:HP STL allocator
SGI STL allocator,以及从C++ standard草案衍化而来的两个不同的allocator设计。
Allocator是一个带有缺省值的template参数，所以你无须指明。如果你确实必须撰写自己的
allocator，你应该详读文档，并找出你的程序库所使用的allocator设计法。


C++ standard定义的所有STL container(vector, list, deque, set, map, multiset, multimap)
都以这种方式来定义其constructors。这些containers的constructors都拥有一个型别为
Allocator的参数，大部分情况下它都是constructor的最后一个参数，并具有缺省值Allocator()
你可以不提到它，以避免使用allocator instances，因此如果我们写:
vector<int> V(100, 0);
就相当于写
vector<int, allocator<int>> V(100, 0, allocator<int>());
 


A.2.2 container Adapters
STL定义三种container adapters: stack, queue, priority_queue。它们并非containers，它们
不提供container的整个接口，只提供该接口的有限子集。
container adapter只是对其底部underlying containers的某种外包装wrapper而已，该底部
container是一个template参数。此一参数化的精确形式目前已经有所改变。


在原始的HP STL中，stack adapter需要单一一个template参数，作为该stack底部数据的型别。
如果你想要产生一个由ints组成的stack并以deque作为其底部数据组织，你得这么声明:
stack<deque<int>>


C++ standard已经改变这一点。stack如今需要两个template参数。第一个是存储于该stack内
的object型别，第二个才是该stack的底部数据组织。当然后者是一个带缺省值的template参数。
对stack而言，该缺省值为deque。因此，由ints组成的stack可以声明为stack<int>。




A.2.3 次要的程序库变动
标准化过程中，STL的接口于某些次要部分亦有些微的改变及扩充。


新的算法
C++ standard内含三个并未定义于原始HP STL中的算法:
1、find_first_of，这很类似C函数库函数strpbrk
2、find_end,它很类似STL算法search
3、search_n


standard还包含了三个泛型算法:
uninitialized_copy
uninitialized_fill
uninitialized_fill_n


以及两个临时内存分配函数:
get_temporary_buffer
return_temporary_buffer
这些特别函数主要用于自行撰写自己的container或adaptive算法。


iterator接口改变
比起原始的HP STL，C++ standard对于iterators多定义了一个次要功能。所有iterators
(Output Iterator除外，因为以下叙述对于它并不合理)如今都定义了member function
operator->。如同你对指针的预期，i->m和(*i).m应该代表相同的事情（动作）。


这对于map和multimap特别方便，因为这些containers的元素都是pairs。如果i是一个iterator,
其value type就是pair<const T, X>，你可以写i->first或i->second。就好像i就是一般指针一
样。




Sequence接口改变
所有的Sequence都包含了并未列于原始HP STL中的三个新的member functons：
1、resize,它会删除或附加元素于尾端，使Sequence变成所指定的大小
2、assign，它是一种一般化的赋值操作行为
3、clear，这是erase(begin(), end());的简略写法，此外，erase member function的返回型
别也有了改变，在HP STL中其返回型别为void，但C++ standard将它改变为iterator。是的，
erase的返回值如今是一个iterator，指向被移除元素的下一个紧邻位置。


multiplies function object
HP STL内含一个function object times，可用来计算两个引数的乘积。C++ standard将这函数
改名为multiplies。原因是times与UNIX的某个头文件名称冲突。






A.3 命名及包装Naming and Packaging
What's in a name? That which we call a rose by any other word would smell as sweet.
我并不鼓励将std namespace内的所有名称导入import.


除了少许例外，C++标准程序库的所有组件都定义于namespace std之中。每当你要使用container
algorithms，或标准程序库中的任何一个名称，都必须明白冠以修饰词std::，否则就得使用
using declaration将它导入import。


以操作符==和<为基础，定义出的一组操作符!=, >, <=, 和>=（都是templates），是以上规则
的例外情况。它们自身并非声明于namespace std中，而是声明于名std::rel_ops的一个嵌套命名
空间中。




C++ standard 头文件         相应的HP STL头文件
<algorithm> <algo.h> 大部分
<deque> <deque.h> 部分
<functional> <function.h> 大部分
<iterator> <iterator.h> 全部
<list> <list.h> 全部
<memory> <defalloc.h> 全部
<tempbuf.h> 全部
<iterator.h>部分
<algo.h> 部分


<numeric> <algo.h> 部分
<queue> <stack.h> 部分
<utility> <pair.h> 全部
<function.h> 部分
<stack> <stack.h> 部分
<vector> <vector.h> 全部
<bvector.h> 全部
<map> <map.h> 全部
<multimap.h> 全部
<set> <set.h> 全部
<multiset.h> 全部