为什么push_back成矢量<矢量<int>>导致 seg 错误？

Question

想要构造一个带有邻接列表的图，但是当我向vector<vector<int>>添加元素时出现段错误。adj.size()打印5，告诉它已分配内存，为什么addEdge()方法中的赛格错误？

#define V 5
struct Edge {
int src, dst;
};
void addEdge(vector<vector<int>> &adj, int u, int v)
{
adj[u].push_back(v);
}
void constructGraph(vector<vector<int>> &adj, vector<Edge> &edges)
{
for(Edge e : edges)
{
addEdge(adj, e.src, e.dst);
}
}
int main()
{
vector<vector<int>> adj(V);
vector<Edge> edges =
{
{ 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 },
{ 3, 2 }, { 4, 5 }, { 5, 4 }
};
constructGraph(adj, edges);
return 0;
}

---

Answer 1

void addEdge(vector<vector<int>> &adj, int u, int v)

{
adj[u].push_back(v);
}

是不正确的。 向量的operator[]()假定提供的索引有效。 如果u无效，则行为未定义。

在代码中，传递的向量有五个元素，最后一个边main()

vector<Edge> edges =

{
{ 0, 1 }, { 1, 2 }, { 2, 0 }, { 2, 1 },
{ 3, 2 }, { 4, 5 }, { 5, 4 }               // note the last pair here
};

将导致addEdge()被调用，u的值为5。 这已经是结束了。

虽然#define V 6可以解决问题，但它并不能保护addEdge()不被传递错误的u值。 相反，我会实现addEdge()以便它保护自己免受不良数据的侵害，如下所示。

void addEdge(vector<vector<int>> &adj, int u, int v)
{
if (u < 0) return;                   // handle negative u
if (u >= adj.size()) adj.resize(u+1);  //   resize if needed
adj[u].push_back(v);
} 

更好的方法是完全避免使用提供的数据(例如main()中edges中的数据(作为数组索引。

Answer 2

已解决。感谢您在此处提供的指导，阅读有关此内容的更多信息，并了解到 C++ 语言内置了针对此类问题的保护。使用 .at(( 方法可以保护程序员免受越界访问。

void addEdge(vector<vector<int>> &adj, int u, int v)
{
adj.at(u).push_back(v);
}

如果使用 adj.at(u( 而不是 adj[u]，程序将很少正常退出

terminate called after throwing an instance of 'std::out_of_range'
what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)
Aborted (core dumped)