C++二维std::vector矩阵最小代价元素高效查找删除问题

你遇到的问题本质是std::vector删除中间元素后，后续元素的列下标会整体左移，依赖静态下标定位的优先队列自然会出现坐标失效。下面给出两种落地成本低、性能优异的方案：

方案1：惰性删除优先队列（改造成本最低） #

这是处理优先队列无效元素的通用方案，无需大幅改动现有逻辑，性能仍能保持O(logN)的均摊复杂度：

改造步骤 #

1. 给矩阵元素增加唯一序列号标识，调整矩阵存储结构：

// 全局序列号生成器，插入元素时自增即可
uint64_t global_seq = 0;
// 原matrix从vector<vector<T>>改为存储 值+序列号 的 pair
std::vector<std::vector<std::pair<T, uint64_t>>> matrix;

2. 给Costelement增加序列号字段：

struct Costelement
{
    int row;
    int column;
    std::vector<double> cost;
    uint64_t seq; // 新增：对应元素的唯一序列号

    struct CompareCosts
    {
        bool operator()(const Costelement &e1, const Costelement &e2)
        {
            return (e1.cost > e2.cost);
        }
    };
};

3. 新增有效元素提取逻辑，弹出优先队列元素时先校验有效性：

Costelement pop_min_valid() {
    while (!Costvec.empty()) {
        auto current = Costvec.top();
        Costvec.pop();
        // 校验坐标合法性 + 序列号匹配性
        if (current.row < matrix.size() 
            && current.column < matrix[current.row].size()
            && matrix[current.row][current.column].second == current.seq) {
            return current;
        }
        // 无效元素直接丢弃即可
    }
    throw std::runtime_error("队列中无有效元素");
}

逻辑说明 #

每次插入新元素时，给元素分配递增的唯一序列号，同时把带序列号的Costelement压入优先队列。删除元素时无需改动优先队列的存量数据，取最小元素时自动过滤掉序列号不匹配的无效记录即可。每个元素最多入队、出队各一次，均摊性能远高于全矩阵遍历的O(N)方案。

方案2：分层堆结构（适合大数据量场景） #

如果你的数据规模很大，惰性删除的无效元素过多，可以用两层堆的结构彻底避免坐标失效问题：

• 每行单独维护一个小顶堆，存储该行所有元素的代价和元素指针/唯一ID，不受列下标偏移影响
• 全局维护一个小顶堆，存储内容为（某行当前最小代价、行号）
• 每次取全局最小元素时，弹出全局堆顶得到对应行号，再弹出该行堆顶的元素即为全局最小元素；之后把该行新的堆顶代价压入全局堆即可。
  该方案无效元素极少，整体性能比单惰性队列更高，但改造成本略高于方案1。

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