| // Queue implementation -*- C++ -*- | |
| // Copyright (C) 2001-2025 Free Software Foundation, Inc. | |
| // | |
| // This file is part of the GNU ISO C++ Library. This library is free | |
| // software; you can redistribute it and/or modify it under the | |
| // terms of the GNU General Public License as published by the | |
| // Free Software Foundation; either version 3, or (at your option) | |
| // any later version. | |
| // This library is distributed in the hope that it will be useful, | |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| // GNU General Public License for more details. | |
| // Under Section 7 of GPL version 3, you are granted additional | |
| // permissions described in the GCC Runtime Library Exception, version | |
| // 3.1, as published by the Free Software Foundation. | |
| // You should have received a copy of the GNU General Public License and | |
| // a copy of the GCC Runtime Library Exception along with this program; | |
| // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
| // <http://www.gnu.org/licenses/>. | |
| /* | |
| * | |
| * Copyright (c) 1994 | |
| * Hewlett-Packard Company | |
| * | |
| * Permission to use, copy, modify, distribute and sell this software | |
| * and its documentation for any purpose is hereby granted without fee, | |
| * provided that the above copyright notice appear in all copies and | |
| * that both that copyright notice and this permission notice appear | |
| * in supporting documentation. Hewlett-Packard Company makes no | |
| * representations about the suitability of this software for any | |
| * purpose. It is provided "as is" without express or implied warranty. | |
| * | |
| * | |
| * Copyright (c) 1996,1997 | |
| * Silicon Graphics Computer Systems, Inc. | |
| * | |
| * Permission to use, copy, modify, distribute and sell this software | |
| * and its documentation for any purpose is hereby granted without fee, | |
| * provided that the above copyright notice appear in all copies and | |
| * that both that copyright notice and this permission notice appear | |
| * in supporting documentation. Silicon Graphics makes no | |
| * representations about the suitability of this software for any | |
| * purpose. It is provided "as is" without express or implied warranty. | |
| */ | |
| /** @file bits/stl_queue.h | |
| * This is an internal header file, included by other library headers. | |
| * Do not attempt to use it directly. @headername{queue} | |
| */ | |
| #ifndef _STL_QUEUE_H | |
| #define _STL_QUEUE_H 1 | |
| #include <bits/concept_check.h> | |
| #include <debug/debug.h> | |
| #if __cplusplus >= 201103L | |
| # include <bits/uses_allocator.h> | |
| #endif | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| # include <ranges> // ranges::to | |
| # include <bits/ranges_algobase.h> // ranges::copy | |
| #endif | |
| namespace std _GLIBCXX_VISIBILITY(default) | |
| { | |
| _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
| #if __glibcxx_format_ranges | |
| template<typename, typename> class formatter; | |
| #endif | |
| /** | |
| * @brief A standard container giving FIFO behavior. | |
| * | |
| * @ingroup sequences | |
| * | |
| * @tparam _Tp Type of element. | |
| * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>. | |
| * | |
| * Meets many of the requirements of a | |
| * <a href="tables.html#65">container</a>, | |
| * but does not define anything to do with iterators. Very few of the | |
| * other standard container interfaces are defined. | |
| * | |
| * This is not a true container, but an @e adaptor. It holds another | |
| * container, and provides a wrapper interface to that container. The | |
| * wrapper is what enforces strict first-in-first-out %queue behavior. | |
| * | |
| * The second template parameter defines the type of the underlying | |
| * sequence/container. It defaults to std::deque, but it can be any type | |
| * that supports @c front, @c back, @c push_back, and @c pop_front, | |
| * such as std::list or an appropriate user-defined type. | |
| * | |
| * Members not found in @a normal containers are @c container_type, | |
| * which is a typedef for the second Sequence parameter, and @c push and | |
| * @c pop, which are standard %queue/FIFO operations. | |
| */ | |
| template<typename _Tp, typename _Sequence = deque<_Tp> > | |
| class queue | |
| { | |
| #ifdef _GLIBCXX_CONCEPT_CHECKS | |
| // concept requirements | |
| typedef typename _Sequence::value_type _Sequence_value_type; | |
| # if __cplusplus < 201103L | |
| __glibcxx_class_requires(_Tp, _SGIAssignableConcept) | |
| # endif | |
| __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) | |
| __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) | |
| __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) | |
| #endif | |
| template<typename _Tp1, typename _Seq1> | |
| friend bool | |
| operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); | |
| template<typename _Tp1, typename _Seq1> | |
| friend bool | |
| operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); | |
| #if __cpp_lib_three_way_comparison | |
| template<typename _Tp1, three_way_comparable _Seq1> | |
| friend compare_three_way_result_t<_Seq1> | |
| operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); | |
| #endif | |
| #if __cplusplus >= 201103L | |
| template<typename _Alloc> | |
| using _Uses = typename | |
| enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; | |
| #if __cplusplus >= 201703L | |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
| // 2566. Requirements on the first template parameter of container | |
| // adaptors | |
| static_assert(is_same<_Tp, typename _Sequence::value_type>::value, | |
| "value_type must be the same as the underlying container"); | |
| #endif // C++17 | |
| #endif // C++11 | |
| public: | |
| typedef typename _Sequence::value_type value_type; | |
| typedef typename _Sequence::reference reference; | |
| typedef typename _Sequence::const_reference const_reference; | |
| typedef typename _Sequence::size_type size_type; | |
| typedef _Sequence container_type; | |
| protected: | |
| /* Maintainers wondering why this isn't uglified as per style | |
| * guidelines should note that this name is specified in the standard, | |
| * C++98 [23.2.3.1]. | |
| * (Why? Presumably for the same reason that it's protected instead | |
| * of private: to allow derivation. But none of the other | |
| * containers allow for derivation. Odd.) | |
| */ | |
| /// @c c is the underlying container. | |
| _Sequence c; | |
| public: | |
| /** | |
| * @brief Default constructor creates no elements. | |
| */ | |
| #if __cplusplus < 201103L | |
| explicit | |
| queue(const _Sequence& __c = _Sequence()) | |
| : c(__c) { } | |
| #else | |
| template<typename _Seq = _Sequence, typename _Requires = typename | |
| enable_if<is_default_constructible<_Seq>::value>::type> | |
| queue() | |
| : c() { } | |
| explicit | |
| queue(const _Sequence& __c) | |
| : c(__c) { } | |
| explicit | |
| queue(_Sequence&& __c) | |
| : c(std::move(__c)) { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| explicit | |
| queue(const _Alloc& __a) | |
| : c(__a) { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| queue(const _Sequence& __c, const _Alloc& __a) | |
| : c(__c, __a) { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| queue(_Sequence&& __c, const _Alloc& __a) | |
| : c(std::move(__c), __a) { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| queue(const queue& __q, const _Alloc& __a) | |
| : c(__q.c, __a) { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| queue(queue&& __q, const _Alloc& __a) | |
| : c(std::move(__q.c), __a) { } | |
| #endif | |
| #ifdef __glibcxx_adaptor_iterator_pair_constructor // C++ >= 23 && HOSTED | |
| template<typename _InputIterator, | |
| typename = _RequireInputIter<_InputIterator>> | |
| queue(_InputIterator __first, _InputIterator __last) | |
| : c(__first, __last) { } | |
| template<typename _InputIterator, typename _Alloc, | |
| typename = _RequireInputIter<_InputIterator>, | |
| typename = _Uses<_Alloc>> | |
| queue(_InputIterator __first, _InputIterator __last, const _Alloc& __a) | |
| : c(__first, __last, __a) { } | |
| #endif | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| /** | |
| * @brief Construct a queue from a range. | |
| * @since C++23 | |
| */ | |
| template<__detail::__container_compatible_range<_Tp> _Rg> | |
| queue(from_range_t, _Rg&& __rg) | |
| : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg))) | |
| { } | |
| /** | |
| * @brief Construct a queue from a range. | |
| * @since C++23 | |
| */ | |
| template<__detail::__container_compatible_range<_Tp> _Rg, | |
| typename _Alloc> | |
| queue(from_range_t, _Rg&& __rg, const _Alloc& __a) | |
| : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)) | |
| { } | |
| #endif | |
| /** | |
| * Returns true if the %queue is empty. | |
| */ | |
| _GLIBCXX_NODISCARD bool | |
| empty() const | |
| { return c.empty(); } | |
| /** Returns the number of elements in the %queue. */ | |
| _GLIBCXX_NODISCARD | |
| size_type | |
| size() const | |
| { return c.size(); } | |
| /** | |
| * Returns a read/write reference to the data at the first | |
| * element of the %queue. | |
| */ | |
| _GLIBCXX_NODISCARD | |
| reference | |
| front() | |
| { | |
| __glibcxx_requires_nonempty(); | |
| return c.front(); | |
| } | |
| /** | |
| * Returns a read-only (constant) reference to the data at the first | |
| * element of the %queue. | |
| */ | |
| _GLIBCXX_NODISCARD | |
| const_reference | |
| front() const | |
| { | |
| __glibcxx_requires_nonempty(); | |
| return c.front(); | |
| } | |
| /** | |
| * Returns a read/write reference to the data at the last | |
| * element of the %queue. | |
| */ | |
| _GLIBCXX_NODISCARD | |
| reference | |
| back() | |
| { | |
| __glibcxx_requires_nonempty(); | |
| return c.back(); | |
| } | |
| /** | |
| * Returns a read-only (constant) reference to the data at the last | |
| * element of the %queue. | |
| */ | |
| _GLIBCXX_NODISCARD | |
| const_reference | |
| back() const | |
| { | |
| __glibcxx_requires_nonempty(); | |
| return c.back(); | |
| } | |
| /** | |
| * @brief Add data to the end of the %queue. | |
| * @param __x Data to be added. | |
| * | |
| * This is a typical %queue operation. The function creates an | |
| * element at the end of the %queue and assigns the given data | |
| * to it. The time complexity of the operation depends on the | |
| * underlying sequence. | |
| */ | |
| void | |
| push(const value_type& __x) | |
| { c.push_back(__x); } | |
| #if __cplusplus >= 201103L | |
| void | |
| push(value_type&& __x) | |
| { c.push_back(std::move(__x)); } | |
| #if __cplusplus > 201402L | |
| template<typename... _Args> | |
| decltype(auto) | |
| emplace(_Args&&... __args) | |
| { return c.emplace_back(std::forward<_Args>(__args)...); } | |
| #else | |
| template<typename... _Args> | |
| void | |
| emplace(_Args&&... __args) | |
| { c.emplace_back(std::forward<_Args>(__args)...); } | |
| #endif | |
| #endif | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| template<__detail::__container_compatible_range<_Tp> _Rg> | |
| void | |
| push_range(_Rg&& __rg) | |
| { | |
| if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); }) | |
| c.append_range(std::forward<_Rg>(__rg)); | |
| else | |
| ranges::copy(__rg, std::back_inserter(c)); | |
| } | |
| #endif | |
| /** | |
| * @brief Removes first element. | |
| * | |
| * This is a typical %queue operation. It shrinks the %queue by one. | |
| * The time complexity of the operation depends on the underlying | |
| * sequence. | |
| * | |
| * Note that no data is returned, and if the first element's | |
| * data is needed, it should be retrieved before pop() is | |
| * called. | |
| */ | |
| void | |
| pop() | |
| { | |
| __glibcxx_requires_nonempty(); | |
| c.pop_front(); | |
| } | |
| #if __cplusplus >= 201103L | |
| void | |
| swap(queue& __q) | |
| #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 | |
| noexcept(__is_nothrow_swappable<_Sequence>::value) | |
| #else | |
| noexcept(__is_nothrow_swappable<_Tp>::value) | |
| #endif | |
| { | |
| using std::swap; | |
| swap(c, __q.c); | |
| } | |
| #endif // __cplusplus >= 201103L | |
| #if __glibcxx_format_ranges | |
| friend class formatter<queue<_Tp, _Sequence>, char>; | |
| friend class formatter<queue<_Tp, _Sequence>, wchar_t>; | |
| #endif | |
| }; | |
| #if __cpp_deduction_guides >= 201606 | |
| template<typename _Container, | |
| typename = _RequireNotAllocator<_Container>> | |
| queue(_Container) -> queue<typename _Container::value_type, _Container>; | |
| template<typename _Container, typename _Allocator, | |
| typename = _RequireNotAllocator<_Container>> | |
| queue(_Container, _Allocator) | |
| -> queue<typename _Container::value_type, _Container>; | |
| #ifdef __glibcxx_adaptor_iterator_pair_constructor | |
| template<typename _InputIterator, | |
| typename _ValT | |
| = typename iterator_traits<_InputIterator>::value_type, | |
| typename = _RequireInputIter<_InputIterator>> | |
| queue(_InputIterator, _InputIterator) -> queue<_ValT>; | |
| template<typename _InputIterator, typename _Allocator, | |
| typename _ValT | |
| = typename iterator_traits<_InputIterator>::value_type, | |
| typename = _RequireInputIter<_InputIterator>, | |
| typename = _RequireAllocator<_Allocator>> | |
| queue(_InputIterator, _InputIterator, _Allocator) | |
| -> queue<_ValT, deque<_ValT, _Allocator>>; | |
| #endif | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| template<ranges::input_range _Rg> | |
| queue(from_range_t, _Rg&&) -> queue<ranges::range_value_t<_Rg>>; | |
| template<ranges::input_range _Rg, __allocator_like _Alloc> | |
| queue(from_range_t, _Rg&&, _Alloc) | |
| -> queue<ranges::range_value_t<_Rg>, | |
| deque<ranges::range_value_t<_Rg>, _Alloc>>; | |
| #endif | |
| #endif | |
| /** | |
| * @brief Queue equality comparison. | |
| * @param __x A %queue. | |
| * @param __y A %queue of the same type as @a __x. | |
| * @return True iff the size and elements of the queues are equal. | |
| * | |
| * This is an equivalence relation. Complexity and semantics depend on the | |
| * underlying sequence type, but the expected rules are: this relation is | |
| * linear in the size of the sequences, and queues are considered equivalent | |
| * if their sequences compare equal. | |
| */ | |
| template<typename _Tp, typename _Seq> | |
| _GLIBCXX_NODISCARD | |
| inline bool | |
| operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return __x.c == __y.c; } | |
| /** | |
| * @brief Queue ordering relation. | |
| * @param __x A %queue. | |
| * @param __y A %queue of the same type as @a x. | |
| * @return True iff @a __x is lexicographically less than @a __y. | |
| * | |
| * This is an total ordering relation. Complexity and semantics | |
| * depend on the underlying sequence type, but the expected rules | |
| * are: this relation is linear in the size of the sequences, the | |
| * elements must be comparable with @c <, and | |
| * std::lexicographical_compare() is usually used to make the | |
| * determination. | |
| */ | |
| template<typename _Tp, typename _Seq> | |
| _GLIBCXX_NODISCARD | |
| inline bool | |
| operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return __x.c < __y.c; } | |
| /// Based on operator== | |
| template<typename _Tp, typename _Seq> | |
| _GLIBCXX_NODISCARD | |
| inline bool | |
| operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return !(__x == __y); } | |
| /// Based on operator< | |
| template<typename _Tp, typename _Seq> | |
| _GLIBCXX_NODISCARD | |
| inline bool | |
| operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return __y < __x; } | |
| /// Based on operator< | |
| template<typename _Tp, typename _Seq> | |
| _GLIBCXX_NODISCARD | |
| inline bool | |
| operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return !(__y < __x); } | |
| /// Based on operator< | |
| template<typename _Tp, typename _Seq> | |
| _GLIBCXX_NODISCARD | |
| inline bool | |
| operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return !(__x < __y); } | |
| #if __cpp_lib_three_way_comparison | |
| template<typename _Tp, three_way_comparable _Seq> | |
| [[nodiscard]] | |
| inline compare_three_way_result_t<_Seq> | |
| operator<=>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) | |
| { return __x.c <=> __y.c; } | |
| #endif | |
| #if __cplusplus >= 201103L | |
| template<typename _Tp, typename _Seq> | |
| inline | |
| #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 | |
| // Constrained free swap overload, see p0185r1 | |
| typename enable_if<__is_swappable<_Seq>::value>::type | |
| #else | |
| void | |
| #endif | |
| swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) | |
| noexcept(noexcept(__x.swap(__y))) | |
| { __x.swap(__y); } | |
| template<typename _Tp, typename _Seq, typename _Alloc> | |
| struct uses_allocator<queue<_Tp, _Seq>, _Alloc> | |
| : public uses_allocator<_Seq, _Alloc>::type { }; | |
| #endif // __cplusplus >= 201103L | |
| /** | |
| * @brief A standard container automatically sorting its contents. | |
| * | |
| * @ingroup sequences | |
| * | |
| * @tparam _Tp Type of element. | |
| * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>. | |
| * @tparam _Compare Comparison function object type, defaults to | |
| * less<_Sequence::value_type>. | |
| * | |
| * This is not a true container, but an @e adaptor. It holds | |
| * another container, and provides a wrapper interface to that | |
| * container. The wrapper is what enforces priority-based sorting | |
| * and %queue behavior. Very few of the standard container/sequence | |
| * interface requirements are met (e.g., iterators). | |
| * | |
| * The second template parameter defines the type of the underlying | |
| * sequence/container. It defaults to std::vector, but it can be | |
| * any type that supports @c front(), @c push_back, @c pop_back, | |
| * and random-access iterators, such as std::deque or an | |
| * appropriate user-defined type. | |
| * | |
| * The third template parameter supplies the means of making | |
| * priority comparisons. It defaults to @c less<value_type> but | |
| * can be anything defining a strict weak ordering. | |
| * | |
| * Members not found in @a normal containers are @c container_type, | |
| * which is a typedef for the second Sequence parameter, and @c | |
| * push, @c pop, and @c top, which are standard %queue operations. | |
| * | |
| * @note No equality/comparison operators are provided for | |
| * %priority_queue. | |
| * | |
| * @note Sorting of the elements takes place as they are added to, | |
| * and removed from, the %priority_queue using the | |
| * %priority_queue's member functions. If you access the elements | |
| * by other means, and change their data such that the sorting | |
| * order would be different, the %priority_queue will not re-sort | |
| * the elements for you. (How could it know to do so?) | |
| */ | |
| template<typename _Tp, typename _Sequence = vector<_Tp>, | |
| typename _Compare = less<typename _Sequence::value_type> > | |
| class priority_queue | |
| { | |
| #ifdef _GLIBCXX_CONCEPT_CHECKS | |
| // concept requirements | |
| typedef typename _Sequence::value_type _Sequence_value_type; | |
| # if __cplusplus < 201103L | |
| __glibcxx_class_requires(_Tp, _SGIAssignableConcept) | |
| # endif | |
| __glibcxx_class_requires(_Sequence, _SequenceConcept) | |
| __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) | |
| __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) | |
| __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, | |
| _BinaryFunctionConcept) | |
| #endif | |
| #if __cplusplus >= 201103L | |
| template<typename _Alloc> | |
| using _Uses = typename | |
| enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; | |
| #if __cplusplus >= 201703L | |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
| // 2566. Requirements on the first template parameter of container | |
| // adaptors | |
| static_assert(is_same<_Tp, typename _Sequence::value_type>::value, | |
| "value_type must be the same as the underlying container"); | |
| #endif // C++17 | |
| #endif // C++11 | |
| public: | |
| typedef typename _Sequence::value_type value_type; | |
| typedef typename _Sequence::reference reference; | |
| typedef typename _Sequence::const_reference const_reference; | |
| typedef typename _Sequence::size_type size_type; | |
| typedef _Sequence container_type; | |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
| // DR 2684. priority_queue lacking comparator typedef | |
| typedef _Compare value_compare; | |
| protected: | |
| // See queue::c for notes on these names. | |
| _Sequence c; | |
| _Compare comp; | |
| public: | |
| /** | |
| * @brief Default constructor creates no elements. | |
| */ | |
| #if __cplusplus < 201103L | |
| explicit | |
| priority_queue(const _Compare& __x = _Compare(), | |
| const _Sequence& __s = _Sequence()) | |
| : c(__s), comp(__x) | |
| { std::make_heap(c.begin(), c.end(), comp); } | |
| #else | |
| template<typename _Seq = _Sequence, typename _Requires = typename | |
| enable_if<__and_<is_default_constructible<_Compare>, | |
| is_default_constructible<_Seq>>::value>::type> | |
| priority_queue() | |
| : c(), comp() { } | |
| explicit | |
| priority_queue(const _Compare& __x, const _Sequence& __s) | |
| : c(__s), comp(__x) | |
| { std::make_heap(c.begin(), c.end(), comp); } | |
| explicit | |
| priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence()) | |
| : c(std::move(__s)), comp(__x) | |
| { std::make_heap(c.begin(), c.end(), comp); } | |
| priority_queue(const priority_queue&) = default; | |
| priority_queue& operator=(const priority_queue&) = default; | |
| 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(); } | |
| priority_queue& | |
| operator=(priority_queue&& __q) | |
| noexcept(__and_<is_nothrow_move_assignable<_Sequence>, | |
| is_nothrow_move_assignable<_Compare>>::value) | |
| { | |
| c = std::move(__q.c); | |
| __q.c.clear(); | |
| comp = std::move(__q.comp); | |
| return *this; | |
| } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| explicit | |
| priority_queue(const _Alloc& __a) | |
| : c(__a), comp() { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| 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>> | |
| 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>> | |
| 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>> | |
| priority_queue(const priority_queue& __q, const _Alloc& __a) | |
| : c(__q.c, __a), comp(__q.comp) { } | |
| template<typename _Alloc, typename _Requires = _Uses<_Alloc>> | |
| priority_queue(priority_queue&& __q, const _Alloc& __a) | |
| : c(std::move(__q.c), __a), comp(std::move(__q.comp)) | |
| { __q.c.clear(); } | |
| #endif | |
| /** | |
| * @brief Builds a %queue from a range. | |
| * @param __first An input iterator. | |
| * @param __last An input iterator. | |
| * @param __x A comparison functor describing a strict weak ordering. | |
| * @param __s An initial sequence with which to start. | |
| * | |
| * Begins by copying @a __s, inserting a copy of the elements | |
| * from @a [first,last) into the copy of @a __s, then ordering | |
| * the copy according to @a __x. | |
| * | |
| * For more information on function objects, see the | |
| * documentation on @link functors functor base classes@endlink. | |
| */ | |
| #if __cplusplus < 201103L | |
| template<typename _InputIterator> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x = _Compare(), | |
| const _Sequence& __s = _Sequence()) | |
| : c(__s), comp(__x) | |
| { | |
| __glibcxx_requires_valid_range(__first, __last); | |
| c.insert(c.end(), __first, __last); | |
| std::make_heap(c.begin(), c.end(), comp); | |
| } | |
| #else | |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
| // 3529. priority_queue(first, last) should construct c with (first, last) | |
| template<typename _InputIterator, | |
| typename = std::_RequireInputIter<_InputIterator>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x = _Compare()) | |
| : c(__first, __last), comp(__x) | |
| { std::make_heap(c.begin(), c.end(), comp); } | |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
| // 3522. Missing requirement on InputIterator template parameter | |
| template<typename _InputIterator, | |
| typename = std::_RequireInputIter<_InputIterator>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x, const _Sequence& __s) | |
| : c(__s), comp(__x) | |
| { | |
| __glibcxx_requires_valid_range(__first, __last); | |
| c.insert(c.end(), __first, __last); | |
| std::make_heap(c.begin(), c.end(), comp); | |
| } | |
| template<typename _InputIterator, | |
| typename = std::_RequireInputIter<_InputIterator>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x, _Sequence&& __s) | |
| : c(std::move(__s)), comp(__x) | |
| { | |
| __glibcxx_requires_valid_range(__first, __last); | |
| c.insert(c.end(), __first, __last); | |
| std::make_heap(c.begin(), c.end(), comp); | |
| } | |
| // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
| // 3506. Missing allocator-extended constructors for priority_queue | |
| template<typename _InputIterator, typename _Alloc, | |
| typename = std::_RequireInputIter<_InputIterator>, | |
| typename _Requires = _Uses<_Alloc>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Alloc& __alloc) | |
| : c(__first, __last, __alloc), comp() | |
| { std::make_heap(c.begin(), c.end(), comp); } | |
| template<typename _InputIterator, typename _Alloc, | |
| typename = std::_RequireInputIter<_InputIterator>, | |
| typename _Requires = _Uses<_Alloc>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x, const _Alloc& __alloc) | |
| : c(__first, __last, __alloc), comp(__x) | |
| { std::make_heap(c.begin(), c.end(), comp); } | |
| template<typename _InputIterator, typename _Alloc, | |
| typename = std::_RequireInputIter<_InputIterator>, | |
| typename _Requires = _Uses<_Alloc>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x, const _Sequence& __s, | |
| const _Alloc& __alloc) | |
| : c(__s, __alloc), comp(__x) | |
| { | |
| __glibcxx_requires_valid_range(__first, __last); | |
| c.insert(c.end(), __first, __last); | |
| std::make_heap(c.begin(), c.end(), comp); | |
| } | |
| template<typename _InputIterator, typename _Alloc, | |
| typename _Requires = _Uses<_Alloc>> | |
| priority_queue(_InputIterator __first, _InputIterator __last, | |
| const _Compare& __x, _Sequence&& __s, | |
| const _Alloc& __alloc) | |
| : c(std::move(__s), __alloc), comp(__x) | |
| { | |
| __glibcxx_requires_valid_range(__first, __last); | |
| c.insert(c.end(), __first, __last); | |
| std::make_heap(c.begin(), c.end(), comp); | |
| } | |
| #endif | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| /** | |
| * @brief Construct a priority_queue from a range. | |
| * @since C++23 | |
| * | |
| * @{ | |
| */ | |
| template<__detail::__container_compatible_range<_Tp> _Rg> | |
| 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> | |
| 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> | |
| 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); } | |
| /// @} | |
| #endif | |
| /** | |
| * Returns true if the %queue is empty. | |
| */ | |
| _GLIBCXX_NODISCARD bool | |
| empty() const | |
| { return c.empty(); } | |
| /** Returns the number of elements in the %queue. */ | |
| _GLIBCXX_NODISCARD | |
| size_type | |
| size() const | |
| { return c.size(); } | |
| /** | |
| * Returns a read-only (constant) reference to the data at the first | |
| * element of the %queue. | |
| */ | |
| _GLIBCXX_NODISCARD | |
| const_reference | |
| top() const | |
| { | |
| __glibcxx_requires_nonempty(); | |
| return c.front(); | |
| } | |
| /** | |
| * @brief Add data to the %queue. | |
| * @param __x Data to be added. | |
| * | |
| * This is a typical %queue operation. | |
| * The time complexity of the operation depends on the underlying | |
| * sequence. | |
| */ | |
| void | |
| push(const value_type& __x) | |
| { | |
| c.push_back(__x); | |
| std::push_heap(c.begin(), c.end(), comp); | |
| } | |
| #if __cplusplus >= 201103L | |
| void | |
| push(value_type&& __x) | |
| { | |
| c.push_back(std::move(__x)); | |
| std::push_heap(c.begin(), c.end(), comp); | |
| } | |
| template<typename... _Args> | |
| void | |
| emplace(_Args&&... __args) | |
| { | |
| c.emplace_back(std::forward<_Args>(__args)...); | |
| std::push_heap(c.begin(), c.end(), comp); | |
| } | |
| #endif | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| template<__detail::__container_compatible_range<_Tp> _Rg> | |
| void | |
| push_range(_Rg&& __rg) | |
| { | |
| if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); }) | |
| c.append_range(std::forward<_Rg>(__rg)); | |
| else | |
| ranges::copy(__rg, std::back_inserter(c)); | |
| std::make_heap(c.begin(), c.end(), comp); | |
| } | |
| #endif | |
| /** | |
| * @brief Removes first element. | |
| * | |
| * This is a typical %queue operation. It shrinks the %queue | |
| * by one. The time complexity of the operation depends on the | |
| * underlying sequence. | |
| * | |
| * Note that no data is returned, and if the first element's | |
| * data is needed, it should be retrieved before pop() is | |
| * called. | |
| */ | |
| void | |
| pop() | |
| { | |
| __glibcxx_requires_nonempty(); | |
| std::pop_heap(c.begin(), c.end(), comp); | |
| c.pop_back(); | |
| } | |
| #if __cplusplus >= 201103L | |
| void | |
| swap(priority_queue& __pq) | |
| noexcept(__and_< | |
| #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 | |
| __is_nothrow_swappable<_Sequence>, | |
| #else | |
| __is_nothrow_swappable<_Tp>, | |
| #endif | |
| __is_nothrow_swappable<_Compare> | |
| >::value) | |
| { | |
| using std::swap; | |
| swap(c, __pq.c); | |
| swap(comp, __pq.comp); | |
| } | |
| #endif // __cplusplus >= 201103L | |
| #if __glibcxx_format_ranges | |
| friend class formatter<priority_queue<_Tp, _Sequence, _Compare>, char>; | |
| friend class formatter<priority_queue<_Tp, _Sequence, _Compare>, wchar_t>; | |
| #endif | |
| }; | |
| #if __cpp_deduction_guides >= 201606 | |
| template<typename _Compare, typename _Container, | |
| typename = _RequireNotAllocator<_Compare>, | |
| typename = _RequireNotAllocator<_Container>> | |
| priority_queue(_Compare, _Container) | |
| -> priority_queue<typename _Container::value_type, _Container, _Compare>; | |
| template<typename _InputIterator, typename _ValT | |
| = typename iterator_traits<_InputIterator>::value_type, | |
| typename _Compare = less<_ValT>, | |
| typename _Container = vector<_ValT>, | |
| typename = _RequireInputIter<_InputIterator>, | |
| typename = _RequireNotAllocator<_Compare>, | |
| typename = _RequireNotAllocator<_Container>> | |
| priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), | |
| _Container = _Container()) | |
| -> priority_queue<_ValT, _Container, _Compare>; | |
| template<typename _Compare, typename _Container, typename _Allocator, | |
| typename = _RequireNotAllocator<_Compare>, | |
| typename = _RequireNotAllocator<_Container>> | |
| priority_queue(_Compare, _Container, _Allocator) | |
| -> priority_queue<typename _Container::value_type, _Container, _Compare>; | |
| #if __glibcxx_containers_ranges // C++ >= 23 | |
| template<ranges::input_range _Rg, | |
| __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>, | |
| __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>> | |
| priority_queue(from_range_t, _Rg&&, _Compare = _Compare(), | |
| _Alloc = _Alloc()) | |
| -> priority_queue<ranges::range_value_t<_Rg>, | |
| vector<ranges::range_value_t<_Rg>, _Alloc>, | |
| _Compare>; | |
| template<ranges::input_range _Rg, __allocator_like _Alloc> | |
| priority_queue(from_range_t, _Rg&&, _Alloc) | |
| -> priority_queue<ranges::range_value_t<_Rg>, | |
| vector<ranges::range_value_t<_Rg>, _Alloc>>; | |
| #endif | |
| #endif | |
| // No equality/comparison operators are provided for priority_queue. | |
| #if __cplusplus >= 201103L | |
| template<typename _Tp, typename _Sequence, typename _Compare> | |
| inline | |
| #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 | |
| // Constrained free swap overload, see p0185r1 | |
| typename enable_if<__and_<__is_swappable<_Sequence>, | |
| __is_swappable<_Compare>>::value>::type | |
| #else | |
| void | |
| #endif | |
| swap(priority_queue<_Tp, _Sequence, _Compare>& __x, | |
| priority_queue<_Tp, _Sequence, _Compare>& __y) | |
| noexcept(noexcept(__x.swap(__y))) | |
| { __x.swap(__y); } | |
| template<typename _Tp, typename _Sequence, typename _Compare, | |
| typename _Alloc> | |
| struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> | |
| : public uses_allocator<_Sequence, _Alloc>::type { }; | |
| #endif // __cplusplus >= 201103L | |
| _GLIBCXX_END_NAMESPACE_VERSION | |
| } // namespace | |
| #endif /* _STL_QUEUE_H */ |