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); https://reviews.llvm.org/D57734
Quuxplusone · Feb 5, 2019 · d1c84fd · d1c84fd
1 parent 49af5dc
commit d1c84fd
Show file tree

Hide file tree

Showing 2 changed files with 68 additions and 0 deletions.
diff --git a/include/algorithm b/include/algorithm
@@ -4907,6 +4907,32 @@ 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>

diff --git a/include/queue b/include/queue
@@ -544,6 +544,16 @@ public:
     _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 &&
@@ -766,6 +776,38 @@ priority_queue<_Tp, _Container, _Compare>::pop()
     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