3

我有两个priority_queue这样的float：

std::priority_queue<float> queue1;
std::priority_queue<float> queue2;

我需要合并它们。但是 STLmerge算法不允许priority_queue直接使用：

merge(
  queue1.begin(), queue2.end(),
  queue2.begin(), queue2.end(),
  queue1
);

有没有办法在priority_queue不使用辅助数据结构的情况下进行合并？

4

3 回答 3

5

priority_queue是容器适配器，而不是常规的标准容器。特别是，它不提供begin()andend()成员函数。因此，您必须将元素从一个队列中弹出并将它们推入另一个队列：

while (!queue2.empty())
{
    queue1.push(queue2.top());
    queue2.pop();
}
于 2013-04-06T14:59:57.293 回答
5

添加到 Andy 的答案中，一项重要的优化是始终将较小优先级队列中的元素合并到较大的优先级队列中。这可以使用std::swap：

// merge elements into dest from src
template<typename T>
void merge_pq(std::priority_queue<T>& dest, std::priority_queue<T>& src) {
  if (dest.size() < src.size()) {
    std::swap(dest, src);
  }
  while (!src.empty()) {
    dest.push(src.top());
    src.pop();
  }
}

这可以产生真正的差异，尤其是当两个优先级队列的大小非常不同时。

在最近的 Facebook 黑客杯编程竞赛中，有一个问题要求您将优先级队列合并为更大算法的一部分。如果您不进行此优化，您的代码将花费太长时间，并且您将无法正确回答问题。这发生在我身上；我的代码在没有这个优化的情况下运行了 5 多分钟，但在比赛结束后我添加这个优化时不到 10 秒。我没有收到这个问题的功劳。希望如果您正在阅读本文并遇到类似的问题，您会更成功:)

于 2018-09-20T02:26:46.187 回答
1

为了获得更好的性能，您可以从队列中“窃取”底层容器，合并它们并从合并的容器中构造另一个，而不是像之前建议的那样逐个处理它们priority_queue：

// https://stackoverflow.com/a/1385520/8414561
template <class T, class S, class C>
S& Container(std::priority_queue<T, S, C>& q) {
    struct HackedQueue : private std::priority_queue<T, S, C> {
        static S& Container(std::priority_queue<T, S, C>& q) {
            return q.*&HackedQueue::c;
        }
    };
    return HackedQueue::Container(q);
}

int main()
{
    std::priority_queue<int> queue1{std::less<int>{}, {1,2,3,4,5,6,7}};
    std::priority_queue<int> queue2{std::less<int>{}, {10,14,15}};

    auto v1 = std::move(Container(queue1));
    auto v2 = std::move(Container(queue2));

    v1.insert(v1.end(), std::make_move_iterator(v2.begin()), std::make_move_iterator(v2.end()));

    std::priority_queue<int>queue3{std::less<int>{}, std::move(v1)};
    while (!queue3.empty()) {
        std::cout << queue3.top() << std::endl;
        queue3.pop();
    }
}

活生生的例子。

于 2018-09-20T05:43:12.807 回答