C++ Std 队列和 vector 性能

Question

我最近一直在处理图形，我正在研究从图形返回路径。该路径需要作为包含所有节点的标准 vector 返回，其中起始节点在前。

我一直在寻找两种选择: - 使用slow vector insert方法在vector前面添加节点 - 使用双端队列将节点添加到前端 (push_front)，这样速度更快。然后使用 std::copy 将双端队列复制到 vector

与另一种方法相比，使用一种方法是否有显着的性能提升？

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 只是替换了 copy 的使用，您必须从 deque 到 vector。