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 /** 306 * @brief Queue equality comparison. 307 * @param __x A %queue. 308 * @param __y A %queue of the same type as @a __x. 309 * @return True iff the size and elements of the queues are equal. 310 * 311 * This is an equivalence relation. Complexity and semantics depend on the 312 * underlying sequence type, but the expected rules are: this relation is 313 * linear in the size of the sequences, and queues are considered equivalent 314 * if their sequences compare equal. 315 */ 316 template<typename _Tp, typename _Seq> 317 inline bool 318 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 319 { return __x.c == __y.c; } 320 321 /** 322 * @brief Queue ordering relation. 323 * @param __x A %queue. 324 * @param __y A %queue of the same type as @a x. 325 * @return True iff @a __x is lexicographically less than @a __y. 326 * 327 * This is an total ordering relation. Complexity and semantics 328 * depend on the underlying sequence type, but the expected rules 329 * are: this relation is linear in the size of the sequences, the 330 * elements must be comparable with @c <, and 331 * std::lexicographical_compare() is usually used to make the 332 * determination. 333 */ 334 template<typename _Tp, typename _Seq> 335 inline bool 336 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 337 { return __x.c < __y.c; } 338 339 /// Based on operator== 340 template<typename _Tp, typename _Seq> 341 inline bool 342 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 343 { return !(__x == __y); } 344 345 /// Based on operator< 346 template<typename _Tp, typename _Seq> 347 inline bool 348 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 349 { return __y < __x; } 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 !(__y < __x); } 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 !(__x < __y); } 362 363 #if __cplusplus >= 201103L 364 template<typename _Tp, typename _Seq> 365 inline 366 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 367 // Constrained free swap overload, see p0185r1 368 typename enable_if<__is_swappable<_Seq>::value>::type 369 #else 370 void 371 #endif 372 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 373 noexcept(noexcept(__x.swap(__y))) 374 { __x.swap(__y); } 375 376 template<typename _Tp, typename _Seq, typename _Alloc> 377 struct uses_allocator<queue<_Tp, _Seq>, _Alloc> 378 : public uses_allocator<_Seq, _Alloc>::type { }; 379 #endif // __cplusplus >= 201103L 380 381 /** 382 * @brief A standard container automatically sorting its contents. 383 * 384 * @ingroup sequences 385 * 386 * @tparam _Tp Type of element. 387 * @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>. 388 * @tparam _Compare Comparison function object type, defaults to 389 * less<_Sequence::value_type>. 390 * 391 * This is not a true container, but an @e adaptor. It holds 392 * another container, and provides a wrapper interface to that 393 * container. The wrapper is what enforces priority-based sorting 394 * and %queue behavior. Very few of the standard container/sequence 395 * interface requirements are met (e.g., iterators). 396 * 397 * The second template parameter defines the type of the underlying 398 * sequence/container. It defaults to std::vector, but it can be 399 * any type that supports @c front(), @c push_back, @c pop_back, 400 * and random-access iterators, such as std::deque or an 401 * appropriate user-defined type. 402 * 403 * The third template parameter supplies the means of making 404 * priority comparisons. It defaults to @c less<value_type> but 405 * can be anything defining a strict weak ordering. 406 * 407 * Members not found in @a normal containers are @c container_type, 408 * which is a typedef for the second Sequence parameter, and @c 409 * push, @c pop, and @c top, which are standard %queue operations. 410 * 411 * @note No equality/comparison operators are provided for 412 * %priority_queue. 413 * 414 * @note Sorting of the elements takes place as they are added to, 415 * and removed from, the %priority_queue using the 416 * %priority_queue's member functions. If you access the elements 417 * by other means, and change their data such that the sorting 418 * order would be different, the %priority_queue will not re-sort 419 * the elements for you. (How could it know to do so?) 420 */ 421 template<typename _Tp, typename _Sequence = vector<_Tp>, 422 typename _Compare = less<typename _Sequence::value_type> > 423 class priority_queue 424 { 425 #ifdef _GLIBCXX_CONCEPT_CHECKS 426 // concept requirements 427 typedef typename _Sequence::value_type _Sequence_value_type; 428 # if __cplusplus < 201103L 429 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 430 # endif 431 __glibcxx_class_requires(_Sequence, _SequenceConcept) 432 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 433 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 434 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 435 _BinaryFunctionConcept) 436 #endif 437 438 #if __cplusplus >= 201103L 439 template<typename _Alloc> 440 using _Uses = typename 441 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type; 442 #endif 443 444 public: 445 typedef typename _Sequence::value_type value_type; 446 typedef typename _Sequence::reference reference; 447 typedef typename _Sequence::const_reference const_reference; 448 typedef typename _Sequence::size_type size_type; 449 typedef _Sequence container_type; 450 // _GLIBCXX_RESOLVE_LIB_DEFECTS 451 // DR 2684. priority_queue lacking comparator typedef 452 typedef _Compare value_compare; 453 454 protected: 455 // See queue::c for notes on these names. 456 _Sequence c; 457 _Compare comp; 458 459 public: 460 /** 461 * @brief Default constructor creates no elements. 462 */ 463 #if __cplusplus < 201103L 464 explicit 465 priority_queue(const _Compare& __x = _Compare(), 466 const _Sequence& __s = _Sequence()) 467 : c(__s), comp(__x) 468 { std::make_heap(c.begin(), c.end(), comp); } 469 #else 470 template<typename _Seq = _Sequence, typename _Requires = typename 471 enable_if<__and_<is_default_constructible<_Compare>, 472 is_default_constructible<_Seq>>::value>::type> 473 priority_queue() 474 : c(), comp() { } 475 476 explicit 477 priority_queue(const _Compare& __x, const _Sequence& __s) 478 : c(__s), comp(__x) 479 { std::make_heap(c.begin(), c.end(), comp); } 480 481 explicit 482 priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence()) 483 : c(std::move(__s)), comp(__x) 484 { std::make_heap(c.begin(), c.end(), comp); } 485 486 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 487 explicit 488 priority_queue(const _Alloc& __a) 489 : c(__a), comp() { } 490 491 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 492 priority_queue(const _Compare& __x, const _Alloc& __a) 493 : c(__a), comp(__x) { } 494 495 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 496 priority_queue(const _Compare& __x, const _Sequence& __c, 497 const _Alloc& __a) 498 : c(__c, __a), comp(__x) { } 499 500 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 501 priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) 502 : c(std::move(__c), __a), comp(__x) { } 503 504 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 505 priority_queue(const priority_queue& __q, const _Alloc& __a) 506 : c(__q.c, __a), comp(__q.comp) { } 507 508 template<typename _Alloc, typename _Requires = _Uses<_Alloc>> 509 priority_queue(priority_queue&& __q, const _Alloc& __a) 510 : c(std::move(__q.c), __a), comp(std::move(__q.comp)) { } 511 #endif 512 513 /** 514 * @brief Builds a %queue from a range. 515 * @param __first An input iterator. 516 * @param __last An input iterator. 517 * @param __x A comparison functor describing a strict weak ordering. 518 * @param __s An initial sequence with which to start. 519 * 520 * Begins by copying @a __s, inserting a copy of the elements 521 * from @a [first,last) into the copy of @a __s, then ordering 522 * the copy according to @a __x. 523 * 524 * For more information on function objects, see the 525 * documentation on @link functors functor base 526 * classes@endlink. 527 */ 528 #if __cplusplus < 201103L 529 template<typename _InputIterator> 530 priority_queue(_InputIterator __first, _InputIterator __last, 531 const _Compare& __x = _Compare(), 532 const _Sequence& __s = _Sequence()) 533 : c(__s), comp(__x) 534 { 535 __glibcxx_requires_valid_range(__first, __last); 536 c.insert(c.end(), __first, __last); 537 std::make_heap(c.begin(), c.end(), comp); 538 } 539 #else 540 template<typename _InputIterator> 541 priority_queue(_InputIterator __first, _InputIterator __last, 542 const _Compare& __x, 543 const _Sequence& __s) 544 : c(__s), comp(__x) 545 { 546 __glibcxx_requires_valid_range(__first, __last); 547 c.insert(c.end(), __first, __last); 548 std::make_heap(c.begin(), c.end(), comp); 549 } 550 551 template<typename _InputIterator> 552 priority_queue(_InputIterator __first, _InputIterator __last, 553 const _Compare& __x = _Compare(), 554 _Sequence&& __s = _Sequence()) 555 : c(std::move(__s)), comp(__x) 556 { 557 __glibcxx_requires_valid_range(__first, __last); 558 c.insert(c.end(), __first, __last); 559 std::make_heap(c.begin(), c.end(), comp); 560 } 561 #endif 562 563 /** 564 * Returns true if the %queue is empty. 565 */ 566 bool 567 empty() const 568 { return c.empty(); } 569 570 /** Returns the number of elements in the %queue. */ 571 size_type 572 size() const 573 { return c.size(); } 574 575 /** 576 * Returns a read-only (constant) reference to the data at the first 577 * element of the %queue. 578 */ 579 const_reference 580 top() const 581 { 582 __glibcxx_requires_nonempty(); 583 return c.front(); 584 } 585 586 /** 587 * @brief Add data to the %queue. 588 * @param __x Data to be added. 589 * 590 * This is a typical %queue operation. 591 * The time complexity of the operation depends on the underlying 592 * sequence. 593 */ 594 void 595 push(const value_type& __x) 596 { 597 c.push_back(__x); 598 std::push_heap(c.begin(), c.end(), comp); 599 } 600 601 #if __cplusplus >= 201103L 602 void 603 push(value_type&& __x) 604 { 605 c.push_back(std::move(__x)); 606 std::push_heap(c.begin(), c.end(), comp); 607 } 608 609 template<typename... _Args> 610 void 611 emplace(_Args&&... __args) 612 { 613 c.emplace_back(std::forward<_Args>(__args)...); 614 std::push_heap(c.begin(), c.end(), comp); 615 } 616 #endif 617 618 /** 619 * @brief Removes first element. 620 * 621 * This is a typical %queue operation. It shrinks the %queue 622 * by one. The time complexity of the operation depends on the 623 * underlying sequence. 624 * 625 * Note that no data is returned, and if the first element's 626 * data is needed, it should be retrieved before pop() is 627 * called. 628 */ 629 void 630 pop() 631 { 632 __glibcxx_requires_nonempty(); 633 std::pop_heap(c.begin(), c.end(), comp); 634 c.pop_back(); 635 } 636 637 #if __cplusplus >= 201103L 638 void 639 swap(priority_queue& __pq) 640 noexcept(__and_< 641 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 642 __is_nothrow_swappable<_Sequence>, 643 #else 644 __is_nothrow_swappable<_Tp>, 645 #endif 646 __is_nothrow_swappable<_Compare> 647 >::value) 648 { 649 using std::swap; 650 swap(c, __pq.c); 651 swap(comp, __pq.comp); 652 } 653 #endif // __cplusplus >= 201103L 654 }; 655 656 // No equality/comparison operators are provided for priority_queue. 657 658 #if __cplusplus >= 201103L 659 template<typename _Tp, typename _Sequence, typename _Compare> 660 inline 661 #if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 662 // Constrained free swap overload, see p0185r1 663 typename enable_if<__and_<__is_swappable<_Sequence>, 664 __is_swappable<_Compare>>::value>::type 665 #else 666 void 667 #endif 668 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 669 priority_queue<_Tp, _Sequence, _Compare>& __y) 670 noexcept(noexcept(__x.swap(__y))) 671 { __x.swap(__y); } 672 673 template<typename _Tp, typename _Sequence, typename _Compare, 674 typename _Alloc> 675 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> 676 : public uses_allocator<_Sequence, _Alloc>::type { }; 677 #endif // __cplusplus >= 201103L 678 679 _GLIBCXX_END_NAMESPACE_VERSION 680 } // namespace 681 682 #endif /* _STL_QUEUE_H */ 683