1// Queue implementation -*- C++ -*- 2 3// Copyright (C) 2001-2020 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 65namespace std _GLIBCXX_VISIBILITY(default) 66{ 67_GLIBCXX_BEGIN_NAMESPACE_VERSION 68 69 /** 70 * @brief A standard container giving FIFO behavior. 71 * 72 * @ingroup sequences 73 * 74 * @tparam _Tp Type of element. 75 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>. 76 * 77 * Meets many of the requirements of a 78 * <a href="tables.html#65">container</a>, 79 * but does not define anything to do with iterators. Very few of the 80 * other standard container interfaces are defined. 81 * 82 * This is not a true container, but an @e adaptor. It holds another 83 * container, and provides a wrapper interface to that container. The 84 * wrapper is what enforces strict first-in-first-out %queue behavior. 85 * 86 * The second template parameter defines the type of the underlying 87 * sequence/container. It defaults to std::deque, but it can be any type 88 * that supports @c front, @c back, @c push_back, and @c pop_front, 89 * such as std::list or an appropriate user-defined type. 90 * 91 * Members not found in @a normal containers are @c container_type, 92 * which is a typedef for the second Sequence parameter, and @c push and 93 * @c pop, which are standard %queue/FIFO operations. 94 */ 95 template<typename _Tp, typename _Sequence = deque<_Tp> > 96 class queue 97 { 98#ifdef _GLIBCXX_CONCEPT_CHECKS 99 // concept requirements 100 typedef typename _Sequence::value_type _Sequence_value_type; 101# if __cplusplus < 201103L 102 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 103# endif 104 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 105 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 106 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 107#endif 108 109 template<typename _Tp1, typename _Seq1> 110 friend bool 111 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 112 113 template<typename _Tp1, typename _Seq1> 114 friend bool 115 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 116 117#if __cpp_lib_three_way_comparison 118 template<typename _Tp1, three_way_comparable _Seq1> 119 friend compare_three_way_result_t<_Seq1> 120 operator<=>(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 121#endif 122 123#if __cplusplus >= 201103L 124 template<typename _Alloc> 125 using _Uses = typename 126 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; 127 128#if __cplusplus >= 201703L 129 // _GLIBCXX_RESOLVE_LIB_DEFECTS 130 // 2566. Requirements on the first template parameter of container 131 // adaptors 132 static_assert(is_same<_Tp, typename _Sequence::value_type>::value, 133 "value_type must be the same as the underlying container"); 134#endif // C++17 135#endif // C++11 136 137 public: 138 typedef typename _Sequence::value_type value_type; 139 typedef typename _Sequence::reference reference; 140 typedef typename _Sequence::const_reference const_reference; 141 typedef typename _Sequence::size_type size_type; 142 typedef _Sequence container_type; 143 144 protected: 145 /* Maintainers wondering why this isn't uglified as per style 146 * guidelines should note that this name is specified in the standard, 147 * C++98 [23.2.3.1]. 148 * (Why? Presumably for the same reason that it's protected instead 149 * of private: to allow derivation. But none of the other 150 * containers allow for derivation. Odd.) 151 */ 152 /// @c c is the underlying container. 153 _Sequence c; 154 155 public: 156 /** 157 * @brief Default constructor creates no elements. 158 */ 159#if __cplusplus < 201103L 160 explicit 161 queue(const _Sequence& __c = _Sequence()) 162 : c(__c) { } 163#else 164 template<typename _Seq = _Sequence, typename _Requires = typename 165 enable_if<is_default_constructible<_Seq>::value>::type> 166 queue() 167 : c() { } 168 169 explicit 170 queue(const _Sequence& __c) 171 : c(__c) { } 172 173 explicit 174 queue(_Sequence&& __c) 175 : c(std::move(__c)) { } 176 177 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 178 explicit 179 queue(const _Alloc& __a) 180 : c(__a) { } 181 182 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 183 queue(const _Sequence& __c, const _Alloc& __a) 184 : c(__c, __a) { } 185 186 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 187 queue(_Sequence&& __c, const _Alloc& __a) 188 : c(std::move(__c), __a) { } 189 190 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 191 queue(const queue& __q, const _Alloc& __a) 192 : c(__q.c, __a) { } 193 194 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 195 queue(queue&& __q, const _Alloc& __a) 196 : c(std::move(__q.c), __a) { } 197#endif 198 199 /** 200 * Returns true if the %queue is empty. 201 */ 202 _GLIBCXX_NODISCARD bool 203 empty() const 204 { return c.empty(); } 205 206 /** Returns the number of elements in the %queue. */ 207 size_type 208 size() const 209 { return c.size(); } 210 211 /** 212 * Returns a read/write reference to the data at the first 213 * element of the %queue. 214 */ 215 reference 216 front() 217 { 218 __glibcxx_requires_nonempty(); 219 return c.front(); 220 } 221 222 /** 223 * Returns a read-only (constant) reference to the data at the first 224 * element of the %queue. 225 */ 226 const_reference 227 front() const 228 { 229 __glibcxx_requires_nonempty(); 230 return c.front(); 231 } 232 233 /** 234 * Returns a read/write reference to the data at the last 235 * element of the %queue. 236 */ 237 reference 238 back() 239 { 240 __glibcxx_requires_nonempty(); 241 return c.back(); 242 } 243 244 /** 245 * Returns a read-only (constant) reference to the data at the last 246 * element of the %queue. 247 */ 248 const_reference 249 back() const 250 { 251 __glibcxx_requires_nonempty(); 252 return c.back(); 253 } 254 255 /** 256 * @brief Add data to the end of the %queue. 257 * @param __x Data to be added. 258 * 259 * This is a typical %queue operation. The function creates an 260 * element at the end of the %queue and assigns the given data 261 * to it. The time complexity of the operation depends on the 262 * underlying sequence. 263 */ 264 void 265 push(const value_type& __x) 266 { c.push_back(__x); } 267 268#if __cplusplus >= 201103L 269 void 270 push(value_type&& __x) 271 { c.push_back(std::move(__x)); } 272 273#if __cplusplus > 201402L 274 template<typename... _Args> 275 decltype(auto) 276 emplace(_Args&&... __args) 277 { return c.emplace_back(std::forward<_Args>(__args)...); } 278#else 279 template<typename... _Args> 280 void 281 emplace(_Args&&... __args) 282 { c.emplace_back(std::forward<_Args>(__args)...); } 283#endif 284#endif 285 286 /** 287 * @brief Removes first element. 288 * 289 * This is a typical %queue operation. It shrinks the %queue by one. 290 * The time complexity of the operation depends on the underlying 291 * sequence. 292 * 293 * Note that no data is returned, and if the first element's 294 * data is needed, it should be retrieved before pop() is 295 * called. 296 */ 297 void 298 pop() 299 { 300 __glibcxx_requires_nonempty(); 301 c.pop_front(); 302 } 303 304#if __cplusplus >= 201103L 305 void 306 swap(queue& __q) 307#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 308 noexcept(__is_nothrow_swappable<_Sequence>::value) 309#else 310 noexcept(__is_nothrow_swappable<_Tp>::value) 311#endif 312 { 313 using std::swap; 314 swap(c, __q.c); 315 } 316#endif // __cplusplus >= 201103L 317 }; 318 319#if __cpp_deduction_guides >= 201606 320 template<typename _Container, 321 typename = _RequireNotAllocator<_Container>> 322 queue(_Container) -> queue<typename _Container::value_type, _Container>; 323 324 template<typename _Container, typename _Allocator, 325 typename = _RequireNotAllocator<_Container>, 326 typename = _RequireAllocator<_Allocator>> 327 queue(_Container, _Allocator) 328 -> queue<typename _Container::value_type, _Container>; 329#endif 330 331 /** 332 * @brief Queue equality comparison. 333 * @param __x A %queue. 334 * @param __y A %queue of the same type as @a __x. 335 * @return True iff the size and elements of the queues are equal. 336 * 337 * This is an equivalence relation. Complexity and semantics depend on the 338 * underlying sequence type, but the expected rules are: this relation is 339 * linear in the size of the sequences, and queues are considered equivalent 340 * if their sequences compare equal. 341 */ 342 template<typename _Tp, typename _Seq> 343 inline bool 344 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 345 { return __x.c == __y.c; } 346 347 /** 348 * @brief Queue ordering relation. 349 * @param __x A %queue. 350 * @param __y A %queue of the same type as @a x. 351 * @return True iff @a __x is lexicographically less than @a __y. 352 * 353 * This is an total ordering relation. Complexity and semantics 354 * depend on the underlying sequence type, but the expected rules 355 * are: this relation is linear in the size of the sequences, the 356 * elements must be comparable with @c <, and 357 * std::lexicographical_compare() is usually used to make the 358 * determination. 359 */ 360 template<typename _Tp, typename _Seq> 361 inline bool 362 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 363 { return __x.c < __y.c; } 364 365 /// Based on operator== 366 template<typename _Tp, typename _Seq> 367 inline bool 368 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 369 { return !(__x == __y); } 370 371 /// Based on operator< 372 template<typename _Tp, typename _Seq> 373 inline bool 374 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 375 { return __y < __x; } 376 377 /// Based on operator< 378 template<typename _Tp, typename _Seq> 379 inline bool 380 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 381 { return !(__y < __x); } 382 383 /// Based on operator< 384 template<typename _Tp, typename _Seq> 385 inline bool 386 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 387 { return !(__x < __y); } 388 389#if __cpp_lib_three_way_comparison 390 template<typename _Tp, three_way_comparable _Seq> 391 inline compare_three_way_result_t<_Seq> 392 operator<=>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 393 { return __x.c <=> __y.c; } 394#endif 395 396#if __cplusplus >= 201103L 397 template<typename _Tp, typename _Seq> 398 inline 399#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 400 // Constrained free swap overload, see p0185r1 401 typename enable_if<__is_swappable<_Seq>::value>::type 402#else 403 void 404#endif 405 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 406 noexcept(noexcept(__x.swap(__y))) 407 { __x.swap(__y); } 408 409 template<typename _Tp, typename _Seq, typename _Alloc> 410 struct uses_allocator<queue<_Tp, _Seq>, _Alloc> 411 : public uses_allocator<_Seq, _Alloc>::type { }; 412#endif // __cplusplus >= 201103L 413 414 /** 415 * @brief A standard container automatically sorting its contents. 416 * 417 * @ingroup sequences 418 * 419 * @tparam _Tp Type of element. 420 * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>. 421 * @tparam _Compare Comparison function object type, defaults to 422 * less<_Sequence::value_type>. 423 * 424 * This is not a true container, but an @e adaptor. It holds 425 * another container, and provides a wrapper interface to that 426 * container. The wrapper is what enforces priority-based sorting 427 * and %queue behavior. Very few of the standard container/sequence 428 * interface requirements are met (e.g., iterators). 429 * 430 * The second template parameter defines the type of the underlying 431 * sequence/container. It defaults to std::vector, but it can be 432 * any type that supports @c front(), @c push_back, @c pop_back, 433 * and random-access iterators, such as std::deque or an 434 * appropriate user-defined type. 435 * 436 * The third template parameter supplies the means of making 437 * priority comparisons. It defaults to @c less<value_type> but 438 * can be anything defining a strict weak ordering. 439 * 440 * Members not found in @a normal containers are @c container_type, 441 * which is a typedef for the second Sequence parameter, and @c 442 * push, @c pop, and @c top, which are standard %queue operations. 443 * 444 * @note No equality/comparison operators are provided for 445 * %priority_queue. 446 * 447 * @note Sorting of the elements takes place as they are added to, 448 * and removed from, the %priority_queue using the 449 * %priority_queue's member functions. If you access the elements 450 * by other means, and change their data such that the sorting 451 * order would be different, the %priority_queue will not re-sort 452 * the elements for you. (How could it know to do so?) 453 */ 454 template<typename _Tp, typename _Sequence = vector<_Tp>, 455 typename _Compare = less<typename _Sequence::value_type> > 456 class priority_queue 457 { 458#ifdef _GLIBCXX_CONCEPT_CHECKS 459 // concept requirements 460 typedef typename _Sequence::value_type _Sequence_value_type; 461# if __cplusplus < 201103L 462 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 463# endif 464 __glibcxx_class_requires(_Sequence, _SequenceConcept) 465 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 466 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 467 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 468 _BinaryFunctionConcept) 469#endif 470 471#if __cplusplus >= 201103L 472 template<typename _Alloc> 473 using _Uses = typename 474 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; 475 476#if __cplusplus >= 201703L 477 // _GLIBCXX_RESOLVE_LIB_DEFECTS 478 // 2566. Requirements on the first template parameter of container 479 // adaptors 480 static_assert(is_same<_Tp, typename _Sequence::value_type>::value, 481 "value_type must be the same as the underlying container"); 482#endif // C++17 483#endif // C++11 484 485 public: 486 typedef typename _Sequence::value_type value_type; 487 typedef typename _Sequence::reference reference; 488 typedef typename _Sequence::const_reference const_reference; 489 typedef typename _Sequence::size_type size_type; 490 typedef _Sequence container_type; 491 // _GLIBCXX_RESOLVE_LIB_DEFECTS 492 // DR 2684. priority_queue lacking comparator typedef 493 typedef _Compare value_compare; 494 495 protected: 496 // See queue::c for notes on these names. 497 _Sequence c; 498 _Compare comp; 499 500 public: 501 /** 502 * @brief Default constructor creates no elements. 503 */ 504#if __cplusplus < 201103L 505 explicit 506 priority_queue(const _Compare& __x = _Compare(), 507 const _Sequence& __s = _Sequence()) 508 : c(__s), comp(__x) 509 { std::make_heap(c.begin(), c.end(), comp); } 510#else 511 template<typename _Seq = _Sequence, typename _Requires = typename 512 enable_if<__and_<is_default_constructible<_Compare>, 513 is_default_constructible<_Seq>>::value>::type> 514 priority_queue() 515 : c(), comp() { } 516 517 explicit 518 priority_queue(const _Compare& __x, const _Sequence& __s) 519 : c(__s), comp(__x) 520 { std::make_heap(c.begin(), c.end(), comp); } 521 522 explicit 523 priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence()) 524 : c(std::move(__s)), comp(__x) 525 { std::make_heap(c.begin(), c.end(), comp); } 526 527 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 528 explicit 529 priority_queue(const _Alloc& __a) 530 : c(__a), comp() { } 531 532 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 533 priority_queue(const _Compare& __x, const _Alloc& __a) 534 : c(__a), comp(__x) { } 535 536 // _GLIBCXX_RESOLVE_LIB_DEFECTS 537 // 2537. Constructors [...] taking allocators should call make_heap 538 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 539 priority_queue(const _Compare& __x, const _Sequence& __c, 540 const _Alloc& __a) 541 : c(__c, __a), comp(__x) 542 { std::make_heap(c.begin(), c.end(), comp); } 543 544 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 545 priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) 546 : c(std::move(__c), __a), comp(__x) 547 { std::make_heap(c.begin(), c.end(), comp); } 548 549 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 550 priority_queue(const priority_queue& __q, const _Alloc& __a) 551 : c(__q.c, __a), comp(__q.comp) { } 552 553 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 554 priority_queue(priority_queue&& __q, const _Alloc& __a) 555 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { } 556#endif 557 558 /** 559 * @brief Builds a %queue from a range. 560 * @param __first An input iterator. 561 * @param __last An input iterator. 562 * @param __x A comparison functor describing a strict weak ordering. 563 * @param __s An initial sequence with which to start. 564 * 565 * Begins by copying @a __s, inserting a copy of the elements 566 * from @a [first,last) into the copy of @a __s, then ordering 567 * the copy according to @a __x. 568 * 569 * For more information on function objects, see the 570 * documentation on @link functors functor base 571 * classes@endlink. 572 */ 573#if __cplusplus < 201103L 574 template<typename _InputIterator> 575 priority_queue(_InputIterator __first, _InputIterator __last, 576 const _Compare& __x = _Compare(), 577 const _Sequence& __s = _Sequence()) 578 : c(__s), comp(__x) 579 { 580 __glibcxx_requires_valid_range(__first, __last); 581 c.insert(c.end(), __first, __last); 582 std::make_heap(c.begin(), c.end(), comp); 583 } 584#else 585 template<typename _InputIterator> 586 priority_queue(_InputIterator __first, _InputIterator __last, 587 const _Compare& __x, 588 const _Sequence& __s) 589 : c(__s), comp(__x) 590 { 591 __glibcxx_requires_valid_range(__first, __last); 592 c.insert(c.end(), __first, __last); 593 std::make_heap(c.begin(), c.end(), comp); 594 } 595 596 template<typename _InputIterator> 597 priority_queue(_InputIterator __first, _InputIterator __last, 598 const _Compare& __x = _Compare(), 599 _Sequence&& __s = _Sequence()) 600 : c(std::move(__s)), comp(__x) 601 { 602 __glibcxx_requires_valid_range(__first, __last); 603 c.insert(c.end(), __first, __last); 604 std::make_heap(c.begin(), c.end(), comp); 605 } 606#endif 607 608 /** 609 * Returns true if the %queue is empty. 610 */ 611 _GLIBCXX_NODISCARD bool 612 empty() const 613 { return c.empty(); } 614 615 /** Returns the number of elements in the %queue. */ 616 size_type 617 size() const 618 { return c.size(); } 619 620 /** 621 * Returns a read-only (constant) reference to the data at the first 622 * element of the %queue. 623 */ 624 const_reference 625 top() const 626 { 627 __glibcxx_requires_nonempty(); 628 return c.front(); 629 } 630 631 /** 632 * @brief Add data to the %queue. 633 * @param __x Data to be added. 634 * 635 * This is a typical %queue operation. 636 * The time complexity of the operation depends on the underlying 637 * sequence. 638 */ 639 void 640 push(const value_type& __x) 641 { 642 c.push_back(__x); 643 std::push_heap(c.begin(), c.end(), comp); 644 } 645 646#if __cplusplus >= 201103L 647 void 648 push(value_type&& __x) 649 { 650 c.push_back(std::move(__x)); 651 std::push_heap(c.begin(), c.end(), comp); 652 } 653 654 template<typename... _Args> 655 void 656 emplace(_Args&&... __args) 657 { 658 c.emplace_back(std::forward<_Args>(__args)...); 659 std::push_heap(c.begin(), c.end(), comp); 660 } 661#endif 662 663 /** 664 * @brief Removes first element. 665 * 666 * This is a typical %queue operation. It shrinks the %queue 667 * by one. The time complexity of the operation depends on the 668 * underlying sequence. 669 * 670 * Note that no data is returned, and if the first element's 671 * data is needed, it should be retrieved before pop() is 672 * called. 673 */ 674 void 675 pop() 676 { 677 __glibcxx_requires_nonempty(); 678 std::pop_heap(c.begin(), c.end(), comp); 679 c.pop_back(); 680 } 681 682#if __cplusplus >= 201103L 683 void 684 swap(priority_queue& __pq) 685 noexcept(__and_< 686#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 687 __is_nothrow_swappable<_Sequence>, 688#else 689 __is_nothrow_swappable<_Tp>, 690#endif 691 __is_nothrow_swappable<_Compare> 692 >::value) 693 { 694 using std::swap; 695 swap(c, __pq.c); 696 swap(comp, __pq.comp); 697 } 698#endif // __cplusplus >= 201103L 699 }; 700 701#if __cpp_deduction_guides >= 201606 702 template<typename _Compare, typename _Container, 703 typename = _RequireNotAllocator<_Compare>, 704 typename = _RequireNotAllocator<_Container>> 705 priority_queue(_Compare, _Container) 706 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 707 708 template<typename _InputIterator, typename _ValT 709 = typename iterator_traits<_InputIterator>::value_type, 710 typename _Compare = less<_ValT>, 711 typename _Container = vector<_ValT>, 712 typename = _RequireInputIter<_InputIterator>, 713 typename = _RequireNotAllocator<_Compare>, 714 typename = _RequireNotAllocator<_Container>> 715 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), 716 _Container = _Container()) 717 -> priority_queue<_ValT, _Container, _Compare>; 718 719 template<typename _Compare, typename _Container, typename _Allocator, 720 typename = _RequireNotAllocator<_Compare>, 721 typename = _RequireNotAllocator<_Container>, 722 typename = _RequireAllocator<_Allocator>> 723 priority_queue(_Compare, _Container, _Allocator) 724 -> priority_queue<typename _Container::value_type, _Container, _Compare>; 725#endif 726 727 // No equality/comparison operators are provided for priority_queue. 728 729#if __cplusplus >= 201103L 730 template<typename _Tp, typename _Sequence, typename _Compare> 731 inline 732#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 733 // Constrained free swap overload, see p0185r1 734 typename enable_if<__and_<__is_swappable<_Sequence>, 735 __is_swappable<_Compare>>::value>::type 736#else 737 void 738#endif 739 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 740 priority_queue<_Tp, _Sequence, _Compare>& __y) 741 noexcept(noexcept(__x.swap(__y))) 742 { __x.swap(__y); } 743 744 template<typename _Tp, typename _Sequence, typename _Compare, 745 typename _Alloc> 746 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> 747 : public uses_allocator<_Sequence, _Alloc>::type { }; 748#endif // __cplusplus >= 201103L 749 750_GLIBCXX_END_NAMESPACE_VERSION 751} // namespace 752 753#endif /* _STL_QUEUE_H */ 754