如何实现std :: function？

Question

根据我发现的源代码,lambda表达式基本上是由编译器创建一个带有重载函数调用运算符的类和引用变量作为成员的类实现的.这表明lambda表达式的大小是变化的,并且给定足够的引用变量,其大小可以是任意大的.

一个std::function应该有一个固定的大小,但一定要能包住任何可调用的,包括相同种类的任何lambda表达式.它是如何实现的？如果std::function内部使用指向其目标的指针,那么在std::function复制或移动实例时会发生什么？是否涉及堆分配？

Answer 1

实现std::function可能因实现而异,但核心思想是使用类型擦除.虽然有多种方法可以实现,但您可以想象一个简单(非最佳)的解决方案可能是这样的(std::function<int (double)>为了简单起见,针对具体情况进行了简化):

struct callable_base {
   virtual int operator()(double d) = 0;
   virtual ~callable_base() {}
};
template <typename F>
struct callable : callable_base {
   F functor;
   callable(F functor) : functor(functor) {}
   virtual int operator()(double d) { return functor(d); }
};
class function_int_double {
   std::unique_ptr<callable_base> c;
public:
   template <typename F>
   function(F f) {
      c.reset(new callable<F>(f));
   }
   int operator()(double d) { return c(d); }
// ...
};

在这种简单的方法中,function对象只存储unique_ptr一个基本类型.对于与其一起使用的每个不同的函子function,创建从基础派生的新类型,并且动态地实例化该类型的对象.的std::function对象始终是相同大小的,并根据需要在堆的不同函子将分配空间.

在现实生活中,有不同的优化可以提供性能优势,但会使答案复杂化.该类型可以使用小对象优化,动态分派可以由自由函数指针替换,该指针将函子作为参数来避免一个级别的间接......但是这个想法基本相同.

关于std::function行为副本的问题,快速测试表明内部可调用对象的副本已完成,而不是共享状态.

// g++4.8
int main() {
   int value = 5;
   typedef std::function<void()> fun;
   fun f1 = [=]() mutable { std::cout << value++ << '\n' };
   fun f2 = f1;
   f1();                    // prints 5
   fun f3 = f1;
   f2();                    // prints 5
   f3();                    // prints 6 (copy after first increment)
}

测试表明f2获取可调用实体的副本,而不是引用.如果可调用实体由不同std::function<>对象共享,则程序的输出将为5,6,7.

Answer 2

对于某些类型的自变量("如果f的目标是经由通过一个可调用对象reference_wrapper或一个函数指针"),std::function的构造不允许任何异常,因此使用动态存储器是不可能的.对于这种情况,所有数据必须直接存储在std::function对象内.

在一般情况下,(包括拉姆达情况下),使用动态存储器(通过任一标准分配器,或传递给一个分配器std::function的构造函数)作为实现认为合适是允许的.如果可以避免,标准建议实现不使用动态内存,但正如你正确地说,如果函数对象(不是std::function对象,而是包含在其中的对象)足够大,则无法阻止它,因为std::function有一个固定的大小.

抛出异常的权限被授予普通构造函数和复制构造函数,它们在复制期间也明确允许动态内存分配.对于移动,没有理由需要动态内存.标准似乎没有明确地禁止它,如果移动可能会调用包装对象的类型的移动构造函数,则可能不能,但是你应该能够假设如果实现和你的对象都是合理的,移动不会导致任何分配.

Answer 3

@DavidRodríguez的答案 - dribeas有助于演示类型擦除但不够好,因为类型擦除还包括如何复制类型(在该答案中,函数对象将不是可复制构造的).function除了仿函数数据之外,这些行为也存储在对象中.

在Ubuntu 14.04 gcc 4.8的STL实现中使用的技巧是编写一个泛型函数,使用每种可能的函子类型对其进行特化,并将它们转换为通用函数指针类型.因此,类型信息被删除.

我已经拼凑了一个简化版本.希望它会有所帮助

#include <iostream>
#include <memory>

template <typename T>
class function;

template <typename R, typename... Args>
class function<R(Args...)>
{
    // function pointer types for the type-erasure behaviors
    // all these char* parameters are actually casted from some functor type
    typedef R (*invoke_fn_t)(char*, Args&&...);
    typedef void (*construct_fn_t)(char*, char*);
    typedef void (*destroy_fn_t)(char*);

    // type-aware generic functions for invoking
    // the specialization of these functions won't be capable with
    //   the above function pointer types, so we need some cast
    template <typename Functor>
    static R invoke_fn(Functor* fn, Args&&... args)
    {
        return (*fn)(std::forward<Args>(args)...);
    }

    template <typename Functor>
    static void construct_fn(Functor* construct_dst, Functor* construct_src)
    {
        // the functor type must be copy-constructible
        new (construct_dst) Functor(*construct_src);
    }

    template <typename Functor>
    static void destroy_fn(Functor* f)
    {
        f->~Functor();
    }

    // these pointers are storing behaviors
    invoke_fn_t invoke_f;
    construct_fn_t construct_f;
    destroy_fn_t destroy_f;

    // erase the type of any functor and store it into a char*
    // so the storage size should be obtained as well
    std::unique_ptr<char[]> data_ptr;
    size_t data_size;
public:
    function()
        : invoke_f(nullptr)
        , construct_f(nullptr)
        , destroy_f(nullptr)
        , data_ptr(nullptr)
        , data_size(0)
    {}

    // construct from any functor type
    template <typename Functor>
    function(Functor f)
        // specialize functions and erase their type info by casting
        : invoke_f(reinterpret_cast<invoke_fn_t>(invoke_fn<Functor>))
        , construct_f(reinterpret_cast<construct_fn_t>(construct_fn<Functor>))
        , destroy_f(reinterpret_cast<destroy_fn_t>(destroy_fn<Functor>))
        , data_ptr(new char[sizeof(Functor)])
        , data_size(sizeof(Functor))
    {
        // copy the functor to internal storage
        this->construct_f(this->data_ptr.get(), reinterpret_cast<char*>(&f));
    }

    // copy constructor
    function(function const& rhs)
        : invoke_f(rhs.invoke_f)
        , construct_f(rhs.construct_f)
        , destroy_f(rhs.destroy_f)
        , data_size(rhs.data_size)
    {
        if (this->invoke_f) {
            // when the source is not a null function, copy its internal functor
            this->data_ptr.reset(new char[this->data_size]);
            this->construct_f(this->data_ptr.get(), rhs.data_ptr.get());
        }
    }

    ~function()
    {
        if (data_ptr != nullptr) {
            this->destroy_f(this->data_ptr.get());
        }
    }

    // other constructors, from nullptr, from function pointers

    R operator()(Args&&... args)
    {
        return this->invoke_f(this->data_ptr.get(), std::forward<Args>(args)...);
    }
};

// examples
int main()
{
    int i = 0;
    auto fn = [i](std::string const& s) mutable
    {
        std::cout << ++i << ". " << s << std::endl;
    };
    fn("first");                                   // 1. first
    fn("second");                                  // 2. second

    // construct from lambda
    ::function<void(std::string const&)> f(fn);
    f("third");                                    // 3. third

    // copy from another function
    ::function<void(std::string const&)> g(f);
    f("forth - f");                                // 4. forth - f
    g("forth - g");                                // 4. forth - g

    // capture and copy non-trivial types like std::string
    std::string x("xxxx");
    ::function<void()> h([x]() { std::cout << x << std::endl; });
    h();

    ::function<void()> k(h);
    k();
    return 0;
}

STL版本中也有一些优化

• 在construct_f和destroy_f混合成一个函数指针(以告诉做什么额外的参数),以节省一些字节
• 原始指针用于存储仿函数对象,以及a中的函数指针union,这样当function从函数指针构造对象时,它将直接存储在union而不是堆空间中

也许STL实现不是最好的解决方案,因为我听说过一些更快的实现.但是我相信潜在的机制是一样的.