在C++优先队列中自定义比较器类的拷贝构造函数被过度调用。

huangapple go评论100阅读模式
英文:

Excessive Invocation of Copy Constructor for Custom Comparator Class in C++ Priority Queue

问题

I had declared a priority_queue with custom comparator having a vector property in it. Below is the full code for it:

CODE

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. class Compare
  4. {
  5. private:
  6. vector<int> vec;
  7. public:
  8. Compare(const vector<int> &vec) { this->vec = vec; }
  9. Compare(const Compare &obj)
  10. {
  11. this->vec = obj.vec;
  12. cout << "Copy Constructor Called!\n";
  13. }
  14. bool operator()(const int &left, const int &right)
  15. {
  16. return vec[left] > vec[right];
  17. }
  18. };
  19. int main(void)
  20. {
  21. vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  22. priority_queue<int, vector<int>, Compare> pq{Compare(vec)};
  23. cout << "Pushing 1\n";
  24. pq.push(1);
  25. cout << "Pushed 1\n";
  26. cout << "Pushing 2\n";
  27. pq.push(2);
  28. cout << "Pushed 2\n";
  29. while (!pq.empty())
  30. {
  31. cout << "Popped = " << pq.top() << '\n';
  32. pq.pop();
  33. }
  34. return 0;
  35. }

But the output is strange!!

OUTPUT

  1. Copy Constructor Called!
  2. Copy Constructor Called!
  3. Copy Constructor Called!
  4. Copy Constructor Called!
  5. Pushing 1
  6. Copy Constructor Called!
  7. Copy Constructor Called!
  8. Copy Constructor Called!
  9. Pushed 1
  10. Pushing 2
  11. Copy Constructor Called!
  12. Copy Constructor Called!
  13. Copy Constructor Called!
  14. Pushed 2
  15. Popped = 1
  16. Copy Constructor Called!
  17. Copy Constructor Called!
  18. Copy Constructor Called!
  19. Copy Constructor Called!
  20. Copy Constructor Called!
  21. Popped = 2
  22. Copy Constructor Called!

Why the copy constructor is called so many times, for every push and pop operation?

Also without any push or pop operation, when I just declared the priority_queue, the copy constructor is called 4 times

Why is this occurring? Isn't it correct that the priority_queue stores the comparator class object and utilizes it whenever comparisons are needed?

英文:

I had declared a priority_queue with custom comparator having a vector property in it. Below is the full code for it:

CODE

  1. #include &lt;bits/stdc++.h&gt;
  2. using namespace std;
  3. class Compare
  4. {
  5. private:
  6. vector&lt;int&gt; vec;
  7. public:
  8. Compare(const vector&lt;int&gt; &amp;vec) { this-&gt;vec = vec; }
  9. Compare(const Compare &amp;obj)
  10. {
  11. this-&gt;vec = obj.vec;
  12. cout &lt;&lt; &quot;Copy Constructor Called!\n&quot;;
  13. }
  14. bool operator()(const int &amp;left, const int &amp;right)
  15. {
  16. return vec[left] &gt; vec[right];
  17. }
  18. };
  19. int main(void)
  20. {
  21. vector&lt;int&gt; vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  22. priority_queue&lt;int, vector&lt;int&gt;, Compare&gt; pq{Compare(vec)};
  23. cout &lt;&lt; &quot;Pushing 1\n&quot;;
  24. pq.push(1);
  25. cout &lt;&lt; &quot;Pushed 1\n&quot;;
  26. cout &lt;&lt; &quot;Pushing 2\n&quot;;
  27. pq.push(2);
  28. cout &lt;&lt; &quot;Pushed 2\n&quot;;
  29. while (!pq.empty())
  30. {
  31. cout &lt;&lt; &quot;Popped = &quot; &lt;&lt; pq.top() &lt;&lt; &#39;\n&#39;;
  32. pq.pop();
  33. }
  34. return 0;
  35. }

But the output is strange!!

OUTPUT

  1. Copy Constructor Called!
  2. Copy Constructor Called!
  3. Copy Constructor Called!
  4. Copy Constructor Called!
  5. Pushing 1
  6. Copy Constructor Called!
  7. Copy Constructor Called!
  8. Copy Constructor Called!
  9. Pushed 1
  10. Pushing 2
  11. Copy Constructor Called!
  12. Copy Constructor Called!
  13. Copy Constructor Called!
  14. Pushed 2
  15. Popped = 1
  16. Copy Constructor Called!
  17. Copy Constructor Called!
  18. Copy Constructor Called!
  19. Copy Constructor Called!
  20. Copy Constructor Called!
  21. Popped = 2
  22. Copy Constructor Called!

Why the copy constructor is called so many times, for every push and pop operation?

Also without any push or pop operation, when I just declared the priority_queue, the copy constructor is called 4 times

Why is this occurring? Isn't it correct that the priority_queue stores the comparator class object and utilizes it whenever comparisons are needed?

答案1

得分: 3

std::make_heap按值传递比较器libstdc++ 实现 make_heap 的许多内部函数也是如此。libc++ 传递方式较少按值传递,但也有一些按值传递。

比较器应该便宜复制。如果它们需要外部数据,请让它们存储指向外部数据的指针。

英文:

std::make_heap takes the comparator by value see, and so do numerous internal functions in the libstdc++ implementation of make_heap. libc++ does less passing by value, but it does some.

Comparators are supposed to be cheap to copy. If they need external data, make them store a pointer to external data.

huangapple
  • 本文由 发表于 2023年6月29日 22:12:34
  • 转载请务必保留本文链接:https://go.coder-hub.com/76581879.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定