C++ Move-Semantics – How to Move Objects Between Sets with Different Comparison Functors

c++data-structuresmove-semanticsstdsetstl

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?

Best Answer

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.

Live demo 1

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
}

Live demo 2

Related Question