C++中支持权重随机访问更新的priority queue的STL替代容器有哪些？

STL 没有原生自带支持随机元素权重高效更新的优先队列容器，但可以通过现有STL容器组合实现需求，以下是两种最常用的适配方案：

方案1：基于 std::priority_queue 的惰性删除实现 #

• 实现逻辑：不对队列中已有的旧权重元素做修改，直接将更新了新权重的同一元素插入队列，同时额外用 std::unordered_map 维护每个元素的最新有效权重。
• 取元素逻辑：每次弹出队首元素时，先校验其权重是否和哈希表中存储的该元素最新权重一致，不一致则直接丢弃该无效元素，直到取出有效元素再执行后续操作。
• 复杂度匹配：所有操作均摊复杂度为O(log n)，完全适配你每步仅更新O(1)个元素的场景，实现成本极低。
• 注意事项：如果元素权重更新频率极高，队列中会堆积一定量的无效元素，内存占用会略高，但绝大多数业务场景下完全可接受。

方案2：用 std::set 模拟有序优先队列 #

• 实现逻辑：std::set 底层为红黑树，本身维持元素的有序性，你可以将 (权重, 元素唯一ID) 作为存储的键值存入set，set的首/尾元素就是当前权重最小/最大的待处理元素。
• 更新逻辑：需要更新某个元素的权重时，先从set中删除(旧权重, 元素ID)对应的节点，再插入(新权重, 元素ID)即可，两个操作复杂度均为O(log n)，符合你的更新需求。
• 优势：不存在惰性删除方案的无效元素堆积问题，内存占用更可控，更新逻辑直观。
• 注意事项：如果多个元素权重相同，必须添加元素唯一ID作为第二排序关键字，避免set因为键重复自动删除不同元素。

如果你的场景对性能和内存占用要求极高，也可以基于std::vector手写二叉堆，额外用std::unordered_map维护每个元素在堆数组中的下标，更新权重时直接定位下标调整堆结构，复杂度同样为O(log n)，但实现成本高于上述两种方案。

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