从零开始的 STL 实现记录：Adapter-2

前言

上一节介绍了 iterator adapter 的内容，本节将介绍 adapter 家族的最后一部分成员：functor adapter。

functor adapter 是所有配接器中数量最庞大的一类，配接灵活程度非常高，通过它们之间的绑定、组合与修饰，几乎可以创造出各种表达式。

如同 container adapters 内藏了一个 container member 一样、或是像 reverse iterator （adapters）内藏了一个 iterator mermber 一样、或是像 stream iterator（adapters）内藏了一个 pointer to stream 一样，或是像 insert iterator （adapters）内藏了一个 pointer to container （并因而得以取其 iterator）一样，每一个 function adapters 也内藏了一个member object，其型别等同于它所要配接的对象（那个对象当然是一个“可配接的仿函数”，adaptable functor）。当 function adapter 有了完全属于自己的一份修饰对象（的副本）在手，它就成了该修饰对象（的副本）的主人，也就有资格调用该修饰对象（一个仿函数），并在参数和返回值上面动手脚了。

functor adapter 主要可以分为五类，以下将分别介绍。

对返回值进行逻辑否定：`not1`、`not2`

这两个配接器会分别将一个一元仿函数与一个二元仿函数的结果取反，由于被修饰的仿函数返回值类型为 bool，因此也可被称为谓词。

/// @brief 仿函数配接器，用于将一个一元谓词取反
/// @tparam Predicate 
template <class Predicate>
class unary_negate: public unary_function<typename Predicate::argument_type, bool> {
protected:
    Predicate pred;  // 将谓词作为成员变量，就能对其运算结果进行操作了
public:
    explicit unary_negate(const Predicate& x): pred(x) {}
    bool operator()(const typename Predicate::argument_type& x) const { return !pred(x); }
};

/// @brief 辅助函数，用于生成一个 unary_negate 对象
template <class Predicate>
inline unary_negate<Predicate> not1(const Predicate& pred) {
    return unary_negate<Predicate>(pred);
}


/// @brief 仿函数配接器，用于将一个二元谓词取反
/// @tparam Predicate
template <class Predicate>
class binary_negate: public binary_function<typename Predicate::first_argument_type,
                                            typename Predicate::second_argument_type,
                                            bool> {
protected:
    Predicate pred;
public:
    explicit binary_negate(const Predicate& x): pred(x) {}
    bool operator()(const typename Predicate::first_argument_type& x,
                    const typename Predicate::second_argument_type& y) const {
        return !pred(x, y);
    }
};

/// @brief 辅助函数，用于生成一个 binary_negate 对象
template <class Predicate>
inline binary_negate<Predicate> not2(const Predicate& pred) {
    return binary_negate<Predicate>(pred);
}

对参数进行绑定：`bind1st`、`bind2nd`

这两个配接器分别将一个二元仿函数的第一个参数与第二个参数绑定为一个固定值。

/// @brief 仿函数配接器，用于将一个二元仿函数的第一个参数绑定为一个固定值，使其变成一元仿函数
/// @tparam Operation 
template <class Operation>
class binder1st: public unary_function<typename Operation::second_argument_type,
                                       typename Operation::result_type> {
protected:
    Operation op;  // 将二元仿函数作为成员变量
    typename Operation::first_argument_type value;  // 绑定的值
public:
    binder1st(const Operation& x, const typename Operation::first_argument_type& y)
        : op(x), value(y) {}
    typename Operation::result_type operator()(const typename Operation::second_argument_type& x) const {
        return op(value, x);
    }
};

/// @brief 辅助函数，将二元仿函数的第一个参数绑定为一个固定值，使其变成一元仿函数
/// @param op 二元仿函数
/// @param x  绑定的值
/// @return  返回一个一元仿函数
template <class Operation, class T>
inline binder1st<Operation> bind1st(const Operation& op, const T& x) {
    typedef typename Operation::first_argument_type arg1_type;
    return binder1st<Operation>(op, arg1_type(x));
}


/// @brief 仿函数配接器，用于将一个二元仿函数的第二个参数绑定为一个固定值，使其变成一元仿函数
/// @tparam Operation 
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:
    binder2nd(const Operation& x, const typename Operation::second_argument_type& y)
        : op(x), value(y) {}
    typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const {
        return op(x, value);
    }
};

/// @brief 辅助函数，将二元仿函数的第二个参数绑定为一个固定值，使其变成一元仿函数
/// @param op 二元仿函数
/// @param x  绑定的值
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T& x) {
    typedef typename Operation::second_argument_type arg2_type;
    return binder2nd<Operation>(op, arg2_type(x));
}

用于函数合成：`compose1`、`compose2`

这两个配接器用于合成一些仿函数的运算结果，具体说来：

compose1(op1, op2)：合成后的 f(x) 效果相当于 $f(x) = op1(op2(x))$
compose2(op1, op2, op3)：合成后的 f(x) 效果相当于 $f(x) = op1(op2(x), op3(x))$

/// @brief 仿函数配接器，产生一个仿函数 f(x) = op1(op2(x))
/// @tparam Operation1
/// @tparam Operation2
template <class Operation1, class Operation2>
class unary_compose: public unary_function<typename Operation2::argument_type,
                                           typename Operation1::result_type> {
protected:
    Operation1 op1;
    Operation2 op2;
public:
    unary_compose(const Operation1& x, const Operation2& y): op1(x), op2(y) {}
    typename Operation1::result_type operator()(const typename Operation2::argument_type& x) const {
        return op1(op2(x));
    }
};

/// @brief 辅助函数，产生一个仿函数 f(x) = op1(op2(x))
template <class Operation1, class Operation2>
inline unary_compose<Operation1, Operation2> compose1(const Operation1& op1, const Operation2& op2) {
    return unary_compose<Operation1, Operation2>(op1, op2);
}


/// @brief 仿函数配接器，产生一个仿函数 f(x) = op1(op2(x), op3(x))
/// @tparam Operation1
/// @tparam Operation2
/// @tparam Operation3
template <class Operation1, class Operation2, class Operation3>
class binary_compose: public unary_function<typename Operation2::argument_type,
                                            typename Operation1::result_type> {
protected:
    Operation1 op1;
    Operation2 op2;
    Operation3 op3;
public:
    binary_compose(const Operation1& x, const Operation2& y, const Operation3& z)
        : op1(x), op2(y), op3(z) {}
    typename Operation1::result_type operator()(const typename Operation2::argument_type& x) const {
        return op1(op2(x), op3(x));
    }
};

/// @brief 辅助函数，产生一个仿函数 f(x) = op1(op2(x), op3(x))
template <class Operation1, class Operation2, class Operation3>
inline binary_compose<Operation1, Operation2, Operation3> 
compose2(const Operation1& op1, const Operation2& op2, const Operation3& op3) {
    return binary_compose<Operation1, Operation2, Operation3>(op1, op2, op3);
}

用于函数指针与成员函数指针：`ptr_fun`、`mem_fun`、`mem_fun_ref`

这两种配接器使我们能够将一般函数与成员函数当做仿函数使用。

一般函数当做仿函数传给STL算法，就语言层面本来就是可以的，就好像原生指针可被当做迭代器传给 STL 算法一样；至于成员函数，虽然说要麻烦一些但仍然可以使用匿名函数（lambda）的方式传给 STL 的算法。但如果你不使用这里所说的两个配接器先做一番包装，你所使用的那个一般函数将无配接能力、也就无法和前数小节介绍过的其它配接器接轨。

可能部分读者对于“可配接能力”这一概念还不是很理解，这里就说一下博主的理解：

首先，STL 中针对仿函数与配接器的设计是怎样的？没错，通过模板参数推导以及继承的方式规范了各种仿函数的接口。具体说来，每个一元仿函数（unary）都继承自 unary_function，从而可以通过 argument_type 以及 result_type 来获得仿函数的参数以及返回值的型别信息；对于二元仿函数（binary）来说也是如此。因此，各种配接器才能在一个抽象的层面上工作，并且可以不断地组合或配接。

以 binary_compose::operator() 为例：

typename Operation1::result_type 
operator()(const typename Operation2::argument_type& x) const {
    return op1(op2(x), op3(x));
}

由于所有的仿函数全都统一了接口，因此我们便可以用 Operation1::result_type 取得返回值类型，Operation2::argument_type 取得参数类型。而不用关心具体的仿函数是什么样的；进一步地，以 compose2() 为例，其返回值类型为 binary_compose<Operation1, Operation2, Operation3> 而 binary_compose 又是继承于 unary_function。因此被配接器修饰后的结果依然可以通过 first_argument_type 和 result_type 等型别萃取出信息，从而可以继续配接。

template <class Operation1, class Operation2, class Operation3>
inline binary_compose<Operation1, Operation2, Operation3> 
compose2(const Operation1& op1, const Operation2& op2, const Operation3& op3) {
    return binary_compose<Operation1, Operation2, Operation3>(op1, op2, op3);
}

这大概就是“可配接能力”的体现了吧，反观普通函数与成员函数，它们自然不会继承于 unary_function 或 binary_function 类型，虽然也可以通过函数指针的方式传给 STL 算法，但还是失去了配接能力，即不能再与其他的 STL 仿函数与配接器“合作”。

用于函数指针：`ptr_fun`

通过模板参数推导萃取出函数指针的参数，并通过继承，统一对外的接口。

/// @brief 函数配接器，将一个一元函数包装为仿函数
/// @tparam Arg 一元函数的参数类型
/// @tparam Result 一元函数的返回值类型
template <class Arg, class Result>
class pointer_to_unary_function: public unary_function<Arg, Result> {
protected:
    Result (*ptr)(Arg);  // 函数指针
public:
    pointer_to_unary_function() {}
    explicit pointer_to_unary_function(Result (*x)(Arg)): ptr(x) {}
    Result operator()(Arg x) const { return ptr(x); }
};

/// @brief 将一个一元函数包装为仿函数
/// @param x  一元函数
/// @return  仿函数
template <class Arg, class Result>
inline pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) {
    return pointer_to_unary_function<Arg, Result>(x);
}


/// @brief 函数配接器，将一个二元函数包装为仿函数
/// @tparam Arg1 二元函数的第一个参数类型
/// @tparam Arg2 二元函数的第二个参数类型
/// @tparam Result 二元函数的返回值类型
template <class Arg1, class Arg2, class Result>
class pointer_to_binary_function: public binary_function<Arg1, Arg2, Result> {
protected:
    Result (*ptr)(Arg1, Arg2);
public:
    pointer_to_binary_function() {}
    explicit pointer_to_binary_function(Result (*x)(Arg1, Arg2)): ptr(x) {}
    Result operator()(Arg1 x, Arg2 y) const { return ptr(x, y); }
};

/// @brief 将一个二元函数包装为仿函数
/// @param x  二元函数
/// @return  仿函数
template <class Arg1, class Arg2, class Result>
inline pointer_to_binary_function<Arg1, Arg2, Result> ptr_fun(Result (*x)(Arg1, Arg2)) {
    return pointer_to_binary_function<Arg1, Arg2, Result>(x);
}

用于成员函数指针：`mem_fun`、`mem_fun_ref`

成员函数指针的配接器相比于普通函数指针的配接器实现起来有一些不同的地方：

首先，无任何参数的成员函数被修饰后会变为 unary_function 类型，而有一个参数的成员函数会变为 binary_function。

这主要是因为成员函数是通过该类的实例化对象来调用的，熟悉成员函数的读者都知道，成员函数在调用时会隐式地传递一个 this 指针指向当前对象。因此，即使是调用无参数的成员函数，也需要通过 obj->f() 或 obj.f() 的方式调用，因此在重载 operator() 时一定需要传入一个该类型的对象，再由该对象调用成员函数。

由于各种条件的排列组合，成员函数指针配接器一共要实现 8 种不同的版本：

具体说来：（1）无任何参数 vs 有一个参数（2）通过指针调用 vs 通过引用调用（3）const 成员函数 vs 非 const 成员函数。组合下来共 $2^3 = 8$ 个不同的类模板，为了方便使用，STL 也提供了 8 个不同版本的辅助函数，这些辅助函数通过函数重载来实现不同条件下的匹配，十分方便。

容器中存放的既有可能是对象的指针，也有可能是对象本身，因此需要分出通过指针调用与通过引用调用两种不同的版本。

/// @brief 无任何参数，通过指针调用，non-const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
template <class S, class T>
class mem_fun_t: public unary_function<T*, S> {
public:
    explicit mem_fun_t(S (T::*pf)()): f(pf) {}
    S operator()(T* p) const { return (p->*f)(); }  // 转调用
private:
    S (T::*f)();  // 内部成员，指向成员函数
};


/// @brief 无任何参数，通过指针调用，const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
template <class S, class T>
class const_mem_fun_t: public unary_function<const T*, S> {
public:
    explicit const_mem_fun_t(S (T::*pf)() const): f(pf) {}
    S operator()(const T* p) const { return (p->*f)(); }
private:
    S (T::*f)() const;
};


/// @brief 无任何参数，通过引用调用，non-const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
template <class S, class T>
class mem_fun_ref_t: public unary_function<T, S> {
public:
    explicit mem_fun_ref_t(S (T::*pf)()): f(pf) {}
    S operator()(T& r) const { return (r.*f)(); }
private:
    S (T::*f)();
};


/// @brief 无任何参数，通过引用调用，const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
template <class S, class T>
class const_mem_fun_ref_t: public unary_function<T, S> {
public:
    explicit const_mem_fun_ref_t(S (T::*pf)() const): f(pf) {}
    S operator()(const T& r) const { return (r.*f)(); }
private:
    S (T::*f)() const;
};


/// @brief 一个参数，通过指针调用，non-const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
/// @tparam A 参数类型
template <class S, class T, class A>
class mem_fun1_t: public binary_function<T*, A, S> {
public:
    explicit mem_fun1_t(S (T::*pf)(A)): f(pf) {}
    S operator()(T* p, A x) const { return (p->*f)(x); }
private:
    S (T::*f)(A);
};


/// @brief 一个参数，通过指针调用，const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
/// @tparam A 参数类型
template <class S, class T, class A>
class const_mem_fun1_t: public binary_function<const T*, A, S> {
public:
    explicit const_mem_fun1_t(S (T::*pf)(A) const): f(pf) {}
    S operator()(const T* p, A x) const { return (p->*f)(x); }
private:
    S (T::*f)(A) const;
};


/// @brief 一个参数，通过引用调用，non-const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
/// @tparam A 参数类型
template <class S, class T, class A>
class mem_fun1_ref_t: public binary_function<T, A, S> {
public:
    explicit mem_fun1_ref_t(S (T::*pf)(A)): f(pf) {}
    S operator()(T& r, A x) const { return (r.*f)(x); }
private:
    S (T::*f)(A);
};


/// @brief 一个参数，通过引用调用，const 成员函数
/// @tparam S 返回值类型
/// @tparam T 成员函数所属的类
/// @tparam A 参数类型
template <class S, class T, class A>
class const_mem_fun1_ref_t: public binary_function<T, A, S> {
public:
    explicit const_mem_fun1_ref_t(S (T::*pf)(A) const): f(pf) {}
    S operator()(const T& r, A x) const { return (r.*f)(x); }
private:
    S (T::*f)(A) const;
};

对应的辅助函数，使用了重载所以只需要使用 mem_fun() 与 mem_fun_ref() 两个对外接口即可。

template <class S, class T>
inline mem_fun_t<S, T> mem_fun(S (T::*f)()) {
    return mem_fun_t<S, T>(f);
}

template <class S, class T>
inline const_mem_fun_t<S, T> mem_fun(S (T::*f)() const) {
    return const_mem_fun_t<S, T>(f);
}

template <class S, class T>
inline mem_fun_ref_t<S, T> mem_fun_ref(S (T::*f)()) {
    return mem_fun_ref_t<S, T>(f);
}

template <class S, class T>
inline const_mem_fun_ref_t<S, T> mem_fun_ref(S (T::*f)() const) {
    return const_mem_fun_ref_t<S, T>(f);
}

template <class S, class T, class A>
inline mem_fun1_t<S, T, A> mem_fun(S (T::*f)(A)) {
    return mem_fun1_t<S, T, A>(f);
}

template <class S, class T, class A>
inline const_mem_fun1_t<S, T, A> mem_fun(S (T::*f)(A) const) {
    return const_mem_fun1_t<S, T, A>(f);
}

template <class S, class T, class A>
inline mem_fun1_ref_t<S, T, A> mem_fun_ref(S (T::*f)(A)) {
    return mem_fun1_ref_t<S, T, A>(f);
}

template <class S, class T, class A>
inline const_mem_fun1_ref_t<S, T, A> mem_fun_ref(S (T::*f)(A) const) {
    return const_mem_fun1_ref_t<S, T, A>(f);
}

测试

以下简单测试上面提到的几种 adapter 的用法。

void functor_adapter_test()
{
    tinystl::vector<int> v1 = tinystl::vector<int>(10);
    tinystl::iota(v1.begin(), v1.end(), 0);

    // 打印出大于5的元素
    tinystl::copy_if(
        v1.begin(), 
        v1.end(), 
        tinystl::ostream_iterator<int>(std::cout, " "), 
        tinystl::bind2nd(tinystl::greater<int>(), 5)
    );
    std::cout << std::endl;

    // 6 7 8 9 

    // 打印出大于2小于7的元素
    tinystl::copy_if(
        v1.begin(), 
        v1.end(), 
        tinystl::ostream_iterator<int>(std::cout, " "), 
        tinystl::compose2(
            tinystl::logical_and<bool>(),
            tinystl::bind2nd(tinystl::greater<int>(), 2), 
            tinystl::bind2nd(tinystl::less<int>(), 7)
        )
    );
    std::cout << std::endl;

    // 3 4 5 6 

    // 打印出小于等于2或者大于等于7的元素
    tinystl::copy_if(
        v1.begin(), 
        v1.end(), 
        tinystl::ostream_iterator<int>(std::cout, " "), 
        tinystl::not1(
            tinystl::compose2(
                tinystl::logical_and<bool>(),
                tinystl::bind2nd(tinystl::greater<int>(), 2), 
                tinystl::bind2nd(tinystl::less<int>(), 7)
            )
        )
    );
    std::cout << std::endl;

    // 0 1 2 7 8 9 
}

首先是 not、bind、compose 等的测试，可以看到，拥有了配接能力就是可以为所欲为，可以随意配接直到得到我们想要的表达式，再配合 STL 的一些算法，可以很轻松地处理容器中的内容。

bool in2to7(int i)
{
    return i > 2 && i < 7;
}

// 打印出大于2小于7的元素
tinystl::copy_if(
    v1.begin(), 
    v1.end(), 
    tinystl::ostream_iterator<int>(std::cout, " "), 
    tinystl::ptr_fun(in2to7)
);
std::cout << std::endl;

// 3 4 5 6 

// 打印出小于等于2或者大于等于7的元素
tinystl::copy_if(
    v1.begin(), 
    v1.end(), 
    tinystl::ostream_iterator<int>(std::cout, " "), 
    tinystl::not1(tinystl::ptr_fun(in2to7))
);
std::cout << std::endl;

// 0 1 2 7 8 9 

// 打印出小于等于2或者大于等于7的元素
// tinystl::copy_if(
//     v1.begin(), 
//     v1.end(), 
//     tinystl::ostream_iterator<int>(std::cout, " "), 
//     tinystl::not1(in2to7)
// );
// std::cout << std::endl;
// 报错

这部分例子测试了 ptr_fun 的功能，可以将普通的函数也修饰为 STL 的仿函数，从而可以进行配接，如果不用 ptr_fun 进行修饰，是无法融入仿函数大家族的，也就没有配接能力。

class Shape
{
public:
    virtual void draw() {
        std::cout << "draw shape" << std::endl;
    };
};

class Circle : public Shape
{
public:
    void draw() override
    {
        std::cout << "draw circle" << std::endl;
    }
};

class Rectangle : public Shape
{
public:
    void draw() override
    {
        std::cout << "draw rectangle" << std::endl;
    }
};

class Square : public Shape
{
public:
    void draw() override
    {
        std::cout << "draw square" << std::endl;
    }
};

void mem_fun_test()
{
    tinystl::vector<Shape*> v;
    v.push_back(new Circle());
    v.push_back(new Rectangle());
    v.push_back(new Square());

    tinystl::for_each(v.begin(), v.end(), tinystl::mem_fun(&Shape::draw));

    // draw circle
    // draw rectangle
    // draw square

    tinystl::for_each(v.begin(), v.end(), [](Shape *s) { s->draw(); });

    // draw circle
    // draw rectangle
    // draw square

    tinystl::vector<Shape> v1;
    v1.push_back(Circle());
    v1.push_back(Rectangle());
    v1.push_back(Square());

    tinystl::for_each(v1.begin(), v1.end(), tinystl::mem_fun_ref(&Shape::draw));

    // draw shape
    // draw shape
    // draw shape

    tinystl::for_each(v1.begin(), v1.end(), [](Shape &s) { s.draw(); });

    // draw shape
    // draw shape
    // draw shape
}

这部分的例子测试了 mem_fun 与 mem_fun_ref 的功能，可以看出，配合多态的特点，for_each 可以做到在遍历过程中的“多态调用（polymorphic function call）”。当然匿名函数也可以做到这一点，只是与上述的结论一样，不再具有配接能力。mem_fun_ref 的测试也是如此。

比较耐人寻味的是两种 for_each 的输出结果，vector<Shape*> 实现了多态调用，而 vector<Shape> 的测试用调用的仍然是父类的 draw() 函数，原因其实比较简单，就是在 v1.push_back(Circle()); 时已经发生了隐式类型转换，将所有的插入元素都转换为了 Shape 类型，所以调用 s.draw() 才都会是父类的版本。

总结

本节主要分析了 adapter 的最后一部分 functor adapter 的内容，functor adapter 是配接器中最为庞大的一个分支，与此相对的，功能也十分强大，可以配接、配接、再配接，直至创造出我们想要的表达式；在 functor adapter 中，ptr_fun 与 mem_fun 及 mem_fun_ref 是比较独特的两类配接器，它们可以将原本不属于 STL 结构中的对象，纳入到 STL 体系中，十分强大。

至此，adapter 部分的内容也就分析完毕了，这也是 STL 中的最后一部分内容，《STL》源码剖析也已经翻到了第 460 页，收工！

前言

对返回值进行逻辑否定：not1、not2

对参数进行绑定：bind1st、bind2nd

用于函数合成：compose1、compose2

用于函数指针与成员函数指针：ptr_fun、mem_fun、mem_fun_ref

用于函数指针：ptr_fun

用于成员函数指针：mem_fun、mem_fun_ref

测试

总结