c++ - 如何有效地将整个队列复制到 C++ 中的向量/数组？

Question

如何有效地将整个队列复制到 C++ 中的向量/数组？

假设我有一个 std::queue 并且在某些时候我想将它复制到一个向量/一个数组然后对其进行排序。

感谢大家的回答。

我真正想做的是创建一个固定长度的窗口，有时我需要复制该窗口内的所有元素并对它们进行排序。窗口正在移动，并且有新数据通过另一个界面进入，所以我想使用队列。有没有更好的实现？

Answer 1

如果您只想保留排序队列，请查看priority_queue。

Answer 2

你写了：

我真正想做的是创建一个固定长度的窗口，有时我需要复制该窗口内的所有元素并对它们进行排序。窗口正在移动，并且有新数据通过另一个界面进入，所以我想使用队列。

我建议退后一步，重新考虑你是否真的想使用queue. 我想你想要它是因为你

1. 想要向将数据添加到队列的其他组件公开一个最小接口。
2. 在前/后有效添加/删除元素（以实现“固定宽度窗口”概念）
3. 访问排序窗口中可见数据的有效方法

不幸的是，std::queue不太适合（3）。因此，我建议寻找地址（2）和（3）的东西，然后考虑编写某种包装器（也许是一个简单的函数，它只是将一个元素添加到队列中？）来实现（1 ）。

例如，我会考虑使用普通的std::deque. 它可以在恒定时间内从队列的开头/结尾添加/删除元素。在窗口上获得排序视图也很容易，例如，如果复制队列的元素很便宜，您可以使用std::sort如下：

std::vector<Elem> sortedView( queue.begin(), queue.end() );
std::sort( sortedView.begin(), sortedView.end() );

...您当然也可以通过不复制数据而是vector在队列中创建一个迭代器或使用不同的排序算法（如partial_sort.

Answer 3

访问 std::queue 元素的唯一方法是使用 , , 的组合，因为front没有迭代器。（为了能够使用迭代器，您应该直接使用底层容器（例如 std::deque），而不是 std::queue。backpushpopstd::queue

由于您要制作副本（大概将元素保留在队列中），因此您可以在弹出元素后将它们推回队列中。

此外，由于您知道队列的大小，您可以使用它vector::reserve来防止由vector::push_back. 所以

std::vector<int> V;
std::queue<int> Q;
V.reserve(Q.size());
for(size_t numPos = 0; numPops < Q.size(); ++numPops) {
  V.push_back(Q.front());
  Q.pop();
  Q.push(V.back());
}
std::sort(V.begin(), V.end());

Answer 4

老实说，最好的选择是从一开始就使用正确的 STL 数据结构。如果您想要对数据进行排序，则 std::queue不是正确的数据结构。

考虑使用映射（或者可能是哈希映射）。地图的典型实现实际上构建了排序的地图，查找在 O(ln) 时间内执行。如果您真的愿意，您仍然可以按顺序遍历地图。