[Bug libstdc++/67085] New: priority queue should not copy comparators when calling push_heap and pop_heap

[konig121 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67085

Bug ID: 67085
   Summary: priority queue should not copy comparators when
calling push_heap and pop_heap
   Product: gcc
   Version: unknown
Status: UNCONFIRMED
  Severity: normal
  Priority: P3
 Component: libstdc++
  Assignee: unassigned at gcc dot gnu.org
  Reporter: konig121 at gmail dot com
  Target Milestone: ---

Created attachment 36103
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=36103&action=edit
Program demonstrating the extra copy operations

The implementation of std::priority_queue's constructor, push, and pop methods
do not force the comparators to be passed by reference, resulting in extra copy
operations. See the attached program for example reproduction steps. The issue
seems to be due to the way that push_heap and pop_heap are called.

[Bug libstdc++/67085] priority queue should not copy comparators when calling push_heap and pop_heap

[konig121 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67085

Andrew Calcutt  changed:

   What|Removed |Added

   Severity|normal  |enhancement

--- Comment #1 from Andrew Calcutt  ---
The current implementation of push and company likely need to be updated to
specify that the comparator be passed by reference explicitly. For Example:

Before:
 std::push_heap(c.begin(), c.end(), comp);

After:
 typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
 std::push_heap<_Sequence::iterator,_Comp_ref>(c.begin(), c.end(), comp);

[Bug libstdc++/67085] priority queue should not copy comparators when calling push_heap and pop_heap

[konig121 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67085

--- Comment #3 from Andrew Calcutt  ---
Hi Jonathan,

I can understand your reservation, but it seems to me like there is a case for
making this change if the comparator provided to the priority_queue was
explicitly a reference type. For example:

 std::priority_queue, MyComparator&> queue;

would create an object which contained a reference to an external comparator.
Even in this case, however, the heap operations would use a copy of the
provided comparator. I believe that fixing this would allow for move only
comparators to be used, and would not require as complex a change. Simply
providing the comparator type to the heap calls would be sufficient without
requiring std::ref.

Are there technical reasons this is not desirable or possible beyond what you
have already stated? Is the behavior of the priority queue here also outside of
the intent of the standard?

Thanks,
Andrew