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

[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 <konig121 at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

--- Comment #1 from Andrew Calcutt <konig121 at gmail dot com> ---
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

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |WONTFIX

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Andrew Calcutt from comment #1)
>  typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
>  std::push_heap<_Sequence::iterator,_Comp_ref>(c.begin(), c.end(), comp);

Apart from the fact that this is not valid in C++03, this is not how push_heap
is meant to be used. It is defined to take its arguments by value, not by
reference, so it's expected to be cheap to copy the functor, which is common to
all STL algorithms. I see no reason to change that just for priority_queue
(although if we were to do it I'd use std::ref not std::add_lvalue_reference).

[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 <konig121 at gmail dot com> ---
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<int, std::vector<int>, 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

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

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Andrew Calcutt from comment #3)
> 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?

Yes, using a reference type for the comparison object of std::priority_queue is
highly quesitonable. Use std::reference_wrapper<C> if you want reference
semantics.