为什么 std::priority_queue 中的元素解构了这么多次？

Question

我正在使用

std::priority_queue

进行文件排序，我认为堆是对流数据进行排序的最佳方式。

这是代码：

#include <bits/stdc++.h>
using namespace std;

struct A { 
  A(int a, size_t b, double c) : a_(a), b_(b), c_(c){}
  ~A() { printf("%d dead\n", a_); }
  int a_; 
  size_t b_; 
  double c_; 
  bool operator <(const A & b) const {
    return a_ > b.a_;
  }
  void show() const {
    printf("%d %zu %lf\n", a_, b_, c_);
  }
};

int main() {
  std::priority_queue<A> q;
  q.push(A(1,2,3));
  q.push(A(3,2,3));
  q.push(A(2,2,3));
  while (!q.empty()) {
    const A & s = q.top();
    s.show();
    q.pop();
  }
}

排序过程很好，但让我惊讶的是元素被解构了很多次，输出是：

1 dead
1 dead
1 dead
1 dead
3 dead
3 dead
3 dead
1 dead
3 dead
2 dead
2 dead
2 dead
1 2 3.000000
2 dead
2 dead
2 dead
1 dead
2 2 3.000000
3 dead
3 dead
3 dead
2 dead
3 2 3.000000
3 dead

我认为每个元素都应该解构一次，你能解释一下吗？

我认为只有 3 个元素被构造，我期望的只是 3 次解构。我认为这没有浪费。

Answer 1

首先，正如评论者所指出的，您没有记录应该记录的所有内容。 即，

• 复制构造和移动构造将创建新对象。 此外

• std::priority_queue

  是一个适配器，它使用

  std::vector

  作为容器，调整

  std::vector

  的大小会导致复制/移动构造

话虽如此，对于 GCC 来说，所需的临时对象数量是“令人震惊”的。 对于 q.push(A(1))，至少人们会期望：

A(1)
1. 需要构造为函数参数移动施工将
A(1)
2. 移动到底层

   std::vector

   临时
A(1)
3. 对象被销毁
但是，并非每个标准库都提供这个最低限度。 这是基于 @molbdnilo 代码的

libstdc++ 和 libc++

之间的比较。

// libc++
1 created at 0x7ffdde3ba7b4  // A(1)
1 moved into 0x55d082adb2b0  // move into std::vetor
1 dead at 0x7ffdde3ba7b4     // destroy A(1)

// libstdc++
1 created at 0x7ffeefa52ef8  // A(1)
1 moved into 0x5641c7b9c2c0  // move into std::vector
1 moved into 0x7ffeefa52eb8  // ?!?!
1 moved into 0x7ffeefa52eb0  // ???????
1 move assigned to 0x5641c7b9c2c0 // ????????????
1 dead at 0x7ffeefa52eb0
1 dead at 0x7ffeefa52eb8
1 dead at 0x7ffeefa52ef8     // destroy A(1)