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