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