Background
I’ve thought I was good at C++, however, after my friend asking me about rvalue, I realized that I knew nothing about the strength of C++.
In this article, I won’t introduce either rvalue or move constructor. Instead, I will describe and dig into his question and try to explain what benefits the move constructor provides.
Question
For std::map<Key, T, Compare, Allocator>::insert, there are two overloadings:
-
since C++11
template <class P> std::pair<iterator, bool> insert(P&& value); -
since C++17
std::pair<iterator, bool> insert(value_type&& value);
So, what’s the difference? Why to add the second overloading into C++17?
You Should Know
-
std::moveis just a type cast to rvalue and does nothing else. -
rvalue reference to rvalue reference collapses to rvalue reference, all other combinations form lvalue reference:
typedef int& lref; typedef int&& rref; int n; lref& r1 = n; // type of r1 is int& lref&& r2 = n; // type of r2 is int& rref& r3 = n; // type of r3 is int& rref&& r4 = 1; // type of r4 is int&& -
rvalue reference variables are lvalues when used in expressions:
int&& x = 1; f(x); // calls f(int& x) f(std::move(x)); // calls f(int&& x) -
Forwarding references are a special kind of references that preserve the value category of a function argument.
E.g. Function parameter of a function template declared as rvalue reference to cv-unqualified type template parameter of that same function template:template<class T> int f(T&& x) { // x is a forwarding reference return g(std::forward<T>(x)); // and so can be forwarded } int main() { int i; f(i); // argument is lvalue, calls f<int&>(int&), std::forward<int&>(x) is lvalue f(0); // argument is rvalue, calls f<int>(int&&), std::forward<int>(x) is rvalue }
Experiment 1
The best way to expain the purpose of the above two methods is using them.
Because the map::insert is a little more complicated, let me write a simple program first:
You can just skim thru the source code now.
I will explain it in detail later.
#include <iostream>
#include <string>
#include <list>
using namespace std;
struct A
{
string str;
A(const A& a) : str(a.str)
{
cout << "copy A" << endl;
}
A(A&& a) noexcept : str(move(a.str))
{
cout << "move A" << endl;
}
A(const string& str) : str(str)
{
cout << "init A (const string&)" << endl;
}
A(string&& str) : str(move(str))
{
cout << "init A (string&&)" << endl;
}
A(int n) : str(to_string(n))
{
cout << "init A (int)" << endl;
}
A& operator=(const A& rhs)
{
str = rhs.str;
cout << "copy assign A" << endl;
return *this;
}
A& operator=(A&& rhs) noexcept
{
str = move(rhs.str);
cout << "move assign A" << endl;
return *this;
}
};
struct Container
{
list<A> aList;
void Add(A&& a)
{
cout << "Add(A&&)" << endl;
aList.push_back(move(a));
cout << aList.back().str << endl;
cout << "---" << endl;
}
void Add(const A& a)
{
cout << "Add(const A&)" << endl;
aList.push_back(a);
cout << aList.back().str << endl;
cout << "---" << endl;
}
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
cout << "Add(U&&)" << endl;
aList.emplace_back(forward<U>(v));
cout << aList.back().str << endl;
cout << "---" << endl;
}
};
int main()
{
Container c;
// pass in `A`
{
// pass in `A` rvalue
// constructed from `string` rvalue
// constructed from `const char *`
c.Add(A("1"));
// pass in `A` rvalue
// constructed from `string` rvalue
// constructed from `const char *`
c.Add({ "2" });
// pass in `A` rvalue
// constructed from `string` rvalue
// constructed from `const char *`
c.Add({ {"3"} });
// pass in `A` rvalue
// constructed from `string` lvalue
{
string x("4");
c.Add(A(x));
}
// pass in `A` lvalue
{
A a("5");
c.Add(a);
}
}
// pass in `string`
{
// pass in `string` rvalue
// constructed from `const char *`
c.Add(string("6"));
// pass in `string` rvalue
// moved from`string` lvalue
{
string x("7");
c.Add(move(x));
}
// pass in `string` lvalue
{
string x("8");
c.Add(x);
}
}
// pass in `int`
{
// pass in `int` rvalue
c.Add(9);
// pass in `int` lvalue
{
int n = 10;
c.Add(n);
}
}
// pass in `const char *`
{
// This is only applicable to Add(T&&).
c.Add("11");
}
return 0;
}
Explore the Program
The program is simple but long. Let’s explore it together:
Struct A
A has copy constructor, move constructor, copy assignment operator, move assignment operator and 3 conversion constructors.
A(const A& a);
A(A&& a) noexcept;
A(const string& str);
A(string&& str);
A(int n);
A& operator=(const A& rhs);
A& operator=(A&& rhs) noexcept;
Struct Container (list wrapper)
In Container, there is a list<A> member and 3 overloaded methods to add an A to that list.
The following code is the simplified implementation of Container.
list<A> aList;
void Add(A&& a)
{
aList.push_back(move(a));
}
void Add(const A& a)
{
aList.push_back(a);
}
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
Main
In main function, I call different Add methods with different As constructed by different constructors.
I will analyze and explain them one by one in the following section.
Output
Before the analysis, let me show you the results for reference:
init A (string&&)
Add(A&&)
move A
1
---
init A (string&&)
Add(A&&)
move A
2
---
init A (string&&)
Add(A&&)
move A
3
---
init A (const string&)
Add(A&&)
move A
4
---
init A (string&&)
Add(U&&)
copy A
5
---
Add(U&&)
init A (string&&)
6
---
Add(U&&)
init A (string&&)
7
---
Add(U&&)
init A (const string&)
8
---
Add(U&&)
init A (int)
9
---
Add(U&&)
init A (int)
10
---
Add(U&&)
init A (string&&)
11
---
Analysis
Case 1
// pass in `A` rvalue constructed from `string` rvalue constructed from `const char *`
c.Add(A("1"));
init A (string&&)
Add(A&&)
move A
Since "1" is an string rvalue, and A(...) is an rvalue too, we see that A was constructed by string&& and then Add(A&&) was called.
void Add(A&& a)
{
aList.push_back(move(a));
}
In Add(A&&), the A rvalue was moved to aList.
Case 2
// pass in `A` rvalue constructed from `string` rvalue constructed from `const char *`
c.Add({ "2" });
init A (string&&)
Add(A&&)
move A
Actually, it’s totally the same as Case 1 except list initialization is used here.
The list initialization here produces an rvalue, so it will match the move constructor with a parameter accepting const char *. Because string could be converted from const char * implicitly, the A(string&&) constructor was called.
What happened then (move A) are exactly the same as Case 1.
Case 3
// pass in `A` rvalue constructed from `string` rvalue constructed from `const char *`
c.Add({ {"3"} });
init A (string&&)
Add(A&&)
move A
This is really the same as Case 1 or 2.
The inner list initialization constructed a string rvalue and the outer list initialization constructed an A rvalue.
Case 4
// pass in `A` rvalue constructed from `string` lvalue
string x("4");
c.Add(A(x));
init A (const string&)
Add(A&&)
move A
The only difference between this and Case 1-3, is that a string lvalue was passed in the constructor of A.
So, the constructor A(const string&) was called instead. And the following calls remained the same.
Case 5
// pass in `A` lvalue
A a("5");
c.Add(a);
init A (string&&)
Add(U&&)
copy A
In this case, an A lvalue was passed in Add. So, it matched the Add(U&&) where U = A&.
You may wonder what the Add(A& &&) is. Remember what is forwarding references in You Should Know (the 4th tips).
Why didn’t it match Add(const A&)?
Why should it? It requires another const conversion between A& and const A&. But the template one is the exact match when U = A&.
You can try to add const before A a("5") and see what happened.
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
// when U = A&, the equivalent method is:
void Add(A& v)
{
aList.emplace_back(v);
}
emplace will directly forward the arguments to construct the object on the memory location where it want it to be.
As v is A&, emplace_back will call the copy constructor of A to construct an A in place.
Case 6
// pass in `string` rvalue constructed from `const char *`
c.Add(string("6"));
Add(U&&)
init A (string&&)
Obviously, U = string here.
So, before calling Add, the A doesn’t need to be constructed.
Inside Add, list<A>::emplace_back was called, which forwarded the arguments directly to the constructor of A.
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
// when U = string, the equivalent method is:
void Add(string&& v)
{
aList.emplace_back(move(v));
}
Now that U = string, v is a string rvalue and A was constructed by v, thus the constructor A(string&&) was called.
As you can see, no move or copy after A was constructed. This is because emplace will directly forward the arguments to construct the object on the memory location where it want it to be. As it is in place, no additional move or copy needed.
This is different with Case 5 because Case 5 has lvalue passed in.
Case 7
// pass in `string` rvalue moved from`string` lvalue
string x("7");
c.Add(move(x));
Add(U&&)
init A (string&&)
This is exactly the same as Case 6 because we moved the string lvalue to rvalue.
Case 8
// pass in `string` lvalue
string x("8");
c.Add(x);
Add(U&&)
init A (const string&)
U = string& here. So, A wasn’t needed before calling Add.
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
// when U = string&, the equivalent method is:
void Add(string& v)
{
aList.emplace_back(v);
}
Inside Add, an A will be constructed in place by emplace_back a string lvalue. So, A(const string&) constructor was called.
And no further operator either.
Case 9
// pass in `int` rvalue
c.Add(9);
Add(U&&)
init A (int)
In this case, U = int.
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
// when U = int, the equivalent method is:
void Add(int&& v)
{
aList.emplace_back(move(v));
}
Since A has only one constructor accepting int&&, A(int) would be called then.
Case 10
// pass in `int` lvalue
int n = 10;
c.Add(n);
Add(U&&)
init A (int)
The only difference is that the passed in int is lvalue here.
So, U = int&.
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
// when U = int&, the equivalent method is:
void Add(int& v)
{
aList.emplace_back(v);
}
However, A has only one constructor accepting int&, A(int) would be called.
Case 11
// pass in `const char *`
c.Add("11");
Add(U&&)
init A (string&&)
In this case, U = const char &[3] which is basically the same as const char *&.
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
// when U = const char *&, the equivalent method is:
void Add(const char*& v)
{
aList.emplace_back(v);
}
The const char *& v was implicityly converted to string rvalue while being forwarded by emplace_back. So, A(string&&) was called.
Experiment 2
The above experimentation and analysis explain how the different constructors and Add methods behave. But now we want to know why we need them.
In this experiment, I will remove one Add method and see what will happen.
Remove Add(U&&)
I commented the template Add method.
void Add(A&& a)
{
aList.push_back(move(a));
}
void Add(const A& a)
{
aList.push_back(a);
}
/*
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
*/
I found that I cannot even compile the program. Let’s solve it first.
The error comes from:
c.Add("11");
Now, it couldn’t find a proper overloading to call, because A couldn’t be constructed directly from const char *.
After removing this case, all other cases could be compiled successfully.
Let’s see what changed.
Case 5 Changes
// pass in `A` lvalue
A a("5");
c.Add(a);
Because no template Add now, it called Add(const A&) instead. No performance difference here.
Case 6 Changes
// pass in `string` rvalue constructed from `const char *`
c.Add(string("6"));
No Add accepts string, so, Add(A&&) was called. And before that, string rvalue should be converted to A rvalue.
You see A(string&&) is the first call and Add(A&&) is the next. And at the end, A should be moved to aList, which has overhead.
You may ask why not use emplace_back here to remove the overhead.
You can use emplace, but the overhead is still there, because emplace would just call the move constructor of A. It’s different from constructing A by a string rvalue. Here, we already have an A.
Case 7-10 Changes
In these cases, the construction of A was put in advance, just as Case 6. Though, they use different constructors to construct the A rvalue implicitly.
After that, the A rvalue was passed into Add(A&&), and all following things become same as Case 6.
Summary for Exp 2
As you can see, without the template Add method, we cannot make use of emplace, which could save some memory move or copy overhead for us.
OK now, what’s the use of Add(A&&)? Could it be replaced by template Add?
Let’s try again.
Experiment 3
Remove Add(A&&)
I commented the Add(A&&) method.
/*
void Add(A&& a)
{
aList.push_back(move(a));
}
*/
void Add(const A& a)
{
aList.push_back(a);
}
template <class U, class = enable_if_t<is_constructible_v<A, U>>>
void Add(U&& v)
{
aList.emplace_back(forward<U>(v));
}
Let’s see what changed.
Case 1,4 Changes
// pass in `A` rvalue constructed from `string` rvalue constructed from `const char *`
c.Add(A("1"));
// pass in `A` rvalue constructed from `string` lvalue
string x("4");
c.Add(A(x));
Because no direct Add(A&&) to match, it will match the template one, where U = A. Nothing else changed.
Case 2-3 Changes
// pass in `A` rvalue constructed from `string` rvalue constructed from `const char *`
c.Add({ "2" });
// pass in `A` rvalue constructed from `string` rvalue constructed from `const char *`
c.Add({ {"3"} });
Because list initialization needs to know the certain type, which template Add cannot provide, the Add(const A&) was called instead.
Consequently, the previous move became copy, which added overhead.
Summary for Exp 3
Add(A&&) is useful when you use list initialization without type hint. The compiler have to match the type to method parameter list. But the template method cannot provide a certain type.
If you remove both Add(A&&) and Add(const A&), Case 2 and 3 won’t be compiled.
Back to the Question
-
since C++11
template <class P> std::pair<iterator, bool> insert(P&& value); -
since C++17
std::pair<iterator, bool> insert(value_type&& value);
First, we should know that value_type in map<Key, T> is pair<const Key, T>. And there are many constructors for pair.
So, providing both of these two methods will help to avoid overheads by enabling emplace and using move instead of copy as much as possible.
Comparison between gcc 7.1 and gcc 9.1
Please zoom in the web page or right-click the image to open it in new tab.
Please ignore the compiler options
--std=c++14. It seems no use to determine whethermap::insert(value_type&&)exists or not.
Another Question
I’m confused about the meaningness of Add(const A&) now.
As you can see, in experiment 1, it wasn’t used at all.
The only way to call it is to pass in exactly const A lvalue. But what’s the purpose to deal with const lvalue separately?
map also provides a method:
std::pair<iterator, bool> insert(const value_type& value);
Is this neccessary?