What you need _not_ know about std::function - Part 1

• Part-2 : Implementation of std::function
• Part-3 : Performance benchmarks

std::function is cool. No doubt about that. It provides you with a constant interface to create callable objects irrespective of whether it is constructed from a function pointer or member function pointer or functor or functionoid. I assume that everyone who is reading this have used it at least once. The mechanics of how it actually works is near magic.

In this post and in the second part of it, I will try my best to dissect the functional header file provided by libstd++. This post will be covering the basic type traits that will be required, std::mem_fn, few other technical stuff and in the next post I will discuss about the implementation of std::function.

The only part I am not going to touch from that file is std::bind. It's dark magic. Let's leave it at that.

Few notes:
1. The code would mostly be the prettified version of libstd++ implementation.
2. No guarantee about the correctness of my understanding. Comments are welcome if you see anything wrong in the explanation.

Some Basic Definitions

A expression for a function call as defined by the standard is

postfix-expression ( expression-list <optional> ) 

Few important definitions from the standard (Section 20.8.*)

1. Function Object Type is an object having the type of postfix-expression in the function call expression (see above).
2. Function Object is just an object of function object type.
3. Call Signature is the name of a return type followed by a parenthesized comma-separated list of zero or more argument types.
Example: Consider the function:

int foo (char c) {...}

Call signature for the above is:

int (char);

4. A Callable Type is a function object type or a pointer to member.
5. A Callable Object is an object of a callable type.
6. A Call Wrapper Type is a type that holds a callable object and supports a call operation that forwards to that object.
Below shows a very simple (but useless) example of such a call wrapper:

/* 
A wrapper around a callable type which
returns a void and takes an int.
*/
struct VoidCallWrapper {
  void operator()(int v) {
    callable_(v);
  }

  CallableType callable_; // Target Object
};

7. A Call Wrapper is an object of call wrapper type.

8. A target object is the callable object held by a call wrapper.

As you see, unlike 'C' which has only one callable type that I know of which is a function pointer, C++ has lot more variety of callable types:
1. Function pointer
2. Member function pointer
3. Member data
4. Functor
5. Functionoid

Having so many options definitely gives more flexibility, but at the same time can cause a lot of inconvenience due to difference in their syntaxes. One can easily use a template to hide the syntax differences and as we will see later that's what one should do when we do not need a stored callable object. But, when we need to store a callable object and which must remain valid across call stacks, we should use std::function. It has only the call signature as part of its type information, all the rest is erased (type-erasure). So, it is kind of a generic function pointer. All this would be the meat of discussion in one of the coming sections. 

Deep Dive into Type-Traits

Type traits are basically compile time introspection mechanism for getting some characteristics about the passed type (Mostly as a template parameter).
A quick example of a type-trait which checks whether the passed type has a member-type named value_type:

template <typename... T>
using void_t = void;

template <typename T, typename = void_t<>>
struct has_value_type : std::false_type {};

template <typename T>
struct has_value_type<T, void_t<typename T::value_type>> :
  std::true_type {};

int main() {
    static_assert (!has_value_type<int>::value, "Integer cannot have a value type!!");
    static_assert (has_value_type<std::string::iterator>::value, 
                                                  "String iterator must have value_type!!");
    return 0; 
}

The example shown makes use of the void_t trick.

Now, let's understand the type_traits used by std::mem_fn and std::function one by one.

NOTE: Not all the specializations for a type-trait would be covered in this post. The specializations for c-v qualification(s) and varargs are omitted for the sake of clarity and less typing.

Result Type for a Callable Type

A type-trait to know what the callable type returns when its object is called.

template<typename Functor>
struct Weak_result_type
    : Weak_result_type_impl<Functor>
{ };

As said earlier, the template has magically removed all the syntax differences between different callable types. All the type specific details are found out by doing partial specialization of Weak_result_type_impl struct for each callable type:

1. Specialization for regular function call signature

template <typename Res, typename... ArgTypes>
struct Weak_result_type_impl <Res(ArgTypes...)>
{ typedef Res result_type; };

This is simple, the partially specialized template parameter has pretty much the same signature of that of the call expression. The template argument deduction settles in for this specialization because it matches best (OR no other specialization matches) for a simple function.

Let's see an example of how this would work:

// This is not how the actual definition of Weak_result_type_impl
// is. It's just here for example.
template <typename F> struct Weak_result_type_impl;

template <typename Res, typename... ArgTypes>
struct Weak_result_type_impl <Res(ArgTypes...)>
{ typedef Res result_type; };

template <typename Functor>
struct Weak_result_type
    : Weak_result_type_impl <Functor>
{ };

int foobar() {
  return 42;
}

int main() {
  static_assert (
       std::is_same<Weak_result_type<decltype(foobar)>::result_type, int>::value,  
               "foobar should always return an int!!");
  return 0;
}

This should give good idea on how the rest of the partial specializations would work.

2. Specialization for function reference

template <typename Res, typename... ArgTypes>
struct Weak_result_type_impl<Res(&)(ArgTypes...)>
{ typedef Res result_type; };

3. Specialization for function pointer

template <typename Res, typename... ArgTypes>
struct Weak_result_type_impl <Res(*)(ArgTypes...)>
{ typedef Res result_type; };

4. Specialization for member function pointer

template <typename Res, typename Class, typename... ArgTypes>
struct Weak_result_type_impl <Res (Class::*)(ArgTypes...)>
{ typedef Res result_type; };

5. Specialization for Functor having a result_type  as a member type

template <bool Has_result_type, typename Functor>
struct Maybe_get_result_type {};

template <typename Functor>
struct Maybe_get_result_type <true, Functor>
{ typedef typename Functor::result_type result_type; };

template <typename Functor>
struct Weak_result_type_impl
    : Maybe_get_result_type <has_result_type<Functor>::value, Functor>
{ };

So, for a functor, it is important for that functor to have a member type called result_type in order for this type trait to work. 
Well, that's kind of not-so-generic, isn't it ? Yeah, there are other ways to get the result_type from a functor:

template <typename T, typename = void_t<>> struct Functor_return_type {};

template <typename T, typename... Args>
struct Functor_return_type<T(Args...),
                           void_t<decltype(
                                    std::declval<T>().operator()(
                                                    std::declval<Args>()...
                                  )  )
                           >>
{
 using result_type = decltype(std::declval<T>().operator()(std::declval<Args>()...));
};

class Functor {
public:
  int operator()(int v) {
    return 42;
  }
};

int main() {
  static_assert (std::is_same<Functor_return_type<Functor(int)>::result_type, int>::value, "");
  return 0;
}

This is somewhat what std::result_of does which is bit more complicated than what we have done here. So, the point was just to show that there are ways to get the return type from the functor or target callable object, but with a different interface (We had to provide expected argument types for the above.).

6. Metafunction to check if all is true

This basically means to check if all the checks passed into a metafunction evaluates to true or not. libstd++ makes use of '__and_', but here we will make use of the bool-trick, which I found here on StackOverflow.

template <bool... B>
struct bool_pack {};

template <bool... V>
using all_true = std::is_same<bool_pack<true, V...>, bool_pack<V..., true>>;

We will see a use case for it soon.

7. Metafunction to check if parameters passed are convertible to another.

We do have a standard meta function std::is_convertible<From, To> which evaluates to true if type From is implicitly convertible to To.

AllConvertible meta function works for variadic sets of template parameters and evaluates to true if and only if all the parameters provided in the first set are convertible into its respective parameters provided in the second set.

// To store the parameters as a list
template <typename... T> 
struct Pack : std::integral_constant<size_t, sizeof...(T)>
{};

template <typename From, typename To, bool = From::value == To::value>
struct AllConvertible : std::false_type
{ };

template <typename... From, typename... To>
struct AllConvertible<Pack<From...>, Pack<To...>, true>
    : all_true<std::is_convertible<From, To>...>
{ };
 

8. Metafunction Require

Require metafunction takes in a set of checks (same as bool-trick), but will fail to compile if any of the checks is false. Thus can be used as SFINAE, but maily used in mem_fn and std::function as hard compile time errors.

template <typename... Cond>
using Require = typename std::enable_if<all_true<Cond...>::value>::type;

What is std::mem_fn ?

In C++, for a class/struct, we can have pointers to its member functions and also pointers to its data members. Unlike regular function pointers, member function pointer is useless without an object to invoke it on. So, whenever you have the case for using member function pointer as a callback, one has to also provide the instance on which it needs to be called on. And, if you are in a situation wherein you want to make use of a pointer to a data member, you would have to use a slightly different dereferencing syntax. Also, member function/data pointers syntax are not pretty things to look at, but that's a secondary problem.

So, what mem_fn provides us is a consistent interface to create a callable object for both member function pointer and member data pointer.

What we get from that ? We can use it with STL algorithms now:

class Test {
public:
  void take() {
    std::cout << "Passed\n";
  }
};

int main() {
  std::array<Test, 3> arr = {Test(), Test(), Test()};
  std::for_each(std::begin(arr), std::end(arr), std::mem_fn(&Test::take));
  return 0;
}

It wouldn't be this easy (and beautiful) had we used raw member function pointers. 
Wait, I lied, there is a much more elegant way (and preferred) to do this using lambda expression:

  std::for_each(std::begin(arr), std::end(arr), [](const Test& t){ t.take(); });

Now, since mem_fn returns a callable object, it can also be used with std::function. 

std::mem_fn Implementation details

mem_fn is a template function and has the below signature:

template <typename Tp, typename Class>
Mem_fn<Tp Class::*>
mem_fn(Tp Class::*) noexcept;

It takes in a member function pointer or a member data pointer and returns an object of template class Mem_fn (capital 'M').

Definition of mem_fn:

template <typename Tp, typename Class>
Mem_fn <Tp Class::*>
mem_fn(Tp Class::* pm) noexcept
{
  return Mem_fn<Tp Class::*>(pm);
}

Pretty much the stuff explained before, nothing interesting. The interesting part would be to see, how Mem_fn provides a consistent interface for both member function pointers and member data pointers.

In the real implementation Mem_fn has several specializations  to deal with c-v qualifications, but as mentioned before, we will be looking at only one specialization i.e the one without c-v qualification involved. 

Also, Mem_fn is partially specialized to deal with pointers to member function and pointers to data members. This is how it provides a consistent call operator for both member function pointer and member data pointer.

Specialization for Member function

template <typename T> class Mem_Fn;

template <typename RetType, typename Class, typename... ArgTypes>
class Mem_Fn<RetType (Class::*) (ArgTypes...)>
{
  using Functor = RetType (Class::*) (ArgTypes...);

public:
  explicit Mem_Fn(Functor mf): func_(mf) { }

  // Handle lvalue reference to an object
  template <typename... Args,
            typename _R_ = AllConvertible<Pack<Args...>, Pack<ArgTypes...>>
           >
  RetType operator()(Class& obj, Args&&... args)
  {
    return (obj.*func_)(std::forward<Args>(args)...);
  }

  // Handle Rvalue reference
  template <typename... Args,
            typename _R_ = AllConvertible<Pack<Args...>, Pack<ArgTypes...>>
           >
  RetType operator()(Class&& obj, Args&&... args)
  {
    return (std::move(obj).*func_)(std::forward<Args>(args)...);
  }

  // Handle plain pointer to an object
  template <typename... Args,
            typename _R_ = AllConvertible<Pack<Args...>, Pack<ArgTypes...>>
           >
  RetType operator()(Class* obj, Args&&... args)
  {
    return (obj->*func_)(std::forward<Args>(args)...);
  }

  // Handle reference wrapper
  template <typename T, typename... Args,
            typename _R_ = AllConvertible<Pack<Args...>, Pack<ArgTypes...>>,
            typename std::enable_if<std::is_base_of<T, Class>::value>::type* = nullptr
           >
  RetType operator()(std::reference_wrapper<T> ref, Args&&... args)
  {
    return operator()(ref.get(), std::forward<Args>(args)...);
  }

  // Handle smart pointer
  // Maybe sometime later...... :)


private:
  // The member function pointer
  Functor func_;
};

With the knowledge of the type-traits we saw earlier it should be pretty easy to follow the template constraints put on the member functions. This is onle of the ways how c++ template metaprogramming offers tight type system checks.

Behaviour with Ref Qualified member functions

This is pretty basic stuff, except for one important behaviour/optimization which I surely would have missed implementing (but actually doesn't work, see next para) had I have had to implement this class.  Here, I am specifically talking about the overload for rvalue reference. Notice how the member function is called on the moved object:

 return (std::move(obj).*func_)(std::forward<Args>(args)...);

At first I expected it to call the rvalue ref-qualified version of the function (if provided of course). But that does not seem to be the case. The ref-qualifiers are tightly bound to the member function signature and unless explicitly provided, it would not call it.
Checkout this SO question for more details.

A peek into std::function

As the holy standard puts it:

The function class template provides polymorphic wrappers that generalize the notion of a function pointer. Wrappers can store, copy and call arbitrary callable objects, given a call signature, allowing functions to be first-class objects.

In the next section we will go about seeing how std::function is really implemented. So, stay tuned...

Part-2 of the series is HERE !