使用std::vector.push_back()存入自定义Queue类对象时程序崩溃求助

架构老林

2026-8-3

LeetCode Q1091 最短路径问题中的堆使用后释放错误排查

问题场景

我在解决LeetCode Q1091（最短路径二进制矩阵）问题时，自定义了Queue类存储坐标和路径长度，实现了Solution类，但程序执行Solution::addNewQueue时崩溃，报堆使用后释放（heap-use-after-free）错误。

自定义Queue类代码

class Queue {
public:
    int x;
    int y;
    int length;
    Queue(int xx, int yy, int l): x(xx), y(yy), length(l) {};
};

Solution类完整实现

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid);
    void addNewQueue(vector<vector<int>>& grid, int x, int y, vector<vector<int>>& path, int length, vector<Queue>& queues);
};

int Solution::shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return -1; //表示没有迷宫需要解决
    if (grid[0][0] == 1) return -1;
    vector<vector<int>> path(grid.size());
    for (auto &r: path) r.resize(grid.size(), INT_MAX);
    path[0][0] = 0;
    vector<Queue> queues;
    queues.push_back(Queue(0, 0, 0));
    while (!queues.empty()) {
        auto q = queues.begin();
        addNewQueue(grid, q->x+1, q->y, path, q->length, queues);
        addNewQueue(grid, q->x-1, q->y, path, q->length, queues);
        addNewQueue(grid, q->x+1, q->y+1, path, q->length, queues);
        addNewQueue(grid, q->x, q->y+1, path, q->length, queues);
        addNewQueue(grid, q->x-1, q->y+1, path, q->length, queues);
        addNewQueue(grid, q->x+1, q->y-1, path, q->length, queues);
        addNewQueue(grid, q->x, q->y-1, path, q->length, queues);
        addNewQueue(grid, q->x-1, q->y-1, path, q->length, queues);
        queues.erase(queues.begin());
    }
    if (path[path.size()-1][path.size()-1] == INT_MAX) return -1;
    else return path[path.size()-1][path.size()-1];
}
void Solution::addNewQueue(vector<vector<int>>& grid, int x, int y, vector<vector<int>>& path, int length, vector<Queue>& queues) {
    if (x < grid.size() && y < grid.size() && x >= 0 && y >= 0 && length+1 < path[x][y] && grid[x][y] == 0) {
        queues.push_back(Queue(x, y, length+1));
        path[x][y] = length + 1;
    }

    return;
}

错误信息

=================================================================
==31==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000110 at pc 0x000000347b34 bp 0x7ffdc8ec3510 sp 0x7ffdc8ec3508
READ of size 4 at 0x602000000110 thread T0
    #2 0x7fa07b4830b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000110 is located 0 bytes inside of 12-byte region [0x602000000110,0x60200000011c)
freed by thread T0 here:
    #5 0x7fa07b4830b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
previously allocated by thread T0 here:
    #5 0x7fa07b4830b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 00 fa
  0x0c047fff8010: fa fa fd fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8020: fa fa[fd]fd fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==31==ABORTING

错误原因分析

核心问题是迭代器失效：

在shortestPathBinaryMatrix中，用auto q = queues.begin();获取队列头部迭代器后，调用addNewQueue向queues执行push_back操作。
当vector剩余容量不足时，push_back会重新分配内存块，导致之前获取的迭代器q直接失效。后续访问q->x、q->length等成员时，实际是访问已被释放的内存区域，触发heap-use-after-free错误。

修复方案

方式1：提前保存节点数据，避免使用迭代器

在调用addNewQueue前，将当前节点的x、y、length值保存到局部变量，彻底规避迭代器失效问题：

while (!queues.empty()) {
    // 提前保存当前节点的所有数据
    int curr_x = queues[0].x;
    int curr_y = queues[0].y;
    int curr_len = queues[0].length;
    // 使用保存的数据调用addNewQueue
    addNewQueue(grid, curr_x+1, curr_y, path, curr_len, queues);
    addNewQueue(grid, curr_x-1, curr_y, path, curr_len, queues);
    addNewQueue(grid, curr_x+1, curr_y+1, path, curr_len, queues);
    addNewQueue(grid, curr_x, curr_y+1, path, curr_len, queues);
    addNewQueue(grid, curr_x-1, curr_y+1, path, curr_len, queues);
    addNewQueue(grid, curr_x+1, curr_y-1, path, curr_len, queues);
    addNewQueue(grid, curr_x, curr_y-1, path, curr_len, queues);
    addNewQueue(grid, curr_x-1, curr_y-1, path, curr_len, queues);
    queues.erase(queues.begin());
}

方式2：使用标准库std::queue实现BFS

直接用C++标准库的std::queue，它的插入操作不会导致迭代器失效，更适配BFS场景：

#include <queue>

class Queue {
public:
    int x;
    int y;
    int length;
    Queue(int xx, int yy, int l): x(xx), y(yy), length(l) {};
};

int Solution::shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    if (grid.size() == 0 || grid[0].size() == 0) return -1;
    if (grid[0][0] == 1) return -1;
    int n = grid.size();
    vector<vector<int>> path(n, vector<int>(n, INT_MAX));
    path[0][0] = 0;
    std::queue<Queue> q;
    q.emplace(0, 0, 0);
    
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        int curr_x = curr.x;
        int curr_y = curr.y;
        int curr_len = curr.length;
        
        // 用数组统一管理8个方向，简化代码
        vector<pair<int, int>> dirs = {{1,0}, {-1,0}, {1,1}, {0,1}, {-1,1}, {1,-1}, {0,-1}, {-1,-1}};
        for (auto& dir : dirs) {
            int x = curr_x + dir.first;
            int y = curr_y + dir.second;
            if (x >=0 && x <n && y >=0 && y <n && grid[x][y] ==0 && curr_len+1 < path[x][y]) {
                path[x][y] = curr_len +1;
                q.emplace(x, y, curr_len+1);
            }
        }
    }
    return path[n-1][n-1] == INT_MAX ? -1 : path[n-1][n-1];
}

测试代码修正

你的main.cpp存在赋值错误，grid[0][1] = 0;覆盖了之前的grid[0][1] =1;，修正后如下：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 提前声明类
class Queue {
public:
    int x;
    int y;
    int length;
    Queue(int xx, int yy, int l): x(xx), y(yy), length(l) {};
};

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid);
    void addNewQueue(vector<vector<int>>& grid, int x, int y, vector<vector<int>>& path, int length, vector<Queue>& queues);
};

// 这里实现Solution的成员函数...

int main() {
    Solution s;
    vector<vector<int>> grid(2, vector<int>(2));
    grid[0][0] = 0;
    grid[0][1] = 1;
    grid[1][0] = 1;
    grid[1][1] = 0; // 修正此处赋值目标
    cout << grid[0][0] << " " << grid[0][1] << endl;
    cout << grid[1][0] << " " << grid[1][1] << endl;
    cout << s.shortestPathBinaryMatrix(grid);
    
}

补充说明

该错误在部分编译器中可能不会立即显现，因为vector重新分配内存的时机不确定，但本质是访问已释放内存的未定义行为，必须修复。

内容的提问来源于stack exchange，提问作者李承軒

使用std::vector.push_back()存入自定义Queue类对象时程序崩溃求助

问题场景 #

自定义Queue类代码 #

Solution类完整实现 #

错误信息 #

错误原因分析 #

修复方案 #

方式1：提前保存节点数据，避免使用迭代器 #

方式2：使用标准库std::queue实现BFS #

测试代码修正 #

补充说明 #