dijkstra算法中直接用vector
为什么Dijkstra里用指针反而容易出错
直接用 std::vector 存邻接表 + std::priority_queue 做堆，比手写指针管理更安全、更高效。C++ 中对图结构频繁增删边、动态改权值的场景极少，强行用裸指针（比如 Edge* 或 Node*）不仅没性能收益，还会引入悬空指针、内存泄漏和迭代器失效问题。
常见错误现象：segmentation fault 出现在堆弹出节点后访问已释放的 Edge*；或更新距离时修改了某条边的权值，但堆里还存着旧指针，导致比较逻辑错乱。
- STL 容器（如
vector<vector int>></vector>）在局部作用域内自动管理内存，无需new/delete -
priority_queue存的是节点编号和距离（pair<int int></int>），不是指针，避免了对象生命周期错配 - 现代编译器对
vector的连续内存访问有良好优化，缓存友好性远超链式指针结构
什么时候真需要指针？只有一种情况
当图结构本身要被多个算法共享且**长期驻留内存**（比如地图服务中加载一次、反复查路多年），并且你明确做了对象池或 arena 分配——这时可用 unique_ptr<node></node> 管理节点，用 shared_ptr<edge></edge> 共享边（避免重复存储反向边）。但注意：这不加速 Dijkstra，只是方便复用图结构。
使用场景举例：导航后台服务启动时加载整个城市路网，后续每次请求都复用同一份图数据。
- 必须用智能指针，禁用裸指针；
unique_ptr负责所有权，shared_ptr仅用于跨子图共享边 - 邻接表仍建议用
vector<vector>></vector>，而非vector<shared_ptr>></shared_ptr>—— 因为 Dijkstra 只需遍历邻居，不需要通过节点指针来回跳 - 不要把
shared_ptr<edge></edge>塞进priority_queue：引用计数开销大，且无法按权值排序（得额外加自定义比较器）
priority_queue 里存什么？别存指针
标准写法是存 pair<int int></int>：第一项为距离（用于最小堆排序），第二项为节点编号。若存 Node*，一旦该 Node 对象被移动或析构，堆里就留下野指针。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
错误示例：priority_queue<node vector>, Compare> pq;</node> —— Compare 得手动解引用，且无法保证 Node* 指向有效内存。
- 正确做法：用
priority_queue<pair int>, vector<pair int>>, greater<pair int>>></pair></pair></pair> - 如果真要封装，定义结构体
State { int dist; int u; }，重载operator，但字段仍用值语义，不包含指针成员 - 性能影响：
pair<int></int>是 trivial 类型，拷贝成本几乎为零；而指针解引用+缓存未命中反而更慢
想提速？换容器，不是换指针
Dijkstra 瓶颈通常在堆操作（O(E log V)）和邻接表遍历（O(E)）。优化方向是：降低常数、减少分配、提升缓存局部性。裸指针对此毫无帮助。
实操建议：
- 用
vector<vector int>></vector>替代链表式邻接表：连续内存，CPU 预取友好 - 考虑
std::set或fibonacci_heap（Boost）替代priority_queue，仅当图极度稀疏且 E ≫ V² 时有意义 - 如果图固定且顶点编号密集（0~N-1），可预分配
dist[N]数组，避免vector::at()边界检查开销 - 禁用
ios_base::sync_with_stdio(false)后再读图数据——I/O 常比算法本身更慢
真正卡住性能的，从来不是“该不该用指针”，而是邻接表是否连续、堆是否支持减键操作、以及有没有把 dist[u] == d 的过期堆元素当场丢弃。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
