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