Warning, /include/c++/v1/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_QUEUE
0011 #define _LIBCPP_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 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0258 # include <__cxx03/queue>
0259 #else
0260 # include <__algorithm/make_heap.h>
0261 # include <__algorithm/pop_heap.h>
0262 # include <__algorithm/push_heap.h>
0263 # include <__algorithm/ranges_copy.h>
0264 # include <__config>
0265 # include <__functional/operations.h>
0266 # include <__fwd/deque.h>
0267 # include <__fwd/queue.h>
0268 # include <__iterator/back_insert_iterator.h>
0269 # include <__iterator/iterator_traits.h>
0270 # include <__memory/uses_allocator.h>
0271 # include <__ranges/access.h>
0272 # include <__ranges/concepts.h>
0273 # include <__ranges/container_compatible_range.h>
0274 # include <__ranges/from_range.h>
0275 # include <__utility/forward.h>
0276 # include <deque>
0277 # include <vector>
0278 # include <version>
0279
0280 // standard-mandated includes
0281
0282 // [queue.syn]
0283 # include <compare>
0284 # include <initializer_list>
0285
0286 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0287 # pragma GCC system_header
0288 # endif
0289
0290 _LIBCPP_PUSH_MACROS
0291 # include <__undef_macros>
0292
0293 _LIBCPP_BEGIN_NAMESPACE_STD
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>
0299 _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y);
0300
0301 template <class _Tp, class _Container /*= deque<_Tp>*/>
0302 class _LIBCPP_TEMPLATE_VIS queue {
0303 public:
0304 typedef _Container container_type;
0305 typedef typename container_type::value_type value_type;
0306 typedef typename container_type::reference reference;
0307 typedef typename container_type::const_reference const_reference;
0308 typedef typename container_type::size_type size_type;
0309 static_assert(is_same<_Tp, value_type>::value, "");
0310
0311 protected:
0312 container_type c;
0313
0314 public:
0315 _LIBCPP_HIDE_FROM_ABI queue() _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value) : c() {}
0316
0317 _LIBCPP_HIDE_FROM_ABI queue(const queue& __q) : c(__q.c) {}
0318
0319 # if _LIBCPP_STD_VER >= 23
0320 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0321 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
0322
0323 template <_ContainerCompatibleRange<_Tp> _Range>
0324 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range) : c(from_range, std::forward<_Range>(__range)) {}
0325
0326 template <class _InputIterator,
0327 class _Alloc,
0328 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
0329 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0330 _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)
0331 : c(__first, __second, __alloc) {}
0332
0333 template <_ContainerCompatibleRange<_Tp> _Range,
0334 class _Alloc,
0335 __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0336 _LIBCPP_HIDE_FROM_ABI queue(from_range_t, _Range&& __range, const _Alloc& __alloc)
0337 : c(from_range, std::forward<_Range>(__range), __alloc) {}
0338
0339 # endif
0340
0341 _LIBCPP_HIDE_FROM_ABI queue& operator=(const queue& __q) {
0342 c = __q.c;
0343 return *this;
0344 }
0345
0346 # ifndef _LIBCPP_CXX03_LANG
0347 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q) noexcept(is_nothrow_move_constructible<container_type>::value)
0348 : c(std::move(__q.c)) {}
0349
0350 _LIBCPP_HIDE_FROM_ABI queue& operator=(queue&& __q) noexcept(is_nothrow_move_assignable<container_type>::value) {
0351 c = std::move(__q.c);
0352 return *this;
0353 }
0354 # endif // _LIBCPP_CXX03_LANG
0355
0356 _LIBCPP_HIDE_FROM_ABI explicit queue(const container_type& __c) : c(__c) {}
0357 # ifndef _LIBCPP_CXX03_LANG
0358 _LIBCPP_HIDE_FROM_ABI explicit queue(container_type&& __c) : c(std::move(__c)) {}
0359 # endif // _LIBCPP_CXX03_LANG
0360
0361 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0362 _LIBCPP_HIDE_FROM_ABI explicit queue(const _Alloc& __a) : 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 queue& __q, const _Alloc& __a) : c(__q.c, __a) {}
0366
0367 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0368 _LIBCPP_HIDE_FROM_ABI queue(const container_type& __c, const _Alloc& __a) : c(__c, __a) {}
0369
0370 # ifndef _LIBCPP_CXX03_LANG
0371 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0372 _LIBCPP_HIDE_FROM_ABI queue(container_type&& __c, const _Alloc& __a) : c(std::move(__c), __a) {}
0373
0374 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0375 _LIBCPP_HIDE_FROM_ABI queue(queue&& __q, const _Alloc& __a) : c(std::move(__q.c), __a) {}
0376 # endif // _LIBCPP_CXX03_LANG
0377
0378 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
0379 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
0380
0381 _LIBCPP_HIDE_FROM_ABI reference front() { return c.front(); }
0382 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return c.front(); }
0383 _LIBCPP_HIDE_FROM_ABI reference back() { return c.back(); }
0384 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return c.back(); }
0385
0386 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v) { c.push_back(__v); }
0387 # ifndef _LIBCPP_CXX03_LANG
0388 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v) { c.push_back(std::move(__v)); }
0389
0390 # if _LIBCPP_STD_VER >= 23
0391 template <_ContainerCompatibleRange<_Tp> _Range>
0392 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
0393 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
0394 c.append_range(std::forward<_Range>(__range));
0395 } else {
0396 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
0397 }
0398 }
0399 # endif
0400
0401 template <class... _Args>
0402 _LIBCPP_HIDE_FROM_ABI
0403 # if _LIBCPP_STD_VER >= 17
0404 decltype(auto)
0405 emplace(_Args&&... __args) {
0406 return c.emplace_back(std::forward<_Args>(__args)...);
0407 }
0408 # else
0409 void
0410 emplace(_Args&&... __args) {
0411 c.emplace_back(std::forward<_Args>(__args)...);
0412 }
0413 # endif
0414 # endif // _LIBCPP_CXX03_LANG
0415 _LIBCPP_HIDE_FROM_ABI void pop() { c.pop_front(); }
0416
0417 _LIBCPP_HIDE_FROM_ABI void swap(queue& __q) _NOEXCEPT_(__is_nothrow_swappable_v<container_type>) {
0418 using std::swap;
0419 swap(c, __q.c);
0420 }
0421
0422 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
0423
0424 template <class _T1, class _OtherContainer>
0425 friend _LIBCPP_HIDE_FROM_ABI bool
0426 operator==(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
0427
0428 template <class _T1, class _OtherContainer>
0429 friend _LIBCPP_HIDE_FROM_ABI bool
0430 operator<(const queue<_T1, _OtherContainer>& __x, const queue<_T1, _OtherContainer>& __y);
0431 };
0432
0433 # if _LIBCPP_STD_VER >= 17
0434 template <class _Container, class = enable_if_t<!__is_allocator<_Container>::value> >
0435 queue(_Container) -> queue<typename _Container::value_type, _Container>;
0436
0437 template <class _Container,
0438 class _Alloc,
0439 class = enable_if_t<!__is_allocator<_Container>::value>,
0440 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
0441 queue(_Container, _Alloc) -> queue<typename _Container::value_type, _Container>;
0442 # endif
0443
0444 # if _LIBCPP_STD_VER >= 23
0445 template <class _InputIterator, __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0>
0446 queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>;
0447
0448 template <ranges::input_range _Range>
0449 queue(from_range_t, _Range&&) -> queue<ranges::range_value_t<_Range>>;
0450
0451 template <class _InputIterator,
0452 class _Alloc,
0453 __enable_if_t<__has_input_iterator_category<_InputIterator>::value, int> = 0,
0454 __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
0455 queue(_InputIterator,
0456 _InputIterator,
0457 _Alloc) -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
0458
0459 template <ranges::input_range _Range, class _Alloc, __enable_if_t<__is_allocator<_Alloc>::value, int> = 0>
0460 queue(from_range_t,
0461 _Range&&,
0462 _Alloc) -> queue<ranges::range_value_t<_Range>, deque<ranges::range_value_t<_Range>, _Alloc>>;
0463 # endif
0464
0465 template <class _Tp, class _Container>
0466 inline _LIBCPP_HIDE_FROM_ABI bool operator==(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0467 return __x.c == __y.c;
0468 }
0469
0470 template <class _Tp, class _Container>
0471 inline _LIBCPP_HIDE_FROM_ABI bool operator<(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0472 return __x.c < __y.c;
0473 }
0474
0475 template <class _Tp, class _Container>
0476 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0477 return !(__x == __y);
0478 }
0479
0480 template <class _Tp, class _Container>
0481 inline _LIBCPP_HIDE_FROM_ABI bool operator>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0482 return __y < __x;
0483 }
0484
0485 template <class _Tp, class _Container>
0486 inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0487 return !(__x < __y);
0488 }
0489
0490 template <class _Tp, class _Container>
0491 inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0492 return !(__y < __x);
0493 }
0494
0495 # if _LIBCPP_STD_VER >= 20
0496
0497 template <class _Tp, three_way_comparable _Container>
0498 _LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
0499 operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
0500 // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
0501 return __x.__get_container() <=> __y.__get_container();
0502 }
0503
0504 # endif
0505
0506 template <class _Tp, class _Container, __enable_if_t<__is_swappable_v<_Container>, int> = 0>
0507 inline _LIBCPP_HIDE_FROM_ABI void swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
0508 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
0509 __x.swap(__y);
0510 }
0511
0512 template <class _Tp, class _Container, class _Alloc>
0513 struct _LIBCPP_TEMPLATE_VIS uses_allocator<queue<_Tp, _Container>, _Alloc> : public uses_allocator<_Container, _Alloc> {
0514 };
0515
0516 template <class _Tp, class _Container, class _Compare>
0517 class _LIBCPP_TEMPLATE_VIS priority_queue {
0518 public:
0519 typedef _Container container_type;
0520 typedef _Compare value_compare;
0521 typedef typename container_type::value_type value_type;
0522 typedef typename container_type::reference reference;
0523 typedef typename container_type::const_reference const_reference;
0524 typedef typename container_type::size_type size_type;
0525 static_assert(is_same<_Tp, value_type>::value, "");
0526
0527 protected:
0528 container_type c;
0529 value_compare comp;
0530
0531 public:
0532 _LIBCPP_HIDE_FROM_ABI priority_queue() _NOEXCEPT_(
0533 is_nothrow_default_constructible<container_type>::value&& is_nothrow_default_constructible<value_compare>::value)
0534 : c(), comp() {}
0535
0536 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
0537
0538 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(const priority_queue& __q) {
0539 c = __q.c;
0540 comp = __q.comp;
0541 return *this;
0542 }
0543
0544 # ifndef _LIBCPP_CXX03_LANG
0545 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q) noexcept(
0546 is_nothrow_move_constructible<container_type>::value && is_nothrow_move_constructible<value_compare>::value)
0547 : c(std::move(__q.c)), comp(std::move(__q.comp)) {}
0548
0549 _LIBCPP_HIDE_FROM_ABI priority_queue& operator=(priority_queue&& __q) noexcept(
0550 is_nothrow_move_assignable<container_type>::value && is_nothrow_move_assignable<value_compare>::value) {
0551 c = std::move(__q.c);
0552 comp = std::move(__q.comp);
0553 return *this;
0554 }
0555 # endif // _LIBCPP_CXX03_LANG
0556
0557 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(const value_compare& __comp) : c(), comp(__comp) {}
0558 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, const container_type& __c);
0559 # ifndef _LIBCPP_CXX03_LANG
0560 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c);
0561 # endif
0562 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
0563 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp = value_compare());
0564
0565 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
0566 _LIBCPP_HIDE_FROM_ABI
0567 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c);
0568
0569 # ifndef _LIBCPP_CXX03_LANG
0570 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> = 0>
0571 _LIBCPP_HIDE_FROM_ABI
0572 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c);
0573 # endif // _LIBCPP_CXX03_LANG
0574
0575 # if _LIBCPP_STD_VER >= 23
0576 template <_ContainerCompatibleRange<_Tp> _Range>
0577 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp = value_compare())
0578 : c(from_range, std::forward<_Range>(__range)), comp(__comp) {
0579 std::make_heap(c.begin(), c.end(), comp);
0580 }
0581 # endif
0582
0583 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0584 _LIBCPP_HIDE_FROM_ABI explicit priority_queue(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 _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 value_compare& __comp, const container_type& __c, const _Alloc& __a);
0591
0592 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0593 _LIBCPP_HIDE_FROM_ABI priority_queue(const priority_queue& __q, const _Alloc& __a);
0594
0595 # ifndef _LIBCPP_CXX03_LANG
0596 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0597 _LIBCPP_HIDE_FROM_ABI priority_queue(const value_compare& __comp, container_type&& __c, const _Alloc& __a);
0598
0599 template <class _Alloc, __enable_if_t<uses_allocator<container_type, _Alloc>::value, int> = 0>
0600 _LIBCPP_HIDE_FROM_ABI priority_queue(priority_queue&& __q, const _Alloc& __a);
0601 # endif // _LIBCPP_CXX03_LANG
0602
0603 template <
0604 class _InputIter,
0605 class _Alloc,
0606 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0607 int> = 0>
0608 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a);
0609
0610 template <
0611 class _InputIter,
0612 class _Alloc,
0613 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0614 int> = 0>
0615 _LIBCPP_HIDE_FROM_ABI priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a);
0616
0617 template <
0618 class _InputIter,
0619 class _Alloc,
0620 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0621 int> = 0>
0622 _LIBCPP_HIDE_FROM_ABI priority_queue(
0623 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a);
0624
0625 # ifndef _LIBCPP_CXX03_LANG
0626 template <
0627 class _InputIter,
0628 class _Alloc,
0629 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<container_type, _Alloc>::value,
0630 int> = 0>
0631 _LIBCPP_HIDE_FROM_ABI
0632 priority_queue(_InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a);
0633 # endif // _LIBCPP_CXX03_LANG
0634
0635 # if _LIBCPP_STD_VER >= 23
0636
0637 template <_ContainerCompatibleRange<_Tp> _Range,
0638 class _Alloc,
0639 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
0640 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const value_compare& __comp, const _Alloc& __a)
0641 : c(from_range, std::forward<_Range>(__range), __a), comp(__comp) {
0642 std::make_heap(c.begin(), c.end(), comp);
0643 }
0644
0645 template <_ContainerCompatibleRange<_Tp> _Range,
0646 class _Alloc,
0647 class = enable_if_t<uses_allocator<_Container, _Alloc>::value>>
0648 _LIBCPP_HIDE_FROM_ABI priority_queue(from_range_t, _Range&& __range, const _Alloc& __a)
0649 : c(from_range, std::forward<_Range>(__range), __a), comp() {
0650 std::make_heap(c.begin(), c.end(), comp);
0651 }
0652
0653 # endif
0654
0655 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const { return c.empty(); }
0656 _LIBCPP_HIDE_FROM_ABI size_type size() const { return c.size(); }
0657 _LIBCPP_HIDE_FROM_ABI const_reference top() const { return c.front(); }
0658
0659 _LIBCPP_HIDE_FROM_ABI void push(const value_type& __v);
0660 # ifndef _LIBCPP_CXX03_LANG
0661 _LIBCPP_HIDE_FROM_ABI void push(value_type&& __v);
0662
0663 # if _LIBCPP_STD_VER >= 23
0664 template <_ContainerCompatibleRange<_Tp> _Range>
0665 _LIBCPP_HIDE_FROM_ABI void push_range(_Range&& __range) {
0666 if constexpr (requires(container_type& __c) { __c.append_range(std::forward<_Range>(__range)); }) {
0667 c.append_range(std::forward<_Range>(__range));
0668 } else {
0669 ranges::copy(std::forward<_Range>(__range), std::back_inserter(c));
0670 }
0671
0672 std::make_heap(c.begin(), c.end(), comp);
0673 }
0674 # endif
0675
0676 template <class... _Args>
0677 _LIBCPP_HIDE_FROM_ABI void emplace(_Args&&... __args);
0678 # endif // _LIBCPP_CXX03_LANG
0679 _LIBCPP_HIDE_FROM_ABI void pop();
0680
0681 _LIBCPP_HIDE_FROM_ABI void swap(priority_queue& __q)
0682 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>);
0683
0684 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI const _Container& __get_container() const { return c; }
0685 };
0686
0687 # if _LIBCPP_STD_VER >= 17
0688 template <class _Compare,
0689 class _Container,
0690 class = enable_if_t<!__is_allocator<_Compare>::value>,
0691 class = enable_if_t<!__is_allocator<_Container>::value> >
0692 priority_queue(_Compare, _Container) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
0693
0694 template <class _InputIterator,
0695 class _Compare = less<__iter_value_type<_InputIterator>>,
0696 class _Container = vector<__iter_value_type<_InputIterator>>,
0697 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0698 class = enable_if_t<!__is_allocator<_Compare>::value>,
0699 class = enable_if_t<!__is_allocator<_Container>::value> >
0700 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
0701 -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
0702
0703 template <class _Compare,
0704 class _Container,
0705 class _Alloc,
0706 class = enable_if_t<!__is_allocator<_Compare>::value>,
0707 class = enable_if_t<!__is_allocator<_Container>::value>,
0708 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
0709 priority_queue(_Compare, _Container, _Alloc) -> priority_queue<typename _Container::value_type, _Container, _Compare>;
0710
0711 template <class _InputIterator,
0712 class _Allocator,
0713 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0714 class = enable_if_t<__is_allocator<_Allocator>::value> >
0715 priority_queue(_InputIterator, _InputIterator, _Allocator)
0716 -> priority_queue<__iter_value_type<_InputIterator>,
0717 vector<__iter_value_type<_InputIterator>, _Allocator>,
0718 less<__iter_value_type<_InputIterator>>>;
0719
0720 template <class _InputIterator,
0721 class _Compare,
0722 class _Allocator,
0723 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0724 class = enable_if_t<!__is_allocator<_Compare>::value>,
0725 class = enable_if_t<__is_allocator<_Allocator>::value> >
0726 priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
0727 -> priority_queue<__iter_value_type<_InputIterator>,
0728 vector<__iter_value_type<_InputIterator>, _Allocator>,
0729 _Compare>;
0730
0731 template <class _InputIterator,
0732 class _Compare,
0733 class _Container,
0734 class _Alloc,
0735 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
0736 class = enable_if_t<!__is_allocator<_Compare>::value>,
0737 class = enable_if_t<!__is_allocator<_Container>::value>,
0738 class = enable_if_t<uses_allocator<_Container, _Alloc>::value> >
0739 priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
0740 -> priority_queue<typename _Container::value_type, _Container, _Compare>;
0741 # endif
0742
0743 # if _LIBCPP_STD_VER >= 23
0744
0745 template <ranges::input_range _Range,
0746 class _Compare = less<ranges::range_value_t<_Range>>,
0747 class = enable_if_t<!__is_allocator<_Compare>::value>>
0748 priority_queue(from_range_t, _Range&&, _Compare = _Compare())
0749 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>>, _Compare>;
0750
0751 template <ranges::input_range _Range,
0752 class _Compare,
0753 class _Alloc,
0754 class = enable_if_t<!__is_allocator<_Compare>::value>,
0755 class = enable_if_t<__is_allocator<_Alloc>::value>>
0756 priority_queue(from_range_t, _Range&&, _Compare, _Alloc)
0757 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>, _Compare>;
0758
0759 template <ranges::input_range _Range, class _Alloc, class = enable_if_t<__is_allocator<_Alloc>::value>>
0760 priority_queue(from_range_t, _Range&&, _Alloc)
0761 -> priority_queue<ranges::range_value_t<_Range>, vector<ranges::range_value_t<_Range>, _Alloc>>;
0762
0763 # endif
0764
0765 template <class _Tp, class _Container, class _Compare>
0766 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp, const container_type& __c)
0767 : c(__c), comp(__comp) {
0768 std::make_heap(c.begin(), c.end(), comp);
0769 }
0770
0771 # ifndef _LIBCPP_CXX03_LANG
0772
0773 template <class _Tp, class _Container, class _Compare>
0774 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, container_type&& __c)
0775 : c(std::move(__c)), comp(__comp) {
0776 std::make_heap(c.begin(), c.end(), comp);
0777 }
0778
0779 # endif // _LIBCPP_CXX03_LANG
0780
0781 template <class _Tp, class _Container, class _Compare>
0782 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
0783 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0784 _InputIter __f, _InputIter __l, const value_compare& __comp)
0785 : c(__f, __l), comp(__comp) {
0786 std::make_heap(c.begin(), c.end(), comp);
0787 }
0788
0789 template <class _Tp, class _Container, class _Compare>
0790 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
0791 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0792 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c)
0793 : c(__c), comp(__comp) {
0794 c.insert(c.end(), __f, __l);
0795 std::make_heap(c.begin(), c.end(), comp);
0796 }
0797
0798 # ifndef _LIBCPP_CXX03_LANG
0799
0800 template <class _Tp, class _Container, class _Compare>
0801 template <class _InputIter, __enable_if_t<__has_input_iterator_category<_InputIter>::value, int> >
0802 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0803 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c)
0804 : c(std::move(__c)), comp(__comp) {
0805 c.insert(c.end(), __f, __l);
0806 std::make_heap(c.begin(), c.end(), comp);
0807 }
0808
0809 # endif // _LIBCPP_CXX03_LANG
0810
0811 template <class _Tp, class _Container, class _Compare>
0812 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0813 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a) : c(__a) {}
0814
0815 template <class _Tp, class _Container, class _Compare>
0816 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0817 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp, const _Alloc& __a)
0818 : c(__a), comp(__comp) {}
0819
0820 template <class _Tp, class _Container, class _Compare>
0821 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0822 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0823 const value_compare& __comp, const container_type& __c, const _Alloc& __a)
0824 : c(__c, __a), comp(__comp) {
0825 std::make_heap(c.begin(), c.end(), comp);
0826 }
0827
0828 template <class _Tp, class _Container, class _Compare>
0829 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0830 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q, const _Alloc& __a)
0831 : c(__q.c, __a), comp(__q.comp) {}
0832
0833 # ifndef _LIBCPP_CXX03_LANG
0834
0835 template <class _Tp, class _Container, class _Compare>
0836 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0837 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0838 const value_compare& __comp, container_type&& __c, const _Alloc& __a)
0839 : c(std::move(__c), __a), comp(__comp) {
0840 std::make_heap(c.begin(), c.end(), comp);
0841 }
0842
0843 template <class _Tp, class _Container, class _Compare>
0844 template <class _Alloc, __enable_if_t<uses_allocator<_Container, _Alloc>::value, int> >
0845 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q, const _Alloc& __a)
0846 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) {}
0847
0848 # endif // _LIBCPP_CXX03_LANG
0849
0850 template <class _Tp, class _Container, class _Compare>
0851 template <
0852 class _InputIter,
0853 class _Alloc,
0854 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0855 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a)
0856 : c(__f, __l, __a), comp() {
0857 std::make_heap(c.begin(), c.end(), comp);
0858 }
0859
0860 template <class _Tp, class _Container, class _Compare>
0861 template <
0862 class _InputIter,
0863 class _Alloc,
0864 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0865 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0866 _InputIter __f, _InputIter __l, const value_compare& __comp, const _Alloc& __a)
0867 : c(__f, __l, __a), comp(__comp) {
0868 std::make_heap(c.begin(), c.end(), comp);
0869 }
0870
0871 template <class _Tp, class _Container, class _Compare>
0872 template <
0873 class _InputIter,
0874 class _Alloc,
0875 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0876 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0877 _InputIter __f, _InputIter __l, const value_compare& __comp, const container_type& __c, const _Alloc& __a)
0878 : c(__c, __a), comp(__comp) {
0879 c.insert(c.end(), __f, __l);
0880 std::make_heap(c.begin(), c.end(), comp);
0881 }
0882
0883 # ifndef _LIBCPP_CXX03_LANG
0884 template <class _Tp, class _Container, class _Compare>
0885 template <
0886 class _InputIter,
0887 class _Alloc,
0888 __enable_if_t<__has_input_iterator_category<_InputIter>::value && uses_allocator<_Container, _Alloc>::value, int> >
0889 inline priority_queue<_Tp, _Container, _Compare>::priority_queue(
0890 _InputIter __f, _InputIter __l, const value_compare& __comp, container_type&& __c, const _Alloc& __a)
0891 : c(std::move(__c), __a), comp(__comp) {
0892 c.insert(c.end(), __f, __l);
0893 std::make_heap(c.begin(), c.end(), comp);
0894 }
0895 # endif // _LIBCPP_CXX03_LANG
0896
0897 template <class _Tp, class _Container, class _Compare>
0898 inline void priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v) {
0899 c.push_back(__v);
0900 std::push_heap(c.begin(), c.end(), comp);
0901 }
0902
0903 # ifndef _LIBCPP_CXX03_LANG
0904
0905 template <class _Tp, class _Container, class _Compare>
0906 inline void priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v) {
0907 c.push_back(std::move(__v));
0908 std::push_heap(c.begin(), c.end(), comp);
0909 }
0910
0911 template <class _Tp, class _Container, class _Compare>
0912 template <class... _Args>
0913 inline void priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args) {
0914 c.emplace_back(std::forward<_Args>(__args)...);
0915 std::push_heap(c.begin(), c.end(), comp);
0916 }
0917
0918 # endif // _LIBCPP_CXX03_LANG
0919
0920 template <class _Tp, class _Container, class _Compare>
0921 inline void priority_queue<_Tp, _Container, _Compare>::pop() {
0922 std::pop_heap(c.begin(), c.end(), comp);
0923 c.pop_back();
0924 }
0925
0926 template <class _Tp, class _Container, class _Compare>
0927 inline void priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
0928 _NOEXCEPT_(__is_nothrow_swappable_v<container_type>&& __is_nothrow_swappable_v<value_compare>) {
0929 using std::swap;
0930 swap(c, __q.c);
0931 swap(comp, __q.comp);
0932 }
0933
0934 template <class _Tp,
0935 class _Container,
0936 class _Compare,
0937 __enable_if_t<__is_swappable_v<_Container> && __is_swappable_v<_Compare>, int> = 0>
0938 inline _LIBCPP_HIDE_FROM_ABI void
0939 swap(priority_queue<_Tp, _Container, _Compare>& __x, priority_queue<_Tp, _Container, _Compare>& __y)
0940 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
0941 __x.swap(__y);
0942 }
0943
0944 template <class _Tp, class _Container, class _Compare, class _Alloc>
0945 struct _LIBCPP_TEMPLATE_VIS uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
0946 : public uses_allocator<_Container, _Alloc> {};
0947
0948 _LIBCPP_END_NAMESPACE_STD
0949
0950 _LIBCPP_POP_MACROS
0951
0952 # if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0953 # include <concepts>
0954 # include <cstdlib>
0955 # include <functional>
0956 # include <type_traits>
0957 # endif
0958 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0959
0960 #endif // _LIBCPP_QUEUE
