The Question
I have a type T that is move assignable and move constructible but not default constructible. I want to create a T temp[N]; using the move constructor so that I can safely move assign Ts into temp.
I am most interested in the case where temp is a class member, but it may be easier to find a solution when temp is a local variable of a function. How can I do that?
Background
I am writing a generic library function that will execute many std::swaps:
template<typename T>
void func(){
while(true){
// do stuff
// perform swap
std::swap(t1, t2);
}
}
A typical implementation of std::swap is the following:
template<typename T>
void swap(T& t1, T& t2) {
T temp = std::move(t1); // or T temp(std::move(t1));
t1 = std::move(t2);
t2 = std::move(temp);
}
Every invocation of std::swap will allocate a T temp and call T temps destructor. I want to eliminate this cost.
If the T is default constructible, I may try something like this:
template<typename T>
void func(){
T temp;
while(true){
// do stuff
// perform swap
temp = std::move(t1);
t1 = std::move(t2);
t2 = std::move(temp);
}
}
In my case, I cannot assume T is default constructible, but I may assume it is move assignable and move constructible. If I happen to have a t prior to the while loop, I can do the following:
template<typename T>
void func(){
T temp = std::move(t);
t = std::move(temp);
while(true){
// do stuff
// perform swap
t = std::move(t1);
t1 = std::move(t2);
t2 = std::move(t);
}
}
The above code works. However, there is a second optimization I haven't mentioned. After I swap t1 and t2, it is likely that I will soon swap t2 and t3. Instead of performing t2 = std::move(t); followed by temp = std::move(t2);, I want to leave the value of t2 in temp.
At any given moment, there may be at most 8 temp values that have yet to be swapped to their final destination (well, not 8, but a large constexpr number determined by the library user). If T were default constructible, that would look something like this:
template<typename T>
void func(){
T temp[8];
while(true){
// do stuff
// perform swap
t1 = std::move(temp[i]);
temp[i] = std::move(t2);
}
}
which doesn't work since T temp[8]; calls Ts default constructor. My idea now looks something like this
- Allocate some local uninitialized memory for a
T temp[8];with something likemalloc. - Move-construct the first 8
temps into the uninitialized memory with placementnew. - Somehow ensure destructors are called for the moved-out-of
temps.
std::vectorinsteadstd::optionalto hold those temporary values.Tto overloadswap()for itself, if the standard implementation is too expensive for it. You'd then dousing std::swap; swap(a, b);to swap the object, which will pick up the custom overload, or fall back tostd::swapif there's none.std::vector.alignas(alignof(T)) buffer[sizeof(T) * N];and for convenience aT* temp = reinterpret_cast<T*>(buffer);. And then you have to deal with the move construction and destruction manually (probably usingstd::uninitialized_moveandstd::destroy_at)