Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/stl_queue.h
1 // Queue implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2025 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_queue.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{queue} 54 */ 55 56 #ifndef _STL_QUEUE_H 57 #define _STL_QUEUE_H 1 58 59 #include <bits/concept_check.h> 60 #include <debug/debug.h> 61 #if __cplusplus >= 201103L 62 # include <bits/uses_allocator.h> 63 #endif 64 #if __glibcxx_containers_ranges // C++ >= 23 65 # include <ranges> // ranges::to 66 # include <bits/ranges_algobase.h> // ranges::copy 67 #endif 68 69 namespace std _GLIBCXX_VISIBILITY(default) 70 { 71 _GLIBCXX_BEGIN_NAMESPACE_VERSION 72 73 #if __glibcxx_format_ranges 74 template<typename, typename> class formatter; 75 #endif 76 77 /** 78 * @brief A standard container giving FIFO behavior. 79 * 80 * @ingroup sequences 81 * 82 * @tparam _Tp Type of element. 83 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>. 84 * 85 * Meets many of the requirements of a 86 * <a href="tables.html#65">container</a>, 87 * but does not define anything to do with iterators. Very few of the 88 * other standard container interfaces are defined. 89 * 90 * This is not a true container, but an @e adaptor. It holds another 91 * container, and provides a wrapper interface to that container. The 92 * wrapper is what enforces strict first-in-first-out %queue behavior. 93 * 94 * The second template parameter defines the type of the underlying 95 * sequence/container. It defaults to std::deque, but it can be any type 96 * that supports @c front, @c back, @c push_back, and @c pop_front, 97 * such as std::list or an appropriate user-defined type. 98 * 99 * Members not found in @a normal containers are @c container_type, 100 * which is a typedef for the second Sequence parameter, and @c push and 101 * @c pop, which are standard %queue/FIFO operations. 102 */ 103 template<typename _Tp, typename _Sequence = deque<_Tp> > 104 class queue 105 { 106 #ifdef _GLIBCXX_CONCEPT_CHECKS 107 // concept requirements 108 typedef typename _Sequence::value_type _Sequence_value_type; 109 # if __cplusplus < 201103L 110 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 111 # endif 112 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 113 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 114 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 115 #endif 116 117 template<typename _Tp1, typename _Seq1> 118 friend bool 119 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 120 121 template<typename _Tp1, typename _Seq1> 122 friend bool 123 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 124 125 #if __cpp_lib_three_way_comparison 126 template<typename _Tp1, three_way_comparable _Seq1> 127 friend compare_three_way_result_t<_Seq1> 128 operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 129 #endif 130 131 #if __cplusplus >= 201103L 132 template<typename _Alloc> 133 using _Uses = typename 134 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; 135 136 #if __cplusplus >= 201703L 137 // _GLIBCXX_RESOLVE_LIB_DEFECTS 138 // 2566. Requirements on the first template parameter of container 139 // adaptors 140 static_assert(is_same<_Tp, typename _Sequence::value_type>::value, 141 "value_type must be the same as the underlying container"); 142 #endif // C++17 143 #endif // C++11 144 145 public: 146 typedef typename _Sequence::value_type value_type; 147 typedef typename _Sequence::reference reference; 148 typedef typename _Sequence::const_reference const_reference; 149 typedef typename _Sequence::size_type size_type; 150 typedef _Sequence container_type; 151 152 protected: 153 /* Maintainers wondering why this isn't uglified as per style 154 * guidelines should note that this name is specified in the standard, 155 * C++98 [23.2.3.1]. 156 * (Why? Presumably for the same reason that it's protected instead 157 * of private: to allow derivation. But none of the other 158 * containers allow for derivation. Odd.) 159 */ 160 /// @c c is the underlying container. 161 _Sequence c; 162 163 public: 164 /** 165 * @brief Default constructor creates no elements. 166 */ 167 #if __cplusplus < 201103L 168 explicit 169 queue(const _Sequence& __c = _Sequence()) 170 : c(__c) { } 171 #else 172 template<typename _Seq = _Sequence, typename _Requires = typename 173 enable_if<is_default_constructible<_Seq>::value>::type> 174 queue() 175 : c() { } 176 177 explicit 178 queue(const _Sequence& __c) 179 : c(__c) { } 180 181 explicit 182 queue(_Sequence&& __c) 183 : c(std::move(__c)) { } 184 185 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 186 explicit 187 queue(const _Alloc& __a) 188 : c(__a) { } 189 190 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 191 queue(const _Sequence& __c, const _Alloc& __a) 192 : c(__c, __a) { } 193 194 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 195 queue(_Sequence&& __c, const _Alloc& __a) 196 : c(std::move(__c), __a) { } 197 198 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 199 queue(const queue& __q, const _Alloc& __a) 200 : c(__q.c, __a) { } 201 202 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 203 queue(queue&& __q, const _Alloc& __a) 204 : c(std::move(__q.c), __a) { } 205 #endif 206 207 #ifdef __glibcxx_adaptor_iterator_pair_constructor // C++ >= 23 && HOSTED 208 template<typename _InputIterator, 209 typename = _RequireInputIter<_InputIterator>> 210 queue(_InputIterator __first, _InputIterator __last) 211 : c(__first, __last) { } 212 213 template<typename _InputIterator, typename _Alloc, 214 typename = _RequireInputIter<_InputIterator>, 215 typename = _Uses<_Alloc>> 216 queue(_InputIterator __first, _InputIterator __last, const _Alloc& __a) 217 : c(__first, __last, __a) { } 218 #endif 219 220 #if __glibcxx_containers_ranges // C++ >= 23 221 /** 222 * @brief Construct a queue from a range. 223 * @since C++23 224 */ 225 template<__detail::__container_compatible_range<_Tp> _Rg> 226 queue(from_range_t, _Rg&& __rg) 227 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg))) 228 { } 229 230 /** 231 * @brief Construct a queue from a range. 232 * @since C++23 233 */ 234 template<__detail::__container_compatible_range<_Tp> _Rg, 235 typename _Alloc> 236 queue(from_range_t, _Rg&& __rg, const _Alloc& __a) 237 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)) 238 { } 239 #endif 240 241 /** 242 * Returns true if the %queue is empty. 243 */ 244 _GLIBCXX_NODISCARD bool 245 empty() const 246 { return c.empty(); } 247 248 /** Returns the number of elements in the %queue. */ 249 _GLIBCXX_NODISCARD 250 size_type 251 size() const 252 { return c.size(); } 253 254 /** 255 * Returns a read/write reference to the data at the first 256 * element of the %queue. 257 */ 258 _GLIBCXX_NODISCARD 259 reference 260 front() 261 { 262 __glibcxx_requires_nonempty(); 263 return c.front(); 264 } 265 266 /** 267 * Returns a read-only (constant) reference to the data at the first 268 * element of the %queue. 269 */ 270 _GLIBCXX_NODISCARD 271 const_reference 272 front() const 273 { 274 __glibcxx_requires_nonempty(); 275 return c.front(); 276 } 277 278 /** 279 * Returns a read/write reference to the data at the last 280 * element of the %queue. 281 */ 282 _GLIBCXX_NODISCARD 283 reference 284 back() 285 { 286 __glibcxx_requires_nonempty(); 287 return c.back(); 288 } 289 290 /** 291 * Returns a read-only (constant) reference to the data at the last 292 * element of the %queue. 293 */ 294 _GLIBCXX_NODISCARD 295 const_reference 296 back() const 297 { 298 __glibcxx_requires_nonempty(); 299 return c.back(); 300 } 301 302 /** 303 * @brief Add data to the end of the %queue. 304 * @param __x Data to be added. 305 * 306 * This is a typical %queue operation. The function creates an 307 * element at the end of the %queue and assigns the given data 308 * to it. The time complexity of the operation depends on the 309 * underlying sequence. 310 */ 311 void 312 push(const value_type& __x) 313 { c.push_back(__x); } 314 315 #if __cplusplus >= 201103L 316 void 317 push(value_type&& __x) 318 { c.push_back(std::move(__x)); } 319 320 #if __cplusplus > 201402L 321 template<typename... _Args> 322 decltype(auto) 323 emplace(_Args&&... __args) 324 { return c.emplace_back(std::forward<_Args>(__args)...); } 325 #else 326 template<typename... _Args> 327 void 328 emplace(_Args&&... __args) 329 { c.emplace_back(std::forward<_Args>(__args)...); } 330 #endif 331 #endif 332 333 #if __glibcxx_containers_ranges // C++ >= 23 334 template<__detail::__container_compatible_range<_Tp> _Rg> 335 void 336 push_range(_Rg&& __rg) 337 { 338 if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); }) 339 c.append_range(std::forward<_Rg>(__rg)); 340 else 341 ranges::copy(__rg, std::back_inserter(c)); 342 } 343 #endif 344 345 /** 346 * @brief Removes first element. 347 * 348 * This is a typical %queue operation. It shrinks the %queue by one. 349 * The time complexity of the operation depends on the underlying 350 * sequence. 351 * 352 * Note that no data is returned, and if the first element's 353 * data is needed, it should be retrieved before pop() is 354 * called. 355 */ 356 void 357 pop() 358 { 359 __glibcxx_requires_nonempty(); 360 c.pop_front(); 361 } 362 363 #if __cplusplus >= 201103L 364 void 365 swap(queue& __q) 366 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 367 noexcept(__is_nothrow_swappable<_Sequence>::value) 368 #else 369 noexcept(__is_nothrow_swappable<_Tp>::value) 370 #endif 371 { 372 using std::swap; 373 swap(c, __q.c); 374 } 375 #endif // __cplusplus >= 201103L 376 377 #if __glibcxx_format_ranges 378 friend class formatter<queue<_Tp, _Sequence>, char>; 379 friend class formatter<queue<_Tp, _Sequence>, wchar_t>; 380 #endif 381 }; 382 383 #if __cpp_deduction_guides >= 201606 384 template<typename _Container, 385 typename = _RequireNotAllocator<_Container>> 386 queue(_Container) -> queue<typename _Container::value_type, _Container>; 387 388 template<typename _Container, typename _Allocator, 389 typename = _RequireNotAllocator<_Container>> 390 queue(_Container, _Allocator) 391 -> queue<typename _Container::value_type, _Container>; 392 393 #ifdef __glibcxx_adaptor_iterator_pair_constructor 394 template<typename _InputIterator, 395 typename _ValT 396 = typename iterator_traits<_InputIterator>::value_type, 397 typename = _RequireInputIter<_InputIterator>> 398 queue(_InputIterator, _InputIterator) -> queue<_ValT>; 399 400 template<typename _InputIterator, typename _Allocator, 401 typename _ValT 402 = typename iterator_traits<_InputIterator>::value_type, 403 typename = _RequireInputIter<_InputIterator>, 404 typename = _RequireAllocator<_Allocator>> 405 queue(_InputIterator, _InputIterator, _Allocator) 406 -> queue<_ValT, deque<_ValT, _Allocator>>; 407 #endif 408 409 #if __glibcxx_containers_ranges // C++ >= 23 410 template<ranges::input_range _Rg> 411 queue(from_range_t, _Rg&&) -> queue<ranges::range_value_t<_Rg>>; 412 413 template<ranges::input_range _Rg, __allocator_like _Alloc> 414 queue(from_range_t, _Rg&&, _Alloc) 415 -> queue<ranges::range_value_t<_Rg>, 416 deque<ranges::range_value_t<_Rg>, _Alloc>>; 417 #endif 418 #endif 419 420 /** 421 * @brief Queue equality comparison. 422 * @param __x A %queue. 423 * @param __y A %queue of the same type as @a __x. 424 * @return True iff the size and elements of the queues are equal. 425 * 426 * This is an equivalence relation. Complexity and semantics depend on the 427 * underlying sequence type, but the expected rules are: this relation is 428 * linear in the size of the sequences, and queues are considered equivalent 429 * if their sequences compare equal. 430 */ 431 template<typename _Tp, typename _Seq> 432 _GLIBCXX_NODISCARD 433 inline bool 434 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 435 { return __x.c == __y.c; } 436 437 /** 438 * @brief Queue ordering relation. 439 * @param __x A %queue. 440 * @param __y A %queue of the same type as @a x. 441 * @return True iff @a __x is lexicographically less than @a __y. 442 * 443 * This is an total ordering relation. Complexity and semantics 444 * depend on the underlying sequence type, but the expected rules 445 * are: this relation is linear in the size of the sequences, the 446 * elements must be comparable with @c <, and 447 * std::lexicographical_compare() is usually used to make the 448 * determination. 449 */ 450 template<typename _Tp, typename _Seq> 451 _GLIBCXX_NODISCARD 452 inline bool 453 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 454 { return __x.c < __y.c; } 455 456 /// Based on operator== 457 template<typename _Tp, typename _Seq> 458 _GLIBCXX_NODISCARD 459 inline bool 460 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 461 { return !(__x == __y); } 462 463 /// Based on operator< 464 template<typename _Tp, typename _Seq> 465 _GLIBCXX_NODISCARD 466 inline bool 467 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 468 { return __y < __x; } 469 470 /// Based on operator< 471 template<typename _Tp, typename _Seq> 472 _GLIBCXX_NODISCARD 473 inline bool 474 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 475 { return !(__y < __x); } 476 477 /// Based on operator< 478 template<typename _Tp, typename _Seq> 479 _GLIBCXX_NODISCARD 480 inline bool 481 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 482 { return !(__x < __y); } 483 484 #if __cpp_lib_three_way_comparison 485 template<typename _Tp, three_way_comparable _Seq> 486 [[nodiscard]] 487 inline compare_three_way_result_t<_Seq> 488 operator<=>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 489 { return __x.c <=> __y.c; } 490 #endif 491 492 #if __cplusplus >= 201103L 493 template<typename _Tp, typename _Seq> 494 inline 495 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 496 // Constrained free swap overload, see p0185r1 497 typename enable_if<__is_swappable<_Seq>::value>::type 498 #else 499 void 500 #endif 501 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 502 noexcept(noexcept(__x.swap(__y))) 503 { __x.swap(__y); } 504 505 template<typename _Tp, typename _Seq, typename _Alloc> 506 struct uses_allocator<queue<_Tp, _Seq>, _Alloc> 507 : public uses_allocator<_Seq, _Alloc>::type { }; 508 #endif // __cplusplus >= 201103L 509 510 /** 511 * @brief A standard container automatically sorting its contents. 512 * 513 * @ingroup sequences 514 * 515 * @tparam _Tp Type of element. 516 * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>. 517 * @tparam _Compare Comparison function object type, defaults to 518 * less<_Sequence::value_type>. 519 * 520 * This is not a true container, but an @e adaptor. It holds 521 * another container, and provides a wrapper interface to that 522 * container. The wrapper is what enforces priority-based sorting 523 * and %queue behavior. Very few of the standard container/sequence 524 * interface requirements are met (e.g., iterators). 525 * 526 * The second template parameter defines the type of the underlying 527 * sequence/container. It defaults to std::vector, but it can be 528 * any type that supports @c front(), @c push_back, @c pop_back, 529 * and random-access iterators, such as std::deque or an 530 * appropriate user-defined type. 531 * 532 * The third template parameter supplies the means of making 533 * priority comparisons. It defaults to @c less<value_type> but 534 * can be anything defining a strict weak ordering. 535 * 536 * Members not found in @a normal containers are @c container_type, 537 * which is a typedef for the second Sequence parameter, and @c 538 * push, @c pop, and @c top, which are standard %queue operations. 539 * 540 * @note No equality/comparison operators are provided for 541 * %priority_queue. 542 * 543 * @note Sorting of the elements takes place as they are added to, 544 * and removed from, the %priority_queue using the 545 * %priority_queue's member functions. If you access the elements 546 * by other means, and change their data such that the sorting 547 * order would be different, the %priority_queue will not re-sort 548 * the elements for you. (How could it know to do so?) 549 */ 550 template<typename _Tp, typename _Sequence = vector<_Tp>, 551 typename _Compare = less<typename _Sequence::value_type> > 552 class priority_queue 553 { 554 #ifdef _GLIBCXX_CONCEPT_CHECKS 555 // concept requirements 556 typedef typename _Sequence::value_type _Sequence_value_type; 557 # if __cplusplus < 201103L 558 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 559 # endif 560 __glibcxx_class_requires(_Sequence, _SequenceConcept) 561 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 562 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 563 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 564 _BinaryFunctionConcept) 565 #endif 566 567 #if __cplusplus >= 201103L 568 template<typename _Alloc> 569 using _Uses = typename 570 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; 571 572 #if __cplusplus >= 201703L 573 // _GLIBCXX_RESOLVE_LIB_DEFECTS 574 // 2566. Requirements on the first template parameter of container 575 // adaptors 576 static_assert(is_same<_Tp, typename _Sequence::value_type>::value, 577 "value_type must be the same as the underlying container"); 578 #endif // C++17 579 #endif // C++11 580 581 public: 582 typedef typename _Sequence::value_type value_type; 583 typedef typename _Sequence::reference reference; 584 typedef typename _Sequence::const_reference const_reference; 585 typedef typename _Sequence::size_type size_type; 586 typedef _Sequence container_type; 587 // _GLIBCXX_RESOLVE_LIB_DEFECTS 588 // DR 2684. priority_queue lacking comparator typedef 589 typedef _Compare value_compare; 590 591 protected: 592 // See queue::c for notes on these names. 593 _Sequence c; 594 _Compare comp; 595 596 public: 597 /** 598 * @brief Default constructor creates no elements. 599 */ 600 #if __cplusplus < 201103L 601 explicit 602 priority_queue(const _Compare& __x = _Compare(), 603 const _Sequence& __s = _Sequence()) 604 : c(__s), comp(__x) 605 { std::make_heap(c.begin(), c.end(), comp); } 606 #else 607 template<typename _Seq = _Sequence, typename _Requires = typename 608 enable_if<__and_<is_default_constructible<_Compare>, 609 is_default_constructible<_Seq>>::value>::type> 610 priority_queue() 611 : c(), comp() { } 612 613 explicit 614 priority_queue(const _Compare& __x, const _Sequence& __s) 615 : c(__s), comp(__x) 616 { std::make_heap(c.begin(), c.end(), comp); } 617 618 explicit 619 priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence()) 620 : c(std::move(__s)), comp(__x) 621 { std::make_heap(c.begin(), c.end(), comp); } 622 623 priority_queue(const priority_queue&) = default; 624 priority_queue& operator=(const priority_queue&) = default; 625 626 priority_queue(priority_queue&& __q) 627 noexcept(__and_<is_nothrow_move_constructible<_Sequence>, 628 is_nothrow_move_constructible<_Compare>>::value) 629 : c(std::move(__q.c)), comp(std::move(__q.comp)) 630 { __q.c.clear(); } 631 632 priority_queue& 633 operator=(priority_queue&& __q) 634 noexcept(__and_<is_nothrow_move_assignable<_Sequence>, 635 is_nothrow_move_assignable<_Compare>>::value) 636 { 637 c = std::move(__q.c); 638 __q.c.clear(); 639 comp = std::move(__q.comp); 640 return *this; 641 } 642 643 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 644 explicit 645 priority_queue(const _Alloc& __a) 646 : c(__a), comp() { } 647 648 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 649 priority_queue(const _Compare& __x, const _Alloc& __a) 650 : c(__a), comp(__x) { } 651 652 // _GLIBCXX_RESOLVE_LIB_DEFECTS 653 // 2537. Constructors [...] taking allocators should call make_heap 654 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 655 priority_queue(const _Compare& __x, const _Sequence& __c, 656 const _Alloc& __a) 657 : c(__c, __a), comp(__x) 658 { std::make_heap(c.begin(), c.end(), comp); } 659 660 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 661 priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) 662 : c(std::move(__c), __a), comp(__x) 663 { std::make_heap(c.begin(), c.end(), comp); } 664 665 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 666 priority_queue(const priority_queue& __q, const _Alloc& __a) 667 : c(__q.c, __a), comp(__q.comp) { } 668 669 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 670 priority_queue(priority_queue&& __q, const _Alloc& __a) 671 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) 672 { __q.c.clear(); } 673 #endif 674 675 /** 676 * @brief Builds a %queue from a range. 677 * @param __first An input iterator. 678 * @param __last An input iterator. 679 * @param __x A comparison functor describing a strict weak ordering. 680 * @param __s An initial sequence with which to start. 681 * 682 * Begins by copying @a __s, inserting a copy of the elements 683 * from @a [first,last) into the copy of @a __s, then ordering 684 * the copy according to @a __x. 685 * 686 * For more information on function objects, see the 687 * documentation on @link functors functor base classes@endlink. 688 */ 689 #if __cplusplus < 201103L 690 template<typename _InputIterator> 691 priority_queue(_InputIterator __first, _InputIterator __last, 692 const _Compare& __x = _Compare(), 693 const _Sequence& __s = _Sequence()) 694 : c(__s), comp(__x) 695 { 696 __glibcxx_requires_valid_range(__first, __last); 697 c.insert(c.end(), __first, __last); 698 std::make_heap(c.begin(), c.end(), comp); 699 } 700 #else 701 // _GLIBCXX_RESOLVE_LIB_DEFECTS 702 // 3529. priority_queue(first, last) should construct c with (first, last) 703 template<typename _InputIterator, 704 typename = std::_RequireInputIter<_InputIterator>> 705 priority_queue(_InputIterator __first, _InputIterator __last, 706 const _Compare& __x = _Compare()) 707 : c(__first, __last), comp(__x) 708 { std::make_heap(c.begin(), c.end(), comp); } 709 710 // _GLIBCXX_RESOLVE_LIB_DEFECTS 711 // 3522. Missing requirement on InputIterator template parameter 712 template<typename _InputIterator, 713 typename = std::_RequireInputIter<_InputIterator>> 714 priority_queue(_InputIterator __first, _InputIterator __last, 715 const _Compare& __x, const _Sequence& __s) 716 : c(__s), comp(__x) 717 { 718 __glibcxx_requires_valid_range(__first, __last); 719 c.insert(c.end(), __first, __last); 720 std::make_heap(c.begin(), c.end(), comp); 721 } 722 723 template<typename _InputIterator, 724 typename = std::_RequireInputIter<_InputIterator>> 725 priority_queue(_InputIterator __first, _InputIterator __last, 726 const _Compare& __x, _Sequence&& __s) 727 : c(std::move(__s)), comp(__x) 728 { 729 __glibcxx_requires_valid_range(__first, __last); 730 c.insert(c.end(), __first, __last); 731 std::make_heap(c.begin(), c.end(), comp); 732 } 733 734 // _GLIBCXX_RESOLVE_LIB_DEFECTS 735 // 3506. Missing allocator-extended constructors for priority_queue 736 template<typename _InputIterator, typename _Alloc, 737 typename = std::_RequireInputIter<_InputIterator>, 738 typename _Requires = _Uses<_Alloc>> 739 priority_queue(_InputIterator __first, _InputIterator __last, 740 const _Alloc& __alloc) 741 : c(__first, __last, __alloc), comp() 742 { std::make_heap(c.begin(), c.end(), comp); } 743 744 template<typename _InputIterator, typename _Alloc, 745 typename = std::_RequireInputIter<_InputIterator>, 746 typename _Requires = _Uses<_Alloc>> 747 priority_queue(_InputIterator __first, _InputIterator __last, 748 const _Compare& __x, const _Alloc& __alloc) 749 : c(__first, __last, __alloc), comp(__x) 750 { std::make_heap(c.begin(), c.end(), comp); } 751 752 template<typename _InputIterator, typename _Alloc, 753 typename = std::_RequireInputIter<_InputIterator>, 754 typename _Requires = _Uses<_Alloc>> 755 priority_queue(_InputIterator __first, _InputIterator __last, 756 const _Compare& __x, const _Sequence& __s, 757 const _Alloc& __alloc) 758 : c(__s, __alloc), comp(__x) 759 { 760 __glibcxx_requires_valid_range(__first, __last); 761 c.insert(c.end(), __first, __last); 762 std::make_heap(c.begin(), c.end(), comp); 763 } 764 765 template<typename _InputIterator, typename _Alloc, 766 typename _Requires = _Uses<_Alloc>> 767 priority_queue(_InputIterator __first, _InputIterator __last, 768 const _Compare& __x, _Sequence&& __s, 769 const _Alloc& __alloc) 770 : c(std::move(__s), __alloc), comp(__x) 771 { 772 __glibcxx_requires_valid_range(__first, __last); 773 c.insert(c.end(), __first, __last); 774 std::make_heap(c.begin(), c.end(), comp); 775 } 776 #endif 777 778 #if __glibcxx_containers_ranges // C++ >= 23 779 /** 780 * @brief Construct a priority_queue from a range. 781 * @since C++23 782 * 783 * @{ 784 */ 785 template<__detail::__container_compatible_range<_Tp> _Rg> 786 priority_queue(from_range_t, _Rg&& __rg, 787 const _Compare& __x = _Compare()) 788 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg))), comp(__x) 789 { std::make_heap(c.begin(), c.end(), comp); } 790 791 template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc> 792 priority_queue(from_range_t, _Rg&& __rg, const _Compare& __x, 793 const _Alloc& __a) 794 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp(__x) 795 { std::make_heap(c.begin(), c.end(), comp); } 796 797 template<__detail::__container_compatible_range<_Tp> _Rg, typename _Alloc> 798 priority_queue(from_range_t, _Rg&& __rg, const _Alloc& __a) 799 : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a)), comp() 800 { std::make_heap(c.begin(), c.end(), comp); } 801 /// @} 802 #endif 803 804 /** 805 * Returns true if the %queue is empty. 806 */ 807 _GLIBCXX_NODISCARD bool 808 empty() const 809 { return c.empty(); } 810 811 /** Returns the number of elements in the %queue. */ 812 _GLIBCXX_NODISCARD 813 size_type 814 size() const 815 { return c.size(); } 816 817 /** 818 * Returns a read-only (constant) reference to the data at the first 819 * element of the %queue. 820 */ 821 _GLIBCXX_NODISCARD 822 const_reference 823 top() const 824 { 825 __glibcxx_requires_nonempty(); 826 return c.front(); 827 } 828 829 /** 830 * @brief Add data to the %queue. 831 * @param __x Data to be added. 832 * 833 * This is a typical %queue operation. 834 * The time complexity of the operation depends on the underlying 835 * sequence. 836 */ 837 void 838 push(const value_type& __x) 839 { 840 c.push_back(__x); 841 std::push_heap(c.begin(), c.end(), comp); 842 } 843 844 #if __cplusplus >= 201103L 845 void 846 push(value_type&& __x) 847 { 848 c.push_back(std::move(__x)); 849 std::push_heap(c.begin(), c.end(), comp); 850 } 851 852 template<typename... _Args> 853 void 854 emplace(_Args&&... __args) 855 { 856 c.emplace_back(std::forward<_Args>(__args)...); 857 std::push_heap(c.begin(), c.end(), comp); 858 } 859 #endif 860 861 #if __glibcxx_containers_ranges // C++ >= 23 862 template<__detail::__container_compatible_range<_Tp> _Rg> 863 void 864 push_range(_Rg&& __rg) 865 { 866 if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); }) 867 c.append_range(std::forward<_Rg>(__rg)); 868 else 869 ranges::copy(__rg, std::back_inserter(c)); 870 std::make_heap(c.begin(), c.end(), comp); 871 } 872 #endif 873 874 /** 875 * @brief Removes first element. 876 * 877 * This is a typical %queue operation. It shrinks the %queue 878 * by one. The time complexity of the operation depends on the 879 * underlying sequence. 880 * 881 * Note that no data is returned, and if the first element's 882 * data is needed, it should be retrieved before pop() is 883 * called. 884 */ 885 void 886 pop() 887 { 888 __glibcxx_requires_nonempty(); 889 std::pop_heap(c.begin(), c.end(), comp); 890 c.pop_back(); 891 } 892 893 #if __cplusplus >= 201103L 894 void 895 swap(priority_queue& __pq) 896 noexcept(__and_< 897 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 898 __is_nothrow_swappable<_Sequence>, 899 #else 900 __is_nothrow_swappable<_Tp>, 901 #endif 902 __is_nothrow_swappable<_Compare> 903 >::value) 904 { 905 using std::swap; 906 swap(c, __pq.c); 907 swap(comp, __pq.comp); 908 } 909 #endif // __cplusplus >= 201103L 910 911 #if __glibcxx_format_ranges 912 friend class formatter<priority_queue<_Tp, _Sequence, _Compare>, char>; 913 friend class formatter<priority_queue<_Tp, _Sequence, _Compare>, wchar_t>; 914 #endif 915 }; 916 917 #if __cpp_deduction_guides >= 201606 918 template<typename _Compare, typename _Container, 919 typename = _RequireNotAllocator<_Compare>, 920 typename = _RequireNotAllocator<_Container>> 921 priority_queue(_Compare, _Container) 922 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 923 924 template<typename _InputIterator, typename _ValT 925 = typename iterator_traits<_InputIterator>::value_type, 926 typename _Compare = less<_ValT>, 927 typename _Container = vector<_ValT>, 928 typename = _RequireInputIter<_InputIterator>, 929 typename = _RequireNotAllocator<_Compare>, 930 typename = _RequireNotAllocator<_Container>> 931 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), 932 _Container = _Container()) 933 -> priority_queue<_ValT, _Container, _Compare>; 934 935 template<typename _Compare, typename _Container, typename _Allocator, 936 typename = _RequireNotAllocator<_Compare>, 937 typename = _RequireNotAllocator<_Container>> 938 priority_queue(_Compare, _Container, _Allocator) 939 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 940 941 #if __glibcxx_containers_ranges // C++ >= 23 942 template<ranges::input_range _Rg, 943 __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>, 944 __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>> 945 priority_queue(from_range_t, _Rg&&, _Compare = _Compare(), 946 _Alloc = _Alloc()) 947 -> priority_queue<ranges::range_value_t<_Rg>, 948 vector<ranges::range_value_t<_Rg>, _Alloc>, 949 _Compare>; 950 951 template<ranges::input_range _Rg, __allocator_like _Alloc> 952 priority_queue(from_range_t, _Rg&&, _Alloc) 953 -> priority_queue<ranges::range_value_t<_Rg>, 954 vector<ranges::range_value_t<_Rg>, _Alloc>>; 955 #endif 956 #endif 957 958 // No equality/comparison operators are provided for priority_queue. 959 960 #if __cplusplus >= 201103L 961 template<typename _Tp, typename _Sequence, typename _Compare> 962 inline 963 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 964 // Constrained free swap overload, see p0185r1 965 typename enable_if<__and_<__is_swappable<_Sequence>, 966 __is_swappable<_Compare>>::value>::type 967 #else 968 void 969 #endif 970 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 971 priority_queue<_Tp, _Sequence, _Compare>& __y) 972 noexcept(noexcept(__x.swap(__y))) 973 { __x.swap(__y); } 974 975 template<typename _Tp, typename _Sequence, typename _Compare, 976 typename _Alloc> 977 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> 978 : public uses_allocator<_Sequence, _Alloc>::type { }; 979 #endif // __cplusplus >= 201103L 980 981 _GLIBCXX_END_NAMESPACE_VERSION 982 } // namespace 983 984 #endif /* _STL_QUEUE_H */
