November 8, 2014 at 23:37Perfect Transmission and Universal Links in C ++
- Transfer
Recently, a link to an article by Eli Bendersky "Perfect forwarding and universal references in C ++" was published on isocpp.org . This short article has a simple answer to a simple question - for what tasks and how to use rvalue links.
One of the innovations of C ++ 11 that aims to increase the efficiency of programs is the emplace family of methods for STL containers. For example, the emplace_back method (almost an analogue of the push_back method) and the emplace method (almost an analogue of the insert method) appeared in std :: vector.
Here is a small example showing the purpose of these new methods:
If you follow the calls to the constructors and destructors of the MyKlass class, during a call to push_back you can see the following:
As you can see, quite a lot of work is being done, a large amount of which is not very necessary, since the object passed to the push_back method is obviously an rvalue reference and is destroyed immediately after this expression is executed. Thus, there is no reason to create and destroy a temporary object. Why, in this case, not create an object immediately inside the vector? This is exactly what the emplace_back method does. For the expression from the example v.emplace_back (2, 3.14f), only one constructor will be executed, which creates an object inside the vector. Without using temporary objects. emplace_back itself calls the MyKlass constructor and passes the necessary arguments to it. This behavior was made possible thanks to two innovations of C ++ 11: templates with a variable number of arguments (variadic templates) and ideal transmission (perfect forwarding).
Suppose there is some func function that takes parameters of types E1, E2, ..., En. You need to create a wrapper function that accepts the same set of parameters. In other words, to define a function that will pass the received parameters to another function without creating temporary variables, that is, it will perform an ideal transfer.
In order to specify the problem, consider the emplace_back method, which was described above. vector :: emplace_back passes its parameters to the constructor T without knowing anything about what T. is.
The next step is to consider a few examples showing how you can achieve this behavior without using C ++ 11 innovations. For simplicity, we will not take into account the need to use templates with a variable number of argument parameters; suppose that you need to pass only two arguments.
The first option that comes to mind:
But this obviously will not work as needed if func takes parameters by reference, since wrapper takes parameters by value. In this case, if func changes the parameters received by reference, this will not affect the parameters passed to the wrapper (copies created inside the wrapper will be changed).
Well, then we can redo the wrapper so that it accepts parameters by reference. This will not be an obstacle if func accepts not by reference, but by value, since the func inside the wrapper will make the necessary copies for itself.
Here is another problem. Rvalue cannot be passed to a function as a reference. Thus, a completely trivial call will not compile:
And right away, if the idea came to make these links constant - this also will not solve the problem. Because func may require non-constant references as parameters.
All that remains is the crude approach used in some libraries: to overload the function for constant non-constant links:
Exponential growth. You can imagine how much fun it will deliver when you need to process some reasonable amount of parameters of real functions. To make matters worse, C ++ 11 adds rvalue links, which also need to be considered in the wrapper function, and this is definitely not an extensible solution.
To explain how perfect transfer is implemented in C ++ 11, you first need to understand two new rules that have been added to this programming language.
Let's start with a simple one - link collapsing. As you know, taking a link to a link in C ++ is not allowed, but this can sometimes happen when implementing templates:
What happens if you call this function as follows:
When instantiating a template, T is set to int &. What type will the variable k inside the function be? The compiler will "see" int & & - and since this is a forbidden construct, the compiler simply converts this to a regular link. In fact, before C ++ 11, this behavior was not standardized, but many compilers accepted and converted such code, since it is often found in metaprogramming. After rvalue links were added in C ++ 11, it became important to determine the behavior when combining different types of links (for example, what does int && &? Mean).
So the rule of link compression appeared. This rule is very simple - a single ampersand (&) always wins. So - (& and &) is (&), just like (&& and &), and (& and &&). The only case in which compression results in (&&) is (&& and &&). This rule can be compared with the result of a logical OR, in which & is 1, and && is 0.
Another C ++ add-on that is directly related to this topic is the special type deduction rules for rvalue links in various cases [1]. Consider an example of a template function:
Do not let the double ampersand fool you - t is not an rvalue reference here [2]. When it appears in this situation (when a special type inference is needed), T && takes on a special meaning - when func is instantiated, T changes depending on the type passed. If an lvalue of type U has been passed, then T becomes U &. If U is an rvalue, then T becomes just U. Example:
This rule may seem unusual and even strange. It is. But, nevertheless, this rule becomes quite obvious when it comes to understanding that this rule helps solve the problem of perfect transmission.
Now let's get back to our wrapper template function described above. Here's how it should be implemented using C ++ 11:
And here is how forward [3] is implemented:
Consider the following call:
Consider the first argument (the second is similar): ii is an lvalue, so T1 becomes int & in accordance with the rule of special type inference. It turns out a call to func (forward(e1), ...). Thus, the forward pattern is instantiated by type int & and we get the following version of this function:
Time to apply link compression rule:
In other words, the argument is passed by reference to func, as required by lvalue.
The following example:
Here the arguments are rvalue, so T1 becomes int. We get a call to func (forward (e1), ...). Thus, the forward template function is instantiated by type int and we get the following version of the function:
The argument obtained by reference is converted to an rvalue reference, which is what is required to be received from forward.
The forward forward function can be thought of as some kind of wrapper over static_cast(t) when T can take the value U & or U &&, depending on the type of input argument (lvalue or rvalue). Now wrapper is one template that handles any combination of argument types.
The forward template function is implemented in C ++ 11, in the header file “utility”, in the std namespace.
Another point to note: using std :: remove_reference. In fact, forward can be implemented without using this function. Link compression does all the work, so using std :: remove_reference is redundant for this. However, this function allows you to print T & t in a situation where this type cannot be deduced (according to the C ++ standard, 14.8.2.5), so you must explicitly specify the template parameters when calling std :: forward.
In his speeches, blog posts, and books, Scott Myers gives the name “universal reference” for rvalue links that are in the context of type inference. Successful name or not, it is difficult to say. For me, the first time I read a chapter on this topic from the new book, Effective C ++, I felt confused. More or less, everything became clear later, when I figured out the underlying mechanisms (link compression and special type inference rules).
The trap is that the phrase “universal references” [4] is certainly more concise and beautiful than “rvalue links in the context of type inference”. But if you really want to understand some code, you won’t be able to avoid a full description.
Perfect transmission is quite useful because it makes programming at a higher level possible. Higher-order functions are functions that can take other functions as arguments or return them. Without a perfect pass, applying higher-order functions is quite burdensome, as there is no convenient way to pass arguments to a function inside a wrapper function. By the term “function”, here, in addition to the functions themselves, I also mean classes whose constructors are actually functions as well.
At the beginning of this article, I described the emplace_back container method. Another good example is the standard template function make_unique, which I described in a previous article :
I admit honestly that in that article I simply ignored the strange double ampersand and focused on the variable number of template arguments. But now it’s completely easy to fully understand the code. It goes without saying that the ideal pass and templates with a variable number of arguments are very often used together, because, in most cases, it is not known how many arguments the function or constructor takes with which we pass these arguments.
As an example with much more complex use of ideal transfer, you can see the implementation of std :: bind.
Here are some sources that have helped me a lot in preparing the material:
Notes:
[1] Auto and decltype can also be used, here I describe only the case of using a template.
[2] I consider the decision of the C ++ standardization committee to choose notation for rvalue links (overloading &&) unsuccessful. Scott Myers admitted in his speech (and commented a bit on his blog) that after 3 years this material is still not easy to learn. And Björn Straustrup in The 4th edition of “The C ++ Programming Language”, when describing std :: forward, forgot the explicit indication of the template argument. It can be concluded that this is indeed a rather difficult area.
[3] This is a simplified version of std :: forward from STL C ++ 11. There is still an additional version, overloaded explicitly for rvalue arguments. I'm still trying to figure out why it is needed. Let me know if you have any idea.
[4] Forwarding references is another designation that I have come across
From the translator: at CppCon2014, many (including Meyers, Straustrup, Saffer) decided to use the term forwarding references instead of universal references .
A couple of articles on this topic:
A brief introduction to rvalue links
"Universal" links in C ++ 11 or T && do not always mean "Rvalue Reference"
One of the innovations of C ++ 11 that aims to increase the efficiency of programs is the emplace family of methods for STL containers. For example, the emplace_back method (almost an analogue of the push_back method) and the emplace method (almost an analogue of the insert method) appeared in std :: vector.
Here is a small example showing the purpose of these new methods:
class MyKlass {
public:
MyKlass(int ii_, float ff_) {...}
private:
{...}
};
some function {
std::vector v;
v.push_back(MyKlass(2, 3.14f));
v.emplace_back(2, 3.14f);
}
If you follow the calls to the constructors and destructors of the MyKlass class, during a call to push_back you can see the following:
- First, the constructor of the temporary object of the MyKlass class is executed
- Then, for the object located directly inside the vector, the move constructor is called (if one is defined in MyClass, if not defined, then the copy constructor is called)
- Temporal Object Destructor
As you can see, quite a lot of work is being done, a large amount of which is not very necessary, since the object passed to the push_back method is obviously an rvalue reference and is destroyed immediately after this expression is executed. Thus, there is no reason to create and destroy a temporary object. Why, in this case, not create an object immediately inside the vector? This is exactly what the emplace_back method does. For the expression from the example v.emplace_back (2, 3.14f), only one constructor will be executed, which creates an object inside the vector. Without using temporary objects. emplace_back itself calls the MyKlass constructor and passes the necessary arguments to it. This behavior was made possible thanks to two innovations of C ++ 11: templates with a variable number of arguments (variadic templates) and ideal transmission (perfect forwarding).
Perfect transmission problem
Suppose there is some func function that takes parameters of types E1, E2, ..., En. You need to create a wrapper function that accepts the same set of parameters. In other words, to define a function that will pass the received parameters to another function without creating temporary variables, that is, it will perform an ideal transfer.
In order to specify the problem, consider the emplace_back method, which was described above. vector :: emplace_back passes its parameters to the constructor T without knowing anything about what T. is.
The next step is to consider a few examples showing how you can achieve this behavior without using C ++ 11 innovations. For simplicity, we will not take into account the need to use templates with a variable number of argument parameters; suppose that you need to pass only two arguments.
The first option that comes to mind:
template
void wrapper(T1 e1, T2 e2) {
func(e1, e2);
}
But this obviously will not work as needed if func takes parameters by reference, since wrapper takes parameters by value. In this case, if func changes the parameters received by reference, this will not affect the parameters passed to the wrapper (copies created inside the wrapper will be changed).
Well, then we can redo the wrapper so that it accepts parameters by reference. This will not be an obstacle if func accepts not by reference, but by value, since the func inside the wrapper will make the necessary copies for itself.
template
void wrapper(T1& e1, T2& e2) {
func(e1, e2);
}
Here is another problem. Rvalue cannot be passed to a function as a reference. Thus, a completely trivial call will not compile:
wrapper(42, 3.14f); // ошибка: инициализация неконстантной ссылки rvalue-значением
wrapper(i, foo_returning_float()); // та же ошибка
And right away, if the idea came to make these links constant - this also will not solve the problem. Because func may require non-constant references as parameters.
All that remains is the crude approach used in some libraries: to overload the function for constant non-constant links:
template
void wrapper(T1& e1, T2& e2) { func(e1, e2); }
template
void wrapper(const T1& e1, T2& e2) { func(e1, e2); }
template
void wrapper(T1& e1, const T2& e2) { func(e1, e2); }
template
void wrapper(const T1& e1, const T2& e2) { func(e1, e2); }
Exponential growth. You can imagine how much fun it will deliver when you need to process some reasonable amount of parameters of real functions. To make matters worse, C ++ 11 adds rvalue links, which also need to be considered in the wrapper function, and this is definitely not an extensible solution.
Link compression and special type inference for rvalue links
To explain how perfect transfer is implemented in C ++ 11, you first need to understand two new rules that have been added to this programming language.
Let's start with a simple one - link collapsing. As you know, taking a link to a link in C ++ is not allowed, but this can sometimes happen when implementing templates:
template
void baz(T t) {
T& k = t;
}
What happens if you call this function as follows:
int ii = 4;
baz(ii);
When instantiating a template, T is set to int &. What type will the variable k inside the function be? The compiler will "see" int & & - and since this is a forbidden construct, the compiler simply converts this to a regular link. In fact, before C ++ 11, this behavior was not standardized, but many compilers accepted and converted such code, since it is often found in metaprogramming. After rvalue links were added in C ++ 11, it became important to determine the behavior when combining different types of links (for example, what does int && &? Mean).
So the rule of link compression appeared. This rule is very simple - a single ampersand (&) always wins. So - (& and &) is (&), just like (&& and &), and (& and &&). The only case in which compression results in (&&) is (&& and &&). This rule can be compared with the result of a logical OR, in which & is 1, and && is 0.
Another C ++ add-on that is directly related to this topic is the special type deduction rules for rvalue links in various cases [1]. Consider an example of a template function:
template
void func(T&& t) {
}
Do not let the double ampersand fool you - t is not an rvalue reference here [2]. When it appears in this situation (when a special type inference is needed), T && takes on a special meaning - when func is instantiated, T changes depending on the type passed. If an lvalue of type U has been passed, then T becomes U &. If U is an rvalue, then T becomes just U. Example:
func(4); // 4 это rvalue: T становится int
double d = 3.14;
func(d); // d это lvalue; T становится double&
float f() {...}
func(f()); // f() это rvalue; T становится float
int bar(int i) {
func(i); // i это lvalue; T становится int&
}
This rule may seem unusual and even strange. It is. But, nevertheless, this rule becomes quite obvious when it comes to understanding that this rule helps solve the problem of perfect transmission.
Implementing perfect transfer using std :: forward
Now let's get back to our wrapper template function described above. Here's how it should be implemented using C ++ 11:
template
void wrapper(T1&& e1, T2&& e2) {
func(forward(e1), forward(e2));
}
And here is how forward [3] is implemented:
template
T&& forward(typename std::remove_reference::type& t) noexcept {
return static_cast(t);
}
Consider the following call:
int ii ...;
float ff ...;
wrapper(ii, ff);
Consider the first argument (the second is similar): ii is an lvalue, so T1 becomes int & in accordance with the rule of special type inference. It turns out a call to func (forward
int& && forward(int& t) noexcept {
return static_cast(t);
}
Time to apply link compression rule:
int& forward(int& t) noexcept {
return static_cast(t);
}
In other words, the argument is passed by reference to func, as required by lvalue.
The following example:
wrapper(42, 3.14f);
Here the arguments are rvalue, so T1 becomes int. We get a call to func (forward (e1), ...). Thus, the forward template function is instantiated by type int and we get the following version of the function:
int&& forward(int& t) noexcept {
return static_cast(t);
}
The argument obtained by reference is converted to an rvalue reference, which is what is required to be received from forward.
The forward forward function can be thought of as some kind of wrapper over static_cast
The forward template function is implemented in C ++ 11, in the header file “utility”, in the std namespace.
Another point to note: using std :: remove_reference. In fact, forward can be implemented without using this function. Link compression does all the work, so using std :: remove_reference is redundant for this. However, this function allows you to print T & t in a situation where this type cannot be deduced (according to the C ++ standard, 14.8.2.5), so you must explicitly specify the template parameters when calling std :: forward.
Universal Links
In his speeches, blog posts, and books, Scott Myers gives the name “universal reference” for rvalue links that are in the context of type inference. Successful name or not, it is difficult to say. For me, the first time I read a chapter on this topic from the new book, Effective C ++, I felt confused. More or less, everything became clear later, when I figured out the underlying mechanisms (link compression and special type inference rules).
The trap is that the phrase “universal references” [4] is certainly more concise and beautiful than “rvalue links in the context of type inference”. But if you really want to understand some code, you won’t be able to avoid a full description.
Perfect Transmission Examples
Perfect transmission is quite useful because it makes programming at a higher level possible. Higher-order functions are functions that can take other functions as arguments or return them. Without a perfect pass, applying higher-order functions is quite burdensome, as there is no convenient way to pass arguments to a function inside a wrapper function. By the term “function”, here, in addition to the functions themselves, I also mean classes whose constructors are actually functions as well.
At the beginning of this article, I described the emplace_back container method. Another good example is the standard template function make_unique, which I described in a previous article :
template
unique_ptr make_unique(Args&&... args)
{
return unique_ptr(new T(std::forward(args)...));
}
I admit honestly that in that article I simply ignored the strange double ampersand and focused on the variable number of template arguments. But now it’s completely easy to fully understand the code. It goes without saying that the ideal pass and templates with a variable number of arguments are very often used together, because, in most cases, it is not known how many arguments the function or constructor takes with which we pass these arguments.
As an example with much more complex use of ideal transfer, you can see the implementation of std :: bind.
References to sources
Here are some sources that have helped me a lot in preparing the material:
- The 4th edition of "The C ++ Programming Language" by Bjarne Stroustrup
- The new "Effective Modern C ++" by Scott Myers. This book discusses "universal links" extensively. In fact, more than a fifth of this book is devoted to this topic.
- Technical paper n1385 : "The forwarding problem: Arguments."
- Thomas Becker C ++ Rvalue references explained - excellently written and very useful article
Notes:
[1] Auto and decltype can also be used, here I describe only the case of using a template.
[2] I consider the decision of the C ++ standardization committee to choose notation for rvalue links (overloading &&) unsuccessful. Scott Myers admitted in his speech (and commented a bit on his blog) that after 3 years this material is still not easy to learn. And Björn Straustrup in The 4th edition of “The C ++ Programming Language”, when describing std :: forward, forgot the explicit indication of the template argument. It can be concluded that this is indeed a rather difficult area.
[3] This is a simplified version of std :: forward from STL C ++ 11. There is still an additional version, overloaded explicitly for rvalue arguments. I'm still trying to figure out why it is needed. Let me know if you have any idea.
[4] Forwarding references is another designation that I have come across
From the translator: at CppCon2014, many (including Meyers, Straustrup, Saffer) decided to use the term forwarding references instead of universal references .
A couple of articles on this topic:
A brief introduction to rvalue links
"Universal" links in C ++ 11 or T && do not always mean "Rvalue Reference"