Warning, /include/c++/v1/__cxx03/queue is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___CXX03_QUEUE
0011 #define _LIBCPP___CXX03_QUEUE
0012
0013 /*
0014 queue synopsis
0015
0016 namespace std
0017 {
0018
0019 template <class T, class Container = deque<T>>
0020 class queue
0021 {
0022 public:
0023 typedef Container container_type;
0024 typedef typename container_type::value_type value_type;
0025 typedef typename container_type::reference reference;
0026 typedef typename container_type::const_reference const_reference;
0027 typedef typename container_type::size_type size_type;
0028
0029 protected:
0030 container_type c;
0031
0032 public:
0033 queue() = default;
0034 ~queue() = default;
0035
0036 queue(const queue& q) = default;
0037 queue(queue&& q) = default;
0038
0039 queue& operator=(const queue& q) = default;
0040 queue& operator=(queue&& q) = default;
0041
0042 explicit queue(const container_type& c);
0043 explicit queue(container_type&& c)
0044 template<class InputIterator>
0045 queue(InputIterator first, InputIterator last); // since C++23
0046 template<container-compatible-range<T> R> queue(from_range_t, R&& rg); // since C++23
0047 template <class Alloc>
0048 explicit queue(const Alloc& a);
0049 template <class Alloc>
0050 queue(const container_type& c, const Alloc& a);
0051 template <class Alloc>
0052 queue(container_type&& c, const Alloc& a);
0053 template <class Alloc>
0054 queue(const queue& q, const Alloc& a);
0055 template <class Alloc>
0056 queue(queue&& q, const Alloc& a);
0057 template <class InputIterator, class Alloc>
0058 queue(InputIterator first, InputIterator last, const Alloc&); // since C++23
0059 template<container-compatible-range<T> R, class Alloc>
0060 queue(from_range_t, R&& rg, const Alloc&); // since C++23
0061
0062 bool empty() const;
0063 size_type size() const;
0064
0065 reference front();
0066 const_reference front() const;
0067 reference back();
0068 const_reference back() const;
0069
0070 void push(const value_type& v);
0071 void push(value_type&& v);
0072 template<container-compatible-range<T> R>
0073 void push_range(R&& rg); // C++23
0074 template <class... Args> reference emplace(Args&&... args); // reference in C++17
0075 void pop();
0076
0077 void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
0078 };
0079
0080 template<class Container>
0081 queue(Container) -> queue<typename Container::value_type, Container>; // C++17
0082
0083 template<class InputIterator>
0084 queue(InputIterator, InputIterator) -> queue<iter-value-type<InputIterator>>; // since C++23
0085
0086 template<ranges::input_range R>
0087 queue(from_range_t, R&&) -> queue<ranges::range_value_t<R>>; // since C++23
0088
0089 template<class Container, class Allocator>
0090 queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17
0091
0092 template<class InputIterator, class Allocator>
0093 queue(InputIterator, InputIterator, Allocator)
0094 -> queue<iter-value-type<InputIterator>,
0095 deque<iter-value-type<InputIterator>, Allocator>>; // since C++23
0096
0097 template<ranges::input_range R, class Allocator>
0098 queue(from_range_t, R&&, Allocator)
0099 -> queue<ranges::range_value_t<R>, deque<ranges::range_value_t<R>, Allocator>>; // since C++23
0100
0101 template <class T, class Container>
0102 bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
0103
0104 template <class T, class Container>
0105 bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
0106
0107 template <class T, class Container>
0108 bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
0109
0110 template <class T, class Container>
0111 bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
0112
0113 template <class T, class Container>
0114 bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
0115
0116 template <class T, class Container>
0117 bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
0118
0119 template<class T, three_way_comparable Container>
0120 compare_three_way_result_t<Container>
0121 operator<=>(const queue<T, Container>& x, const queue<T, Container>& y); // since C++20
0122
0123 template <class T, class Container>
0124 void swap(queue<T, Container>& x, queue<T, Container>& y)
0125 noexcept(noexcept(x.swap(y)));
0126
0127 template <class T, class Container = vector<T>,
0128 class Compare = less<typename Container::value_type>>
0129 class priority_queue
0130 {
0131 public:
0132 typedef Container container_type;
0133 typedef typename container_type::value_type value_type;
0134 typedef typename container_type::reference reference;
0135 typedef typename container_type::const_reference const_reference;
0136 typedef typename container_type::size_type size_type;
0137
0138 protected:
0139 container_type c;
0140 Compare comp;
0141
0142 public:
0143 priority_queue() : priority_queue(Compare()) {} // C++20
0144 explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
0145 priority_queue(const Compare& x, const Container&);
0146 explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20
0147 priority_queue(const Compare& x, Container&&); // C++20
0148 template <class InputIterator>
0149 priority_queue(InputIterator first, InputIterator last,
0150 const Compare& comp = Compare());
0151 template <class InputIterator>
0152 priority_queue(InputIterator first, InputIterator last,
0153 const Compare& comp, const Container& c);
0154 template <class InputIterator>
0155 priority_queue(InputIterator first, InputIterator last,
0156 const Compare& comp, Container&& c);
0157 template <container-compatible-range<T> R>
0158 priority_queue(from_range_t, R&& rg, const Compare& x = Compare()); // since C++23
0159 template <class Alloc>
0160 explicit priority_queue(const Alloc& a);
0161 template <class Alloc>
0162 priority_queue(const Compare& comp, const Alloc& a);
0163 template <class Alloc>
0164 priority_queue(const Compare& comp, const Container& c,
0165 const Alloc& a);
0166 template <class Alloc>
0167 priority_queue(const Compare& comp, Container&& c,
0168 const Alloc& a);
0169 template <class InputIterator>
0170 priority_queue(InputIterator first, InputIterator last,
0171 const Alloc& a);
0172 template <class InputIterator>
0173 priority_queue(InputIterator first, InputIterator last,
0174 const Compare& comp, const Alloc& a);
0175 template <class InputIterator>
0176 priority_queue(InputIterator first, InputIterator last,
0177 const Compare& comp, const Container& c, const Alloc& a);
0178 template <class InputIterator>
0179 priority_queue(InputIterator first, InputIterator last,
0180 const Compare& comp, Container&& c, const Alloc& a);
0181 template <container-compatible-range<T> R, class Alloc>
0182 priority_queue(from_range_t, R&& rg, const Compare&, const Alloc&); // since C++23
0183 template <container-compatible-range<T> R, class Alloc>
0184 priority_queue(from_range_t, R&& rg, const Alloc&); // since C++23
0185 template <class Alloc>
0186 priority_queue(const priority_queue& q, const Alloc& a);
0187 template <class Alloc>
0188 priority_queue(priority_queue&& q, const Alloc& a);
0189
0190 bool empty() const;
0191 size_type size() const;
0192 const_reference top() const;
0193
0194 void push(const value_type& v);
0195 void push(value_type&& v);
0196 template<container-compatible-range<T> R>
0197 void push_range(R&& rg); // C++23
0198 template <class... Args> void emplace(Args&&... args);
0199 void pop();
0200
0201 void swap(priority_queue& q)
0202 noexcept(is_nothrow_swappable_v<Container> &&
0203 is_nothrow_swappable_v<Comp>)
0204 };
0205
0206 template <class Compare, class Container>
0207 priority_queue(Compare, Container)
0208 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
0209
0210 template<class InputIterator,
0211 class Compare = less<iter-value-type<InputIterator>>,
0212 class Container = vector<iter-value-type<InputIterator>>>
0213 priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
0214 -> priority_queue<iter-value-type<InputIterator>, Container, Compare>; // C++17
0215
0216 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>>
0217 priority_queue(from_range_t, R&&, Compare = Compare())
0218 -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>>, Compare>; // C++23
0219
0220 template<class Compare, class Container, class Allocator>
0221 priority_queue(Compare, Container, Allocator)
0222 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
0223
0224 template<class InputIterator, class Allocator>
0225 priority_queue(InputIterator, InputIterator, Allocator)
0226 -> priority_queue<iter-value-type<InputIterator>,
0227 vector<iter-value-type<InputIterator>, Allocator>,
0228 less<iter-value-type<InputIterator>>>; // C++17
0229
0230 template<class InputIterator, class Compare, class Allocator>
0231 priority_queue(InputIterator, InputIterator, Compare, Allocator)
0232 -> priority_queue<iter-value-type<InputIterator>,
0233 vector<iter-value-type<InputIterator>, Allocator>, Compare>; // C++17
0234
0235 template<class InputIterator, class Compare, class Container, class Allocator>
0236 priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
0237 -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
0238
0239 template<ranges::input_range R, class Compare, class Allocator>
0240 priority_queue(from_range_t, R&&, Compare, Allocator)
0241 -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>,
0242 Compare>; // C++23
0243
0244 template<ranges::input_range R, class Allocator>
0245 priority_queue(from_range_t, R&&, Allocator)
0246 -> priority_queue<ranges::range_value_t<R>, vector<ranges::range_value_t<R>, Allocator>>; // C++23
0247
0248 template <class T, class Container, class Compare>
0249 void swap(priority_queue<T, Container, Compare>& x,
0250 priority_queue<T, Container, Compare>& y)
0251 noexcept(noexcept(x.swap(y)));
0252
0253 } // std
0254
0255 */
0256
0257 #include <__cxx03/__algorithm/make_heap.h>
0258 #include <__cxx03/__algorithm/pop_heap.h>
0259 #include <__cxx03/__algorithm/push_heap.h>
0260 #include <__cxx03/__algorithm/ranges_copy.h>
0261 #include <__cxx03/__config>
0262 #include <__cxx03/__functional/operations.h>
0263 #include <__cxx03/__fwd/deque.h>
0264 #include <__cxx03/__fwd/queue.h>
0265 #include <__cxx03/__iterator/back_insert_iterator.h>
0266 #include <__cxx03/__iterator/iterator_traits.h>
0267 #include <__cxx03/__memory/uses_allocator.h>
0268 #include <__cxx03/__ranges/access.h>
0269 #include <__cxx03/__ranges/concepts.h>
0270 #include <__cxx03/__ranges/container_compatible_range.h>
0271 #include <__cxx03/__ranges/from_range.h>
0272 #include <__cxx03/__utility/forward.h>
0273 #include <__cxx03/deque>
0274 #include <__cxx03/vector>
0275 #include <__cxx03/version>
0276
0277 // standard-mandated includes
0278
0279 // [queue.syn]
0280 #include <__cxx03/compare>
0281 #include <__cxx03/initializer_list>
0282
0283 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0284 # pragma GCC system_header
0285 #endif
0286
0287 _LIBCPP_PUSH_MACROS
0288 #include <__cxx03/__undef_macros>
0289
0290 _LIBCPP_BEGIN_NAMESPACE_STD
0291
0292 template <class _Tp, class _Container>
0293 _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
0294
0295 template <class _Tp, class _Container>
0296 _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
0297
0298 template <class _Tp, class _Container /*= deque<_Tp>*/>
0299 class _LIBCPP_TEMPLATE_VIS queue {
0300 public:
0301 typedef _Container container_type;
0302 typedef typename container_type::value_type value_type;
0303 typedef typename container_type::reference reference;
0304 typedef typename container_type::const_reference const_reference;
0305 typedef typename container_type::size_type size_type;
0306 static_assert(is_same<_Tp, value_type>::value, "");
0307
0308 protected:
0309 container_type c;
0310
0311 public:
0312 _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}
0313
0314 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {}
0315
0316 #if _LIBCPP_STD_VER >= 23
0317 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0318 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
0319
0320 template <_ContainerCompatibleRange<_Tp> _Range>
0321 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}
0322
0323 template <class _InputIterator,
0324 class _Alloc,
0325 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
0326 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0327 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)
0328 : c(__first, __second, __alloc) {}
0329
0330 template <_ContainerCompatibleRange<_Tp> _Range,
0331 class _Alloc,
0332 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0333 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc)
0334 : c(from_range, std::forward<_Range>(__range), __alloc) {}
0335
0336 #endif
0337
0338 _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) {
0339 c = __q.c;
0340 return *this;
0341 }
0342
0343 #ifndef _LIBCPP_CXX03_LANG
0344 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)
0345 : c(std::move(__q.c)) {}
0346
0347 _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {
0348 c = std::move(__q.c);
0349 return *this;
0350 }
0351 #endif // _LIBCPP_CXX03_LANG
0352
0353 _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {}
0354 #ifndef _LIBCPP_CXX03_LANG
0355 _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {}
0356 #endif // _LIBCPP_CXX03_LANG
0357
0358 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0359 _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a) : c(__a) {}
0360
0361 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0362 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q, const _Alloc& __a) : c(__q.c, __a) {}
0363
0364 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0365 _LIBCPP_HIDE_FROM_ABI queue(const container_type& __c, const _Alloc& __a) : c(__c, __a) {}
0366
0367 #ifndef _LIBCPP_CXX03_LANG
0368 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0369 _LIBCPP_HIDE_FROM_ABI queue(container_type&& __c, const _Alloc& __a) : c(std::move(__c), __a) {}
0370
0371 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0372 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a) {}
0373 #endif // _LIBCPP_CXX03_LANG
0374
0375 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
0376 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
0377
0378 _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); }
0379 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); }
0380 _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); }
0381 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); }
0382
0383 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }
0384 #ifndef _LIBCPP_CXX03_LANG
0385 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }
0386
0387 # if _LIBCPP_STD_VER >= 23
0388 template <_ContainerCompatibleRange<_Tp> _Range>
0389 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
0390 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
0391 c.append_range(std::forward<_Range>(__range));
0392 } else {
0393 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
0394 }
0395 }
0396 # endif
0397
0398 template <class... _Args>
0399 _LIBCPP_HIDE_FROM_ABI
0400 # if _LIBCPP_STD_VER >= 17
0401 decltype(auto)
0402 emplace(_Args&&... __args) {
0403 return c.emplace_back(std::forward<_Args>(__args)...);
0404 }
0405 # else
0406 void
0407 emplace(_Args&&... __args) {
0408 c.emplace_back(std::forward<_Args>(__args)...);
0409 }
0410 # endif
0411 #endif // _LIBCPP_CXX03_LANG
0412 _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); }
0413
0414 _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {
0415 using std::swap;
0416 swap(c, __q.c);
0417 }
0418
0419 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
0420
0421 template <class _T1, class _OtherContainer>
0422 friend _LIBCPP_HIDE_FROM_ABI bool
0423 operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
0424
0425 template <class _T1, class _OtherContainer>
0426 friend _LIBCPP_HIDE_FROM_ABI bool
0427 operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
0428 };
0429
0430 #if _LIBCPP_STD_VER >= 17
0431 template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> >
0432 queue(_Container) -> queue<typename _Container::value_type, _Container>;
0433
0434 template <class _Container,
0435 class _Alloc,
0436 class = enable_if_t<!__is_allocator<_Container>::value>,
0437 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
0438 queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>;
0439 #endif
0440
0441 #if _LIBCPP_STD_VER >= 23
0442 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0443 queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>;
0444
0445 template <ranges::input_range _Range>
0446 queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>;
0447
0448 template <class _InputIterator,
0449 class _Alloc,
0450 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
0451 __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
0452 queue(_InputIterator,
0453 _InputIterator,
0454 _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
0455
0456 template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
0457 queue(from_range_t,
0458 _Range&&,
0459 _Alloc) -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;
0460 #endif
0461
0462 template <class _Tp, class _Container>
0463 inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0464 return __x.c == __y.c;
0465 }
0466
0467 template <class _Tp, class _Container>
0468 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0469 return __x.c < __y.c;
0470 }
0471
0472 template <class _Tp, class _Container>
0473 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0474 return !(__x == __y);
0475 }
0476
0477 template <class _Tp, class _Container>
0478 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0479 return __y < __x;
0480 }
0481
0482 template <class _Tp, class _Container>
0483 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0484 return !(__x < __y);
0485 }
0486
0487 template <class _Tp, class _Container>
0488 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0489 return !(__y < __x);
0490 }
0491
0492 #if _LIBCPP_STD_VER >= 20
0493
0494 template <class _Tp, three_way_comparable _Container>
0495 _LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
0496 operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0497 // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
0498 return __x.__get_container() <=> __y.__get_container();
0499 }
0500
0501 #endif
0502
0503 template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>
0504 inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
0505 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
0506 __x.swap(__y);
0507 }
0508
0509 template <class _Tp, class _Container, class _Alloc>
0510 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {
0511 };
0512
0513 template <class _Tp, class _Container, class _Compare>
0514 class _LIBCPP_TEMPLATE_VIS priority_queue {
0515 public:
0516 typedef _Container container_type;
0517 typedef _Compare value_compare;
0518 typedef typename container_type::value_type value_type;
0519 typedef typename container_type::reference reference;
0520 typedef typename container_type::const_reference const_reference;
0521 typedef typename container_type::size_type size_type;
0522 static_assert(is_same<_Tp, value_type>::value, "");
0523
0524 protected:
0525 container_type c;
0526 value_compare comp;
0527
0528 public:
0529 _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_(
0530 is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value)
0531 : c(), comp() {}
0532
0533 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
0534
0535 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) {
0536 c = __q.c;
0537 comp = __q.comp;
0538 return *this;
0539 }
0540
0541 #ifndef _LIBCPP_CXX03_LANG
0542 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept(
0543 is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value)
0544 : c(std::move(__q.c)), comp(std::move(__q.comp)) {}
0545
0546 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept(
0547 is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) {
0548 c = std::move(__q.c);
0549 comp = std::move(__q.comp);
0550 return *this;
0551 }
0552 #endif // _LIBCPP_CXX03_LANG
0553
0554 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp) : c(), comp(__comp) {}
0555 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c);
0556 #ifndef _LIBCPP_CXX03_LANG
0557 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c);
0558 #endif
0559 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
0560 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare());
0561
0562 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
0563 _LIBCPP_HIDE_FROM_ABI
0564 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c);
0565
0566 #ifndef _LIBCPP_CXX03_LANG
0567 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
0568 _LIBCPP_HIDE_FROM_ABI
0569 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c);
0570 #endif // _LIBCPP_CXX03_LANG
0571
0572 #if _LIBCPP_STD_VER >= 23
0573 template <_ContainerCompatibleRange<_Tp> _Range>
0574 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())
0575 : c(from_range, std::forward<_Range>(__range)), comp(__comp) {
0576 std::make_heap(c.begin(), c.end(), comp);
0577 }
0578 #endif
0579
0580 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0581 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const _Alloc& __a);
0582
0583 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0584 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const _Alloc& __a);
0585
0586 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0587 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c, const _Alloc& __a);
0588
0589 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0590 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a);
0591
0592 #ifndef _LIBCPP_CXX03_LANG
0593 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0594 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a);
0595
0596 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0597 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a);
0598 #endif // _LIBCPP_CXX03_LANG
0599
0600 template <
0601 class _InputIter,
0602 class _Alloc,
0603 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0604 int> = 0>
0605 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a);
0606
0607 template <
0608 class _InputIter,
0609 class _Alloc,
0610 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0611 int> = 0>
0612 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a);
0613
0614 template <
0615 class _InputIter,
0616 class _Alloc,
0617 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0618 int> = 0>
0619 _LIBCPP_HIDE_FROM_ABI priority_queue(
0620 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a);
0621
0622 #ifndef _LIBCPP_CXX03_LANG
0623 template <
0624 class _InputIter,
0625 class _Alloc,
0626 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0627 int> = 0>
0628 _LIBCPP_HIDE_FROM_ABI
0629 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a);
0630 #endif // _LIBCPP_CXX03_LANG
0631
0632 #if _LIBCPP_STD_VER >= 23
0633
0634 template <_ContainerCompatibleRange<_Tp> _Range,
0635 class _Alloc,
0636 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
0637 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)
0638 : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) {
0639 std::make_heap(c.begin(), c.end(), comp);
0640 }
0641
0642 template <_ContainerCompatibleRange<_Tp> _Range,
0643 class _Alloc,
0644 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
0645 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)
0646 : c(from_range, std::forward<_Range>(__range), __a), comp() {
0647 std::make_heap(c.begin(), c.end(), comp);
0648 }
0649
0650 #endif
0651
0652 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
0653 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
0654 _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); }
0655
0656 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v);
0657 #ifndef _LIBCPP_CXX03_LANG
0658 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v);
0659
0660 # if _LIBCPP_STD_VER >= 23
0661 template <_ContainerCompatibleRange<_Tp> _Range>
0662 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
0663 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
0664 c.append_range(std::forward<_Range>(__range));
0665 } else {
0666 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
0667 }
0668
0669 std::make_heap(c.begin(), c.end(), comp);
0670 }
0671 # endif
0672
0673 template <class... _Args>
0674 _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args);
0675 #endif // _LIBCPP_CXX03_LANG
0676 _LIBCPP_HIDE_FROM_ABI void pop();
0677
0678 _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q)
0679 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>);
0680
0681 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
0682 };
0683
0684 #if _LIBCPP_STD_VER >= 17
0685 template <class _Compare,
0686 class _Container,
0687 class = enable_if_t<!__is_allocator<_Compare>::value>,
0688 class = enable_if_t<!__is_allocator<_Container>::value> >
0689 priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
0690
0691 template <class _InputIterator,
0692 class _Compare = less<__iter_value_type<_InputIterator>>,
0693 class _Container = vector<__iter_value_type<_InputIterator>>,
0694 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0695 class = enable_if_t<!__is_allocator<_Compare>::value>,
0696 class = enable_if_t<!__is_allocator<_Container>::value> >
0697 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
0698 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
0699
0700 template <class _Compare,
0701 class _Container,
0702 class _Alloc,
0703 class = enable_if_t<!__is_allocator<_Compare>::value>,
0704 class = enable_if_t<!__is_allocator<_Container>::value>,
0705 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
0706 priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
0707
0708 template <class _InputIterator,
0709 class _Allocator,
0710 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0711 class = enable_if_t<__is_allocator<_Allocator>::value> >
0712 priority_queue(_InputIterator, _InputIterator, _Allocator)
0713 -> priority_queue<__iter_value_type<_InputIterator>,
0714 vector<__iter_value_type<_InputIterator>, _Allocator>,
0715 less<__iter_value_type<_InputIterator>>>;
0716
0717 template <class _InputIterator,
0718 class _Compare,
0719 class _Allocator,
0720 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0721 class = enable_if_t<!__is_allocator<_Compare>::value>,
0722 class = enable_if_t<__is_allocator<_Allocator>::value> >
0723 priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
0724 -> priority_queue<__iter_value_type<_InputIterator>,
0725 vector<__iter_value_type<_InputIterator>, _Allocator>,
0726 _Compare>;
0727
0728 template <class _InputIterator,
0729 class _Compare,
0730 class _Container,
0731 class _Alloc,
0732 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0733 class = enable_if_t<!__is_allocator<_Compare>::value>,
0734 class = enable_if_t<!__is_allocator<_Container>::value>,
0735 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
0736 priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
0737 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
0738 #endif
0739
0740 #if _LIBCPP_STD_VER >= 23
0741
0742 template <ranges::input_range _Range,
0743 class _Compare = less<ranges::range_value_t<_Range>>,
0744 class = enable_if_t<!__is_allocator<_Compare>::value>>
0745 priority_queue(from_range_t, _Range&&, _Compare = _Compare())
0746 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;
0747
0748 template <ranges::input_range _Range,
0749 class _Compare,
0750 class _Alloc,
0751 class = enable_if_t<!__is_allocator<_Compare>::value>,
0752 class = enable_if_t<__is_allocator<_Alloc>::value>>
0753 priority_queue(from_range_t, _Range&&, _Compare, _Alloc)
0754 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>;
0755
0756 template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>>
0757 priority_queue(from_range_t, _Range&&, _Alloc)
0758 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;
0759
0760 #endif
0761
0762 template <class _Tp, class _Container, class _Compare>
0763 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c)
0764 : c(__c), comp(__comp) {
0765 std::make_heap(c.begin(), c.end(), comp);
0766 }
0767
0768 #ifndef _LIBCPP_CXX03_LANG
0769
0770 template <class _Tp, class _Container, class _Compare>
0771 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c)
0772 : c(std::move(__c)), comp(__comp) {
0773 std::make_heap(c.begin(), c.end(), comp);
0774 }
0775
0776 #endif // _LIBCPP_CXX03_LANG
0777
0778 template <class _Tp, class _Container, class _Compare>
0779 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
0780 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0781 _InputIter __f, _InputIter __l, const value_compare& __comp)
0782 : c(__f, __l), comp(__comp) {
0783 std::make_heap(c.begin(), c.end(), comp);
0784 }
0785
0786 template <class _Tp, class _Container, class _Compare>
0787 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
0788 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0789 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c)
0790 : c(__c), comp(__comp) {
0791 c.insert(c.end(), __f, __l);
0792 std::make_heap(c.begin(), c.end(), comp);
0793 }
0794
0795 #ifndef _LIBCPP_CXX03_LANG
0796
0797 template <class _Tp, class _Container, class _Compare>
0798 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
0799 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0800 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c)
0801 : c(std::move(__c)), comp(__comp) {
0802 c.insert(c.end(), __f, __l);
0803 std::make_heap(c.begin(), c.end(), comp);
0804 }
0805
0806 #endif // _LIBCPP_CXX03_LANG
0807
0808 template <class _Tp, class _Container, class _Compare>
0809 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0810 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a) : c(__a) {}
0811
0812 template <class _Tp, class _Container, class _Compare>
0813 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0814 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, const _Alloc& __a)
0815 : c(__a), comp(__comp) {}
0816
0817 template <class _Tp, class _Container, class _Compare>
0818 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0819 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0820 const value_compare& __comp, const container_type& __c, const _Alloc& __a)
0821 : c(__c, __a), comp(__comp) {
0822 std::make_heap(c.begin(), c.end(), comp);
0823 }
0824
0825 template <class _Tp, class _Container, class _Compare>
0826 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0827 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, const _Alloc& __a)
0828 : c(__q.c, __a), comp(__q.comp) {}
0829
0830 #ifndef _LIBCPP_CXX03_LANG
0831
0832 template <class _Tp, class _Container, class _Compare>
0833 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0834 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0835 const value_compare& __comp, container_type&& __c, const _Alloc& __a)
0836 : c(std::move(__c), __a), comp(__comp) {
0837 std::make_heap(c.begin(), c.end(), comp);
0838 }
0839
0840 template <class _Tp, class _Container, class _Compare>
0841 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0842 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, const _Alloc& __a)
0843 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {}
0844
0845 #endif // _LIBCPP_CXX03_LANG
0846
0847 template <class _Tp, class _Container, class _Compare>
0848 template <
0849 class _InputIter,
0850 class _Alloc,
0851 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0852 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a)
0853 : c(__f, __l, __a), comp() {
0854 std::make_heap(c.begin(), c.end(), comp);
0855 }
0856
0857 template <class _Tp, class _Container, class _Compare>
0858 template <
0859 class _InputIter,
0860 class _Alloc,
0861 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0862 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0863 _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a)
0864 : c(__f, __l, __a), comp(__comp) {
0865 std::make_heap(c.begin(), c.end(), comp);
0866 }
0867
0868 template <class _Tp, class _Container, class _Compare>
0869 template <
0870 class _InputIter,
0871 class _Alloc,
0872 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0873 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0874 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a)
0875 : c(__c, __a), comp(__comp) {
0876 c.insert(c.end(), __f, __l);
0877 std::make_heap(c.begin(), c.end(), comp);
0878 }
0879
0880 #ifndef _LIBCPP_CXX03_LANG
0881 template <class _Tp, class _Container, class _Compare>
0882 template <
0883 class _InputIter,
0884 class _Alloc,
0885 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0886 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0887 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a)
0888 : c(std::move(__c), __a), comp(__comp) {
0889 c.insert(c.end(), __f, __l);
0890 std::make_heap(c.begin(), c.end(), comp);
0891 }
0892 #endif // _LIBCPP_CXX03_LANG
0893
0894 template <class _Tp, class _Container, class _Compare>
0895 inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) {
0896 c.push_back(__v);
0897 std::push_heap(c.begin(), c.end(), comp);
0898 }
0899
0900 #ifndef _LIBCPP_CXX03_LANG
0901
0902 template <class _Tp, class _Container, class _Compare>
0903 inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) {
0904 c.push_back(std::move(__v));
0905 std::push_heap(c.begin(), c.end(), comp);
0906 }
0907
0908 template <class _Tp, class _Container, class _Compare>
0909 template <class... _Args>
0910 inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) {
0911 c.emplace_back(std::forward<_Args>(__args)...);
0912 std::push_heap(c.begin(), c.end(), comp);
0913 }
0914
0915 #endif // _LIBCPP_CXX03_LANG
0916
0917 template <class _Tp, class _Container, class _Compare>
0918 inline void priority_queue<_Tp, _Container, _Compare>::pop() {
0919 std::pop_heap(c.begin(), c.end(), comp);
0920 c.pop_back();
0921 }
0922
0923 template <class _Tp, class _Container, class _Compare>
0924 inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
0925 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) {
0926 using std::swap;
0927 swap(c, __q.c);
0928 swap(comp, __q.comp);
0929 }
0930
0931 template <class _Tp,
0932 class _Container,
0933 class _Compare,
0934 __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0>
0935 inline _LIBCPP_HIDE_FROM_ABI void
0936 swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y)
0937 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
0938 __x.swap(__y);
0939 }
0940
0941 template <class _Tp, class _Container, class _Compare, class _Alloc>
0942 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
0943 : public uses_allocator<_Container, _Alloc> {};
0944
0945 _LIBCPP_END_NAMESPACE_STD
0946
0947 _LIBCPP_POP_MACROS
0948
0949 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0950 # include <__cxx03/concepts>
0951 # include <__cxx03/cstdlib>
0952 # include <__cxx03/functional>
0953 # include <__cxx03/type_traits>
0954 #endif
0955
0956 #endif // _LIBCPP___CXX03_QUEUE
