Jak zaimplementowano std :: function?

Według źródeł, które znalazłem, wyrażenie lambda jest zasadniczo implementowane przez kompilator, tworząc klasę z przeciążonym operatorem wywołania funkcji i zmiennymi, do których się odwołujemy jako składowymi. Sugeruje to, że rozmiar wyrażeń lambda jest różny, a przy wystarczającej liczbie zmiennych odwołań, rozmiar może być dowolnie duży .

std::functionPowinien mieć stały rozmiar , ale to musi być w stanie owinąć każdy rodzaj callables, w tym wszelkie lambdas tego samego rodzaju. Jak to jest realizowane? Jeśli std::functionwewnętrznie używa wskaźnika do celu, to co się dzieje, gdy std::functioninstancja jest kopiowana lub przenoszona? Czy są zaangażowane jakieś alokacje sterty?

Implementacja std::functionmoże się różnić w zależności od implementacji, ale główną ideą jest to, że używa wymazywania typów. Chociaż można to zrobić na wiele sposobów, możesz sobie wyobrazić, że trywialne (nieoptymalne) rozwiązanie mogłoby wyglądać następująco (uproszczone dla konkretnego przypadku lub std::function<int (double)>dla uproszczenia):

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

W tym prostym podejściu functionobiekt przechowuje tylko a unique_ptrdo typu podstawowego. Dla każdego innego funktora używanego z the function, tworzony jest nowy typ wyprowadzony z bazy i dynamicznie tworzony jest obiekt tego typu. std::functionObiekt jest zawsze tej samej wielkości i przydzieli miejsca, ile potrzeba dla różnych funktorów w stercie.

W rzeczywistości istnieją różne optymalizacje, które zapewniają większą wydajność, ale komplikują odpowiedź. Typ może wykorzystywać małe optymalizacje obiektów, dynamiczne wysyłanie można zastąpić wskaźnikiem swobodnej funkcji, który pobiera funktor jako argument, aby uniknąć jednego poziomu pośrednictwa ... ale idea jest zasadniczo taka sama.

Jeśli chodzi o to, jak std::functionzachowują się kopie , szybki test wskazuje, że kopie wewnętrznego wywoływalnego obiektu są wykonywane, a nie udostępnianie stanu.

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

Test wskazuje, że f2zamiast referencji pobierana jest kopia wywoływalnej jednostki. Jeśli wywoływalna jednostka std::function<>byłaby współdzielona przez różne obiekty, wynik programu wynosiłby 5, 6, 7.

Odpowiedź od @David Rodríguez - dribeas jest dobra do demonstrowania usuwania typów, ale nie jest wystarczająco dobra, ponieważ wymazywanie typów obejmuje również sposób kopiowania typów (w tej odpowiedzi obiekt funkcji nie będzie konstruowany przez kopiowanie). Te zachowania są również przechowywane w functionobiekcie, oprócz danych funktora.

Sztuczka zastosowana w implementacji STL z Ubuntu 14.04 gcc 4.8 polega na napisaniu jednej funkcji ogólnej, wyspecjalizowaniu jej w każdym możliwym typie funktora i rzutowaniu jej na uniwersalny typ wskaźnika funkcji. Dlatego informacje o typie są usuwane .

Przygotowałem uproszczoną wersję tego. Mam nadzieję, że to pomoże

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

W wersji STL są również pewne optymalizacje

• construct_fi destroy_fmiesza się w jeden wskaźnik funkcji (z dodatkowym parametrem, który mówi, co robić), aby zaoszczędzić kilka bajtów
• surowe wskaźniki są używane do przechowywania obiektu funktora, wraz ze wskaźnikiem funkcji w a union, więc gdy functionobiekt jest konstruowany ze wskaźnika funkcji, będzie przechowywany bezpośrednio w przestrzeni unionzamiast sterty

Może implementacja STL nie jest najlepszym rozwiązaniem, ponieważ słyszałem o szybszej implementacji . Uważam jednak, że podstawowy mechanizm jest taki sam.

W przypadku niektórych typów argumentów („jeśli celem f jest wywoływalny obiekt przekazany przez reference_wrapperlub wskaźnik funkcji”), std::functionkonstruktor nie zezwala na żadne wyjątki, więc użycie pamięci dynamicznej nie wchodzi w grę. W tym przypadku wszystkie dane muszą być przechowywane bezpośrednio w std::functionobiekcie.

W ogólnym przypadku (w tym przypadku lambda), użycie pamięci dynamicznej (za pośrednictwem standardowego alokatora lub alokatora przekazanego do std::functionkonstruktora) jest dozwolone zgodnie z wymaganiami implementacji. Standard zaleca implementacje, aby nie używać pamięci dynamicznej, jeśli można tego uniknąć, ale jak słusznie mówisz, jeśli obiekt funkcji (nie std::functionobiekt, ale obiekt w nim zawijany) jest wystarczająco duży, nie ma sposobu, aby temu zapobiec, ponieważ std::functionma stały rozmiar.

To uprawnienie do zgłaszania wyjątków jest udzielane zarówno konstruktorowi zwykłemu, jak i konstruktorowi kopiującemu, który dość jawnie zezwala również na dynamiczne alokacje pamięci podczas kopiowania. W przypadku ruchów nie ma powodu, dla którego pamięć dynamiczna byłaby konieczna. Wydaje się, że standard nie zabrania tego wprost i prawdopodobnie nie może tego zabronić, jeśli move może wywołać konstruktor przenoszenia typu opakowanego obiektu, ale powinieneś być w stanie założyć, że jeśli zarówno implementacja, jak i twoje obiekty są rozsądne, przeniesienie nie spowoduje wszelkie przydziały.

An std::functionprzeciąża operator()czyni go obiektu funktora, praca lambda w ten sam sposób. Zasadniczo tworzy strukturę ze zmiennymi składowymi, do których można uzyskać dostęp wewnątrz operator()funkcji. Zatem podstawową koncepcją, o której należy pamiętać, jest to, że lambda jest obiektem (nazywanym funktorem lub obiektem funkcji), a nie funkcją. Norma mówi, aby nie używać pamięci dynamicznej, jeśli można tego uniknąć.