如何在不同比较器的std::set间移动大对象并切换排序？

问题描述 #

程序中存在大量大对象，当前存储在带自定义比较器的std::set中：

• 集合初始为空，持续通过emplace添加对象，定期从集合一端消费对象
• 需要在2-10个关键节点切换排序方式（共三种排序方式反复切换），要求重新排序时不复制大对象，仅移动

参考示例代码及输出：

#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;
}

输出：

Constructor
Constructor
Constructor
1 2 3 
Copy constructor
Copy constructor
Copy constructor
3 2 1

解决方案 #

能否用移动构造替代复制构造？ #

可以实现，但不能直接用迭代器范围构造std::set——因为std::set的元素是const不可修改的，迭代器返回的是const引用，无法直接触发移动构造。

正确的实现方式是逐个将原集合中的元素移动出来，同时从原集合中删除（避免留下无效元素）：

// 替换原代码中set2的构造部分
std::set<S, decltype(inver)> set2;
auto it = set1.begin();
while (it != set1.end()) {
    // 使用const_cast解除const限制，后续会立即删除该元素，保证安全
    set2.emplace(std::move(const_cast<S&>(*it)));
    // erase会返回下一个有效迭代器，避免迭代器失效
    it = set1.erase(it);
}

修改后的输出会变为：

Constructor
Constructor
Constructor
1 2 3 
Move constructor
Move constructor
Move constructor
3 2 1

注意事项：

• 必须配合erase操作，因为移动后原元素的状态变为"有效但未定义"，从原集合中删除可避免后续访问问题
• const_cast的使用是安全的，因为我们明确会立即移除该元素，不会破坏原集合的排序结构

更优替代方案：分离存储与排序逻辑 #

如果需要频繁切换排序方式，来回移动std::set中的元素仍有额外开销。更高效的方案是将大对象存储在稳定容器中，仅对索引/指针进行排序：

1. 存储大对象：使用std::vector<S>（若能预估大小则提前分配内存，避免扩容导致指针失效），所有大对象仅存储一次，无需移动或复制。
2. 维护排序索引：针对三种排序方式，分别创建std::set<size_t, Comparator>，其中Comparator是自定义比较器，通过索引访问vector中的对象进行排序判断。

示例框架：

// 大对象存储容器（提前预留足够空间避免扩容）
std::vector<S> objects;
objects.reserve(1000); // 根据实际需求设置

// 三种排序的索引集合
auto cmp_order = [&objects](size_t idx1, size_t idx2) {
    return objects[idx1].a < objects[idx2].a;
};
auto cmp_inver = [&objects](size_t idx1, size_t idx2) {
    return objects[idx2].a < objects[idx1].a;
};
// 第三种比较器...

std::set<size_t, decltype(cmp_order)> set_order(cmp_order);
std::set<size_t, decltype(cmp_inver)> set_inver(cmp_inver);

// 添加对象时
objects.emplace_back(1);
size_t new_idx = objects.size() - 1;
set_order.insert(new_idx);
set_inver.insert(new_idx);
// 其他排序集合同理...

// 切换排序方式时，直接使用对应索引集合即可
// 消费对象时，从当前使用的索引集合取出首元素，访问objects[idx]
if (!set_inver.empty()) {
    size_t consume_idx = *set_inver.begin();
    S& target = objects[consume_idx];
    // 处理target...
    // 从所有索引集合中删除该索引（如果消费后不再需要）
    set_order.erase(consume_idx);
    set_inver.erase(consume_idx);
}

这种方案的优势：

• 大对象仅存储一次，完全避免复制/移动开销
• 排序操作仅针对轻量的索引值，效率极高
• 切换排序方式无需任何数据迁移，直接切换使用的索引集合即可

内容的提问来源于stack exchange，提问作者Alberto Santini