The reason of using `std::greater` for creating min heap via `priority_queue`

by

The logical argument is as follows

  1. std::priority_queue is a container adaptor; basic memory considerations make the back the preferred place for modifications (with pop_back() and push_back()) for sequence containers such as std::vector.
  2. the priority_queue primitives are based on std::make_heap (constructor), std::pop_heap + container::pop_back (priority_queue::pop) and on container::push_back + std::push_heap (priority_queue::push)
  3. pop_heap will take the front of the underlying storage, and put it at the back, restoring the heap invariant afterwards. The reverse goes for push_heap.
  4. doing sort_heap on a max_heap (with the max at the front initially) will repeatedly pop the front to the back and sort the range according to less (which is the default comparison operator)
  5. hence, the preferred implementation of a max_heap is to have the max element w.r.t. less at the front, accessed through priority_queue::top (underlying container::front).
  6. one can still debate whether it is intuitive that priority_queue with a std::less comparator is representing a max_heap. It could have been defined as a min_heap by reversing the comparator’s arguments (but see the comment by @T.C. that with C++98 binders this is rather verbose) everywhere in the calls to the various heap functions. The one (for me) counter-intuitive result would have been that top() would then not have given the element with top priority

More Related Contents:

  1. C++ priority_queue with lambda comparator error
  2. Error while passing vector to instance of object in main
  3. Concurrency: Atomic and volatile in C++11 memory model
  4. const vs constexpr on variables
  5. What is a subnormal floating point number?
  6. Pointers in c++ after delete
  7. Why does std::move prevent RVO (return value optimization)?
  8. Does a C++11 range-based for loop condition get evaluated every cycle?
  9. why is `std::initializer_list` often passed by value?
  10. C++11: Compile-time Array with Logarithmic Evaluation Depth
  11. why do lambda functions in c++11 not have function types?
  12. Difference between std::result_of and decltype
  13. Is a `=default` move constructor equivalent to a member-wise move constructor?
  14. How to enable experimental C++11 concurrency features in MinGW?
  15. Is int arr[ ] valid C++?
  16. Can I use std::async without waiting for the future limitation?
  17. std::fstream buffering vs manual buffering (why 10x gain with manual buffering)?
  18. how to avoid static member function when using gsl with c++
  19. Need iterator when using ranged-based for loops
  20. C++ terminate called without an active exception
  21. How to enforce the ‘override’ keyword?
  22. C++11 operator”” with double parameter
  23. std::remove_const with const references
  24. Uniform initialization fails to copy when object has no data members
  25. C++11: Replace all non-owning raw pointers with std::shared_ptr()?
  26. Can we apply content not explicitly cited from the normative references to the C++ standard?
  27. “What happened to my SFINAE” redux: conditional template class members?
  28. Concatenate compile-time strings in a template at compile time?
  29. using extern template (C++11) to avoid instantiation
  30. When will C++0x be finished? [closed]

Leave a Comment