How is std::function implemented?

Question

According to the sources I have found, a lambda expression is essentially implemented by the compiler creating a class with overloaded function call operator and the referenced variables as members. This suggests that the size of lambda expressions varies, and given enough references variables that size can be arbitrarily large.

An std::function should have a fixed size, but it must be able to wrap any kind of callables, including any lambdas of the same kind. How is it implemented? If std::function internally uses a pointer to its target, then what happens, when the std::function instance is copied or moved? Are there any heap allocations involved?

Answer 1

The implementation of std::function can differ from one implementation to another, but the core idea is that it uses type-erasure. While there are multiple ways of doing it, you can imagine a trivial (not optimal) solution could be like this (simplified for the specific case of std::function<int (double)> for the sake of simplicity):

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

In this simple approach the function object would store just a unique_ptr to a base type. For each different functor used with the function, a new type derived from the base is created and an object of that type instantiated dynamically. The std::function object is always of the same size and will allocate space as needed for the different functors in the heap.

In real life there are different optimizations that provide performance advantages but would complicate the answer. The type could use small object optimizations, the dynamic dispatch can be replaced by a free-function pointer that takes the functor as argument to avoid one level of indirection... but the idea is basically the same.

---

Regarding the issue of how copies of the std::function behave, a quick test indicates that copies of the internal callable object are done, rather than sharing the state.

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

The test indicates that f2 gets a copy of the callable entity, rather than a reference. If the callable entity was shared by the different std::function<> objects, the output of the program would have been 5, 6, 7.

Answer 2

An std::function overloads the operator() making it a functor object, lambda's work the same way. It basically creates a struct with member variables that can be accessed inside the operator() function. So the basic concept to keep in mind is that a lambda is an object (called a functor or function object) not a function. The standard says not to use dynamic memory if it can be avoided.

Answer 3

For certain types of arguments ("if f's target is a callable object passed via reference_wrapper or a function pointer"), std::function's constructor disallows any exceptions, so using dynamic memory is out of the question. For this case, all the data must be stored directly inside the std::function object.

In the general case, (including the lambda case), using dynamic memory (via either the standard allocator, or an allocator passed to the std::function constructor) is allowed as the implementation sees fit. The standard recommends implementations do not use dynamic memory if it can be avoided, but as you rightly say, if the function object (not the std::function object, but the object being wrapped inside it) is large enough, there is no way to prevent it, since std::function has a fixed size.

This permission to throw exceptions is granted to both the normal constructor and the copy constructor, which fairly explicitly allows dynamic memory allocations during copying too. For moves, there is no reason why dynamic memory would be necessary. The standard does not seem to explicitly prohibit it, and probably cannot if the move might call the move constructor of the wrapped object's type, but you should be able to assume that if both the implementation and your objects are sensible, moving won't cause any allocations.

Answer 4

@neuront made an exact answer, tricks require emplacement new techniques etc, the code from GNU std::function

// Implementation of std::function -*- C++ -*-

// Copyright (C) 2004-2018 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file include/bits/std_function.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{functional}
 */

#ifndef _GLIBCXX_STD_FUNCTION_H
#define _GLIBCXX_STD_FUNCTION_H 1

#pragma GCC system_header

#if __cplusplus < 201103L
# include <bits/c++0x_warning.h>
#else

#if __cpp_rtti
# include <typeinfo>
#endif
#include <bits/stl_function.h>
#include <bits/invoke.h>
#include <bits/refwrap.h>
#include <bits/functexcept.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   *  @brief Exception class thrown when class template function's
   *  operator() is called with an empty target.
   *  @ingroup exceptions
   */
  class bad_function_call : public std::exception
  {
  public:
    virtual ~bad_function_call() noexcept;

    const char* what() const noexcept;
  };

  /**
   *  Trait identifying "location-invariant" types, meaning that the
   *  address of the object (or any of its members) will not escape.
   *  Trivially copyable types are location-invariant and users can
   *  specialize this trait for other types.
   */
  template<typename _Tp>
    struct __is_location_invariant
    : is_trivially_copyable<_Tp>::type
    { };

  class _Undefined_class;

  union _Nocopy_types
  {
    void*       _M_object;
    const void* _M_const_object;
    void (*_M_function_pointer)();
    void (_Undefined_class::*_M_member_pointer)();
  };

  union [[gnu::may_alias]] _Any_data
  {
    void*       _M_access()       { return &_M_pod_data[0]; }
    const void* _M_access() const { return &_M_pod_data[0]; }

    template<typename _Tp>
      _Tp&
      _M_access()
      { return *static_cast<_Tp*>(_M_access()); }

    template<typename _Tp>
      const _Tp&
      _M_access() const
      { return *static_cast<const _Tp*>(_M_access()); }

    _Nocopy_types _M_unused;
    char _M_pod_data[sizeof(_Nocopy_types)];
  };

  enum _Manager_operation
  {
    __get_type_info,
    __get_functor_ptr,
    __clone_functor,
    __destroy_functor
  };

  // Simple type wrapper that helps avoid annoying const problems
  // when casting between void pointers and pointers-to-pointers.
  template<typename _Tp>
    struct _Simple_type_wrapper
    {
      _Simple_type_wrapper(_Tp __value) : __value(__value) { }

      _Tp __value;
    };

  template<typename _Tp>
    struct __is_location_invariant<_Simple_type_wrapper<_Tp> >
    : __is_location_invariant<_Tp>
    { };

  template<typename _Signature>
    class function;

  /// Base class of all polymorphic function object wrappers.
  class _Function_base
  {
  public:
    static const std::size_t _M_max_size = sizeof(_Nocopy_types);
    static const std::size_t _M_max_align = __alignof__(_Nocopy_types);

    template<typename _Functor>
      class _Base_manager
      {
      protected:
    static const bool __stored_locally =
    (__is_location_invariant<_Functor>::value
     && sizeof(_Functor) <= _M_max_size
     && __alignof__(_Functor) <= _M_max_align
     && (_M_max_align % __alignof__(_Functor) == 0));

    typedef integral_constant<bool, __stored_locally> _Local_storage;

    // Retrieve a pointer to the function object
    static _Functor*
    _M_get_pointer(const _Any_data& __source)
    {
      const _Functor* __ptr =
        __stored_locally? std::__addressof(__source._M_access<_Functor>())
        /* have stored a pointer */ : __source._M_access<_Functor*>();
      return const_cast<_Functor*>(__ptr);
    }

    // Clone a location-invariant function object that fits within
    // an _Any_data structure.
    static void
    _M_clone(_Any_data& __dest, const _Any_data& __source, true_type)
    {
      ::new (__dest._M_access()) _Functor(__source._M_access<_Functor>());
    }

    // Clone a function object that is not location-invariant or
    // that cannot fit into an _Any_data structure.
    static void
    _M_clone(_Any_data& __dest, const _Any_data& __source, false_type)
    {
      __dest._M_access<_Functor*>() =
        new _Functor(*__source._M_access<_Functor*>());
    }

    // Destroying a location-invariant object may still require
    // destruction.
    static void
    _M_destroy(_Any_data& __victim, true_type)
    {
      __victim._M_access<_Functor>().~_Functor();
    }

    // Destroying an object located on the heap.
    static void
    _M_destroy(_Any_data& __victim, false_type)
    {
      delete __victim._M_access<_Functor*>();
    }

      public:
    static bool
    _M_manager(_Any_data& __dest, const _Any_data& __source,
           _Manager_operation __op)
    {
      switch (__op)
        {
#if __cpp_rtti
        case __get_type_info:
          __dest._M_access<const type_info*>() = &typeid(_Functor);
          break;
#endif
        case __get_functor_ptr:
          __dest._M_access<_Functor*>() = _M_get_pointer(__source);
          break;

        case __clone_functor:
          _M_clone(__dest, __source, _Local_storage());
          break;

        case __destroy_functor:
          _M_destroy(__dest, _Local_storage());
          break;
        }
      return false;
    }

    static void
    _M_init_functor(_Any_data& __functor, _Functor&& __f)
    { _M_init_functor(__functor, std::move(__f), _Local_storage()); }

    template<typename _Signature>
      static bool
      _M_not_empty_function(const function<_Signature>& __f)
      { return static_cast<bool>(__f); }

    template<typename _Tp>
      static bool
      _M_not_empty_function(_Tp* __fp)
      { return __fp != nullptr; }

    template<typename _Class, typename _Tp>
      static bool
      _M_not_empty_function(_Tp _Class::* __mp)
      { return __mp != nullptr; }

    template<typename _Tp>
      static bool
      _M_not_empty_function(const _Tp&)
      { return true; }

      private:
    static void
    _M_init_functor(_Any_data& __functor, _Functor&& __f, true_type)
    { ::new (__functor._M_access()) _Functor(std::move(__f)); }

    static void
    _M_init_functor(_Any_data& __functor, _Functor&& __f, false_type)
    { __functor._M_access<_Functor*>() = new _Functor(std::move(__f)); }
      };

    _Function_base() : _M_manager(nullptr) { }

    ~_Function_base()
    {
      if (_M_manager)
    _M_manager(_M_functor, _M_functor, __destroy_functor);
    }

    bool _M_empty() const { return !_M_manager; }

    typedef bool (*_Manager_type)(_Any_data&, const _Any_data&,
                  _Manager_operation);

    _Any_data     _M_functor;
    _Manager_type _M_manager;
  };

  template<typename _Signature, typename _Functor>
    class _Function_handler;

  template<typename _Res, typename _Functor, typename... _ArgTypes>
    class _Function_handler<_Res(_ArgTypes...), _Functor>
    : public _Function_base::_Base_manager<_Functor>
    {
      typedef _Function_base::_Base_manager<_Functor> _Base;

    public:
      static _Res
      _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
      {
    return (*_Base::_M_get_pointer(__functor))(
        std::forward<_ArgTypes>(__args)...);
      }
    };

  template<typename _Functor, typename... _ArgTypes>
    class _Function_handler<void(_ArgTypes...), _Functor>
    : public _Function_base::_Base_manager<_Functor>
    {
      typedef _Function_base::_Base_manager<_Functor> _Base;

     public:
      static void
      _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
      {
    (*_Base::_M_get_pointer(__functor))(
        std::forward<_ArgTypes>(__args)...);
      }
    };

  template<typename _Class, typename _Member, typename _Res,
       typename... _ArgTypes>
    class _Function_handler<_Res(_ArgTypes...), _Member _Class::*>
    : public _Function_handler<void(_ArgTypes...), _Member _Class::*>
    {
      typedef _Function_handler<void(_ArgTypes...), _Member _Class::*>
    _Base;

     public:
      static _Res
      _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
      {
    return std::__invoke(_Base::_M_get_pointer(__functor)->__value,
                 std::forward<_ArgTypes>(__args)...);
      }
    };

  template<typename _Class, typename _Member, typename... _ArgTypes>
    class _Function_handler<void(_ArgTypes...), _Member _Class::*>
    : public _Function_base::_Base_manager<
         _Simple_type_wrapper< _Member _Class::* > >
    {
      typedef _Member _Class::* _Functor;
      typedef _Simple_type_wrapper<_Functor> _Wrapper;
      typedef _Function_base::_Base_manager<_Wrapper> _Base;

    public:
      static bool
      _M_manager(_Any_data& __dest, const _Any_data& __source,
         _Manager_operation __op)
      {
    switch (__op)
      {
#if __cpp_rtti
      case __get_type_info:
        __dest._M_access<const type_info*>() = &typeid(_Functor);
        break;
#endif
      case __get_functor_ptr:
        __dest._M_access<_Functor*>() =
          &_Base::_M_get_pointer(__source)->__value;
        break;

      default:
        _Base::_M_manager(__dest, __source, __op);
      }
    return false;
      }

      static void
      _M_invoke(const _Any_data& __functor, _ArgTypes&&... __args)
      {
    std::__invoke(_Base::_M_get_pointer(__functor)->__value,
              std::forward<_ArgTypes>(__args)...);
      }
    };

  template<typename _From, typename _To>
    using __check_func_return_type
      = __or_<is_void<_To>, is_same<_From, _To>, is_convertible<_From, _To>>;

  /**
   *  @brief Primary class template for std::function.
   *  @ingroup functors
   *
   *  Polymorphic function wrapper.
   */
  template<typename _Res, typename... _ArgTypes>
    class function<_Res(_ArgTypes...)>
    : public _Maybe_unary_or_binary_function<_Res, _ArgTypes...>,
      private _Function_base
    {
      template<typename _Func,
           typename _Res2 = typename result_of<_Func&(_ArgTypes...)>::type>
    struct _Callable : __check_func_return_type<_Res2, _Res> { };

      // Used so the return type convertibility checks aren't done when
      // performing overload resolution for copy construction/assignment.
      template<typename _Tp>
    struct _Callable<function, _Tp> : false_type { };

      template<typename _Cond, typename _Tp>
    using _Requires = typename enable_if<_Cond::value, _Tp>::type;

    public:
      typedef _Res result_type;

      // [3.7.2.1] construct/copy/destroy

      /**
       *  @brief Default construct creates an empty function call wrapper.
       *  @post @c !(bool)*this
       */
      function() noexcept
      : _Function_base() { }

      /**
       *  @brief Creates an empty function call wrapper.
       *  @post @c !(bool)*this
       */
      function(nullptr_t) noexcept
      : _Function_base() { }

      /**
       *  @brief %Function copy constructor.
       *  @param __x A %function object with identical call signature.
       *  @post @c bool(*this) == bool(__x)
       *
       *  The newly-created %function contains a copy of the target of @a
       *  __x (if it has one).
       */
      function(const function& __x);

      /**
       *  @brief %Function move constructor.
       *  @param __x A %function object rvalue with identical call signature.
       *
       *  The newly-created %function contains the target of @a __x
       *  (if it has one).
       */
      function(function&& __x) noexcept : _Function_base()
      {
    __x.swap(*this);
      }

      /**
       *  @brief Builds a %function that targets a copy of the incoming
       *  function object.
       *  @param __f A %function object that is callable with parameters of
       *  type @c T1, @c T2, ..., @c TN and returns a value convertible
       *  to @c Res.
       *
       *  The newly-created %function object will target a copy of
       *  @a __f. If @a __f is @c reference_wrapper<F>, then this function
       *  object will contain a reference to the function object @c
       *  __f.get(). If @a __f is a NULL function pointer or NULL
       *  pointer-to-member, the newly-created object will be empty.
       *
       *  If @a __f is a non-NULL function pointer or an object of type @c
       *  reference_wrapper<F>, this function will not throw.
       */
      template<typename _Functor,
           typename = _Requires<__not_<is_same<_Functor, function>>, void>,
           typename = _Requires<_Callable<_Functor>, void>>
    function(_Functor);

      /**
       *  @brief %Function assignment operator.
       *  @param __x A %function with identical call signature.
       *  @post @c (bool)*this == (bool)x
       *  @returns @c *this
       *
       *  The target of @a __x is copied to @c *this. If @a __x has no
       *  target, then @c *this will be empty.
       *
       *  If @a __x targets a function pointer or a reference to a function
       *  object, then this operation will not throw an %exception.
       */
      function&
      operator=(const function& __x)
      {
    function(__x).swap(*this);
    return *this;
      }

      /**
       *  @brief %Function move-assignment operator.
       *  @param __x A %function rvalue with identical call signature.
       *  @returns @c *this
       *
       *  The target of @a __x is moved to @c *this. If @a __x has no
       *  target, then @c *this will be empty.
       *
       *  If @a __x targets a function pointer or a reference to a function
       *  object, then this operation will not throw an %exception.
       */
      function&
      operator=(function&& __x) noexcept
      {
    function(std::move(__x)).swap(*this);
    return *this;
      }

      /**
       *  @brief %Function assignment to zero.
       *  @post @c !(bool)*this
       *  @returns @c *this
       *
       *  The target of @c *this is deallocated, leaving it empty.
       */
      function&
      operator=(nullptr_t) noexcept
      {
    if (_M_manager)
      {
        _M_manager(_M_functor, _M_functor, __destroy_functor);
        _M_manager = nullptr;
        _M_invoker = nullptr;
      }
    return *this;
      }

      /**
       *  @brief %Function assignment to a new target.
       *  @param __f A %function object that is callable with parameters of
       *  type @c T1, @c T2, ..., @c TN and returns a value convertible
       *  to @c Res.
       *  @return @c *this
       *
       *  This  %function object wrapper will target a copy of @a
       *  __f. If @a __f is @c reference_wrapper<F>, then this function
       *  object will contain a reference to the function object @c
       *  __f.get(). If @a __f is a NULL function pointer or NULL
       *  pointer-to-member, @c this object will be empty.
       *
       *  If @a __f is a non-NULL function pointer or an object of type @c
       *  reference_wrapper<F>, this function will not throw.
       */
      template<typename _Functor>
    _Requires<_Callable<typename decay<_Functor>::type>, function&>
    operator=(_Functor&& __f)
    {
      function(std::forward<_Functor>(__f)).swap(*this);
      return *this;
    }

      /// @overload
      template<typename _Functor>
    function&
    operator=(reference_wrapper<_Functor> __f) noexcept
    {
      function(__f).swap(*this);
      return *this;
    }

      // [3.7.2.2] function modifiers

      /**
       *  @brief Swap the targets of two %function objects.
       *  @param __x A %function with identical call signature.
       *
       *  Swap the targets of @c this function object and @a __f. This
       *  function will not throw an %exception.
       */
      void swap(function& __x) noexcept
      {
    std::swap(_M_functor, __x._M_functor);
    std::swap(_M_manager, __x._M_manager);
    std::swap(_M_invoker, __x._M_invoker);
      }

      // [3.7.2.3] function capacity

      /**
       *  @brief Determine if the %function wrapper has a target.
       *
       *  @return @c true when this %function object contains a target,
       *  or @c false when it is empty.
       *
       *  This function will not throw an %exception.
       */
      explicit operator bool() const noexcept
      { return !_M_empty(); }

      // [3.7.2.4] function invocation

      /**
       *  @brief Invokes the function targeted by @c *this.
       *  @returns the result of the target.
       *  @throws bad_function_call when @c !(bool)*this
       *
       *  The function call operator invokes the target function object
       *  stored by @c this.
       */
      _Res operator()(_ArgTypes... __args) const;

#if __cpp_rtti
      // [3.7.2.5] function target access
      /**
       *  @brief Determine the type of the target of this function object
       *  wrapper.
       *
       *  @returns the type identifier of the target function object, or
       *  @c typeid(void) if @c !(bool)*this.
       *
       *  This function will not throw an %exception.
       */
      const type_info& target_type() const noexcept;

      /**
       *  @brief Access the stored target function object.
       *
       *  @return Returns a pointer to the stored target function object,
       *  if @c typeid(_Functor).equals(target_type()); otherwise, a NULL
       *  pointer.
       *
       * This function does not throw exceptions.
       *
       * @{
       */
      template<typename _Functor>       _Functor* target() noexcept;

      template<typename _Functor> const _Functor* target() const noexcept;
      // @}
#endif

    private:
      using _Invoker_type = _Res (*)(const _Any_data&, _ArgTypes&&...);
      _Invoker_type _M_invoker;
  };

#if __cpp_deduction_guides >= 201606
  template<typename>
    struct __function_guide_helper
    { };

  template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
    struct __function_guide_helper<
      _Res (_Tp::*) (_Args...) noexcept(_Nx)
    >
    { using type = _Res(_Args...); };

  template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
    struct __function_guide_helper<
      _Res (_Tp::*) (_Args...) & noexcept(_Nx)
    >
    { using type = _Res(_Args...); };

  template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
    struct __function_guide_helper<
      _Res (_Tp::*) (_Args...) const noexcept(_Nx)
    >
    { using type = _Res(_Args...); };

  template<typename _Res, typename _Tp, bool _Nx, typename... _Args>
    struct __function_guide_helper<
      _Res (_Tp::*) (_Args...) const & noexcept(_Nx)
    >
    { using type = _Res(_Args...); };

  template<typename _Res, typename... _ArgTypes>
    function(_Res(*)(_ArgTypes...)) -> function<_Res(_ArgTypes...)>;

  template<typename _Functor, typename _Signature = typename
       __function_guide_helper<decltype(&_Functor::operator())>::type>
    function(_Functor) -> function<_Signature>;
#endif

  // Out-of-line member definitions.
  template<typename _Res, typename... _ArgTypes>
    function<_Res(_ArgTypes...)>::
    function(const function& __x)
    : _Function_base()
    {
      if (static_cast<bool>(__x))
    {
      __x._M_manager(_M_functor, __x._M_functor, __clone_functor);
      _M_invoker = __x._M_invoker;
      _M_manager = __x._M_manager;
    }
    }

  template<typename _Res, typename... _ArgTypes>
    template<typename _Functor, typename, typename>
      function<_Res(_ArgTypes...)>::
      function(_Functor __f)
      : _Function_base()
      {
    typedef _Function_handler<_Res(_ArgTypes...), _Functor> _My_handler;

    if (_My_handler::_M_not_empty_function(__f))
      {
        _My_handler::_M_init_functor(_M_functor, std::move(__f));
        _M_invoker = &_My_handler::_M_invoke;
        _M_manager = &_My_handler::_M_manager;
      }
      }

  template<typename _Res, typename... _ArgTypes>
    _Res
    function<_Res(_ArgTypes...)>::
    operator()(_ArgTypes... __args) const
    {
      if (_M_empty())
    __throw_bad_function_call();
      return _M_invoker(_M_functor, std::forward<_ArgTypes>(__args)...);
    }

#if __cpp_rtti
  template<typename _Res, typename... _ArgTypes>
    const type_info&
    function<_Res(_ArgTypes...)>::
    target_type() const noexcept
    {
      if (_M_manager)
    {
      _Any_data __typeinfo_result;
      _M_manager(__typeinfo_result, _M_functor, __get_type_info);
      return *__typeinfo_result._M_access<const type_info*>();
    }
      else
    return typeid(void);
    }

  template<typename _Res, typename... _ArgTypes>
    template<typename _Functor>
      _Functor*
      function<_Res(_ArgTypes...)>::
      target() noexcept
      {
    const function* __const_this = this;
    const _Functor* __func = __const_this->template target<_Functor>();
    return const_cast<_Functor*>(__func);
      }

  template<typename _Res, typename... _ArgTypes>
    template<typename _Functor>
      const _Functor*
      function<_Res(_ArgTypes...)>::
      target() const noexcept
      {
    if (typeid(_Functor) == target_type() && _M_manager)
      {
        _Any_data __ptr;
        _M_manager(__ptr, _M_functor, __get_functor_ptr);
        return __ptr._M_access<const _Functor*>();
      }
    else
      return nullptr;
      }
#endif

  // [20.7.15.2.6] null pointer comparisons

  /**
   *  @brief Compares a polymorphic function object wrapper against 0
   *  (the NULL pointer).
   *  @returns @c true if the wrapper has no target, @c false otherwise
   *
   *  This function will not throw an %exception.
   */
  template<typename _Res, typename... _Args>
    inline bool
    operator==(const function<_Res(_Args...)>& __f, nullptr_t) noexcept
    { return !static_cast<bool>(__f); }

  /// @overload
  template<typename _Res, typename... _Args>
    inline bool
    operator==(nullptr_t, const function<_Res(_Args...)>& __f) noexcept
    { return !static_cast<bool>(__f); }

  /**
   *  @brief Compares a polymorphic function object wrapper against 0
   *  (the NULL pointer).
   *  @returns @c false if the wrapper has no target, @c true otherwise
   *
   *  This function will not throw an %exception.
   */
  template<typename _Res, typename... _Args>
    inline bool
    operator!=(const function<_Res(_Args...)>& __f, nullptr_t) noexcept
    { return static_cast<bool>(__f); }

  /// @overload
  template<typename _Res, typename... _Args>
    inline bool
    operator!=(nullptr_t, const function<_Res(_Args...)>& __f) noexcept
    { return static_cast<bool>(__f); }


  // [20.7.15.2.7] specialized algorithms

  /**
   *  @brief Swap the targets of two polymorphic function object wrappers.
   *
   *  This function will not throw an %exception.
   */
  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 2062. Effect contradictions w/o no-throw guarantee of std::function swaps
  template<typename _Res, typename... _Args>
    inline void
    swap(function<_Res(_Args...)>& __x, function<_Res(_Args...)>& __y) noexcept
    { __x.swap(__y); }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#endif // C++11

#endif // _GLIBCXX_STD_FUNCTION_H

Answer 5

@neuront gave an inspiring answer, however calling a function through a function pointer of different type may invoke undefined behavior. I tried to implement "std::function" in a slightly different way, which may be incomplete but can be used with the example code in https://en.cppreference.com/w/cpp/utility/functional/function

#include <type_traits>
#include <utility>
#include <stdexcept>

template <typename... Args> class function;

template <typename R, typename... Args>
class function<R(Args...)> {
public:
  /** construct empty function object */
  function(): m_functor(nullptr), m_invoke(nullptr), m_delete(nullptr), m_copy(nullptr) {}

  /** destruct function object */
  ~function() {
    if (m_delete) m_delete(*this);
  }

  /** construct a valid function object from the copy of the given function pointer or functor */
  template <typename F, typename std::enable_if<
    !std::is_same<typename std::decay<F>::type, function>::value, int>::type = 1>
  function(F&& functor): function(1, cast_mem_fn(std::forward<F>(functor))) {}

  /** run function call */
  R operator()(Args... args) const {
    if (!m_functor || !m_invoke) throw std::runtime_error("call an empty function object");
    return (*m_invoke)(*this, static_cast<Args>(args)...);
  }

  /** copy constructor */
  function(const function &other): m_functor(other.m_copy ? (*other.m_copy)(other) : nullptr),
    m_invoke(other.m_invoke), m_delete(other.m_delete), m_copy(other.m_copy) {}

  /** move constructor */
  function(function &&other): m_functor(other.m_functor), m_invoke(other.m_invoke),
    m_delete(other.m_delete), m_copy(other.m_copy) {
    other.m_functor = nullptr;
    other.m_invoke = nullptr;
    other.m_delete = nullptr;
    other.m_copy = nullptr;
  }

  /** copy assignment */
  function& operator=(const function &other) {
    if (this == &other) return *this;
    if (m_delete) m_delete(*this);
    m_functor = other.m_copy ? (*other.m_copy)(other) : nullptr;
    m_invoke = other.m_invoke;
    m_delete = other.m_delete;
    m_copy = other.m_copy;
    return *this;
  }

  /** move assignment */
  function& operator=(function &&other) {
    if (m_delete) m_delete(*this);
    m_functor = other.m_functor;
    m_invoke = other.m_invoke;
    m_delete = other.m_delete;
    m_copy = other.m_copy;
    other.m_functor = nullptr;
    other.m_invoke = nullptr;
    other.m_delete = nullptr;
    other.m_copy = nullptr;
    return *this;
  }

private:

  template <typename F>
  function(int dummy, F&& functor): m_functor(reinterpret_cast<char*>(new
    typename std::decay<F>::type(std::forward<F>(functor)))) {
    typedef typename std::decay<F>::type functor_type;
    static_assert(std::is_same<R, decltype(invoke_impl<functor_type>(
      function(), std::declval<Args>()...))>::value, "invalid functor type");
    static_assert(std::is_copy_constructible<functor_type>::value,
      "uncopyable functor type");
    m_invoke = invoke_impl<functor_type>;
    m_delete = delete_impl<functor_type>;
    m_copy = copy_impl<functor_type>;
  }

  template <typename F>
  F&& cast_mem_fn(F&& f) {
    return static_cast<F&&>(f);
  }

  /** a pointer to class member cannot be casted to char* */
  /** conversion to a functor can solve this issue */
  template <typename CLASS, typename METHOD>
  class pmf_wrapper {
    METHOD CLASS::*m_pmf;

  public:
    pmf_wrapper(METHOD CLASS::*pmf): m_pmf(pmf) {}

    R operator()(Args... args) {
      return invoke<METHOD>(static_cast<Args>(args)...);
    }

  private:
    template <typename T, typename std::enable_if<std::is_same<CLASS,
      typename std::decay<T>::type>::value, int>::type = 1>
    T&& transfer(T&& inst) {
      return static_cast<T&&>(inst);
    }

    template <typename T, typename std::enable_if<std::is_same<CLASS,
      typename std::decay<decltype(*T())>::type>::value, int>::type = 1>
    auto transfer(T&& ptr)->decltype(*ptr) {
      return *ptr;
    }
    
    /** member function pointer */
    template <typename MT,
      typename std::enable_if<std::is_function<MT>::value, int>::type = 1,
      typename T, typename... SUBARGS>
    R invoke(T&& inst, SUBARGS&&... args) {
      return (transfer(std::forward<T>(inst)).*m_pmf)(std::forward<SUBARGS>(args)...);
    }

    /** data member pointer */
    template <typename MT,
      typename std::enable_if<!std::is_function<MT>::value, int>::type = 1,
      typename T>
    R invoke(T&& inst) {
      return transfer(std::forward<T>(inst)).*m_pmf;
    }
  };

  template <typename CLASS, typename METHOD>
  pmf_wrapper<CLASS, METHOD> cast_mem_fn(METHOD CLASS::*pmf) {
    return pmf_wrapper<CLASS, METHOD>(pmf);
  }

  template <typename F>
  static auto invoke_impl(const function &obj, Args... args)->
    decltype(std::declval<F>()(static_cast<Args>(args)...)) {
    return (*reinterpret_cast<F*>(obj.m_functor))(static_cast<Args>(args)...);
  }

  template <typename F>
  static void delete_impl(const function &obj) {
    delete reinterpret_cast<F*>(obj.m_functor);
  }

  template <typename F>
  static char *copy_impl(const function &obj) {
    return reinterpret_cast<char*>(new F(*reinterpret_cast<const F*>(obj.m_functor)));
  }

  /** pointer to the internal function pointer/functor object (on heap) */
  char *m_functor;

  /** call m_functor */
  R (*m_invoke)(const function &obj, Args... args);

  /** destroy m_functor */
  void (*m_delete)(const function &obj);

  /** copy m_functor */
  char *(*m_copy)(const function &obj);

};

Answer 6

This code is for anyone who want to understand the magic behind type-erasure. It certainly lacks tonnes of features (utilities, protections ...) of std::function, but you can run it directly.

#include <iostream>
#include <memory>

using namespace std;

template<typename R, typename ...Args>
class DummyFunction;

template<typename R, typename ...Args>
class DummyFunction<R(Args...)> {
public:
    template<class F>
    DummyFunction(const F &callback):wrapper(new ChildWrapper<F>(callback)) {
    }

    R operator()(Args ...args) {
        return (*wrapper)(args...);
    }

    class BaseWrapper {
    public:
        virtual R operator()(Args ...args) = 0;
    };

    template<class F>
    class ChildWrapper : public BaseWrapper {
    public:
        explicit ChildWrapper(const F &callback) : callback(callback) {
        }

        virtual R operator()(Args ...args) {
            return callback(args...);
        }

    private:
        F callback;
    };

    shared_ptr<BaseWrapper> wrapper;
};

int main() {

    struct BinaryOp {
        int operator()(int a, int b) {
            return a + b;
        }
    } binaryOp;

    auto callMe = [](DummyFunction<int(int, int)> callable) {
        cout << "The result is " << callable(2, 3) << endl;
    };

    auto dummy1 = DummyFunction<int(int, int)>(binaryOp);
    callMe(dummy1);
    callMe(binaryOp);
    callMe([](int a, int b) -> int {
        return a * b;
    });
}

To explain, when you construct a DummyFunction<int(int,int)> the constructor receives another 'F' type, which represents the actual type of the callable (lambda, struct ...). It uses this to construct a ChildWrapper object which is aware of the type 'F', which is stored in a shared_ptr<BaseWrapper>.

The takeaway here is neither DummyFunction nor BaseWrapper are aware of the type 'F', thus type erased. (Of course, they know the types of the arguments and returned value).

So, when you call the dummy function, you call the BaseWrapper which in turn through run-time polymorphism (since declared virtual) invokes that of ChildWrapper, which is F-aware.

Answer 7

The answer from @David Rodríguez - dribeas is good for demonstrating the type-erasure but not good enough since type-erasure also includes how types are copied (in that answer the function object won't be copy-constructible). Those behaviors are also stored in the function object, besides the functor data.

The trick, used in the STL implementation from Ubuntu 14.04 gcc 4.8, is to write one generic function, specialize it with each possible functor type, and cast them to a universal function pointer type. Therefore the type information is erased.

I've cobbled up a simplified version of that. Hope it'll help

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

There are also some optimizations in the STL version

• the construct_f and destroy_f are mixed into one function pointer (with an additional parameter that tells what to do) as to save some bytes
• raw pointers are used to store the functor object, along with a function pointer in a union, so that when a function object is constructed from an function pointer, it will be stored directly in the union rather than heap space

Maybe the STL implementation is not the best solution as I've heard about some faster implementation. However I believe the underlying mechanism is the same.