Why is allocator::rebind necessary when we have template template parameters?

Question

Every allocator class must have an interface similar to the following:

template<class T>
class allocator
{
    ...
    template<class Other>
    struct rebind { typedef allocator<Other> other; };
};

And classes that use allocators do something redundant like this:

template<class T, class Alloc = std::allocator<T> >
class vector { ... };

But why is this necessary?

In other words, couldn't they have just said:

template<class T>
class allocator { ... };

template<class T, template<class> class Alloc = std::allocator>
class vector { ... };

which is both more elegant, less redundant, and (in some similar situations) potentially safer?
Why did they go the rebind route, which also causes more redundancy (i.e. you have to say T twice)?

(Similar question goes to char_traits and the rest... although they don't all have rebind, they could still benefit from template template parameters.)

---

Edit:

But this won't work if you need more than 1 template parameter!

Actually, it works very well!

template<unsigned int PoolSize>
struct pool
{
    template<class T>
    struct allocator
    {
        T pool[PoolSize];

        ...
    };
};

Now if vector was only defined this way:

template<class T, template<class> class Alloc>
class vector { ... };

Then you could just say:

typedef vector<int, pool<1>::allocator> int_vector;

And it would work perfectly well, without needing you to (redundantly) say int twice.

And a rebind operation inside vector would just become Alloc<Other> instead of Alloc::template rebind<Other>::other.

Crafty

Note that in C++11 the requirement is relaxed and std::allocator_traits<SomeAllocator<T, Args...>>::rebind_alloc<U> is SomeAllocator<U, Args...> as a sensible default if SomeAllocator doesn't provide rebind. – Deposition

To the last point in the edit: How ugly the rebinding operation looks inside the vector implementation is irrelevant. You, the implementer, have the burden of making things easy for the user, even if it means very ugly and convoluted code under the hood. If you can bury the ugliness into the implementation to leave a cleaner interface, it is your job to do so. – Blear

@MikaelPersson: Sure, but is it even easier for the user? (How so? Examples/comparisons would be helpful! :D) – Crafty

The truth may be disappointing. The template rebinding idiom may just have been easier to implement with older compilers. I found template template argument passing only in newer STL code. So it is not that the implementors just not like template template arguments in general. What I personally like about template template arguments is that a specific intention is already visible at the interface level after only syntactical analysis, i.e. pass a kind of strategy for internal private generic use. – Karney

And if pool<1>::allocator<char>::rebind<int>::other need to be pool<4>::allocator<int>. – Invariable

It does not work when the allocator itself has more than one template parameter which is different from your pool<1>::allocator (where the outer instead of inner class has a template parameter). It could work if the additional template (type) parameters have defaults and the user is ok with using the defaults (raising the question why the additional template parameters are present in the first place). Furthermore, template parameters could be types or non-types. It will not work for non-types, which is very inconvenient for the allocator use case (e.g., alignment, padding, etc.). – Aguilar

Answer 1

A quoted text from Foundations of Algorithms in C++11, Volume 1, chap 4, p. 35 :

template <typename T> 
struct allocator 
{  
   template <typename U>  
   using  rebind = allocator<U>; 
}; 

sample usage :

allocator<int>::rebind<char> x;

---

In The C++ Programming Language, 4th edition, section 34.4.1, p. 998, commenting the 'classical' rebind member in default allocator class :

template<typename U>
     struct rebind { using other = allocator<U>;};

Bjarne Stroustrup writes this:

The curious rebind template is an archaic alias. It should have been:

template<typename U>
using other = allocator<U>;

However, allocator was defined before such aliases were supported by C++.

Devotee

+1 for citing stroustrup, by the way your link is broken – Educator

Answer 2

But why is this necessary?

What if your allocator class has more than one template argument?

That's pretty much it in terms of why it is generally discouraged to use template template arguments, in favor of using normal template arguments, even if it means a bit of redundancy at the instantiation site. In many cases (however, probably not for allocators), that argument might not always be a class template (e.g., a normal class with template member functions).

You might find it convenient (within the implementation of the container class) to use a template template parameter just because it simplifies some of the internal syntax. However, if the user has a multi-argument class template as an allocator he wants to use, but you require the user to provide an allocator which is a single-argument class template, you will in effect force him to create a wrapper for almost any new context in which he must use that allocator. This not only unscalable, it can also become very inconvenient to do. And, at this point, that solution is far from being the "elegant and less redundant" solution you originally thought it would be. Say you had an allocator with two arguments, which of the following is the easiest for the user?

std::vector<T, my_allocator<T,Arg2> > v1;

std::vector<T, my_allocator_wrapper<Arg2>::template type > v2;

You basically force the user to construct a lot of useless things (wrappers, template aliases, etc.) just to satisfy your implementation's demands. Requiring the author of a custom allocator class to supply a nested rebind template (which is just a trivial template alias) is far easier than all the contortions you require with the alternative approach.

Blear

"What if your allocator class has more than one template argument?" How about template<class P1, class P2> struct my_allocator_with_args { template<class T> my_allocator { ... }; };... now you just pass around my_allocator_with_args<Foo, Bar>::my_allocator as a template template parameter. – Crafty

Btw, this answer is a dupe of David's answer. (It's also a dupe of someone else's answer, but he deleted it pretty quickly.) – Crafty

Thanks, now see my edits. ;) If you still think it's a worse option, could you please edit your answer to include the "unscalable" case, and what the equivalent "scalable" version would be when we're using rebind instead? I think one of us is missing something. :) – Crafty

Btw, after you finish coming up with an example ;) there's another question: if this wasn't the kind of problem template template parameters were intended to solve, then what is their purpose in the first place? – Crafty

Answer 3

In your approach you are forcing the allocator to be a template with a single parameter, which might not be always the case. In many cases, allocators can be non-template, and the nested rebind can return the same type of the allocator. In other cases the allocator can have extra template arguments. This second case is the case of std::allocator<> which as all templates in the standard library is allowed to have extra template arguments as long as the implementation provides default values. Also note that the existence of rebind is optional in some cases, where allocator_traits can be used to obtain the rebound type.

The standard actually mentions that the nested rebind is actually just a templated typedef:

§17.6.3.5/3 Note A: The member class template rebind in the table above is effectively a typedef template. [ Note: In general, if the name Allocator is bound to SomeAllocator<T>, then Allocator::rebind<U>::other is the same type as SomeAllocator<U>, where someAllocator<T>::value_type is T and SomeAllocator<U>::value_type is U. — end note ] If Allocator is a class template instantiation of the form SomeAllocator<T, Args>, where Args is zero or more type arguments, and Allocator does not supply a rebind member template, the standard allocator_traits template uses SomeAllocator<U, Args> in place of Allocator:: rebind<U>::other by default. For allocator types that are not template instantiations of the above form, no default is provided.

Shultz

As far as I can see, the number of template parameters couldn't have possibly been an issue -- if you need a different number of parameters then you can just make a wrapper that only needs 1 parameter, which is pretty darn easy and safer/less redundant than having rebind, right? – Crafty

@Mehrdad: you need to create a wrapper, actually more like N wrappers, possibly a lot of them, one for each possible combination of all other arguments that are used in the program, where in each wrapper all the other arguments would be bound to some value – Mccarthy

I don't understand why you say N... could you elaborate/give an example? – Crafty

@Mehrdad: Given a templated allocator that takes two arguments, T and Arg, how can you create a single one argument wrapper with an argument T for all possible values of Arg? – Mccarthy

Uh, nested template classes? The outer one takes Arg, the inner one takes T. You pass around the inner one as a template template parameter... achieves the same exact goals as before, gives you the number of template args you need, but still works the way you need it to. template<class P1, class P2> struct my_allocator_with_args { template<class T> my_allocator { ... }; };... now you just pass around my_allocator_with_args<Foo, Bar>::my_allocator as a template template parameter. I don't see where the N comes in. – Crafty

@Mehrdad: Would that be any simpler than what the standard requires now? (considering that rebind is not even required in most cases?) I might be slightly simpler in the simple case: a single template argument, at the cost of higher complexity when there are more template arguments. Not impossible, but I don't see that you would be winning much, and I don't see immediately how you could implement allocator_traits to avoid requiring the extra cost on the programmer side (in the current version there are few cases where you do need to write rebind) – Mccarthy

(BTW, N comes from not having though much on the solution, and the trivial implementation would be a binded single argument template :)) – Mccarthy

Now that we've established it's 1 and not N... "Would that be any simpler than what the standard requires now?" It would definitely be simpler in a lot of cases, namely where you simply don't need more parameters (in fact, I would argue it's never more complicated, because rebind forces you to repeat all the template args), and it would be always less redundant. Furthermore, it seems like this is exactly the sort of problem that template template parameters are meant to solve in the first place, so why would you avoid them? – Crafty

@Mehrdad: I am not sure you understand that rebind is not a requirement, but rather a tool to enable more flexibility allowing for allocators where you cannot/don't want to conform to what allocator_traits does to remap the allocator. Also note that the number of keystrokes is not a measure of complexity, rebind might require you to repeat all arguments, but it is conceptually simpler than having to provide two levels of template classes where the outer level is there only to fix some arguments (in a similar way that std::bind does for function arguments) – Mccarthy

Yes, I get the point, you're familiar with C++11. Great. But I am not sure you understand that allocator_traits didn't even exist when rebind was invented... why do you keep on bringing up a C++11-only feature when it's blatantly irrelevant to the question? – Crafty

@Mehrdad: I am familiar both with C++03 and C++11, in fact more familiar with C++03. I am not so familiar with allocators though, as in C++03 the allocator model is very limited and we have our own (non-conforming) standard library that implements the Lakos allocator model. I have now looked at the C++03 standard and there is no allocator_traits. – Mccarthy

... at any rate you seem to have fixated on rebind as something to remove for its complexity (really, take a look at it: a simple nested template with a single typedef, how complex is that?). Do you really believe that my_alloc_with_args<P,Q>::allocator is better than my_alloc? Note that the outer template is empty, present only as a hack to inject the arguments into the nested template. The name of the outer template is misleading, my_alloc_with_args is not an allocator is an argument binder just to match an interface. Do you really find it better? – Mccarthy

Yes, because it's less redundant and safer -- did you not read this? Can you tell me how template template parameters were supposed to be used, if this was not their use case? – Crafty

@Mehrdad: I have read that, and the book by Alexandrescu, a couple of times actually. As I already mentioned, we use a slightly different form of allocator, but at any rate, in our case the allocator is not templated (the type, the allocate/deallocate member functions are). That same approach can be taken with standard allocators in C++03. I wonder out there, how many cases there are with none, 1, multiple template arguments. Also note that the potential risks that safer tries to achieve are easily detectable at compile time, and thus not much of an issue... – Mccarthy

... if the template argument passed in is wrong, the signature of allocate will not match and the compiler will complain [I don't recall the exact use case in MC++D, and whether this would apply or not]. I don't find that much more safe. And having to extract the parameters to an enclosing template just looks horrible (opinion). Again, try to document in a single sentence what the outer and the inner templates with your wrapper are, try to explain to someone learning why you must have an empty outer template whose only purpose is holding an internal template function. – Mccarthy

... Regarding the use of template template parameters, I have never found a use for them --that is, something that did not make more sense in my mind/design without a template template parameter. – Mccarthy

Answer 4

Suppose you want to write a function taking all sorts of vectors.

Then it is much more convenient being able to write

template <class T, class A>
void f (std::vector <T, A> vec) {
   // ...
}

than having to write

template <class T, template <class> class A>
void f (std::vector <T, A> vec) {
   // ...
}

In most of the cases, such a function does not care about the allocator anyway.

Further note that allocators are not required to be a template. You could write separate classes for particular types that need to be allocated.

An even more convenient way of designing allocators would probably have been

struct MyAllocator { 
   template <class T>
   class Core {
      // allocator code here
   };
};

Then it would have been possible to write

std::vector <int, MyAllocator> vec;

rather than the somewhat misleading expression

std::vector <int, MyAllocator<int> > vec;

I am not sure whether the above MyAllocator is permitted to be used as an allocator after adding a rebind, i.e. whether the following is a valid allocator class:

struct MyAllocator { 
   template <class T>
   class Core {
      // allocator code here
   };

   template <class T>
   struct rebind { using other=Core<T>; };
};

Cupro

JhonB,why not just using other = core<T> without struct? – Dustydusza