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将a 存储为基本类型。对于与一起使用的每个不同的函子，将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对象内部。

在一般情况下（包括lambda情况），std::function允许使用动态内存（通过标准分配器或传递给构造函数的分配器）以实现适当的实现。该标准建议，如果可以避免的话，请勿使用动态内存，但是正如您正确地说的那样，如果函数对象（不是std::function对象，而是包裹在其中的对象）足够大，则无法阻止它，因为std::function尺寸固定

普通构造函数和复制构造函数均具有这种引发异常的权限，它们也明确地允许在复制期间进行动态内存分配。对于移动，没有理由需要动态内存。该标准似乎没有明确禁止它，并且如果移动可能调用包装对象的类型的move构造函数，则可能不会，但是您应该能够假设，如果实现和您的对象都是明智的，则移动不会导致任何分配。

Answer 3

因为类型擦除还包括如何复制类型（在该答案中，函数对象将不可复制构造）。这些行为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混合成一个函数指针（以告诉做什么额外的参数），以节省一些字节

原始指针用于将functor对象与函数指针一起存储在中union，因此，当function从函数指针构造对象时，它将直接存储在union而不是堆空间中

也许STL的实施不是最好的解决方案，因为我听说一些更快的实施。但是，我相信基本机制是相同的。