I have a large number of large objects in my program. They are currently stored in an std::set with a customer comparison functor. The set starts empty and I keep emplacing objects into it. I also periodically "consume" objects from one end of the set.
At a few (2-10) key points during the execution of my program, I might want to change the sorting of these objects and keep emplacing and consuming them in the new order. I usually have three possible orderings and I keep switching between them.
I would like the resorting to take place without copying the large objects, but rather moving them.
Consider the following example:
#include <iostream>
#include <set>
#include <utility>
struct S {
int a;
S(int a) : a{a} { std::cout << "Constructor\n"; }
S(const S& s) : a{s.a} { std::cout << "Copy constructor\n"; }
S(S&& s) : a{std::exchange(s.a, 0)} { std::cout << "Move constructor\n"; }
S& operator=(const S& s) { std::cout << "Copy assignment\n"; return *this = S(s); }
S& operator=(S&& s) { std::cout << "Move assignment\n"; std::swap(a, s.a); return *this; }
};
int main() {
auto order = [] (const S& s1, const S& s2) -> bool { return s1.a < s2.a; };
auto inver = [] (const S& s1, const S& s2) -> bool { return s2.a < s1.a; };
std::set<S, decltype(order)> set1;
set1.emplace(1);
set1.emplace(3);
set1.emplace(2);
for(auto&& s : set1) {
std::cout << s.a << " ";
}
std::cout << "\n";
std::set<S, decltype(inver)> set2{set1.begin(), set1.end()};
for(auto&& s : set2) {
std::cout << s.a << " ";
}
std::cout << "\n";
return 0;
}
Which prints the following output:
Constructor
Constructor
Constructor
1 2 3
Copy constructor
Copy constructor
Copy constructor
3 2 1
Would it be possible to use the move constructor instead of the copy constructor? How? If this is not possible, what would be a good strategy to solve my problem? Should I just keep my objects in a data structure that doesn't invalidate pointers and has constant-time direct access (such as a large vector that is never resized — or else, please suggest a more appropriate structure) and only sort their indices?
You can use std::set::extract (with std::move and std::set::emplace) in the following way:
std::set<S, decltype(inver)> set2;
auto it = set1.begin();
while (it != set1.end())
{
auto tmp = it;
it++; // increment `it` while it is still valid
set2.emplace(std::move(set1.extract(tmp).value())); // this will invalidate `tmp`, but we not longer need it for the loop
}
Note that we use a tmp iterator for extract (which will invalidate it) while incrementing it which is used in the loop beforehand, while it is still valid.
This way the move constructor of S will be called instead of the copy constructor.
Another option is to use std::set::insert with the node handle (instead of std::set::emplace).
This will move the complete node and even the move constructor of S will not be called:
auto it = set1.begin();
while (it != set1.end())
{
auto tmp = it;
it++; // increment `it` while it is still valid
set2.insert(std::move(set1.extract(tmp))); // this will invalidate `tmp`, but we not longer need it for the loop
}