[PATCH] libstdc++: constexpr priority_queue
Jonathan Wakely
jwakely@redhat.com
Tue Jun 2 15:07:54 GMT 2026
On Tue, 02 Jun 2026 at 22:59 +0800, Yuao Ma wrote:
>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 <c8ef@outlook.com>
>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
These two changes are not needed. The defaulted special members will
be constexpr by default.
> 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
Please put the two SHOUTING MACROS on the same line.
>+ bool
> empty() const
> { return c.empty(); }
>
> /** Returns the number of elements in the %queue. */
> _GLIBCXX_NODISCARD
>+ _GLIBCXX26_CONSTEXPR
Same here.
> size_type
> size() const
> { return c.size(); }
>@@ -824,6 +850,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> * element of the %queue.
> */
> _GLIBCXX_NODISCARD
>+ _GLIBCXX26_CONSTEXPR
And here.
> 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
>
More information about the Libstdc++
mailing list