Como std :: function é implementado?

De acordo com as fontes que encontrei, uma expressão lambda é essencialmente implementada pelo compilador, criando uma classe com o operador de chamada de função sobrecarregado e as variáveis ​​referenciadas como membros. Isso sugere que o tamanho das expressões lambda varia e, dadas variáveis ​​de referências suficientes, esse tamanho pode ser arbitrariamente grande .

Um std::functiondeve ter um tamanho fixo , mas deve ser capaz de encapsular qualquer tipo de callables, incluindo quaisquer lambdas do mesmo tipo. Como isso é implementado? Se std::functionusar internamente um ponteiro para seu destino, o que acontecerá quando a std::functioninstância for copiada ou movida? Há alguma alocação de heap envolvida?

A implementação de std::functionpode ser diferente de uma implementação para outra, mas a ideia central é que ele usa apagamento de tipo. Embora existam várias maneiras de fazer isso, você pode imaginar uma solução trivial (não ideal) como esta (simplificada para o caso específico de std::function<int (double)>por uma questão de simplicidade):

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); }
// ...
};

Nesta abordagem simples, o functionobjeto armazenaria apenas um unique_ptrem um tipo base. Para cada functor diferente usado com o function, um novo tipo derivado da base é criado e um objeto desse tipo instanciado dinamicamente. O std::functionobjeto é sempre do mesmo tamanho e alocará espaço conforme necessário para os diferentes functores no heap.

Na vida real, existem diferentes otimizações que fornecem vantagens de desempenho, mas complicariam a resposta. O tipo pode usar otimizações de pequenos objetos, o despacho dinâmico pode ser substituído por um ponteiro de função livre que leva o functor como argumento para evitar um nível de indireção ... mas a ideia é basicamente a mesma.

Em relação à questão de como as cópias do std::functionse comportam, um teste rápido indica que as cópias do objeto chamável interno são feitas, em vez de compartilhar o estado.

// 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)
}

O teste indica que f2obtém uma cópia da entidade que pode ser chamada, em vez de uma referência. Se a entidade chamável fosse compartilhada por std::function<>objetos diferentes , a saída do programa teria sido 5, 6, 7.

A resposta de @David Rodríguez - dribeas é bom para demonstrar o apagamento de tipo, mas não o suficiente, já que o apagamento de tipo também inclui como os tipos são copiados (nessa resposta o objeto de função não pode ser copiado). Esses comportamentos também são armazenados no functionobjeto, além dos dados do functor.

O truque, usado na implementação STL do Ubuntu 14.04 gcc 4.8, é escrever uma função genérica, especializá-la com cada tipo de função possível e convertê-los em um tipo de ponteiro de função universal. Portanto, as informações de tipo são apagadas .

Eu criei uma versão simplificada disso. Espero que ajude

#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;
}

Existem também algumas otimizações na versão STL

• os construct_fe destroy_fsão misturados em um ponteiro de função (com um parâmetro adicional que diz o que fazer) para salvar alguns bytes
• ponteiros brutos são usados ​​para armazenar o objeto functor, junto com um ponteiro de função em a union, de modo que quando um functionobjeto é construído a partir de um ponteiro de função, ele será armazenado diretamente no unionespaço ao invés de heap

Talvez a implementação de STL não seja a melhor solução, já que ouvi falar de algumas implementações mais rápidas . No entanto, acredito que o mecanismo subjacente é o mesmo.

Para certos tipos de argumentos ("se o alvo de f é um objeto que pode ser chamado passado por reference_wrapperou um ponteiro de função"), std::functiono construtor de não permite quaisquer exceções, portanto, usar memória dinâmica está fora de questão. Para este caso, todos os dados devem ser armazenados diretamente dentro do std::functionobjeto.

No caso geral, (incluindo o caso lambda), o uso de memória dinâmica (por meio do alocador padrão ou de um alocador passado para o std::functionconstrutor) é permitido conforme a implementação considerar adequada. O padrão recomenda que as implementações não usem memória dinâmica se puder ser evitado, mas como você diz com razão, se o objeto de função (não o std::functionobjeto, mas o objeto sendo envolvido nele) for grande o suficiente, não há como evitá-lo, pois std::functiontem um tamanho fixo.

Essa permissão para lançar exceções é concedida ao construtor normal e ao construtor de cópia, o que também permite alocações de memória dinâmica durante a cópia de forma bastante explícita. Para movimentos, não há razão para que a memória dinâmica seja necessária. O padrão não parece proibi-lo explicitamente, e provavelmente não pode se o movimento pode chamar o construtor de movimento do tipo do objeto empacotado, mas você deve ser capaz de assumir que, se a implementação e seus objetos forem sensíveis, o movimento não causará quaisquer alocações.

Um std::functionsobrecarrega o operator()tornando um objeto functor, o lambda funciona da mesma maneira. Basicamente, ele cria uma estrutura com variáveis ​​de membro que podem ser acessadas dentro da operator()função. Portanto, o conceito básico a ter em mente é que lambda é um objeto (chamado de functor ou objeto de função), não uma função. O padrão diz para não usar memória dinâmica se puder ser evitada.