Как реализован std :: function?

Согласно источникам, которые я нашел, лямбда-выражение по существу реализуется компилятором, создающим класс с перегруженным оператором вызова функции и ссылочными переменными в качестве членов. Это говорит о том, что размер лямбда-выражений варьируется, и при наличии достаточного количества ссылочных переменных размер может быть сколь угодно большим .

Объект std::functionдолжен иметь фиксированный размер , но он должен иметь возможность обертывать любые вызываемые объекты, включая любые лямбды того же типа. Как это реализовано? Если std::functionвнутренне использует указатель на свою цель, что происходит, когда std::functionэкземпляр копируется или перемещается? Есть ли какие-либо выделения в куче?

Реализация 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.

Ответ от @David Rodríguez - dribeas хорош для демонстрации стирания типа, но недостаточно хорош, поскольку стирание типа также включает в себя то, как типы копируются (в этом ответе объект функции не будет копируемым). Эти поведения также сохраняются в functionобъекте, помимо данных функтора.

Уловка, используемая в реализации STL из Ubuntu 14.04 gcc 4.8, заключается в том, чтобы написать одну общую функцию, специализовать ее для каждого возможного типа функтора и привести их к универсальному типу указателя функции. Поэтому информация о типе стирается .

Я придумал упрощенную версию этого. Надеюсь, это поможет

#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 - не лучшее решение, поскольку я слышал о более быстрой реализации . Однако я считаю, что основной механизм такой же.

Для определенных типов аргументов («если целью f является вызываемый объект, переданный через reference_wrapperили указатель на функцию»), std::functionконструктор запрещает любые исключения, поэтому использование динамической памяти не может быть и речи. В этом случае все данные должны храниться непосредственно внутри std::functionобъекта.

В общем случае (включая случай лямбда) использование динамической памяти (либо через стандартный распределитель, либо через распределитель, переданный std::functionконструктору) разрешено, если реализация считает нужным. Стандарт рекомендует реализации не использовать динамическую память, если этого можно избежать, но, как вы правильно сказали, если объект функции (не std::functionобъект, а объект, заключенный в него) достаточно велик, нет способа предотвратить это, поскольку std::functionимеет фиксированный размер.

Это разрешение на создание исключений предоставляется как обычному конструктору, так и конструктору копирования, который также явно позволяет выделять динамическую память во время копирования. Для ходов нет причин, по которым может понадобиться динамическая память. Стандарт явно не запрещает это и, вероятно, не может, если перемещение может вызывать конструктор перемещения типа обернутого объекта, но вы должны иметь возможность предположить, что если и реализация, и ваши объекты разумны, перемещение не вызовет любые выделения.

An std::functionперегружает, operator()превращая его в объект-функтор, лямбда работает точно так же. Он в основном создает структуру с переменными-членами, к которым можно получить доступ внутри operator()функции. Итак, основная концепция, которую следует иметь в виду, заключается в том, что лямбда - это объект (называемый функтором или объектом функции), а не функцией. Стандарт запрещает использовать динамическую память, если этого можно избежать.