更新Item速度后如何重排带自定义比较器的set？求更优方案

当前方案的问题分析 #

你在编程竞赛中使用unordered_map存储Item，同时用set<Item*, cmp>保存指针以快速获取速度最快的元素，但修改Item的speed后，set的顺序不会自动更新。这是因为set是基于红黑树实现的有序容器，元素插入后会根据比较器固定位置，不允许直接修改影响排序的键值，否则会破坏容器内部结构。此外，原方案还有隐藏风险：unordered_map扩容时，内部元素的内存地址会变化，导致set中存储的指针变为野指针。

当前方案下的修复方法 #

要在不清空set的情况下维护顺序，必须遵循先删除、再修改、重新插入的流程：

// 假设要修改MP中key为2的Item的speed
Item* target = &MP[2];
// 先从set中删除旧指针（此时speed未修改，set能正确找到元素）
S.erase(target);
// 修改speed值
target->speed = 5;
// 将修改后的指针重新插入set，set会重新排序
S.insert(target);

⚠️ 注意：必须在修改speed前执行erase，否则修改后set无法通过比较器定位到该元素，删除操作会失败。

更优解决方案推荐 #

方案1：用set存储排序键对（避免指针问题） #

放弃存储指针，改用set存储{speed, id}键值对，利用id的唯一性避免排序冲突。这种方式完全规避指针失效风险，操作更安全：

struct Item{
    int speed;
    int id;
};

// 自定义比较器，与原逻辑一致：speed降序，speed相同则id升序
struct Cmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        if (a.first != b.first) {
            return a.first > b.first;
        }
        return a.second < b.second;
    }
};

unordered_map<int, Item> MP;
set<pair<int, int>, Cmp> S;

int main(){
    MP[2] = {2, 20};
    MP[1] = {1, 10};
    MP[3] = {3, 30};
    
    // 初始化set
    for (auto& [key, item] : MP) {
        S.insert({item.speed, item.id});
    }
    
    // 修改MP中key为2的Item的speed
    auto& target_item = MP[2];
    // 删除旧的键对
    S.erase({target_item.speed, target_item.id});
    // 修改speed
    target_item.speed = 5;
    // 插入新的键对
    S.insert({target_item.speed, target_item.id});
    
    // 获取速度最快的元素
    auto fastest = *S.begin();
    // 输出：speed=5, id=20
    cout << "Fastest speed: " << fastest.first << ", id: " << fastest.second << endl;
}

该方案的插入、删除、查询操作均为O(logn)，适合大多数编程竞赛场景。

方案2：优先队列+延迟删除（适合频繁修改场景） #

如果需要频繁修改speed，可以用优先队列（大顶堆）结合延迟删除技巧，修改操作仅需更新unordered_map，无需调整队列：

struct Item{
    int speed;
    int id;
};

// 优先队列比较器：speed降序，speed相同则id升序
struct PQCmp {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        if (a.first != b.first) {
            return a.first < b.first; // 小值优先出堆，实现大顶堆效果
        }
        return a.second > b.second; // id小的优先出堆
    }
};

unordered_map<int, Item> MP;
priority_queue<pair<int, int>, vector<pair<int, int>>, PQCmp> pq;

int main(){
    // 假设MP的key为id，方便通过id查找
    MP[10] = {1, 10};
    MP[20] = {2, 20};
    MP[30] = {3, 30};
    
    // 初始化优先队列
    for (auto& [id, item] : MP) {
        pq.push({item.speed, id});
    }
    
    // 修改id为20的Item的speed
    MP[20].speed = 5;
    
    // 获取当前速度最快的有效元素
    while (!pq.empty()) {
        auto [top_speed, top_id] = pq.top();
        if (MP[top_id].speed == top_speed) {
            // 找到有效元素
            cout << "Fastest speed: " << top_speed << ", id: " << top_id << endl;
            break;
        } else {
            // 弹出无效的旧元素
            pq.pop();
        }
    }
}

该方案修改操作是O(1)，查询最大元素时需清理无效队列元素，适合修改频繁、查询次数相对较少的场景。

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