将元素插入二维向量

Question

我正在创建一个实现邻接表的类，目前在我的类定义中，我初始化了两个向量：

vector<vector<int>> adjList;
vector<int> neighbors;

我声明了两个函数，我计划使用它们来制作它：

bool constructAdjList();
bool insertIntoAdjList(int, int);

我很难理解2D向量的概念。我知道它本质上是由向量构成的向量，但我不清楚如何将新值插入到其中一个“子向量”中。例如，我可以通过以下循环在createAdjList中创建一个空的邻接表：

for (int i = 0; i < numOfValues; i++){
    neighbors.push_back(0);
    adjList.push_back(neighbors);
    neighbors.clear();
}

但是我应该如何在insertIntoAdjList函数中表示将值5 push_back到adjList中的第4个向量呢？

insertIntoAdjList(4, 5);

我知道可以通过输入adjList[4][1]来访问2D向量中的特定值，但是如何将一个值添加到其中呢？

谢谢！

- user3078735

---

我不明白，你不能这样做吗：adjList[4][1] = 987？ - Kam

如果我已经有一个值在[4][1]位置，那么这个方法是有效的，但是如果我想要将一个值推到向量4的末尾，我必须使用push_back对吧？ - user3078735

我认为 std::unordered_map<int, std::unordered_map<int,int>> 可能更适合你。仅代表个人观点。 - WhozCraig

然后执行 adjList[4].push_back()。 - Kam

Answer 1

要将一个向量推到另一个向量中的元素，只需执行以下操作

adjList[x].push_back();

- Kam

---

哇，我不知道你可以只指定2D向量中的一个坐标。这使得它变得更容易了，谢谢！ - user3078735

我认为理解 adjList[x] 返回对存储在位置 x 上的向量的引用是很重要的。因此，adjList[x][y] 相当于 (adjList[x])[y]，意思是：首先，给我一个在 adjList 中位置为 x 的向量（我们称之为 V）的引用，然后给我一个在 V 中位置为 y 的整数的引用。 - Lemming

Answer 2

如果一开始你的向量中没有任何值 - 你可以将值推入一个向量，然后将该向量推入二维向量。 例如：

  vector< vector<int> > vt1;
  vector<int> vt2;

  vt2.push_back(value);
  vt1.push_back(vt2);

如果你的向量已经被填充了，那么-

vt1[index].push_back(value);

- Hanu Tyagi

Answer 3

这里有几点需要注意。

您的循环可以通过使用两个成员的构造函数来显著缩短代码：

vector<int> neighbors(1, 0); // set to length 1, value is zero
vector<vector<int>> adjList(numOfValues,neighbors); // "outer" vector is numOfValues long
.                                                   // each row is a *COPY* of neighbor

如果在构造时不能完成此操作（可能尚未知道numOfValues），那么我们仍然可以使用更好的循环语法：

// neighbors object can be reused
neighbors.clear(0);
neighbors.push_back(0);
adjList.reserve(numOfValues); // reserving memory ahead of time will prevent allocations
for (int i = 0; i < numOfValues; i++){
    adjList.push_back(neighbors); // push_back is by *COPY*
}

在您的示例中，通过使用clear和push_back来在每个循环迭代中构建相同的向量，您正在冒着每次迭代进行分配和释放的风险。实际上，大多数实现不会这样做，但如果我们可以缩短并潜在地使事情更有效率，那么我们也可以这样做。

最后，如果邻居数量相对较小且行与行类似（例如具有四面体元素的有限元代码，其中每个元素连接到约5个其他元素），则如其他人所建议的，您可能最好使用不同于向量的结构。例如，一个单一的向量，逻辑上组织成每N个元素开始一个新的“行”。

- JHumphrey

---

这段代码片段是否在一个for循环内部？ - mLstudent33