C++标准队列和向量的性能表现

Question

我最近一直在处理图形问题，想要返回一个图形中的路径。这个路径需要作为一个 std 向量进行返回，其中包含所有节点，起始节点排在第一位。

我看了两种方法： - 使用缓慢的向量插入方法将节点添加到向量的前面。 - 使用双端队列将节点添加到前端（push_front），这样速度更快。然后使用 std::copy 将双端队列复制到向量中。

是否有一种方法比另一种方法效率更高呢？

- fkrstevski

---

为什么不把向量的元素推到后面呢？ - eerorika

如果您不需要直接访问元素，我建议使用链表。 - user586399

我认为你应该专注于主要的算法，这样你才能找到自己的方向，而不是选择不那么重要的数据结构，因为对于向量和双端队列来说，它们都是O(n)。此外，你认为std::copy不消耗时间和空间吗？ - kaitian521

@Kilanny 在不知道具体使用模式的情况下很难推荐。由于缓存局部性差，列表的迭代时间比连续存储数据类型（如vector）慢。 - Rotem

你在标题中说“queue”，在正文中说“deque”。到底是哪一个？这两个都是标准库中的东西。 - juanchopanza

Answer 1

由于您返回的是路径，因此您可能对其长度有一个上限。因此，您可以创建一个vector，调用reserve，然后（如@user2079303所写）调用push_back来添加路径上的顶点。

const auto n = <graph_size>
std::vector<size_t> path;
path.reserve(n)
...
v.push_back(i); // Push whatever you want.

现在的问题是，至少从问题中来看，v似乎是反向排序的。但是，您可以简单地调用std::reverse：

std::reverse(std::begin(v), std::end(v));

所以，仅使用一个vector：

• 您正在分配单个数据结构而不是两个；此外，使用reserve将只有一次内存分配。

• 在结尾处使用reverse仅替换了从deque到vector必须执行的copy操作。

- Ami Tavory

---

如果您记得使用vector.rbegin()和vector.rend()，以相反的方式迭代返回值，那么您就不需要使用std::reverse()。如果我知道容器的组织方式是“错误的”，我会发现反向迭代器非常方便！ - emvee

@haavee 很好的观点 - 如果可能的话，你也可以反转“惯例”。 - Ami Tavory

Answer 2

如果您想将std::vector包装在std::queue中，那么std::queue将把元素推到向量的后面（快速方式）。

即使不是这样，因为std::vector是连续存储的，所以即使您使用push_font()，它也有可能优于std::deque，因为它与CPU缓存配合良好，数据洗牌很快。

但为什么不尝试两种方法并对代码进行分析，看哪个更有效呢？

- Galik