How Std::Function Works

How std::function works

It uses some type erasure technique.

One possibility is to use mix subtype polymorphism with templates. Here's a simplified version, just to give a feel for the overall structure:

template <typename T>
struct function;

template <typename Result, typename... Args>
struct function<Result(Args...)> {
private:
    // this is the bit that will erase the actual type
    struct concept {
        virtual Result operator()(Args...) const = 0;
    };

    // this template provides us derived classes from `concept`
    // that can store and invoke op() for any type
    template <typename T>
    struct model : concept {
        template <typename U>
        model(U&& u) : t(std::forward<U>(u)) {}

        Result operator()(Args... a) const override {
            t(std::forward<Args>(a)...);
        }

        T t;
    };

    // this is the actual storage
    // note how the `model<?>` type is not used here    
    std::unique_ptr<concept> fn;

public:
    // construct a `model<T>`, but store it as a pointer to `concept`
    // this is where the erasure "happens"
    template <typename T,
        typename=typename std::enable_if<
            std::is_convertible<
                decltype( t(std::declval<Args>()...) ),
                Result
            >::value
        >::type>
    function(T&& t)
    : fn(new model<typename std::decay<T>::type>(std::forward<T>(t))) {}

    // do the virtual call    
    Result operator()(Args... args) const {
        return (*fn)(std::forward<Args>(args)...);
    }
};

(Note that I overlooked several things for the sake of simplicity: it cannot be copied, and maybe other problems; don't use this code in real code)

How is std::function implemented?

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.

What is the purpose of std::function and how to use it?

std::function is a type erasure object. That means it erases the details of how some operations happen, and provides a uniform run time interface to them. For std::function, the primary¹ operations are copy/move, destruction, and 'invocation' with operator() -- the 'function like call operator'.

In less abstruse English, it means that std::function can contain almost any object that acts like a function pointer in how you call it.

The signature it supports goes inside the angle brackets: std::function<void()> takes zero arguments and returns nothing. std::function< double( int, int ) > takes two int arguments and returns double. In general, std::function supports storing any function-like object whose arguments can be converted-from its argument list, and whose return value can be converted-to its return value.

It is important to know that std::function and lambdas are different, if compatible, beasts.

The next part of the line is a lambda. This is new syntax in C++11 to add the ability to write simple function-like objects -- objects that can be invoked with (). Such objects can be type erased and stored in a std::function at the cost of some run time overhead.

[](){ code } in particular is a really simple lambda. It corresponds to this:

struct some_anonymous_type {
  some_anonymous_type() {}
  void operator()const{
    code
  }
};

an instance of the above simple pseudo-function type. An actual class like the above is "invented" by the compiler, with an implementation defined unique name (often including symbols that no user-defined type can contain) (I do not know if it is possible that you can follow the standard without inventing such a class, but every compiler I know of actually creates the class).

The full lambda syntax looks like:

[ capture_list ]( argument_list )
-> return_type optional_mutable
{
  code
}

But many parts can be omitted or left empty. The capture_list corresponds to both the constructor of the resulting anonymous type and its member variables, the argument_list the arguments of the operator(), and the return type the return type. The constructor of the lambda instance is also magically called when the instance is created with the capture_list.

[ capture_list ]( argument_list ) -> return_type { code }

basically becomes

struct some_anonymous_type {
  // capture_list turned into member variables
  some_anonymous_type( /* capture_list turned into arguments */ ):
    /* member variables initialized */
  {}
  return_type operator()( argument_list ) const {
    code
  }
};

Note that in c++20 template arguments were added to lambdas, and that isn't covered above.

[]<typename T>( std::vector<T> const& v ) { return v.size(); }

¹ In addition, RTTI is stored (typeid), and the cast-back-to-original-type operation is included.

std::function works beautifully with std::bind - but why?

Q: What are the basic rules that effectively determine: dist(rng) being used - I don't see why std::bind would enforce this interaction. A lot of interactions seem based around operator () methods.

std::bind performs function composition. The first argument must be a function object, i.e. something callable like a function (e.g. a normal function, or a class with an overloaded operator()).

A call to std::bind makes copies of its arguments, "binds" the copies of the arguments to the first argument (the function object), and returns a new function object that will invoke the copy of the function object.

So in a simple case:

int f(int i) { return i; }
auto f1 = std::bind(f, 1);

this binds the value 1 to the function f, creating a new function object that can be called with no arguments. When you invoke f1() it will invoke f with the argument 1, i.e. it will call f(1), and return whatever that returns (which in this case is just 1).

The actual type of the thing returned by std::bind(f, 1) is some implementation-specific class type, maybe called something like std::__detail::__bind_type<void(*)(int), int>. You're not meant to refer to that type directly, you would either capture the object using auto or store it in something else that doesn't care about the precise type, so either:

auto f1 = std::bind(f, 1);

or:

std::function<int()> f1 = std::bind(f, 1);

In your more complex case, when you call std::bind(decltype(p_dist){0, p - 1}, std::ref(rng))) you get a new function object that contains a copy of the temporary decltype(p_dist){0, p - 1} and a copy of the reference_wrapper<std::mt19937> created by std::ref(rng). When you invoke that new function object it will call the contained distribution, passing it a reference to rng.

That means it is callable with no arguments, and it will call the contained random number distribution with the contained random engine, and return the result.

Q: std::function is helpfully referred to as 'a general-purpose polymorphic function wrapper' on cppreference.com. So is it a function that encapsulates a uint64_t return type?

A std::function<uint64_t()> is a wrapper for a function object that is callable with no arguments and that returns a uint64_t (or something implicitly convertible to uint64_t). It can be used to store a copy of an arbitrary function object that is copy constructible, and callable with no arguments, and returns something convertible to uint64_t.

(And more generally, a std::function<R(A1, A2 ... AN)> is a wrapper for a function object that returns R when called with N arguments, of types A1, A2 ... AN.)

Since the result of your std::bind call is a copy constructible function object that is callable with no arguments and returns a uint64_t, you can store the result of that std::bind call in a std::function<uint64_t()>, and when you invoke the function it will invoke the result of the bind call, which will invoke the contained distribution, and return the result.

Or again, making use of operator () syntax to drive the notion of a function?

I'm not sure what this means, but in general it's true that in C++ we often talk about "function objects" or "callables" which are generalisations of functions, i.e. something that can be invoked using function call syntax, e.g. a(b, c)

How does the argument list for std::function work

You can declare a type like that:

using Func = void(double);

But in the definition, you still need the name of the argument; otherwise, you could not use it in the function:

void passFunc(void func(double)) {}

Note that func is inbetween the return type and the arguments. If you don't like that, you can use the above-defined type:

void passFunc(Func func) {}

How does std::function makes pointer pointing to a member function work?

Member functions have a hidden first parameter, which is the pointer to the object it is called on. So

double mult::operator()(double a, double b) { return a * b; }

is in fact (somewhat) equal to

double operator()(mult* this, double a, double b) {
    return a * b;
}

So that's why you cannot add a mfp type object to a vector of type fp.

edit: what will work is

struct mult {
    static double fun(double a, double b) { return a * b; }
};

fp f = &mult::fun;
functions1.push_back(f);

As by making a member function static, it's no longer tied to an object.

and

functions1.push_back(mfp);

is probably a typo anyway, since mfp was the typedef, and not the function object f...

edit 2: There is also the option to use std::bind to bind the first hidden parameter to a specific object.

E.g. using your original (non-static) member function:

mult obj;
fnc temp = std::bind(&mult::fun, &obj, std::placeholders::_1, std::placeholders::_2);
functions.push_back(temp);

Why does passing functions by value work but not by reference

You are trying to bind a non-constant reference with a temporary object.

You could use a constant reference.

Here is a demonstration program.

#include <iostream>
#include <functional>

void foo( const std::function<int(int)> &stuff )
{
   int x = 10;

   std::cout << stuff( x ) << '\n';
}

int main()
{
    auto fct = [](int x){return x * 10;};

    foo(fct);
}

The program output is

Without the qualifier const you could write for example

#include <iostream>
#include <functional>

void foo( std::function<int(int)> &stuff )
{
   int x = 10;

   std::cout << stuff( x ) << '\n';
}

int main()
{
    auto fct = [](int x){return x * 10;};

    std::function<int(int)> f( fct );

    foo(f);
}

As for the lambda-expression then according to the C++ 17 Standard (8.1.5.1 Closure types)

1 The type of a lambda-expression (which is also the type of the
closure object) is a unique, unnamed non-union class type, called the
closure type, whose properties are described below.

Is there any restriction in returning std::function from a function within a class

This is a variation on the member functions are not regular functions question we get so often. Your code can be made to work like this

public : 
    std::function<void(testClass&,std::string) > getFp(){
        return &testClass::myTestFunction;
    }
};

and to call this method

testClass t ; 
auto fp1 = t.getFp();
fp1(t, "Calling Private Method ?");

Not sure if this is acceptable to you or not.

How Std::Function Works