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