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