如何排序std::vector时同步排序关联bitset以保持选中状态？

当然有办法不用自己实现排序！核心思路是通过索引序列或者绑定元素与选中状态来同步std::vector和动态bitset的顺序，完全可以复用std::sort的高效实现。下面给你两种实用的方案：

方案一：利用索引序列同步排序 #

这种方法的核心是先对元素的索引进行排序，再根据排序后的索引重新排列原vector和bitset，完美保留元素与选中状态的对应关系：

#include <vector>
#include <algorithm>
#include <numeric>
#include <dynamic_bitset>

class SelectionArray {
private:
    std::vector<int> data_; // 示例元素类型为int，可替换为任意类型
    std::dynamic_bitset<> selected_; // 动态bitset，需支持size()、set()、operator[]

public:
    // 构造函数、添加元素等成员函数省略...

    void sort() {
        // 1. 生成元素索引序列：0,1,2,...,n-1
        std::vector<size_t> indices(data_.size());
        std::iota(indices.begin(), indices.end(), 0);

        // 2. 按原vector的元素大小对索引排序
        std::sort(indices.begin(), indices.end(), [this](size_t idx_a, size_t idx_b) {
            return data_[idx_a] < data_[idx_b]; // 升序排序，可改为降序或自定义比较逻辑
        });

        // 3. 根据排序后的索引构建新的vector和bitset
        std::vector<int> new_data;
        new_data.reserve(data_.size());
        std::dynamic_bitset<> new_selected(data_.size());

        for (size_t i = 0; i < indices.size(); ++i) {
            new_data.push_back(data_[indices[i]]);
            new_selected.set(i, selected_[indices[i]]);
        }

        // 4. 替换原容器（swap操作高效，避免不必要的拷贝）
        data_.swap(new_data);
        selected_.swap(new_selected);
    }
};

方案优势： #

• 复用了std::sort的高效O(n log n)实现，无需自己编写排序逻辑
• 当元素类型的拷贝/移动成本较高时，这种方法更高效（仅拷贝小尺寸的索引，最后一次移动元素）
• 灵活支持自定义排序规则，只需修改std::sort的比较lambda即可

方案二：绑定元素与选中状态后排序 #

如果觉得索引法有点绕，也可以把每个元素和它的选中状态绑定成一个pair或自定义struct，排序后再拆分回原容器：

#include <vector>
#include <algorithm>
#include <dynamic_bitset>

class SelectionArray {
private:
    std::vector<int> data_;
    std::dynamic_bitset<> selected_;

public:
    // 构造函数等省略...

    void sort_with_pair() {
        // 1. 将元素与选中状态绑定为pair
        std::vector<std::pair<int, bool>> temp;
        temp.reserve(data_.size());
        for (size_t i = 0; i < data_.size(); ++i) {
            temp.emplace_back(data_[i], selected_[i]);
        }

        // 2. 按元素值排序pair
        std::sort(temp.begin(), temp.end(), [](const auto& a, const auto& b) {
            return a.first < b.first;
        });

        // 3. 拆分回原容器
        for (size_t i = 0; i < temp.size(); ++i) {
            data_[i] = temp[i].first;
            selected_.set(i, temp[i].second);
        }
    }
};

方案优势： #

• 代码逻辑更直观，容易理解和维护
• 不需要额外处理索引，对新手友好

注意事项 #

• 如果你的动态bitset是自定义实现的，只需确保它支持size()、operator[]（访问指定位）和set(size_t pos, bool value)方法即可适配以上代码
• 两种方案都能完美处理空容器、单元素容器等边界情况

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