priority_queue::replace_top(x)

[• Quuxplusone]

Summary

Add a fast replace_top method to std::priority_queue.

Also std::poke_heap(first, last), which assumes that the given range is in max-heap order *except* for the first element, which needs to be put into its proper place. This is just like push_heap, except that push_heap assumes the *last* element is out of order, whereas poke_heap assumes the *first* element is out of order.

The changes in <queue> could use _VSTD::poke_heap instead of __sift_down, but they do not, in order to keep the <queue> changes usable as a single-file patch (in case someone wants to take the <queue> changes without the <algorithm> changes).

The poke_heap approach would replace the last line of each new method with this line instead:

_VSTD::poke_heap(c.begin(), c.end(), comp);

---

I did this patch a while back for a blog post, and initially didn't intend to do anything else with it. Just recently I learned that people (well, Simon Brand and @Leandros) apparently want it enough to tweet about the existence of the patch
https://twitter.com/ArvidGerstmann/status/1071033081719676928
so I figure I should take the next step and actually post it for review.
(The blog post in question was https://quuxplusone.github.io/blog/2018/04/27/pq-replace-top/ )

[• Quuxplusone]

Brought unit tests into line with https://reviews.llvm.org/rL353086

[mclow.lists]

Arthur - I'm sorry to say that this will go nowhere.
You're introducing non-reserved identifiers into libc++, which can cause legal code to break.

For example:

#define poke_heap 9+7
#include <queue>

Same with replace_top
Users are prohibited from doing this for names that is mentioned in the standard, but neither of those fall into that category.
that's why __sift_down is named how it is, for example - users can't define them as a macro.

[• Quuxplusone]

@mclow.lists: Easy peasy! Please take another look.

[mclow.lists]

In D57734#1385286, @Quuxplusone wrote:

@mclow.lists: Easy peasy! Please take another look.

Now no one outside of libc++ can call it (legally)

[• Quuxplusone]

@mclow.lists wrote:

Now no one outside of libc++ can call it (legally)

True. Is that a problem for libc++? I mean, what you're forced to do in the absence of this patch is to call __sift_down, which also can't be done (legally).

Anyway, I'd like to see if anyone else registers an opinion on the desirability of this feature.

[mclow.lists]

No one is "forced" to call __sift_down. In fact, it's explicitly forbidden by the standard.

[• Quuxplusone]

Reverted names back to friendly names. (The uglified __names were a conforming extension; but the friendly names are what people would actually want to use. As this patch is likely going to be stagnant on Phab for a while, I'd rather have it be in the state that's directly apply-able for anyone who does want to merge it locally.)

[ldionne]

I think this functionality might be interesting, but trying to get this into libc++ before it is standardized is definitely putting the cart before the horse. I understand that putting the patch here may make it easier for people to apply it to their local copy of libc++. Hopefully not many people think of themselves as vendors and maintain their own libc++ :-).

include/queue

549

This should instead be #if _LIBCPP_STD_VER > 23, or whatever standard version you target with this feature.

test/libcxx/containers/container.adaptors/priority.queue/priqueue.members/replace_top_rvalue.pass.cpp

10

This should be UNSUPPORTED until the standard version where the feature is being added.

[ldionne]

@Quuxplusone Please re-ping this when/if this feature makes it into the standard so that we avoid re-doing the work.

include/algorithm

 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
     _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
+// poke_heap
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_INLINE_VISIBILITY
+void
+poke_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
+{
+    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
+#ifdef _LIBCPP_DEBUG
+    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
+    __debug_less<_Compare> __c(__comp);
+    __sift_down<_Comp_ref>(__first, __last, __comp, __len, __first);
+#else  // _LIBCPP_DEBUG
+    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
+    __sift_down<_Comp_ref>(__first, __last, __comp, __len, __first);
+#endif  // _LIBCPP_DEBUG
+}
+
+template <class _RandomAccessIterator>
+inline _LIBCPP_INLINE_VISIBILITY
+void
+poke_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+{
+    _VSTD::poke_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+}
+
 // make_heap
 
 template <class _Compare, class _RandomAccessIterator>
 void
 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     difference_type __n = __last - __first;

include/queue

#ifndef _LIBCPP_CXX03_LANG
     template <class... _Args>
     _LIBCPP_INLINE_VISIBILITY
     void emplace(_Args&&... __args);
 #endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     void pop();
 
     _LIBCPP_INLINE_VISIBILITY
+    void replace_top(const value_type& __v);
+#ifndef _LIBCPP_CXX03_LANG
+    _LIBCPP_INLINE_VISIBILITY
+    void replace_top(value_type&& __v);
+    template <class... _Args>
+    _LIBCPP_INLINE_VISIBILITY
+    void reemplace_top(_Args&&... __args);
+#endif  // _LIBCPP_CXX03_LANG
+
+    _LIBCPP_INLINE_VISIBILITY
     void swap(priority_queue& __q)
         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
                    __is_nothrow_swappable<value_compare>::value);
 };
 
 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
 template <class _Compare,
           class _Container,

 {
     _VSTD::pop_heap(c.begin(), c.end(), comp);
     c.pop_back();
 }
 
 template <class _Tp, class _Container, class _Compare>
 inline
 void
+priority_queue<_Tp, _Container, _Compare>::replace_top(const value_type& __v)
+{
+    c.front() = __v;
+    __sift_down<typename add_lvalue_reference<_Compare>::type>(c.begin(), c.end(), comp, c.size(), c.begin());
+}
+
+#ifndef _LIBCPP_CXX03_LANG
+
+template <class _Tp, class _Container, class _Compare>
+inline
+void
+priority_queue<_Tp, _Container, _Compare>::replace_top(value_type&& __v)
+{
+    c.front() = _VSTD::move(__v);
+    __sift_down<typename add_lvalue_reference<_Compare>::type>(c.begin(), c.end(), comp, c.size(), c.begin());
+}
+
+template <class _Tp, class _Container, class _Compare>
+template <class... _Args>
+inline
+void
+priority_queue<_Tp, _Container, _Compare>::reemplace_top(_Args&&... __args)
+{
+    c.front() = _Tp(_VSTD::forward<_Args>(__args)...);
+    __sift_down<typename add_lvalue_reference<_Compare>::type>(c.begin(), c.end(), comp, c.size(), c.begin());
+}
+
+#endif  // _LIBCPP_CXX03_LANG
+
+template <class _Tp, class _Container, class _Compare>
+inline
+void
 priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
         _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
                    __is_nothrow_swappable<value_compare>::value)
 {
     using _VSTD::swap;
     swap(c, __q.c);
     swap(comp, __q.comp);
 }

test/libcxx/algorithms/alg.sorting/alg.heap.operations/poke.heap/poke_heap.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter>
+//         && LessThanComparable<Iter::value_type>
+//   void
+//   poke_heap(Iter first, Iter last);
+
+#include <algorithm>
+#include <random>
+#include <cassert>
+#include <stdio.h>
+
+std::mt19937 randomness;
+
+void test(int M, int N)
+{
+    int* inputs = new int [N];
+    for (int i = 0; i < N; ++i)
+        inputs[i] = i;
+    std::shuffle(inputs, inputs+N, randomness);
+    int* heap = new int[M];
+    int* control = new int[M];
+    std::make_heap(inputs, inputs+M);
+    std::copy(inputs, inputs+M, heap);
+    std::copy(inputs, inputs+M, control);
+    for (int i = 0; i < N; ++i) {
+        std::pop_heap(control, control+M);
+        control[M-1] = inputs[i];
+        heap[0] = inputs[i];
+        std::push_heap(control, control+M);
+        std::poke_heap(heap, heap+M);
+        assert(std::is_heap(control, control+M));
+        assert(std::is_heap(heap, heap+M));
+        assert(std::is_permutation(heap, heap+M, control));
+    }
+    delete [] control;
+    delete [] heap;
+    delete [] inputs;
+}
+
+int main(int, char**)
+{
+    test(100, 1000);
+
+    // Test small cases
+    int ia[] = {1, 2, 3};
+    std::poke_heap(ia, ia);  // no-op
+    assert(ia[0] == 1);
+    std::poke_heap(ia, ia+1);  // no-op
+    assert(ia[0] == 1);
+    std::poke_heap(ia, ia+2);
+    assert(ia[0] == 2 && ia[1] == 1);
+
+  return 0;
+}

test/libcxx/algorithms/alg.sorting/alg.heap.operations/poke.heap/poke_heap_comp.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter>
+//         && LessThanComparable<Iter::value_type>
+//   void
+//   poke_heap(Iter first, Iter last);
+
+#include <algorithm>
+#include <functional>
+#include <random>
+#include <cassert>
+
+#include "test_macros.h"
+
+std::mt19937 randomness;
+
+void test(int M, int N)
+{
+    int* inputs = new int [N];
+    for (int i = 0; i < N; ++i)
+        inputs[i] = i;
+    std::shuffle(inputs, inputs+N, randomness);
+    int* heap = new int[M];
+    int* control = new int[M];
+    std::make_heap(inputs, inputs+M, std::greater<int>());
+    std::copy(inputs, inputs+M, heap);
+    std::copy(inputs, inputs+M, control);
+    for (int i = 0; i < N; ++i) {
+        std::pop_heap(control, control+M, std::greater<int>());
+        control[M-1] = inputs[i];
+        heap[0] = inputs[i];
+        std::push_heap(control, control+M, std::greater<int>());
+        std::poke_heap(heap, heap+M, std::greater<int>());
+        assert(std::is_heap(control, control+M, std::greater<int>()));
+        assert(std::is_heap(heap, heap+M, std::greater<int>()));
+        assert(std::is_permutation(heap, heap+M, control));
+    }
+    delete [] control;
+    delete [] heap;
+    delete [] inputs;
+}
+
+int main(int, char**)
+{
+    test(100, 1000);
+
+    // Test small cases
+    int ia[] = {3, 2, 1};
+    std::poke_heap(ia, ia, std::greater<int>());  // no-op
+    assert(ia[0] == 3);
+    std::poke_heap(ia, ia+1, std::greater<int>());  // no-op
+    assert(ia[0] == 3);
+    std::poke_heap(ia, ia+2, std::greater<int>());
+    assert(ia[0] == 2 && ia[1] == 3);
+
+  return 0;
+}

test/libcxx/containers/container.adaptors/priority.queue/priqueue.members/reemplace_top.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03
+
+// <queue>
+
+// priority_queue();
+
+// template <class... Args> void reemplace_top(Args&&... args);
+
+#include <queue>
+#include <cassert>
+
+#include "../../../../../std/containers/Emplaceable.h"
+
+int main(int, char**)
+{
+    std::priority_queue<Emplaceable> q;
+    q.emplace(1, 2.5);
+    assert(q.top() == Emplaceable(1, 2.5));
+    q.emplace(3, 4.5);
+    assert(q.top() == Emplaceable(3, 4.5));
+    q.reemplace_top(2, 3.5);
+    assert(q.top() == Emplaceable(2, 3.5));
+    q.reemplace_top(0, 1.5);
+    assert(q.top() == Emplaceable(1, 2.5));
+
+  return 0;
+}

test/libcxx/containers/container.adaptors/priority.queue/priqueue.members/replace_top.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// priority_queue();
+
+// void replace_top(const value_type& v);
+
+#include <queue>
+#include <cassert>
+
+int main(int, char**)
+{
+    std::priority_queue<int> q;
+    q.push(1);
+    assert(q.top() == 1);
+    q.push(3);
+    assert(q.top() == 3);
+    q.replace_top(2);
+    assert(q.top() == 2);
+    q.replace_top(0);
+    assert(q.top() == 1);
+
+  return 0;
+}

test/libcxx/containers/container.adaptors/priority.queue/priqueue.members/replace_top_rvalue.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03
+
+// <queue>
+
+// priority_queue();
+
+// void replace_top(value_type&& v);
+
+#include <queue>
+#include <cassert>
+
+#include "MoveOnly.h"
+
+int main(int, char**)
+{
+    std::priority_queue<MoveOnly> q;
+    q.push(1);
+    assert(q.top() == 1);
+    q.push(3);
+    assert(q.top() == 3);
+    q.replace_top(2);
+    assert(q.top() == 2);
+    q.replace_top(0);
+    assert(q.top() == 1);
+
+  return 0;
+}