Hi! This patch makes std::priority_queue constexpr as part of P3372R3. I am unsure whether I should add the FTM here; since the constexpr support for std::queue isn't complete yet, I have omitted the FTM from this patch.
Tested on x86_64-linux. OK for trunk? Additionally, regarding the implementation strategy for other standard containers like std::list, it seems inevitable that we will need to move some function implementations (like _List_node_base) from the .cc files to the headers. This looks like an ABI break. Is this acceptable? Best regards, Yuao
From c4df4c9bced1407499be8c12438ebf1b7c59fca6 Mon Sep 17 00:00:00 2001 From: Yuao Ma <[email protected]> Date: Tue, 2 Jun 2026 22:49:19 +0800 Subject: [PATCH] libstdc++: constexpr priority_queue This patch makes priority_queue constexpr as part of P3372R3. libstdc++-v3/ChangeLog: * include/bits/stl_queue.h: Add constexpr. * testsuite/23_containers/priority_queue/constexpr.cc: New test. --- libstdc++-v3/include/bits/stl_queue.h | 36 +++++++++++++++- .../23_containers/priority_queue/constexpr.cc | 43 +++++++++++++++++++ 2 files changed, 78 insertions(+), 1 deletion(-) create mode 100644 libstdc++-v3/testsuite/23_containers/priority_queue/constexpr.cc diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h index 5dc846e13e1..d00284277a9 100644 --- a/libstdc++-v3/include/bits/stl_queue.h +++ b/libstdc++-v3/include/bits/stl_queue.h @@ -607,28 +607,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Seq = _Sequence, typename _Requires = typename enable_if<__and_<is_default_constructible<_Compare>, is_default_constructible<_Seq>>::value>::type> + _GLIBCXX26_CONSTEXPR priority_queue() : c(), comp() { } + _GLIBCXX26_CONSTEXPR explicit priority_queue(const _Compare& __x, const _Sequence& __s) : c(__s), comp(__x) { std::make_heap(c.begin(), c.end(), comp); } + _GLIBCXX26_CONSTEXPR explicit priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence()) : c(std::move(__s)), comp(__x) { std::make_heap(c.begin(), c.end(), comp); } + _GLIBCXX26_CONSTEXPR priority_queue(const priority_queue&) = default; + _GLIBCXX26_CONSTEXPR priority_queue& operator=(const priority_queue&) = default; + _GLIBCXX26_CONSTEXPR priority_queue(priority_queue&& __q) noexcept(__and_<is_nothrow_move_constructible<_Sequence>, is_nothrow_move_constructible<_Compare>>::value) : c(std::move(__q.c)), comp(std::move(__q.comp)) { __q.c.clear(); } + _GLIBCXX26_CONSTEXPR priority_queue& operator=(priority_queue&& __q) noexcept(__and_<is_nothrow_move_assignable<_Sequence>, @@ -641,32 +648,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR explicit priority_queue(const _Alloc& __a) : c(__a), comp() { } template<typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(const _Compare& __x, const _Alloc& __a) : c(__a), comp(__x) { } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 2537. Constructors [...] taking allocators should call make_heap template<typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(const _Compare& __x, const _Sequence& __c, const _Alloc& __a) : c(__c, __a), comp(__x) { std::make_heap(c.begin(), c.end(), comp); } template<typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) : c(std::move(__c), __a), comp(__x) { std::make_heap(c.begin(), c.end(), comp); } template<typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(const priority_queue& __q, const _Alloc& __a) : c(__q.c, __a), comp(__q.comp) { } template<typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(priority_queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { __q.c.clear(); } @@ -704,6 +717,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // 3529. priority_queue(first, last) should construct c with (first, last) template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x = _Compare()) : c(__first, __last), comp(__x) @@ -713,6 +727,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // 3522. Missing requirement on InputIterator template parameter template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x, const _Sequence& __s) : c(__s), comp(__x) @@ -724,6 +739,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x, _Sequence&& __s) : c(std::move(__s)), comp(__x) @@ -741,6 +757,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator, typename _Alloc, typename = std::_RequireInputIter<_InputIterator>, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc) : c(__first, __last, __alloc), comp() @@ -749,6 +766,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator, typename _Alloc, typename = std::_RequireInputIter<_InputIterator>, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x, const _Alloc& __alloc) : c(__first, __last, __alloc), comp(__x) @@ -757,6 +775,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator, typename _Alloc, typename = std::_RequireInputIter<_InputIterator>, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x, const _Sequence& __s, const _Alloc& __alloc) @@ -769,6 +788,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator, typename _Alloc, typename _Requires = _Uses<_Alloc>> + _GLIBCXX26_CONSTEXPR priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x, _Sequence&& __s, const _Alloc& __alloc) @@ -788,18 +808,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @{ */ template<__detail::__container_compatible_range<_Tp> _Rg> + _GLIBCXX26_CONSTEXPR priority_queue(from_range_t, _Rg&& __rg, const _Compare& __x = _Compare()) : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg))), comp(__x) { std::make_heap(c.begin(), c.end(), comp); } template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc> + _GLIBCXX26_CONSTEXPR priority_queue(from_range_t, _Rg&& __rg, const _Compare& __x, const _Alloc& __a) : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp(__x) { std::make_heap(c.begin(), c.end(), comp); } template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc> + _GLIBCXX26_CONSTEXPR priority_queue(from_range_t, _Rg&& __rg, const _Alloc& __a) : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp() { std::make_heap(c.begin(), c.end(), comp); } @@ -809,12 +832,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * Returns true if the %queue is empty. */ - _GLIBCXX_NODISCARD bool + _GLIBCXX_NODISCARD + _GLIBCXX26_CONSTEXPR + bool empty() const { return c.empty(); } /** Returns the number of elements in the %queue. */ _GLIBCXX_NODISCARD + _GLIBCXX26_CONSTEXPR size_type size() const { return c.size(); } @@ -824,6 +850,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * element of the %queue. */ _GLIBCXX_NODISCARD + _GLIBCXX26_CONSTEXPR const_reference top() const { @@ -839,6 +866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * The time complexity of the operation depends on the underlying * sequence. */ + _GLIBCXX26_CONSTEXPR void push(const value_type& __x) { @@ -847,6 +875,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #if __cplusplus >= 201103L + _GLIBCXX26_CONSTEXPR void push(value_type&& __x) { @@ -855,6 +884,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } template<typename... _Args> + _GLIBCXX26_CONSTEXPR void emplace(_Args&&... __args) { @@ -865,6 +895,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __glibcxx_containers_ranges // C++ >= 23 template<__detail::__container_compatible_range<_Tp> _Rg> + _GLIBCXX26_CONSTEXPR void push_range(_Rg&& __rg) { @@ -887,6 +918,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * data is needed, it should be retrieved before pop() is * called. */ + _GLIBCXX26_CONSTEXPR void pop() { @@ -896,6 +928,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #if __cplusplus >= 201103L + _GLIBCXX26_CONSTEXPR void swap(priority_queue& __pq) noexcept(__and_< @@ -964,6 +997,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus >= 201103L template<typename _Tp, typename _Sequence, typename _Compare> + _GLIBCXX26_CONSTEXPR inline #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 // Constrained free swap overload, see p0185r1 diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/constexpr.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/constexpr.cc new file mode 100644 index 00000000000..fe85617416d --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/priority_queue/constexpr.cc @@ -0,0 +1,43 @@ +// { dg-do compile { target c++26 } } +#include <queue> + +constexpr bool test_constexpr_priority_queue() { + std::priority_queue<int> pq; + if (!pq.empty()) return false; + if (pq.size() != 0) return false; + + pq.push(10); + if (pq.empty()) return false; + if (pq.size() != 1) return false; + if (pq.top() != 10) return false; + + pq.emplace(30); + pq.emplace(20); + if (pq.size() != 3) return false; + if (pq.top() != 30) return false; + + pq.pop(); + if (pq.size() != 2) return false; + if (pq.top() != 20) return false; + + std::priority_queue<int> pq2; + pq2 = pq; + if (pq2.size() != 2) return false; + if (pq2.top() != 20) return false; + + std::priority_queue<int> pq3; + pq3.push(100); + pq.swap(pq3); + if (pq.size() != 1 || pq.top() != 100) return false; + if (pq3.size() != 2 || pq3.top() != 20) return false; + + int arr[] = {50, 200, 10}; + pq.push_range(arr); + if (pq.size() != 4) return false; + if (pq.top() != 200) return false; + + return true; +} + +static_assert(test_constexpr_priority_queue(), + "constexpr priority_queue test failed!"); -- 2.53.0
