What Does (Template) Rebind<> Do

what does (template) rebind do?

The _Alloc template is used to obtain objects of some type. The container may have an internal need to allocate objects of a different type. For example, when you have a std::list<T, A>, the allocator A is meant to allocate objects of type T but the std::list<T, A> actually needs to allocate objects of some node type. Calling the node type _Ty, the std::list<T, A> needs to get hold of an allocator for _Ty objects which is using the allocation mechanism provided by A. Using

typename _A::template rebind<_Ty>::other

specifies the corresponding type. Now, there are a few syntactic annoyances in this declaration:

Since rebind is a member template of _A and _A is a template argument, the rebind becomes a dependent name. To indicate that a dependent name is a template, it needs to be prefixed by template. Without the template keyword the < would be considered to be the less-than operator.
The name other also depends on a template argument, i.e., it is also a dependent name. To indicate that a dependent name is a type, the typename keyword is needed.

What is the purpose of pointer rebind?

The answer to this question comes from allocators, too. Let's take a look at how _Rebind_pointer_t is defined:

template <class _Ptr, class _Ty>
using _Rebind_pointer_t = typename pointer_traits<_Ptr>::template rebind<_Ty>;

That is, we have

template <class _Value_type, class _Voidptr>
struct _List_node {
    using _Nodeptr = typename pointer_traits<_Voidptr>::template rebind<_List_node>;
    // ...
}

Now let's take a look at how _List_node is used:

using _Node = _List_node<_Ty, typename _Alty_traits::void_pointer>;

Effectively, we rebind allocator's void_pointer to _List_node pointer. This trick is needed to support allocators that use fancy pointers internally.

One such example can be found in Boost.Interprocess library. It has boost::interprocess::allocator:

An STL compatible allocator that uses a segment manager as memory source. The internal pointer type will of the same type (raw, smart) as typename SegmentManager::void_pointer type. This allows placing the allocator in shared memory, memory mapped-files, etc...

For example, we can write

namespace bi = boost::interprocess;
using Allocator = bi::allocator<int, bi::managed_shared_memory::segment_manager>;
std::list<int, Allocator> list(/* allocator object */);

Now std::allocator_traits<decltype(list)::allocator_type>::void_pointer will be not void* as with default allocator, but boost::interprocess::offset_ptr<void, ...>. As a result, _Nodeptr will be not _Nodeptr*, but boost::interprocess::offset_ptr<_Nodeptr, ...>.

Why does this allocator not work with `std::allocate_shared`? Bizarre template substitution errors

Thanks to @Nicol Bolas and @Igor Tandetnik, I was able to figure out the reason. As they said, by inheriting an allocator you also inherit the rebind struct which is actually rebinding for the base class. This isn't what we want (allocators I guess don't work well with inheritance), so we'd have to add the following to get this to work:

template <typename T>
class bar_allocator : public std::allocator<T> {
public:
    bar_allocator() = default;

    template <typename U>
    bar_allocator(const bar_allocator<U>& other) : std::allocator<T>(other){
    }

    template<class U>
    struct rebind {
        typedef bar_allocator<U> other;
    };
};

Demo

What are some uses of template template parameters?

I think you need to use template template syntax to pass a parameter whose type is a template dependent on another template like this:

template <template<class> class H, class S>
void f(const H<S> &value) {
}

Here, H is a template, but I wanted this function to deal with all specializations of H.

NOTE: I've been programming c++ for many years and have only needed this once. I find that it is a rarely needed feature (of course handy when you need it!).

I've been trying to think of good examples, and to be honest, most of the time this isn't necessary, but let's contrive an example. Let's pretend that std::vector doesn't have a typedef value_type.

So how would you write a function which can create variables of the right type for the vectors elements? This would work.

template <template<class, class> class V, class T, class A>
void f(V<T, A> &v) {
    // This can be "typename V<T, A>::value_type",
    // but we are pretending we don't have it

    T temp = v.back();
    v.pop_back();
    // Do some work on temp

    std::cout << temp << std::endl;
}

NOTE: std::vector has two template parameters, type, and allocator, so we had to accept both of them. Fortunately, because of type deduction, we won't need to write out the exact type explicitly.

which you can use like this:

f<std::vector, int>(v); // v is of type std::vector<int> using any allocator

or better yet, we can just use:

f(v); // everything is deduced, f can deal with a vector of any type!

UPDATE: Even this contrived example, while illustrative, is no longer an amazing example due to c++11 introducing auto. Now the same function can be written as:

template <class Cont>
void f(Cont &v) {

    auto temp = v.back();
    v.pop_back();
    // Do some work on temp

    std::cout << temp << std::endl;
}

which is how I'd prefer to write this type of code.

How to use rebind with custom allocator and custom list

These are the requirements for an allocator: http://en.cppreference.com/w/cpp/concept/Allocator

Notice that template rebind is optional.

Here is a list of what a container must have in order to qualify for the concept. http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer

Yes, gasp. I have searched in vain for a simple, or at least minimalist example. If all you need is a linked list, and you can use C++11 or later, use std::forward_list.

The following works in the example given.

template<typename T, typename MyAllocator = std::allocator<T>>
class MyList
{
private:
    using node_alloc_t = typename std::allocator_traits<MyAllocator>::
        template rebind_alloc<Node<T>>;

    // create an object of type node allocator
    node_alloc_t node_alloc;
    // etc ....

public:

    template<typename T>
    void emplace(T v)
    {
        Node<T>* new_Node = node_alloc.allocate(1);

        // Etc...
    }

// etc...
};

All together now...

#include <memory>
#include <iostream>

template<typename T>
struct Node
{

    Node() : m_next(nullptr) {}

    Node(T const &t) :
        m_value(t),
        m_next(nullptr)
    {}

    T m_value;
    Node<T>* m_next;
};

template<typename T, typename MyAllocator = std::allocator<T>>
class MyList
{
private:
    using node_alloc_t = typename std::allocator_traits<MyAllocator>::
        template rebind_alloc<Node<T>>;

    // create an object of type node allocator
    node_alloc_t node_alloc;

public:

    class Iterator
    {
    private:
        Node<T>* m_Node;
    public:

        Iterator(Node<T>* Node) : m_Node(Node) {};

        bool operator==(const Iterator& other)
        {
            return this == &other || m_Node == other.m_Node;
        }

        bool operator!=(const Iterator& other)
        {
            return !operator==(other);
        }

        T operator*()
        {
            if (m_Node)
            {
                return m_Node->m_value;
            }
            return T();
        }

        Iterator operator++()
        {
            Iterator i = *this;
            if (m_Node)
            {
                m_Node = m_Node->m_next;
            }
            return i;
        }

    };

    template<typename T>
    void emplace(T v)
    {

        Node<T>* new_Node = node_alloc.allocate(1);
        node_alloc.construct(new_Node, v);
        if (m_head)
        {
            m_tail->m_next = new_Node;
        }
        else {
            m_head = new_Node;
            new_Node->m_next = nullptr;
        }
        m_tail = new_Node;
    }

    Iterator begin() const
    {
        return Iterator(m_head);
    }

    Iterator end() const
    {
        return Iterator(nullptr);
    }

}; 

int main()
{   
    MyList<int> my_list; 
    for (int i = 0; i < 10; ++i)
    {
        my_list.emplace(i);
    }
    for (auto i : my_list) {
        std::cout << i << std::endl;
    }
    return 0;
}

std::function/bind like type-erasure without Standard C++ library

A solid, efficient, std::function<R(Args...)> replacement isn't hard to write.

As we are embedded, we want to avoid allocating memory. So I'd write a small_task< Signature, size_t sz, size_t algn >. It creates a buffer of size sz and alignment algn in which it stores its erased objects.

It also stores a mover, a destroyer, and an invoker function pointer. These pointers can either be locally within the small_task (maximal locality), or within a manual struct vtable { /*...*/ } const* table.

template<class Sig, size_t sz, size_t algn>
struct small_task;

template<class R, class...Args, size_t sz, size_t algn>
struct small_task<R(Args...), sz, algn>{
  struct vtable_t {
    void(*mover)(void* src, void* dest);
    void(*destroyer)(void*);
    R(*invoke)(void const* t, Args&&...args);
    template<class T>
    static vtable_t const* get() {
      static const vtable_t table = {
        [](void* src, void*dest) {
          new(dest) T(std::move(*static_cast<T*>(src)));
        },
        [](void* t){ static_cast<T*>(t)->~T(); },
        [](void const* t, Args&&...args)->R {
          return (*static_cast<T const*>(t))(std::forward<Args>(args)...);
        }
      };
      return &table;
    }
  };
  vtable_t const* table = nullptr;
  std::aligned_storage_t<sz, algn> data;
  template<class F,
    class dF=std::decay_t<F>,
    // don't use this ctor on own type:
    std::enable_if_t<!std::is_same<dF, small_task>{}>* = nullptr,
    // use this ctor only if the call is legal:
    std::enable_if_t<std::is_convertible<
      std::result_of_t<dF const&(Args...)>, R
    >{}>* = nullptr
  >
  small_task( F&& f ):
    table( vtable_t::template get<dF>() )
  {
    // a higher quality small_task would handle null function pointers
    // and other "nullable" callables, and construct as a null small_task

    static_assert( sizeof(dF) <= sz, "object too large" );
    static_assert( alignof(dF) <= algn, "object too aligned" );
    new(&data) dF(std::forward<F>(f));
  }
  // I find this overload to be useful, as it forces some
  // functions to resolve their overloads nicely:
  // small_task( R(*)(Args...) )
  ~small_task() {
    if (table)
      table->destroyer(&data);
  }
  small_task(small_task&& o):
    table(o.table)
  {
    if (table)
      table->mover(&o.data, &data);
  }
  small_task(){}
  small_task& operator=(small_task&& o){
    // this is a bit rude and not very exception safe
    // you can do better:
    this->~small_task();
    new(this) small_task( std::move(o) );
    return *this;
  }
  explicit operator bool()const{return table;}
  R operator()(Args...args)const{
    return table->invoke(&data, std::forward<Args>(args)...);
  }
};

template<class Sig>
using task = small_task<Sig, sizeof(void*)*4, alignof(void*) >;

live example.

Another thing missing is a high quality void(Args...) that doesn't care if the passed-in callable has a return value.

The above task supports move, but not copy. Adding copy means that everything stored must be copyable, and requires another function in the vtable (with an implementation similar to move, except src is const and no std::move).

A small amount of C++14 was used, namely the enable_if_t and decay_t aliases and similar. They can be easily written in C++11, or replaced with typename std::enable_if<?>::type.

bind is best replaced with lambdas, honestly. I don't use it even on non-embedded systems.

Another improvement would be to teach it how to deal with small_tasks that are smaller/less aligned by storing their vtable pointer rather than copying it into the data buffer, and wrapping it in another vtable. That would encourage using small_tasks that are just barely large enough for your problem set.

Converting member functions to function pointers is not only undefined behavior, often the calling convention of a function is different than a member function. In particular, this is passed in a particular register under some calling conventions.

Such differences can be subtle, and can crop up when you change unrelated code, or the compiler version changes, or whatever else. So I'd avoid that unless you have little other choice.

As noted, the platform lacks libraries. Every use of std above is tiny, so I'll just write them:

template<class T>struct tag{using type=T;};
template<class Tag>using type_t=typename Tag::type;
using size_t=decltype(sizeof(int));

move

template<class T>
T&& move(T&t){return static_cast<T&&>(t);}

forward

template<class T>
struct remove_reference:tag<T>{};
template<class T>
struct remove_reference<T&>:tag<T>{};
template<class T>using remove_reference_t=type_t<remove_reference<T>>;

template<class T>
T&& forward( remove_reference_t<T>& t ) {
  return static_cast<T&&>(t);
}
template<class T>
T&& forward( remove_reference_t<T>&& t ) {
  return static_cast<T&&>(t);
}

decay

template<class T>
struct remove_const:tag<T>{};
template<class T>
struct remove_const<T const>:tag<T>{};

template<class T>
struct remove_volatile:tag<T>{};
template<class T>
struct remove_volatile<T volatile>:tag<T>{};

template<class T>
struct remove_cv:remove_const<type_t<remove_volatile<T>>>{};

template<class T>
struct decay3:remove_cv<T>{};
template<class R, class...Args>
struct decay3<R(Args...)>:tag<R(*)(Args...)>{};
template<class T>
struct decay2:decay3<T>{};
template<class T, size_t N>
struct decay2<T[N]>:tag<T*>{};

template<class T>
struct decay:decay2<remove_reference_t<T>>{};

template<class T>
using decay_t=type_t<decay<T>>;

is_convertible

template<class T>
T declval(); // no implementation

template<class T, T t>
struct integral_constant{
  static constexpr T value=t;
  constexpr integral_constant() {};
  constexpr operator T()const{ return value; }
  constexpr T operator()()const{ return value; }
};
template<bool b>
using bool_t=integral_constant<bool, b>;
using true_type=bool_t<true>;
using false_type=bool_t<false>;

template<class...>struct voider:tag<void>{};
template<class...Ts>using void_t=type_t<voider<Ts...>>;

namespace details {
  template<template<class...>class Z, class, class...Ts>
  struct can_apply:false_type{};
  template<template<class...>class Z, class...Ts>
  struct can_apply<Z, void_t<Z<Ts...>>, Ts...>:true_type{};
}
template<template<class...>class Z, class...Ts>
using can_apply = details::can_apply<Z, void, Ts...>;

namespace details {
  template<class From, class To>
  using try_convert = decltype( To{declval<From>()} );
}
template<class From, class To>
struct is_convertible : can_apply< details::try_convert, From, To > {};
template<>
struct is_convertible<void,void>:true_type{};

enable_if

template<bool, class=void>
struct enable_if {};
template<class T>
struct enable_if<true, T>:tag<T>{};
template<bool b, class T=void>
using enable_if_t=type_t<enable_if<b,T>>;

result_of

namespace details {
  template<class F, class...Args>
  using invoke_t = decltype( declval<F>()(declval<Args>()...) );

  template<class Sig,class=void>
  struct result_of {};
  template<class F, class...Args>
  struct result_of<F(Args...), void_t< invoke_t<F, Args...> > >:
    tag< invoke_t<F, Args...> >
  {};
}
template<class Sig>
using result_of = details::result_of<Sig>;
template<class Sig>
using result_of_t=type_t<result_of<Sig>>;

aligned_storage

template<size_t size, size_t align>
struct alignas(align) aligned_storage_t {
  char buff[size];
};

is_same

template<class A, class B>
struct is_same:false_type{};
template<class A>
struct is_same<A,A>:true_type{};

live example, about a dozen lines per std library template I needed.

I would put this "std library reimplementation" into namespace notstd to make it clear what is going on.

If you can, use a linker that folds identical functions together, like the gold linker. template metaprogramming can cause binary bloat without a solid linker to strip it.

std::function and std::bind: what are they, and when should they be used?

std::bind is for partial function application.

That is, suppose you have a function object f which takes 3 arguments:

f(a,b,c);

You want a new function object which only takes two arguments, defined as:

g(a,b) := f(a, 4, b);

g is a "partial application" of the function f: the middle argument has already been specified, and there are two left to go.

You can use std::bind to get g:

auto g = bind(f, _1, 4, _2);

This is more concise than actually writing a functor class to do it.

There are further examples in the article you link to. You generally use it when you need to pass a functor to some algorithm. You have a function or functor that almost does the job you want, but is more configurable (i.e. has more parameters) than the algorithm uses. So you bind arguments to some of the parameters, and leave the rest for the algorithm to fill in:

// raise every value in vec to the power of 7
std::transform(vec.begin(), vec.end(), some_output, std::bind(std::pow, _1, 7));

Here, pow takes two parameters and can raise to any power, but all we care about is raising to the power of 7.

As an occasional use that isn't partial function application, bind can also re-order the arguments to a function:

auto memcpy_with_the_parameters_in_the_right_flipping_order = bind(memcpy, _2, _1, _3);

I don't recommend using it just because you don't like the API, but it has potential practical uses for example because:

not2(bind(less<T>, _2, _1));

is a less-than-or-equal function (assuming a total order, blah blah). This example normally isn't necessary since there already is a std::less_equal (it uses the <= operator rather than <, so if they aren't consistent then you might need this, and you might also need to visit the author of the class with a cluestick). It's the sort of transformation that comes up if you're using a functional style of programming, though.

What Does (Template) Rebind<> Do