1 // Queue implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 4 // 2010, 2011 5 // Free Software Foundation, Inc. 6 // 7 // This file is part of the GNU ISO C++ Library. This library is free 8 // software; you can redistribute it and/or modify it under the 9 // terms of the GNU General Public License as published by the 10 // Free Software Foundation; either version 3, or (at your option) 11 // any later version. 12 13 // This library is distributed in the hope that it will be useful, 14 // but WITHOUT ANY WARRANTY; without even the implied warranty of 15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 // GNU General Public License for more details. 17 18 // Under Section 7 of GPL version 3, you are granted additional 19 // permissions described in the GCC Runtime Library Exception, version 20 // 3.1, as published by the Free Software Foundation. 21 22 // You should have received a copy of the GNU General Public License and 23 // a copy of the GCC Runtime Library Exception along with this program; 24 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 25 // <http://www.gnu.org/licenses/>. 26 27 /* 28 * 29 * Copyright (c) 1994 30 * Hewlett-Packard Company 31 * 32 * Permission to use, copy, modify, distribute and sell this software 33 * and its documentation for any purpose is hereby granted without fee, 34 * provided that the above copyright notice appear in all copies and 35 * that both that copyright notice and this permission notice appear 36 * in supporting documentation. Hewlett-Packard Company makes no 37 * representations about the suitability of this software for any 38 * purpose. It is provided "as is" without express or implied warranty. 39 * 40 * 41 * Copyright (c) 1996,1997 42 * Silicon Graphics Computer Systems, Inc. 43 * 44 * Permission to use, copy, modify, distribute and sell this software 45 * and its documentation for any purpose is hereby granted without fee, 46 * provided that the above copyright notice appear in all copies and 47 * that both that copyright notice and this permission notice appear 48 * in supporting documentation. Silicon Graphics makes no 49 * representations about the suitability of this software for any 50 * purpose. It is provided "as is" without express or implied warranty. 51 */ 52 53 /** @file bits/stl_queue.h 54 * This is an internal header file, included by other library headers. 55 * Do not attempt to use it directly. @headername{queue} 56 */ 57 58 #ifndef _STL_QUEUE_H 59 #define _STL_QUEUE_H 1 60 61 #include <bits/concept_check.h> 62 #include <debug/debug.h> 63 64 namespace std _GLIBCXX_VISIBILITY(default) 65 { 66 _GLIBCXX_BEGIN_NAMESPACE_VERSION 67 68 /** 69 * @brief A standard container giving FIFO behavior. 70 * 71 * @ingroup sequences 72 * 73 * Meets many of the requirements of a 74 * <a href="tables.html#65">container</a>, 75 * but does not define anything to do with iterators. Very few of the 76 * other standard container interfaces are defined. 77 * 78 * This is not a true container, but an @e adaptor. It holds another 79 * container, and provides a wrapper interface to that container. The 80 * wrapper is what enforces strict first-in-first-out %queue behavior. 81 * 82 * The second template parameter defines the type of the underlying 83 * sequence/container. It defaults to std::deque, but it can be any type 84 * that supports @c front, @c back, @c push_back, and @c pop_front, 85 * such as std::list or an appropriate user-defined type. 86 * 87 * Members not found in @a normal containers are @c container_type, 88 * which is a typedef for the second Sequence parameter, and @c push and 89 * @c pop, which are standard %queue/FIFO operations. 90 */ 91 template<typename _Tp, typename _Sequence = deque<_Tp> > 92 class queue 93 { 94 // concept requirements 95 typedef typename _Sequence::value_type _Sequence_value_type; 96 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 97 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept) 98 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 99 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 100 101 template<typename _Tp1, typename _Seq1> 102 friend bool 103 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 104 105 template<typename _Tp1, typename _Seq1> 106 friend bool 107 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&); 108 109 public: 110 typedef typename _Sequence::value_type value_type; 111 typedef typename _Sequence::reference reference; 112 typedef typename _Sequence::const_reference const_reference; 113 typedef typename _Sequence::size_type size_type; 114 typedef _Sequence container_type; 115 116 protected: 117 /** 118 * 'c' is the underlying container. Maintainers wondering why 119 * this isn't uglified as per style guidelines should note that 120 * this name is specified in the standard, [23.2.3.1]. (Why? 121 * Presumably for the same reason that it's protected instead 122 * of private: to allow derivation. But none of the other 123 * containers allow for derivation. Odd.) 124 */ 125 _Sequence c; 126 127 public: 128 /** 129 * @brief Default constructor creates no elements. 130 */ 131 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 132 explicit 133 queue(const _Sequence& __c = _Sequence()) 134 : c(__c) { } 135 #else 136 explicit 137 queue(const _Sequence& __c) 138 : c(__c) { } 139 140 explicit 141 queue(_Sequence&& __c = _Sequence()) 142 : c(std::move(__c)) { } 143 #endif 144 145 /** 146 * Returns true if the %queue is empty. 147 */ 148 bool 149 empty() const 150 { return c.empty(); } 151 152 /** Returns the number of elements in the %queue. */ 153 size_type 154 size() const 155 { return c.size(); } 156 157 /** 158 * Returns a read/write reference to the data at the first 159 * element of the %queue. 160 */ 161 reference 162 front() 163 { 164 __glibcxx_requires_nonempty(); 165 return c.front(); 166 } 167 168 /** 169 * Returns a read-only (constant) reference to the data at the first 170 * element of the %queue. 171 */ 172 const_reference 173 front() const 174 { 175 __glibcxx_requires_nonempty(); 176 return c.front(); 177 } 178 179 /** 180 * Returns a read/write reference to the data at the last 181 * element of the %queue. 182 */ 183 reference 184 back() 185 { 186 __glibcxx_requires_nonempty(); 187 return c.back(); 188 } 189 190 /** 191 * Returns a read-only (constant) reference to the data at the last 192 * element of the %queue. 193 */ 194 const_reference 195 back() const 196 { 197 __glibcxx_requires_nonempty(); 198 return c.back(); 199 } 200 201 /** 202 * @brief Add data to the end of the %queue. 203 * @param __x Data to be added. 204 * 205 * This is a typical %queue operation. The function creates an 206 * element at the end of the %queue and assigns the given data 207 * to it. The time complexity of the operation depends on the 208 * underlying sequence. 209 */ 210 void 211 push(const value_type& __x) 212 { c.push_back(__x); } 213 214 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 215 void 216 push(value_type&& __x) 217 { c.push_back(std::move(__x)); } 218 219 template<typename... _Args> 220 void 221 emplace(_Args&&... __args) 222 { c.emplace_back(std::forward<_Args>(__args)...); } 223 #endif 224 225 /** 226 * @brief Removes first element. 227 * 228 * This is a typical %queue operation. It shrinks the %queue by one. 229 * The time complexity of the operation depends on the underlying 230 * sequence. 231 * 232 * Note that no data is returned, and if the first element's 233 * data is needed, it should be retrieved before pop() is 234 * called. 235 */ 236 void 237 pop() 238 { 239 __glibcxx_requires_nonempty(); 240 c.pop_front(); 241 } 242 243 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 244 void 245 swap(queue& __q) 246 noexcept(noexcept(swap(c, __q.c))) 247 { 248 using std::swap; 249 swap(c, __q.c); 250 } 251 #endif 252 }; 253 254 /** 255 * @brief Queue equality comparison. 256 * @param __x A %queue. 257 * @param __y A %queue of the same type as @a __x. 258 * @return True iff the size and elements of the queues are equal. 259 * 260 * This is an equivalence relation. Complexity and semantics depend on the 261 * underlying sequence type, but the expected rules are: this relation is 262 * linear in the size of the sequences, and queues are considered equivalent 263 * if their sequences compare equal. 264 */ 265 template<typename _Tp, typename _Seq> 266 inline bool 267 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 268 { return __x.c == __y.c; } 269 270 /** 271 * @brief Queue ordering relation. 272 * @param __x A %queue. 273 * @param __y A %queue of the same type as @a x. 274 * @return True iff @a __x is lexicographically less than @a __y. 275 * 276 * This is an total ordering relation. Complexity and semantics 277 * depend on the underlying sequence type, but the expected rules 278 * are: this relation is linear in the size of the sequences, the 279 * elements must be comparable with @c <, and 280 * std::lexicographical_compare() is usually used to make the 281 * determination. 282 */ 283 template<typename _Tp, typename _Seq> 284 inline bool 285 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 286 { return __x.c < __y.c; } 287 288 /// Based on operator== 289 template<typename _Tp, typename _Seq> 290 inline bool 291 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 292 { return !(__x == __y); } 293 294 /// Based on operator< 295 template<typename _Tp, typename _Seq> 296 inline bool 297 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 298 { return __y < __x; } 299 300 /// Based on operator< 301 template<typename _Tp, typename _Seq> 302 inline bool 303 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 304 { return !(__y < __x); } 305 306 /// Based on operator< 307 template<typename _Tp, typename _Seq> 308 inline bool 309 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 310 { return !(__x < __y); } 311 312 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 313 template<typename _Tp, typename _Seq> 314 inline void 315 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 316 noexcept(noexcept(__x.swap(__y))) 317 { __x.swap(__y); } 318 319 template<typename _Tp, typename _Seq, typename _Alloc> 320 struct uses_allocator<queue<_Tp, _Seq>, _Alloc> 321 : public uses_allocator<_Seq, _Alloc>::type { }; 322 #endif 323 324 /** 325 * @brief A standard container automatically sorting its contents. 326 * 327 * @ingroup sequences 328 * 329 * This is not a true container, but an @e adaptor. It holds 330 * another container, and provides a wrapper interface to that 331 * container. The wrapper is what enforces priority-based sorting 332 * and %queue behavior. Very few of the standard container/sequence 333 * interface requirements are met (e.g., iterators). 334 * 335 * The second template parameter defines the type of the underlying 336 * sequence/container. It defaults to std::vector, but it can be 337 * any type that supports @c front(), @c push_back, @c pop_back, 338 * and random-access iterators, such as std::deque or an 339 * appropriate user-defined type. 340 * 341 * The third template parameter supplies the means of making 342 * priority comparisons. It defaults to @c less<value_type> but 343 * can be anything defining a strict weak ordering. 344 * 345 * Members not found in @a normal containers are @c container_type, 346 * which is a typedef for the second Sequence parameter, and @c 347 * push, @c pop, and @c top, which are standard %queue operations. 348 * 349 * @note No equality/comparison operators are provided for 350 * %priority_queue. 351 * 352 * @note Sorting of the elements takes place as they are added to, 353 * and removed from, the %priority_queue using the 354 * %priority_queue's member functions. If you access the elements 355 * by other means, and change their data such that the sorting 356 * order would be different, the %priority_queue will not re-sort 357 * the elements for you. (How could it know to do so?) 358 */ 359 template<typename _Tp, typename _Sequence = vector<_Tp>, 360 typename _Compare = less<typename _Sequence::value_type> > 361 class priority_queue 362 { 363 // concept requirements 364 typedef typename _Sequence::value_type _Sequence_value_type; 365 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 366 __glibcxx_class_requires(_Sequence, _SequenceConcept) 367 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 368 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 369 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 370 _BinaryFunctionConcept) 371 372 public: 373 typedef typename _Sequence::value_type value_type; 374 typedef typename _Sequence::reference reference; 375 typedef typename _Sequence::const_reference const_reference; 376 typedef typename _Sequence::size_type size_type; 377 typedef _Sequence container_type; 378 379 protected: 380 // See queue::c for notes on these names. 381 _Sequence c; 382 _Compare comp; 383 384 public: 385 /** 386 * @brief Default constructor creates no elements. 387 */ 388 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 389 explicit 390 priority_queue(const _Compare& __x = _Compare(), 391 const _Sequence& __s = _Sequence()) 392 : c(__s), comp(__x) 393 { std::make_heap(c.begin(), c.end(), comp); } 394 #else 395 explicit 396 priority_queue(const _Compare& __x, 397 const _Sequence& __s) 398 : c(__s), comp(__x) 399 { std::make_heap(c.begin(), c.end(), comp); } 400 401 explicit 402 priority_queue(const _Compare& __x = _Compare(), 403 _Sequence&& __s = _Sequence()) 404 : c(std::move(__s)), comp(__x) 405 { std::make_heap(c.begin(), c.end(), comp); } 406 #endif 407 408 /** 409 * @brief Builds a %queue from a range. 410 * @param __first An input iterator. 411 * @param __last An input iterator. 412 * @param __x A comparison functor describing a strict weak ordering. 413 * @param __s An initial sequence with which to start. 414 * 415 * Begins by copying @a __s, inserting a copy of the elements 416 * from @a [first,last) into the copy of @a __s, then ordering 417 * the copy according to @a __x. 418 * 419 * For more information on function objects, see the 420 * documentation on @link functors functor base 421 * classes@endlink. 422 */ 423 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 424 template<typename _InputIterator> 425 priority_queue(_InputIterator __first, _InputIterator __last, 426 const _Compare& __x = _Compare(), 427 const _Sequence& __s = _Sequence()) 428 : c(__s), comp(__x) 429 { 430 __glibcxx_requires_valid_range(__first, __last); 431 c.insert(c.end(), __first, __last); 432 std::make_heap(c.begin(), c.end(), comp); 433 } 434 #else 435 template<typename _InputIterator> 436 priority_queue(_InputIterator __first, _InputIterator __last, 437 const _Compare& __x, 438 const _Sequence& __s) 439 : c(__s), comp(__x) 440 { 441 __glibcxx_requires_valid_range(__first, __last); 442 c.insert(c.end(), __first, __last); 443 std::make_heap(c.begin(), c.end(), comp); 444 } 445 446 template<typename _InputIterator> 447 priority_queue(_InputIterator __first, _InputIterator __last, 448 const _Compare& __x = _Compare(), 449 _Sequence&& __s = _Sequence()) 450 : c(std::move(__s)), comp(__x) 451 { 452 __glibcxx_requires_valid_range(__first, __last); 453 c.insert(c.end(), __first, __last); 454 std::make_heap(c.begin(), c.end(), comp); 455 } 456 #endif 457 458 /** 459 * Returns true if the %queue is empty. 460 */ 461 bool 462 empty() const 463 { return c.empty(); } 464 465 /** Returns the number of elements in the %queue. */ 466 size_type 467 size() const 468 { return c.size(); } 469 470 /** 471 * Returns a read-only (constant) reference to the data at the first 472 * element of the %queue. 473 */ 474 const_reference 475 top() const 476 { 477 __glibcxx_requires_nonempty(); 478 return c.front(); 479 } 480 481 /** 482 * @brief Add data to the %queue. 483 * @param __x Data to be added. 484 * 485 * This is a typical %queue operation. 486 * The time complexity of the operation depends on the underlying 487 * sequence. 488 */ 489 void 490 push(const value_type& __x) 491 { 492 c.push_back(__x); 493 std::push_heap(c.begin(), c.end(), comp); 494 } 495 496 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 497 void 498 push(value_type&& __x) 499 { 500 c.push_back(std::move(__x)); 501 std::push_heap(c.begin(), c.end(), comp); 502 } 503 504 template<typename... _Args> 505 void 506 emplace(_Args&&... __args) 507 { 508 c.emplace_back(std::forward<_Args>(__args)...); 509 std::push_heap(c.begin(), c.end(), comp); 510 } 511 #endif 512 513 /** 514 * @brief Removes first element. 515 * 516 * This is a typical %queue operation. It shrinks the %queue 517 * by one. The time complexity of the operation depends on the 518 * underlying sequence. 519 * 520 * Note that no data is returned, and if the first element's 521 * data is needed, it should be retrieved before pop() is 522 * called. 523 */ 524 void 525 pop() 526 { 527 __glibcxx_requires_nonempty(); 528 std::pop_heap(c.begin(), c.end(), comp); 529 c.pop_back(); 530 } 531 532 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 533 void 534 swap(priority_queue& __pq) 535 noexcept(noexcept(swap(c, __pq.c)) && noexcept(swap(comp, __pq.comp))) 536 { 537 using std::swap; 538 swap(c, __pq.c); 539 swap(comp, __pq.comp); 540 } 541 #endif 542 }; 543 544 // No equality/comparison operators are provided for priority_queue. 545 546 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 547 template<typename _Tp, typename _Sequence, typename _Compare> 548 inline void 549 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 550 priority_queue<_Tp, _Sequence, _Compare>& __y) 551 noexcept(noexcept(__x.swap(__y))) 552 { __x.swap(__y); } 553 554 template<typename _Tp, typename _Sequence, typename _Compare, 555 typename _Alloc> 556 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> 557 : public uses_allocator<_Sequence, _Alloc>::type { }; 558 #endif 559 560 _GLIBCXX_END_NAMESPACE_VERSION 561 } // namespace 562 563 #endif /* _STL_QUEUE_H */ 564