Search code examples
c++performancepriority-queueemplace

priority_queue::emplace calls push_heap?

According to CPP Reference, std::priority_queue::emplace "effectively calls" 

c.emplace_back(std::forward<Args>(args)...); 
std::push_heap(c.begin(), c.end(), comp);

What does "effectively" mean here? Does it mean emplace has the same functionality as those calls, or that emplace is literally implemented using those calls (my understanding is that the implementation is left to the compilers). If emplace is literally implemented that way, isn't that inefficient? If I add one element to an existing heap, I shouldn't need to heapify the entire heap.

Solution

  • The implementation certainly doesn't have to call the algorithm but probably it does. After emplacing() the element it will be move towards the root until the heap invariant is restored. Note that push_heap() does not touch the entire heap: that would be make_heap(). Instead, push_heap() deals only with adding one new element.