目录

STL与泛型编程 第四周

本页内容是作为 Boolan C++ 开发工程师培训系列的笔记。
因个人水平有限，我撰写的笔记不免出现纰漏。如果您发现错误，请留言提出，谢谢！

迭代器的分类

在 STL 中，算法是以函数模板（Function Template）的形式出现的。算法通过接收容器给的一系列参数来对容器进行操作，而这些参数，正是迭代器。容器通过迭代器返回算法的询问，从而达到容器与算法之间的沟通效果。

根据容器的不同，迭代器又分为了很多种类（category），如下图所示：

<html>

<img src=“/_media/programming/cpp/boolan_cpp/stl_iter_tag.svg” width=“900”/>

</html>

注：无序容器中迭代器的分类可能会因为哈希表单元链表的不同而不同。

关于迭代器种类的详细介绍以及相关可执行的操作请点击链接查看：

迭代器种类的关系

我们把迭代器的种类称为分类，但其实际上却并不是平等的分类关系，而是继承关系：

<html>

<img src=“/_media/programming/cpp/boolan_cpp/stl_iter_tag_inheri.svg” width=“500”/>

</html>

output_iterator 是其中的一个特例。

迭代器分类的打印测试

如果要打印迭代器分类，有两种方法：


第一种方法的实现如下： 

//traits
template<typename T>
void display_category(I itr) {
    typename iterator_traits<II>::Iterator_category cagy;
     display_cat(cagy);
}

//print function example, asking a tag parameter
void display_cat(random_access_iterator_tag) { 
    cout << "random_access_iterator << endl; 
}
......
//calling function with a temporary object by using '()' 
display_category(vector<int>::iterator());

第二种方法则较为简单，只需要将得到的迭代器类型提交给 typeid() 函数就可以。不过相比较于自定义的输出信息 ， typeid() 打印出来的信息根据 STL 实现方法的不同可能会有差异；而且， typeid() 打印出来的信息往往带有编译器自定义的前缀和后缀： 
cout << typeid(itr).name() <<endl;
需要注意的是，使用 typeid() 需要添加头文件 <typeinfo>。

除了容器需要使用的迭代器，I / O 迭代器与其 tag 对应的名称有一些差异。这两个迭代器以 xstream_iterator 的形式定义迭代器对象，但内部定义的迭代器种类却是以 xxput_iterator_tag 的形式表现的。

在各个版本下，对这些迭代器的实现过程中，其接收的参数尽管形式上不同，但实际上是一致的（参数多的会有默认值）。而无论是哪个版本，调用的 tag 都是一样的。

迭代器种类对算法的影响

前面说过算法需要迭代器的信息；而不同的算法对于不同的对象进行操作的时候，往往需要根据具体的情况处理。因此，在标准库中，我们表面上看到的算法都是接收迭代器就可以了，实际上算法在与操作对象的交流中早就知道了迭代器的类型，并且根据这个类型做出了不同的判断。这个判断的过程，一般是通过 traits 来实现的。

为了实现上述的思想，算法的结构可以大致表现为两个部分：

下面来分别看看一些算法的例子。

Distance算法的流程

distance() 算法接收两个迭代器，返回两个迭代器之间的距离。distance() 的主函数由如下代码实现： 

distance(InputIterator first, InputIterator last) {
    typedef typename
        iterator_traits<InputIterator>::iterator_category category;
     return _distance(first, last, category());
从上面的代码可以看到的是，该主函数实际上调用了名为 _distance() 的次函数；而该此函数是需要指定迭代器的类型 category() 的。因此，在调用这个次函数之前，主函数通过 iterator_traits 对其接收的迭代器 InputIterator 的类型进行了判断，然后经过缩减命名之后交给了次函数处理。

很明显的可以看出来的是，这里的 category 参数肯定会因为迭代器的类型而改变。因此，次函数实际上是一组函数的重载，针对不同的迭代器类型调用不同的次函数。distance() 的次函数有两种： 
/* general version */
template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
_distance(InputIterator first, InputIterator last, input_iterator_tag) {
    iterator_traits<InputIterator>::difference_type = 0;
    while (first != last) {
        ++ first;
        ++ n;
    }
    return n;
}

/* random access version */
template<class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
    return last - first;
}
从上面的代码可以看出来的是，distance() 的次函数分为两种，一种是对 Input_iterator 进行处理的函数，另外一种则是对 Random_access_iterator 进行处理的函数。对照这两个函数，我们会发现这两种算法是完全不同的，随机访问版本的函数明显拥有着更高的效率。而我们也可以注意到的是，两个次函数的第三个参数是迭代器的类型参数。该迭代器的参数在编译器接收到迭代器的那一刻就已经判断出来了，并不需要我们去指定。我们只需要按照指定迭代器的方式写好函数的各个部分就可以（注意两个函数的返回类型也是不同的，尽管都是 difference_type）。

迭代器设计为继承关系的重要性

看完上面我们可能会有一个问题：标准库的迭代器类型有 5 种，可是我们的重载版本只给出了两种啊，那么接收到了其他的迭代器怎么办？

我们在 1.1. 中已经讨论过标准库中有 4 种迭代器的类型是处于继承关系下的，Input Iterator 作为这些迭代器的父类。当次函数找不到对应的迭代器类型的时候，就会改而到其父类中寻找解决方法。因此，上例中除了随机访问的类型之外的迭代器，都通过Input Iterator 版本的处理方式来处理。

由此我们也能看出，相比起按参数分类，使用继承关系的优越性：节省了攥写处理相关子类的时间。

其他相关例子

本小节还提供了 advance()，copy(), destory(), unique_copy() 这些例子，从不同的角度来阐述了算法使用 trait 对不同迭代器进行不同操作的流程。以下内容是每个例子的一些比较重要的细节。

Advance

advance() 的功能是将迭代器往前移动 n 个单位。 该算法针对三种迭代器设计了三种不同的处理方法： 

/* Input Iterator */
while (n--) ++i; 

/* Bidirectional Iteraotor */
if(n > 0)
   while (n--) ++i; 
else
   while (n++) --i;
   
/* Random Access Iterator */
 it += n;
在迭代器的设计中有时候设计者还会对迭代器的类型判断进行包装（比如写成函数），然后返回一个临时对象来作为迭代器类型。本算法中就是这样实现的： 
template <class Iterator>
inlin typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
    typedef typename iterator_traits<Iterator>::iterator_category category;
    //return a temporary object 
    return category();
}

Copy

copy() 的作用是将源的元素拷贝到目标中。该算法接收三个参数：源的 first 和 last，以及目标的 first。该算法的主要思想是按位复制，主要的逻辑意向用代码可以表达为： 

while (first != last) {
    *result = *first;
    ++result; 
    ++first;
}
但在实际的实现过程中，整个流程远远比这个要复杂上许多。copy() 的整个流程如下图所示：

<html>

<img src=“/_media/programming/cpp/boolan_cpp/al_copy1.svg” width=“1000”/>

</html>

从上图可以看出，根据不同的参数（迭代器）类型，copy() 选择了不同的方法来进行处理。值得注意的是，copy() 中的萃取机制并不再仅限于 iterator_traits。可以看到在后面选择使用 memmove() 或 _copy_d() 的时候，该算法采用了 type_traits 的机制来进行判断。type_traits 一个重要的衡量标准就是操作对于当前对象来说是否重要，我们在下一个例子里会看到。

Destory

destory() 是 STL 自带的一个用于摧毁对象的算法，其功能与析构函数类似。destory() 的整个流程与相关分支的实现如下图：





从上图我们可以看到 type_traits 在这里使用了析构函数的使用作为判断的标准。我们知道编译器自带析构函数；对于有一些不需要自定义析构函数的类型，我们就不需要自己写一个析构函数来释放内存。因此，析构函数这种操作，在某些条件下就成为了不重要的操作（Trivial Operation）。而 type_traits 正是基于操作的重要性与否来决定分支。

Unique_copy

unique_copy() 是 copy() 的一个变种版本，该算法会得到一个新的结果，该结果里的所有元素都来自源，但不会重复。

通常情况下，该算法接收一个 forward_iterator 类型的迭代器：





该算法的大体实现技术与之前的算法类同。但该函数的实现有一个比}}较需}}要注意的地方在于，这个函数可以接收一个 Output Iterator 类型的迭代器作为其参数。 Output Iterator 类型迭代器有一个重要的特点：只写（Write Only）。按上图左边的实现方法： 

*result = *first; //read operation
该操作对于 Output Iterator 类型的迭代器来说是不允许的。因此，该算法只能针对于 Output Iterator 类型的迭代器在这里的操作再重新设计一遍，即使用一个临时变量 value 来代替。

算法对迭代器类型的暗示

算法本身并不从语法上限制迭代器的类型；但对于某些算法来说，迭代器的类型必须是特定的。C++ 中并没有给出明确的办法来指定算法需要的迭代器类型，但从算法的源码中，我们可以很清楚的看到设计者希望我们用什么样的迭代器去使用算法： 

template <class RandomAccessIterator>
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
......
}
上面的代码是 sort() 的部分实现代码。我们可以看到在开头，代码中在模板名称的地方做出了提示 RandomAccessIterator。尽管该提示只是个名称，但设计者通过这样的方式告诉我们，sort() 应该使用 RandomAccessIterator。

相关具体算法解析

标准库中的泛型算法都有其固定的格式： 

template<typename Iterator>
std::Algorithm(Iterator itr1, Iterator iter2....) {
}
也是说，算法有如下的特点：

下面来看一看比较常用的算法。

Accumulate

accumulate() 是一种用于累积的算法。这个算法有两种形式：

具体的实现代码如下： 

/* First Version */
template<class InputIt, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
    for (; first != last; ++first) {
        init = init + *first;
    }
    return init;
}

/* Version with condition */
template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation op) {
    for (; first != last; ++first) {
        init = op(init, *first);
    }
    return init;
}
第二种版本中的条件是一个二元操作，可以是函数，也可以是仿函数。而这个仿函数可以是标准库自带的二元操作，也可以是自己定义的函数类对象。

详细信息可以查看：外部链接。

For_each

for_each 的功能是对容器内（范围内）每一个个元素都进行一遍制定的操作。具体的代码实现如下： 

template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
{
    for (; first != last; ++first) {
        f(*first);
    }
    return f;
}
该算法的自定义操作为一元操作，比如 n++。

Replace

有些算法分为好几个副版本。这些版本都有固定的用法，比如 _if 后缀就需要添加额外的条件，_copy 后缀则意味着要提供新容器的起始地址（拷贝到新的地方）。按照这些约定速成做法，replace() 可以分为下面三种方法：

相关逻辑代码如下： 

/* replace */
template<class ForwardIt, class T>
void replace(ForwardIt first, ForwardIt last,
             const T& old_value, const T& new_value)
{
    for (; first != last; ++first) {
        if (*first == old_value) {
            *first = new_value;
        }
    }
}

/* replace_if */
template<class ForwardIt, class UnaryPredicate, class T>
void replace_if(ForwardIt first, ForwardIt last,
                UnaryPredicate p, const T& new_value)
{
    for (; first != last; ++first) {
        if(p(*first)) {
            *first = new_value;
        }
    }
}

/* replace_copy */
template<class InputIt, class OutputIt, class T>
OutputIt replace_copy(InputIt first, InputIt last, OutputIt d_first,
                      const T& old_value, const T& new_value)
{
    for (; first != last; ++first) {
        *d_first++ = (*first == old_value) ? new_value : *first;
    }
    return d_first;
}

Count

count() 也有 _if 的版本：

相关逻辑代码如下： 

/* count */
template<class InputIt, class T>
typename iterator_traits<InputIt>::difference_type
    count(InputIt first, InputIt last, const T& value)
{
    typename iterator_traits<InputIt>::difference_type ret = 0;
    for (; first != last; ++first) {
        if (*first == value) {
            ret++;
        }
    }
    return ret;
}

/* count_if */
template<class InputIt, class UnaryPredicate>
typename iterator_traits<InputIt>::difference_type
    count_if(InputIt first, InputIt last, UnaryPredicate p)
{
    typename iterator_traits<InputIt>::difference_type ret = 0;
    for (; first != last; ++first) {
        if (p(*first)) {
            ret++;
        }
    }
    return ret;
}
需要注意的是，关联容器都自带成员函数版本的 count。

Find

find() 也有 _if 的版本：

相关逻辑代码如下： 

/* find */
template<class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

/* find_if */
template<class InputIt, class UnaryPredicate>
InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
{
    for (; first != last; ++first) {
        if (p(*first)) {
            return first;
        }
    }
    return last;
}
需要注意的是，关联容器全部自带成员函数版本 find()。

Sort

sort() 正如其字面含义，是对迭代器范围内的元素进行排序。默认的 sort() 排序规则是 <，但也可以自定义排序规则。sort() 的应用可以表现成如下形式： 

std::sort(s.begin(), s.end()); //sort using the default operator <
std::sort(s.begin(), s.end(), std::greater<int>()); //sort using a standard library compare function object
std::sort(s.begin(), s.end(), customLess);  //// sort using a custom function object
在C++11版本中，sort() 还可以使用 Lambda 表达式作为比较条件。
需要注意的是，关联容器因为其数据结构的原因，天生就是有序的，所以我们不能对其应用 sort()。在顺序容器中，只有 List 和 Forward_List 自带成员函数版本的 sort()。

3.6.1.Reverse_Iterator简介


在 sort() 的应用中，如果希望倒序排列，我们可以直接使用两个反转迭代器 rbegin()、rend()。这两个迭代器通过迭代器适配器 reverse_iterator() 实现： 

rbegin() { return reverse_iterator(end()); }
rend() {return reverse_iterator(begin()); }

binary_search() 是标准库自带的二分查找算法。值得提醒的是，所有二分查找算法必须先排序。

该算法底层是通过 lower_bound() 函数实现。 lower_bound() 接收一个值，然后会按照该值对迭代器范围内所有元素进行大小比较，从而找出在不改变该范围元素的顺序的情况下，找出最靠前可以插入的位置：

<html>

<img src=“/_media/programming/cpp/boolan_cpp/al_bin.svg” width=“500”/>

</html>

因此，binary_search() 只需要通过判断 lower_bound() 返回的位置就知道是否能找到这个值了。如果 lower_bound() 返回的位置在序列的首部或者序列的尾部，都说明这个序列中不存在与当前元素相等的元素： 

return (first != last && !(val < * first));
当然，首迭代器指向的元素都是可以访问的，因此我们可以把 val < * first 这校验提前到调用 lower_bound() 之前，这样会更加有效率。

仿函数 & 函数对象

仿函数（Functor）属于标准库六大部分之一，其表现为类似函数的类，实际意义则是为算法提供各种各样的自定义规则和条件。仿函数，顾名思义，就是要模仿函数的功能。为了实现这一点，仿函数必须在类中重载函数调用操作符（Function call Operator） ()。按照其功能不同，仿函数分为如下三类：

有标准库的特有设计，算法的条件必须设计成仿函数才能传递到算法的内部。在大多数情况下，我们传递的都是仿函数的一个类对象；在标准库的攥写中，很多时候都采用返回一个临时对象作为条件的手法，即对象后接一个 () 表示临时对象，比如： 

less<int>();
需要提出来的是，GNU 自定义了几个独特的仿函数：identity(), select1st(), select2nd()。

标准库的仿函数

通常情况下标准库允许我们自定义仿函数。我们可以通过如下方式实现自定义的仿函数： 

struct my class {
    bool operator() (int i, int j) { return i < j); }
} myobj;
上述代码中的 myobj 对象是可以作为条件传递到算法中的。我们再来看看标准库的代码都是怎么写的： 
template<class T>
struct less: public binary_function<T, T, bool> {
    bool operator() { const T& x, const T& y} const 
    { return x < y; }
}
这一段代码可比上面那一段繁琐多了，可是为什么非要写成这样呢？

我们注意到第二段代码中多出来了一行多的东西：继承了一个 binary_function 的类。为什么要这么做？其实，要理解为什么要这么做，我们得首先看看 binary_function 这个类中有什么东西： 
template<class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
}
这个类除了 3 个类型的 alias 以外什么都没有。那继承的意义何在？

这个意义在于，标准库内部有自己定义的一套“接头规矩”。就像算法和容器交互需要 5 个类型一样，仿函数在传递进算法的时候也需要制定一些规矩。而这里的 binary_function 类，就是告诉算法，我传进来的仿函数会有两个参与运算的类型，和一个用于接收结果的类型；换而言之，也就是告诉算法，传进来的条件是一个二元运算。

该类还有一个姊妹版 unary_function， 表示传进来的条件是一个一元运算（比如 ++）。

而本节开头我们自定义的仿函数写法，可能在某些场合可以使用；但是当我们需要修改或者适配（adapt）其本身的时候，很可能就会出问题了。比如在适配器 bind2nd() 中有这么一段： 
typename operation::second_argument_type value;
这一段也就是在询问仿函数，你的第二个形参的类型是什么？标准库中的仿函数 less 继承了父类，因此可以正确的执行下去。这样的仿函数，我们称之为可适配仿函数（Adaptable Function）。反观我们在开头写的 myobj，显然不具有这样的特性。

适配器

适配器是标准库里的一个重要的部分。适配器实际上做的是“换肤”的工作，比如改变函数的名称或者接口之类的工作。按照类型的不同，适配器分为如下三大部分：

适配器本身并不改变原有的功能，因此适配器主要有两种实现方式：继承和包含。标准库中基本上所有的适配器都是使用包含的方式实现的。

仿函数适配器

试想一下如果我们需要与指定数 40 的大小。如果这是一个作为传入算法的条件，那么按先前的写法，我们需要每一次都将这个 40 作为第二参数写入仿函数的参数列表里。既然这个 40 是不变呢，那有没有一种方法可以在算法里绑定这个 40？

标准库提供了一个 bind2nd() 的函数解决了这个问题。严格意义上说，这个 bind2nd() 是一个仿函数适配器。我们接下来就看看这个适配器是怎么实现的。

首先来看一个 bind2nd() 的使用方法： 

count_if(v.begin(), v,end(), bind2nd(less<int>(), 40));
这里实现的规则是使用 int 的 less 规则；也就是用另外一个整型变量与 40 比大小。 less<int>() 在这里作为一个临时的仿函数对象，也就是我们前面用来做条件的惯用手法。

看到这里我们不禁要问了，函数只会在调用的时候传参数。 bind2nd() 只是条件的一部分，是怎么将 40 绑定到 less<int>() 中的？为了解决这个问题，我们需要看一看 bind2nd() 是如何实现的。

前面说过，bind2nd() 是一个适配器，因此，它的底层是有另外一个函数 binder2nd() 来实现的： 
template <class Operation, class T>
  binder2nd<Operation> bind2nd (const Operation& op, const T& x)
{
  typedef typename Operation::second_argument_type(x) arg2_type;
  return binder2nd<Operation>(op, arg2_type); //type + () means create a object
}
这个 binder2nd() 实际上是一个仿函数。这个仿函数会接受一个操作 op，和一个值 value，然后会返回被操作过的值，即 op(x, value)。 binder2nd() 的实现有几个要点：

binder2nd() 像函数一样将返回值传递给 count_if()，然后在 count_if() 中作为条件(pred)对每一个元素进行判断： 

for(; first != last; ++first)
    if(pred(*first)) ++n;
整个过程概括起来就是：

  1. count_if 在遍历元素的过程中，会对每一个得到的元素带入我们指定的条件，然后得到结果。此时我们条件是 bind2nd(less<int>(), 40)，因此需要看 bind2nd() 是如何处理的。根据上面的代码，bind2nd() 是一个适配器，核心部分由 binder2nd() 实现，因此编译器查看 binder2nd() 做了什么。
  2. binder2nd() 是一个仿函数，也就是类模板。在使用类模板的时候，必须要指定模板的类型；这对普通用户来说是很不方便的一件事。为了简化操作，才有了适配器 bind2nd()。注意这里的bind2nd() 是一个函数，而不是类。而我们都知道，函数模板是可以自行推导实参的；因此，将对外接口改变为函数模板之后，我们就可以将 binder2nd() 的参数推导工作交给编译器去做了。
  3. bind2nd() 通过 binder2nd<Operation>(op, arg2_type) 创建了一个 binder2nd() 的对象，将得到的参数交给 binder2nd() 处理。此时 binder2nd() 通过构造函数存储了得到的参数，再通过 () 重载得到条件比较的结果，然后将结果交给 count_if 调用条件的地方。



除此之外，有几个问题我们需要了解：

  1. 仿函数 bind2nd() 是如何得知条件要求的类型的
  2. 仿函数是如何校验输入类型是否符合条件要求的类型的

这些细节，我们可以倒着过去理解：

首先看一下 binder2nd() 的实现代码： 

template< class Operation >
class binder2nd : public unary_function<typename Operation::first_argument_type,
                                        typename Operation::result_type> {
protected:
    Operation op;
    typename Operation::second_argument_type value;
public:
    //ctor
    binder2nd(const Operation& Operation& x, 
              const typename Operation::second_argument_type& y) 
              : op(x), value(y) {};
    // '()' overloading
    typename Operation::result_type 
        operator()(typename Operation::first_argument_type& x) const {
            return op(x, value);
};
从上面的代码中我们可以看到适配器的使用中牵涉到输入的合法性判断，是通过“问答”的方式来校验的：



再来看看 less 的代码，看看是如何指定的其需要的类型的： 

template <class T>
struct less: public binary_function<T, T, bool> {
.....
};
联系到我们前面说过如何制作一个 Adaptable 的仿函数，其实就明白了；仿函数中的数据类型，是通过其父类 binary_function() 或者其 一元版本进行传递的。当 less 的对象创建的时候，T 就定下来了。余下来的事就是通过其父类再把这个类型传递出去就好了，也就是说，在 binder2nd() 中继承，就可以了。

不过上面的源码里， binder2nd() 继承的是 unrary_function()。这是因为 binder2nd() 只需要接收一个参数，它的第二个参数，早就通过适配器 bind2nd() 确定下来了。

所以，传递到算法里的条件仿函数，必须要继承那几个类型。继承 binary_function() 或者 unrary_function()，就是为了回答算法的询问。

Not1

not1 也是一个仿函数适配器，返回当前条件的相反值。它的结构与 bind2nd() 是类似的：

not1 通过在 unary_negate() 中重载 () 为 !pred(x) 达到相反的效果。

Bind

bind 是C++11 中提供的新内容，用于取代 bind2nd() 等旧式的适配器。bind 适配器定义于头文件 <functional> 之中。bind 可以绑定的对象有：

详细的用法请查看下表：

<html>

<img src=“/_media/programming/cpp/boolan_cpp/stl_bind.svg” width=“1000”/>

</html>

上图的 placeholder 象征着参数在参数序列中的位置。如果你不想指定一个具体的数到参数序列的某个位置，而是要等到调用的时候再输入，你就可以使用 placeholder 代替。

迭代器适配器

迭代器适配器的底层都是由迭代器类实现，通过一系列的运算符重载实现新的功能。这些适配器和迭代器一样，同样需要 5 个关联类型。下面我们来看看这些迭代器都是怎么实现的。

Reverse Iterator

反转迭代器类以 rbegin() 和 rend() 为代表。这两个迭代器的功能与迭代器正好相反：

因此，我们需要重新定义的操作有：取值，前进，后退，以及跳转： 

reference operator* () const { Iterator tem = current; return *--temp; }
self& operator ++ () { --current; return this; }
self& operator -- () { ++current; return this; }
self& operator + (difference_type n) { return self(current - n; }
self& operator + (difference_type n) { return self(current + n; }

Inserter

在算法copy() 中，copy() 会接受三个迭代器：源容器的头尾迭代器和目标容器的头迭代器。由于 copy() 按位拷贝的设定， copy() 并不会检查目标容器是否有足够的空间装纳源容器的所有元素。因此，我们可以使用 Inserter 保证有足够的空间。Inserter 会在 copy() 每一次拷贝的时候将元素插入当前迭代器的位置。

比较有意思的是，copy() 是按位赋值，本身已经不能修改了。为了达到按位插入，Inserter 的设计采用了一个很好的方法：对赋值操作进行重载，在把插入操作写到赋值里： 

operator(const typename Container::value_type& value) {
    iter == container->insert(iter, value);
    ++iter;
    return this;
}
Inserter 先通过 insert() 算法把元素插入当前位置，再通过自加当前迭代器将迭代器移动到下一位，这样就保证了插入的元素永远都在先前插入的元素之前。

X适配器

X适配器主要指的是 I/O Stream 迭代器的适配器，按分类来说应该成为输入输出流的迭代器适配器。这类适配器主要将迭代器应用到输入输出对象上，方便一系列的操作。

Ostream 适配器

Ostream 适配器可以将适配器和一个 Ostream 对象绑定到一起 对 Ostream 中的内容进行操作。一个典型的例子就是 copy()： 

std::ostream_iterator<int> out_it(std::cout, '','');
std::copy(myVec.begin(), myVec.end(), out_it);
在上面的代码中，out_it 作为了 Ostream 适配器的对象，绑定了 cout；out_it 需要的第二个字符串参数是间隔符。该段代码的功能是将 myVec 中的所有内容输出到屏幕，并以 ,号隔开。

从前面的 inserter 我们可以知道， copy() 的内容是已经制定好的，因此我们要用适配器实现新的功能，最有效的办法之一就是重载运算符。在这里我们需要打印当前的值到屏幕，也就是会做类似 cout « value 一样的操作，因此，我们可以对 = 操作进行重载： 
ostream_iterator<T, char T， traits>& operator = (const T& value) {
    *out_stream << value; 
    if（delim != 0) *out_stream << delim;
out_stream 是 basic_ostream<charT, traits>* 的对象，也就是 ostream 的适配器。因此，不难发现上面的代码其实在做两件事：

上面的ostream 适配器以及其第二参数字符串都是通过构造函数初始化的，与 inserter 几乎一致，因此不在多过多描述。

Istream 适配器

注：本节理解可能有些问题，需要进一步的修正。



Istream 适配器与 Ostream 适配器实现方法类似。我们通过使用 Istream 适配器，可以进行对输入端中的内容进行操作。先来看看使用例子： 

istream_iterator<int> iit(cin), eos;
copy(iit, eos, inserter(c, c.begin()));
上面的代码功能是一个简单的输入功能，也就是将输入的内容复制到容器中。

值得注意的是，这里定义了两个 Istream 适配器：iit 和 eos。如果我们仔细观察，会发现其中一个带参数，另外一个不带。对于 Istream 适配器来说，如果对象初始化时带参数，证明是正常的输入对象；如果不带参数，那这个 Istream 适配器代表的是输入端结束的标志（End of Stream）。因此，iit 和 eos 实际上就代表了 cin 的起点和终点，而 copy() 依旧是做的按位拷贝的操作而已。

不过在操作的时候，还有一个小问题：在 Istream 适配器的实现中，对带参数的构造函数的实现如下： 
istream_iterator(istream_type& s):in_stream(&s) { ++*this; }
这里不但取了值，而且当时还对适配器做了自增。而这个自增也是经过重载的： 
istream_iterator<T, charT, Distance> & operator  ++ {
    if(in_stream && !(*in_stream >> value) in_stream = 0;
    return *this;
}
上面这段代码实际上是在判断 Istream 对象的状态：是否 Istream 对象中有内容，并且正等待输入；如果输入完毕，则清空输入对象，并将 value 中的值传回来。看上去迭代器并没有移位，但是通过不断的做输入，清空，返回这三个操作，实际上我们的输入是在一步一步的往前走，直到遇到完全为空。

因此，当 Istream 适配器对象建立的时候，输入操作就已经开始了；我们需要注意的是，如果有任何提示信息需要提前打印，都应该放置到 Istream 适配器对象初始化之前。