C++泛型库

可调用对象

        一些库包含这样一些接口，调用方可以向该类接口传递一些实体，并要求该实体必须被调用。这种编程方式称为回调，调用方传入的实体称为回调函数。

        C++中，可以被用作回调参数的类型如下：

• 函数指针类型
• 仿函数，包括lambda表达式
• 包含一个可以产生函数指针或函数引用的转化函数的class类型

        以上这些类型统称为函数对象类型，其对应的值称为函数对象。

函数对象的支持

        关于上文提到的三种情况，前两种比较好理解，下面便是相关例子：

#include <iostream>
#include <vector>

template <typename Iter, typename Callable>
void foreach(Iter begin, Iter end, Callable callable) {
    for (auto iter = begin; iter != end; ++iter)
        callable(*iter);
}

void func(int i) {
    std::cout << i << std::endl;
}

struct func_obj {
    void operator()(int i) {
        std::cout << i << std::endl;
    }
};

int main(int argc, char **argv)
{
    std::vector<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19 };
    foreach(primes.begin(), primes.end(), func);
    foreach(primes.begin(), primes.end(), &func);
    foreach(primes.begin(), primes.end(), func_obj());
    foreach(primes.begin(), primes.end(), [](int i)->void {std::cout << i << std::endl;});
    return 0;
}

        前两种情况能够说明平时遇到的一些问题，但有时，遇到的情况会复杂一些：

• 调用方已有的函数参数与接口要求的回调参数不一致
• 调用方已有的函数是一个非静态类成员函数，而接口仅允许传入一个函数，不允许传入对象

        上述则是一开始所提到的第三种情况。遇到这种情况，只能对已有的函数进行封装，然后再把封装后的函数或类传给接口，这便是函数转换。下面便是函数转换的一个例子：

#include <iostream>
#include <vector>

template <typename Iter, typename Callable>
void foreach(Iter begin, Iter end, Callable callable) {
    for (auto iter = begin; iter != end; ++iter)
        callable(*iter);
}

void add(int &x, int i) {
    x += i;
}

typedef void (*add_fp)(int &, int);
class add_wrapper
{
public:
    add_wrapper(add_fp fp, int i) : m_fp(fp), m_i(i) {}
    void operator()(int &x) {
        m_fp(x, m_i);
    }
    
private:
    add_fp m_fp;
    int m_i;
};

int main(int argc, char **argv)
{
    std::vector<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19 };
    foreach(primes.begin(), primes.end(), [](int i)->void {std::cout << i << std::endl;});
    foreach(primes.begin(), primes.end(), add_wrapper(add, 100));
    foreach(primes.begin(), primes.end(), [](int i)->void {std::cout << i << std::endl;});
    
    return 0;
}

        看到上面这个例子，很容易联想到std::function，其实上面就是一个乞丐版的std::function实现。当然，直接使用std::function可以更简单地解决问题，如下：

#include <iostream>
#include <vector>

template <typename Iter, typename Callable>
void foreach(Iter begin, Iter end, Callable callable) {
    for (auto iter = begin; iter != end; ++iter)
        callable(*iter);
}

void add(int &x, int i) {
    x += i;
}

class add_class
{
public:
    void add(int &x, int i) {
        x += i;
    }
};

int main(int argc, char **argv)
{
    std::vector<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19 };
    foreach(primes.begin(), primes.end(), [](int i)->void {std::cout << i << std::endl;});
    
    std::function<void(int &)> add1 = std::bind(add, std::placeholders::_1, 100);
    foreach(primes.begin(), primes.end(), add1);
    foreach(primes.begin(), primes.end(), [](int i)->void {std::cout << i << std::endl;});
    
    add_class add_obj;
    std::function<void(int &)> add2 = std::bind(&add_class::add, add_obj, std::placeholders::_1, 100);
    foreach(primes.begin(), primes.end(), add2);
    foreach(primes.begin(), primes.end(), [](int i)->void {std::cout << i << std::endl;});
    
    return 0;
}

        那么问题来了，为什么需要类似std::function的解决方案呢？大体原因如下：

• 由于种种原因，不方便修改foreach和add源码，例如二者都是第三方库
• std::function方案比直接用函数对add进行封装扩展性强，用函数对add封装方案如下，但如果要在原来的数值上加200呢？如果要换成乘法呢?为此需要一遍又一遍地写实现封装函数。

//...
int add_100(int &x) {
    x += 100;
}
//...
foreach(primes.begin(), primes.end(), add_100);
//...

• 比直接使用函数指针更加安全 

 处理成员函数以及额外的参数

        除了前面提到std::function，C++17引入的std::invoke也能起到函数转换的作用，如下：

#include <iostream>
#include <vector>
#include <utility>
#include <functional>

template <typename Iter, typename Callable, typename ...Types>
void foreach(Iter begin, Iter end, Callable callable, Types &...args) {
    for (auto iter = begin; iter != end; ++iter)
        std::invoke(callable, args..., *iter);
}

class callable {
public:
    void print(int i) { std::cout << i << std::endl; }
};

void myprint(int i) { std::cout << i << std::endl; }

class myprint_cls {
public:
    void operator()(int i) { std::cout << i << std::endl; }
};

int main(int argc, char **argv)
{
    std::vector<int> primes = { 2, 3, 5, 7, 11, 13, 17, 19 };
    callable c;
    foreach(primes.begin(), primes.end(), &callable::print, c);
    callable *pc = &c;
    foreach(primes.begin(), primes.end(), &callable::print, pc);
    foreach(primes.begin(), primes.end(), [&](int i)->void { std::cout << i << std::endl; });
    foreach(primes.begin(), primes.end(), myprint);
    foreach(primes.begin(), primes.end(), myprint_cls());
    
    return 0;
}

        在处理回调函数方面，尽管std::invoke有函数转换的作用，统一了全局函数，成员函数，仿函数，以及lambda表达式的调用方式。但与std::function相比，参数位置的处理却没那么灵活。

其他一些实现泛型库的工具

std::addressof

        如果一个类重载了&操作符，就无法通过&获取其对象实例的地址，如下：

#include <memory>
#include <iostream>

class test {
public:
    test *operator&() { return nullptr; }
};

int main(int argc, char **argv) {

    test *ptr = new test();
    std::cout << ptr << std::endl;
    std::cout << &(*ptr) << std::endl;
    
    return 0;
}

         使用std::addressof取代&操作符，就可以解决该问题，如下：

std::cout << std::addressof(*ptr) << std::endl;

        std::declval

        

        函数模板 std::declval()可以被用作某一类型的对象的引用的占位符。该函数模板没有定义， 因此不能被调用(也不会创建对象)。因此它只能被用作不会被计算的操作数(比如 decltype 和 sizeof)。也因此，在不创建对象的情况下，依然可以假设有相应类型的可用对象。        

        比如在如下例子中，会基于模板参数 T1 和 T2 推断出返回类型 RT:

#include <utility>
template<typename T1, typename T2,
typename RT = std::decay_t<decltype(true ? std::declval<T1>() : std::declval<T2>())>>

RT max (T1 a, T2 b) {
    return b < a ? a : b;
}

        为了避免在调用运算符?:的时候不得不去调用 T1 和 T2 的(默认)构造函数，这里使用了

std::declval，这样可以在不创建对象的情况下“使用”它们。不过该方式只能在不会做真正 的计算时(比如 decltype)使用。

 

完美转发临时变量

#include <string>
#include <iostream>

class tracer {
public:
    tracer(void) { std::cout << "tracer::tracer(void)" << std::endl; }
    tracer(const tracer &) { std::cout << "tracer::tracer(const tracer &)" << std::endl; }
    tracer(tracer &&) { std::cout << "tracer::tracer(tracer &&)" << std::endl; }
    tracer &operator=(const tracer &) {
        std::cout << "tracer::operator=(const tracer &)" << std::endl;
        return *this;
    }
    tracer &operator=(tracer &&) {
        std::cout << "tracer::operator=(tracer &&)" << std::endl;
        return *this;
    }
};

template <typename T>
T get(T x) {
    std::cout << "get" << std::endl;
    return x;
}

template <typename T>
void set(T x) {
    std::cout << "set" << std::endl;
}

template <typename T>
void foo(T x) {
    std::cout << "foo" << std::endl;
    //set(get(x));
    T &&tmp = get(x);
    //...
    set(tmp);
}

int main(int argc, char **argv) {
    tracer tr;
    foo(tr);
    return 0;
}

        对于上述代码，foo函数如果直接使用set(get(x));，get的返回值以右值引用传给set。但为了进行其他处理，使用tmp变量对get返回值进行保存，尽管tmp是一个右值引用，但调用set(tmp);时，tmp被已左值引用的方式传递。解决方案如下：

//...
template <typename T>
void foo(T x) {
    std::cout << "foo" << std::endl;
    T &&tmp = get(x);
    //...
    //set(std::move(tmp));
    set(std::forward<decltype(tmp)>(tmp));
}

//...

        当然此处也可以使用std::move（std::move与std::forward区别有待研究）。 

作为模板参数的引用

         如果函数模板的形参传递的不是引用，即使传递一个引用变量作为实参，其模板类型也不会被推断为引用，如下：

#include <iostream>
#include <string>

template <typename T>
void is_ref(T x) {
    std::cout << std::is_reference<T>::value << std::endl;
}

int main(int argc, char **argv) {
    std::string str0 = "hello";
    std::string &str1 = str0;
    is_ref(str0); //0
    is_ref(str1); //0
    is_ref<std::string &>(str0); //1
    is_ref<std::string &>(str1); //1
    
    return 0;
}

        尽管显示指定T的实例化类型为引用，但这不是模板设计的最初目的，因此，这种方案可能引发编译错误，如下：

template <typename T, T Z = T{}>
class ref_mem {
public:
    ref_mem(void) : m_zero(Z) {}
private:
    T m_zero;
};

int null = 0;
int main(int argc, char **argv) {
    ref_mem<int> rm1, rm2;
    rm1 = rm2;
    
    ref_mem<int &> rm3; //non-const lvalue reference to type 'int' cannot bind to an initializer list temporary
                        //in instantiation of default argument for 'ref_mem<int &>' required here
    ref_mem<int &, 0> rm4; //value of type 'int' is not implicitly convertible to 'int &'
    rm3 = rm4;

    ref_mem<int &, null> rm5, rm6;
    rm5 = rm6; //object of type 'ref_mem<int &, null>' cannot be assigned because its copy assignment operator is implicitly deleted
                // copy assignment operator of 'ref_mem<int &, null>' is implicitly deleted because field 'm_zero' is of reference type 'int &'
    
    return 0;
}

        引用类型用于非模板类型参数同样会变的复杂和危险，如下：

#include <vector>
#include <iostream>

template <typename T, int &SZ>
class arr {
public:
    arr(void) : m_elem(SZ) {}
    
    void print(void) {
        for (int i = 0; i < SZ; ++i)
            std::cout << m_elem[i] << ' ';
    }
private:
    std::vector<T> m_elem;
};

int size = 10;
int main(int argc, char **argv) {
    arry<int &, size> y; //编译错误太多，眼花缭乱
    arr<int, size> x; 
    x.print();
    size += 100;
    x.print(); //内存越界，行为未定义
    
    return 0;
}

延迟计算

        在实现模板的时候，有时可能需要考虑不完全类型的情形。什么是不完全类型？下面是一段相关的解释：

‌‌不完全类型‌是指那些在函数之外、类型的大小不能被确定的类型。这种类型可能无法实例化，也不能访问其成员，但可以使用派生的指针类型。不完全类型包括未指定长度的数组、未完全定义的‌结构体或‌联合体，以及void类型。‌

        上述几种非完全类型，数结构体的情况最为复杂，下面是一个结构体相关的不完全类型例子：

#include <stdio.h>

struct Node;

struct List {
    Node head;
};

struct Node {
	int id;
	Node next;
};

int main(int argc, char **argv)
{
	Node n;
	return 0;
}

        关于上面的例子：List定义使用Node时，Node仅仅进行了声明，未进行定义；Node定义中使用Node时，Node未完成定义。这两种情况中Node都属于属于不完全类型，因此，无法实例化，编译报错：

incomplete.cpp:6:10: error: field has incomplete type 'Node'
    Node head;
         ^
incomplete.cpp:3:8: note: forward declaration of 'Node'
struct Node;
       ^
incomplete.cpp:11:7: error: field has incomplete type 'Node'
        Node next;
             ^
incomplete.cpp:9:8: note: definition of 'Node' is not complete until the closing '}'
struct Node {

        可以使用Node指针取代Node来解决问题。接下来，看下非完全类型在模板中的影响。 

#include <string>
#include <iostream>
#include <type_traits>

template <typename T>
class Ptr final {
public:
    Ptr() : m_ptr(new T()) {}
    
    T && foo(void) {
        return *m_ptr;
    }
private:
    T *m_ptr;
};

struct Node {
    std::string name;
    Ptr<Node> next;
};

int main(int argc, char **argv)
{
    Node node;
    return 0;
}

        在上面的例子中，尽管在Node定义next，Node属于不完全类型，上面的源码仍然可以通过编译，因为Ptr中使用的是指针（直接使用Node无法通过编译）。现在，对Ptr::foo做下修改，要求如果类型支持移动语义，返回移动对象，否则返回引用对象，新的源码如下：

...    
    typename std::conditional<std::is_move_constructible<T>::value, T &&, T &> foo(void) {
        return *m_ptr;
    }
...

       然而源码无法通过编译，报错如下：

/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include/c++/v1/__type_traits/is_move_constructible.h:24:38: error: incomplete type 'Node' used in type trait expression
    : public integral_constant<bool, __is_constructible(_Tp, __add_rvalue_reference_t<_Tp>)>
                                     ^
DeferEvaluation.cpp:12:36: note: in instantiation of template class 'std::is_move_constructible<Node>' requested here
    typename std::conditional<std::is_move_constructible<T>::value, T &&, T &> foo(void) {
                                   ^
DeferEvaluation.cpp:22:15: note: in instantiation of template class 'Ptr<Node>' requested here
    Ptr<Node> next;
              ^
DeferEvaluation.cpp:20:8: note: definition of 'Node' is not complete until the closing '}'
struct Node {
       ^

        之所以报错，是因为std::is_move_constructible 要求其参数必须是完全类型。而在使用 Ptr<Node>定义next时，Node属于非完全类型。解决方法是引入一个新的模板参数D，把T作为D的默认参数，新的源码如下：

...
template <typename D = T>
typename std::conditional<std::is_move_constructible<D>::value, D &&, D &> foo(void) {
    return *m_ptr;
}
...

        这样，成员函数foo在实例化后仍然是一个函数模板，不再依赖模板实参Node。再次调用成员函数foo时，foo再次被实例化。但此时即便使用Node作为模板实参也可以正常编译，因为这个实例化过程在Node定义的外部，Node属于完全类型。