前言

配接器（adapters）在 STL 组件的灵活组合运用功能上，扮演着轴承、转换器的角色。Adapter 这个概念，事实上是一种设计模式。 《Design Patterns》一书中对 adapter 样式的定义如下：将一个类的接口转换为另一个类的接口，使原本因接口不兼容而不能合作的类，可以一起运作。

STL 中所提供的配接器，按照配接的对象可以分为三类：

  • 改变 Container 接口的配接器：Containers Adapter
  • 改变 Iterator 接口的配接器：Iterators Adapter
  • 改变 Functor 接口的配接器：Functors Adapter

其中，container Adapter 已经在前面介绍 stack & queue 中介绍过，这两个容器都是通过修饰 deque 接口的方式呈现出另一种容器的样子，这里就不再介绍了。本节将重点介绍 Iterator Adapter 的内容。

Iterator Adapter

STL 提供了许多应用于迭代器身上的配接器，包括 insert iterators、reverse iterators、iostream iterators 等，这些配接器都通过修饰原始的 iterators 对外接口的方式来实现不同的行为。

Insert Iterators

Insert iterators 可以将一般迭代器的赋值（assign）操作转变为插入（insert）操作。这样的迭代器包括专司尾端插人操作的 back_insert_iterator，专司头端插人操作的 front_insert_iterator，以及可从任意位置执行插入操作的 inser_iterator。由于这三个 iterator adapters 的使用接口不是十分直观，给一般用户带来困扰，

因此，STL更提供三个相应函数: back_inserter() 、front_inserter()、inserter()，直接返回一个容器的插入迭代器。

Insert iterators 的主要观念是，每一个 insert iterators 内部都维护有一个容器（必须由用户指定）；容器当然有自己的迭代器，于是，当客户端对 insert iterators 做赋值操作时，就在 insert iterators 中被转为对该容器的迭代器做插入操作。

也就是说，在 insert iterators 的 operator= 操作符中调用底层容器的 push_front() 或 push_back() 或 insert() 操作函数。至于其它的迭代器惯常行为如 operator++，operator++(int)，operator* 都被关闭功能，更没有提供 operator--(int) 或 operator-- 或 operator-> 等功能（因此被类型被定义为 output_iterator_tag）。

换句话说，insert iterators 的前进、后退、取值、成员取用等操作都是没有意义的，甚至是不允许的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/// @brief 配接器 back_insert_iterator，将赋值操作转换为 push_back 操作
/// @tparam Container 
template <class Container>
class back_insert_iterator {
protected:
    Container* container;  // 底层容器

public:  // 类型定义
    // 由于需要进行写入操作，因此迭代器类型为 output_iterator_tag
    typedef output_iterator_tag     iterator_category;
    typedef void                    value_type;
    typedef void                    difference_type;
    typedef void                    pointer;
    typedef void                    reference;
    typedef Container               container_type;

    // 构造函数
    explicit back_insert_iterator(Container& x) :container(&x) {}

    /// @brief back_insert_iterator 功能的关键所在，将赋值操作转换为 push_back 操作
    back_insert_iterator& operator=(const typename Container::value_type& value) {
        container->push_back(value);
        return *this;
    }

    back_insert_iterator& operator=(typename Container::value_type&& value) {
        container->push_back(move(value));
        return *this;
    }

    // 重载操作符
    // 这三个操作符什么都不做，返回自身
    back_insert_iterator& operator*() { return *this; }
    back_insert_iterator& operator++() { return *this; }
    back_insert_iterator& operator++(int) { return *this; }
};


/// @brief 辅助函数，返回一个容器的 back_insert_iterator
template <class Container>
inline back_insert_iterator<Container> back_inserter(Container& x) {
    return back_insert_iterator<Container>(x);
}

back_insert_iterator 就是将迭代器的赋值操作修改为容器的 push_back() 操作，即从容器的尾端插入元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/// @brief 配接器 front_insert_iterator，将赋值操作转换为 push_front 操作
/// @tparam Container 
template <class Container>
class front_insert_iterator {
protected:
    Container* container;  // 底层容器

public:  // 类型定义
    typedef output_iterator_tag     iterator_category;
    typedef void                    value_type;
    typedef void                    difference_type;
    typedef void                    pointer;
    typedef void                    reference;
    typedef Container               container_type;

    // 构造函数
    explicit front_insert_iterator(Container& x) :container(&x) {}

    // NOTE: 由于调用的是 push_front，因此不适用于 vector

    /// @brief front_insert_iterator 功能的关键所在，将赋值操作转换为 push_front 操作
    front_insert_iterator& operator=(const typename Container::value_type& value) {
        container->push_front(value);
        return *this;
    }

    front_insert_iterator& operator=(typename Container::value_type&& value) {
        container->push_front(move(value));
        return *this;
    }

    // 重载操作符
    // 这三个操作符什么都不做，返回自身
    front_insert_iterator& operator*() { return *this; }
    front_insert_iterator& operator++() { return *this; }
    front_insert_iterator& operator++(int) { return *this; }
};

/// @brief 辅助函数，返回一个容器的 front_insert_iterator
template <class Container>
inline front_insert_iterator<Container> front_inserter(Container& x) {
    return front_insert_iterator<Container>(x);
}

front_insert_iterator 将迭代器的赋值操作修改为容器的 push_front() 操作，即从头部插入元素。但需要注意的是，由于 vector 容器不支持 push_front 操作，因此该迭代器不适用于 vector。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/// @brief 配接器 insert_iterator，将赋值操作转换为 insert 操作
/// @tparam Container
template <class Container>
class insert_iterator {
protected:
    Container* container;  // 底层容器
    typename Container::iterator iter;  // 底层迭代器

public:  // 类型定义
    typedef output_iterator_tag     iterator_category;
    typedef void                    value_type;
    typedef void                    difference_type;
    typedef void                    pointer;
    typedef void                    reference;
    typedef Container               container_type;

    // 构造函数
    insert_iterator(Container& x, typename Container::iterator i) :container(&x), iter(i) {}

    /// @brief insert_iterator 功能的关键所在，将赋值操作转换为 insert 操作
    insert_iterator& operator=(const typename Container::value_type& value) {
        iter = container->insert(iter, value);
        ++iter;  // 使迭代器跟随新插入的元素移动
        return *this;
    }

    insert_iterator& operator=(typename Container::value_type&& value) {
        iter = container->insert(iter, move(value));
        ++iter;  // 使迭代器跟随新插入的元素移动
        return *this;
    }

    // 重载操作符
    // 这三个操作符什么都不做，返回自身
    insert_iterator& operator*() { return *this; }
    insert_iterator& operator++() { return *this; }
    insert_iterator& operator++(int) { return *this; }
};

/// @brief 辅助函数，返回一个容器的 insert_iterator
template <class Container, class Iterator>
inline insert_iterator<Container> inserter(Container& x, Iterator i) {
    typedef typename Container::iterator iter;
    return insert_iterator<Container>(x, iter(i));
}

insert_iterator 将迭代器的赋值操作修改为容器的 insert 操作，并且将迭代器右移一个位置，以保证插入操作的连续性。这是与 back_insert_iterator 及 front_insert_iterator 不同的地方。

reverse_iterator

Reverse iterator，就是将迭代器的移动行为倒转。如果 STL 算法接受的不是一般正常的迭代器，而是这种逆向迭代器，它就会以从尾到头的方向来处理序列中的元素。

实际上我们对于这种配接器并不陌生，因为随便打开之前实现过的一个容器，都会发现类似于下面这样的定义：

1
2
reverse_iterator       rbegin()  noexcept       { return reverse_iterator(end()); }
reverse_iterator       rend()    noexcept       { return reverse_iterator(begin()); }

没错，取得 rend() 与 rbegin() 等迭代器，就是靠 reverse_iterator 进行修饰。虽然看似只需要翻转迭代器所有的移动行为就行，但实际上 reverse_iterator 还是暗藏玄机的，主要体现在对于 operator* 的重载上：

1
2
3
4
5
 reference operator*() const { 
    // 实际对应正向迭代器的前一个位置
    auto tmp = current;
    return *--tmp;
}

由于迭代器的区间表示是一种“前闭后开”的方式，换言之是不对称的；因此，为了配合这样的不对称，当迭代器改变方向时，虽然其真实位置（真正的地址）不变，但其逻辑位置（迭代器所代表的元素，即 operator* 取出的元素）却改变了。因为这样才能保证：将一个正向迭代器区间转换为一个逆向迭代器区间后，不必再有任何的额外处理。

下图可以帮助我们理解这一逻辑：

3.png

reverse_iterator 的代码实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/// @brief 配接器 reverse_iterator，将迭代器的前进变为后退，后退变为前进
/// @tparam Iterator 
template <class Iterator>
class reverse_iterator {

    private:
        Iterator current;  // 记录对应的正向迭代器

    public:
        // 反向迭代器的五种相应型别
        typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
        typedef typename iterator_traits<Iterator>::value_type        value_type;
        typedef typename iterator_traits<Iterator>::difference_type   difference_type;
        typedef typename iterator_traits<Iterator>::pointer           pointer;
        typedef typename iterator_traits<Iterator>::reference         reference;

        typedef Iterator                                              iterator_type;
        typedef reverse_iterator<Iterator>                            self;

    public:
        
        // 构造函数
        reverse_iterator() {}
        explicit reverse_iterator(iterator_type i) :current(i) {}
        reverse_iterator(const self& rhs) :current(rhs.current) {}

    public:

        // 取出对应的正向迭代器
        iterator_type base() const { return current; }

        // 重载操作符
        reference operator*() const { 
            // 实际对应正向迭代器的前一个位置
            auto tmp = current;
            return *--tmp;
        }

        pointer operator->() const {
            return &(operator*());
        }

        // 前进(++)变为后退(--)
        self& operator++() {
            --current;
            return *this;
        }

        self operator++(int) {
            self tmp = *this;
            --current;
            return tmp;
        }

        // 后退(--)变为前进(++)
        self& operator--() {
            ++current;
            return *this;
        }

        self operator--(int) {
            self tmp = *this;
            ++current;
            return tmp;
        }

        self& operator+=(difference_type n) {
            current -= n;
            return *this;
        }

        self operator+(difference_type n) const {
            return self(current - n);
        }

        self& operator-=(difference_type n) {
            current += n;
            return *this;
        }

        self operator-(difference_type n) const {
            return self(current + n);
        }

        reference operator[](difference_type n) const {
            return *(*this + n);
        }

};

stream iterator

stream iterctors，可以将迭代器绑定到一个 stream（数据流）对象身上。绑定到 istream对象（例如 std::cin）者，称为istream_iterator，拥有输入能力；绑定到ostream对象（例如 std::cout）者，称为 ostream_iterator，拥有输出能力。

istream iterator

所谓绑定一个 istream object，其实就是在 istrearmn iterator 内部维护一个 istream member，客户端对于这个迭代器所做的 operator++ 操作、会被导引调用迭代器内部所含的那个 istream member 的输入操作（operator>>）。这个迭代器是个 Input lterartor，不具备 operator--。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/// @brief 配接器 istream_iterator，将输入流转换为迭代器
/// @tparam T
/// @tparam Distance
template <class T, class Distance = ptrdiff_t>
class istream_iterator {
protected:
    std::istream* stream;  // 输入流
    T value;  // 保存当前读取的值
    bool end_marker;  // 是否到达流尾

public:  // 类型定义
    typedef input_iterator_tag      iterator_category;
    typedef T                       value_type;
    typedef Distance                difference_type;
    typedef const T*                pointer;
    typedef const T&                reference;

    // 构造函数
    istream_iterator() :stream(&std::cin), end_marker(false) {}
    istream_iterator(std::istream& s) :stream(&s) { read(); }

    // 重载操作符
    reference operator*() const { return value; }
    pointer operator->() const { return &(operator*()); }

    istream_iterator& operator++() {
        read();
        return *this;
    }

    istream_iterator operator++(int) {
        istream_iterator tmp = *this;
        read();
        return tmp;
    }

    // 读取输入流
    void read() {
        end_marker = (*stream) ? true : false;
        if (end_marker) *stream >> value;
        end_marker = (*stream) ? true : false;
    }

    // Return true if x and y are both end or not end, or x and y are the same.
    bool equal(const istream_iterator& rhs) const {
        return (end_marker == rhs.end_marker) && (!end_marker || (stream == rhs.stream));
    } 
};


template <class T, class Distance = ptrdiff_t>
inline bool operator==(const istream_iterator<T, Distance>& lhs,
                       const istream_iterator<T, Distance>& rhs) {
    return lhs.equal(rhs);
}

template <class T, class Distance = ptrdiff_t>
inline bool operator!=(const istream_iterator<T, Distance>& lhs,
                       const istream_iterator<T, Distance>& rhs) {
    return !(lhs == rhs);
}

ostream iterator

至于 ostream iterator，所谓绑定一个 ostream object，就是在其内部维护一个 ostream member，客户端对于这个迭代器所做的 operator=操作，会被导引调用对应的（迭代器内部所含的）那个 ostream member 的输出操作（operator<<）。这个迭代器是个OutputIterator。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/// @brief 配接器 ostream_iterator，将输出流转换为迭代器
/// @tparam T
/// @tparam Distance
template <class T, class Distance = ptrdiff_t>
class ostream_iterator {
protected:
    std::ostream* stream;  // 输出流
    const char* string;  // 分隔符 

public:  // 类型定义
    typedef output_iterator_tag     iterator_category;
    typedef void                    value_type;
    typedef void                    difference_type;
    typedef void                    pointer;
    typedef void                    reference;

    // 构造函数
    ostream_iterator(std::ostream& s) :stream(&s), string(nullptr) {}
    ostream_iterator(std::ostream& s, const char* c) :stream(&s), string(c) {}

    // 重载操作符
    ostream_iterator& operator=(const T& value) {
        *stream << value;
        if (string) *stream << string;
        return *this;
    }

    ostream_iterator& operator*() { return *this; }
    ostream_iterator& operator++() { return *this; }
    ostream_iterator& operator++(int) { return *this; }
};

测试

以下是一些例子，测试一下上述的三种配接器的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
void test1()
{
    tinystl::vector<int> v1 = tinystl::vector<int>(10);
    tinystl::iota(v1.begin(), v1.end(), 0);
    tinystl::vector<int> v2;

    tinystl::copy(v1.begin(), v1.end(), tinystl::back_inserter(v2));

    for (auto i : v2)
        std::cout << i << " ";
    std::cout << std::endl;

    tinystl::copy(v2.begin(), v2.end(), tinystl::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

// 0 1 2 3 4 5 6 7 8 9 
// 0 1 2 3 4 5 6 7 8 9 

void test2()
{
    tinystl::deque<int> d1 = tinystl::deque<int>(10);
    tinystl::iota(d1.begin(), d1.end(), 0);
    tinystl::deque<int> d2;

    tinystl::copy(d1.begin(), d1.end(), tinystl::front_inserter(d2));

    for (auto i : d2)
        std::cout << i << " ";
    std::cout << std::endl;

    tinystl::copy(d2.begin(), d2.end(), tinystl::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

// 9 8 7 6 5 4 3 2 1 0 
// 9 8 7 6 5 4 3 2 1 0 

void reverse_iterator_test()
{
    tinystl::vector<int> v1 = tinystl::vector<int>(10);
    tinystl::iota(v1.begin(), v1.end(), 0);
    
    auto it3 = v1.begin() + 3;
    auto reverse_it3 = tinystl::reverse_iterator<tinystl::vector<int>::iterator>(it3);
    std::cout << *it3 << " " << *reverse_it3 << std::endl;

    tinystl::for_each(v1.begin(), v1.end(), [](int i) { std::cout << i << " "; });
    std::cout << std::endl;

    tinystl::for_each(v1.rbegin(), v1.rend(), [](int i) { std::cout << i << " "; });
    std::cout << std::endl;
}

// 3 2
// 0 1 2 3 4 5 6 7 8 9 
// 9 8 7 6 5 4 3 2 1 0 

void istream_iterator_test()
{
    tinystl::istream_iterator<int> in(std::cin);
    tinystl::istream_iterator<int> eof;

    tinystl::vector<int> v;
    tinystl::copy(in, eof, tinystl::back_inserter(v));

    tinystl::copy(v.begin(), v.end(), tinystl::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

// 1 2 3 4 5   输入
// q           中止输入
// 1 2 3 4 5   输出

总结

本节简要介绍了关于迭代器的一些配接器，包括 insert_adapter、reverse_iterator、stream_iterator 等，作为配接器，它们都通过简单地修改 iterator 中对应接口的形式，使得迭代器呈现出不同的样貌，这正是 “配接器” 这种设计模式的灵魂所在。