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 64namespace 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 { 247 using std::swap; 248 swap(c, __q.c); 249 } 250#endif 251 }; 252 253 /** 254 * @brief Queue equality comparison. 255 * @param x A %queue. 256 * @param y A %queue of the same type as @a x. 257 * @return True iff the size and elements of the queues are equal. 258 * 259 * This is an equivalence relation. Complexity and semantics depend on the 260 * underlying sequence type, but the expected rules are: this relation is 261 * linear in the size of the sequences, and queues are considered equivalent 262 * if their sequences compare equal. 263 */ 264 template<typename _Tp, typename _Seq> 265 inline bool 266 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 267 { return __x.c == __y.c; } 268 269 /** 270 * @brief Queue ordering relation. 271 * @param x A %queue. 272 * @param y A %queue of the same type as @a x. 273 * @return True iff @a x is lexicographically less than @a y. 274 * 275 * This is an total ordering relation. Complexity and semantics 276 * depend on the underlying sequence type, but the expected rules 277 * are: this relation is linear in the size of the sequences, the 278 * elements must be comparable with @c <, and 279 * std::lexicographical_compare() is usually used to make the 280 * determination. 281 */ 282 template<typename _Tp, typename _Seq> 283 inline bool 284 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 285 { return __x.c < __y.c; } 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 !(__x == __y); } 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 !(__y < __x); } 304 305 /// Based on operator< 306 template<typename _Tp, typename _Seq> 307 inline bool 308 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 309 { return !(__x < __y); } 310 311#ifdef __GXX_EXPERIMENTAL_CXX0X__ 312 template<typename _Tp, typename _Seq> 313 inline void 314 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 315 { __x.swap(__y); } 316 317 template<typename _Tp, typename _Seq, typename _Alloc> 318 struct uses_allocator<queue<_Tp, _Seq>, _Alloc> 319 : public uses_allocator<_Seq, _Alloc>::type { }; 320#endif 321 322 /** 323 * @brief A standard container automatically sorting its contents. 324 * 325 * @ingroup sequences 326 * 327 * This is not a true container, but an @e adaptor. It holds 328 * another container, and provides a wrapper interface to that 329 * container. The wrapper is what enforces priority-based sorting 330 * and %queue behavior. Very few of the standard container/sequence 331 * interface requirements are met (e.g., iterators). 332 * 333 * The second template parameter defines the type of the underlying 334 * sequence/container. It defaults to std::vector, but it can be 335 * any type that supports @c front(), @c push_back, @c pop_back, 336 * and random-access iterators, such as std::deque or an 337 * appropriate user-defined type. 338 * 339 * The third template parameter supplies the means of making 340 * priority comparisons. It defaults to @c less<value_type> but 341 * can be anything defining a strict weak ordering. 342 * 343 * Members not found in @a normal containers are @c container_type, 344 * which is a typedef for the second Sequence parameter, and @c 345 * push, @c pop, and @c top, which are standard %queue operations. 346 * 347 * @note No equality/comparison operators are provided for 348 * %priority_queue. 349 * 350 * @note Sorting of the elements takes place as they are added to, 351 * and removed from, the %priority_queue using the 352 * %priority_queue's member functions. If you access the elements 353 * by other means, and change their data such that the sorting 354 * order would be different, the %priority_queue will not re-sort 355 * the elements for you. (How could it know to do so?) 356 */ 357 template<typename _Tp, typename _Sequence = vector<_Tp>, 358 typename _Compare = less<typename _Sequence::value_type> > 359 class priority_queue 360 { 361 // concept requirements 362 typedef typename _Sequence::value_type _Sequence_value_type; 363 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 364 __glibcxx_class_requires(_Sequence, _SequenceConcept) 365 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 366 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 367 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 368 _BinaryFunctionConcept) 369 370 public: 371 typedef typename _Sequence::value_type value_type; 372 typedef typename _Sequence::reference reference; 373 typedef typename _Sequence::const_reference const_reference; 374 typedef typename _Sequence::size_type size_type; 375 typedef _Sequence container_type; 376 377 protected: 378 // See queue::c for notes on these names. 379 _Sequence c; 380 _Compare comp; 381 382 public: 383 /** 384 * @brief Default constructor creates no elements. 385 */ 386#ifndef __GXX_EXPERIMENTAL_CXX0X__ 387 explicit 388 priority_queue(const _Compare& __x = _Compare(), 389 const _Sequence& __s = _Sequence()) 390 : c(__s), comp(__x) 391 { std::make_heap(c.begin(), c.end(), comp); } 392#else 393 explicit 394 priority_queue(const _Compare& __x, 395 const _Sequence& __s) 396 : c(__s), comp(__x) 397 { std::make_heap(c.begin(), c.end(), comp); } 398 399 explicit 400 priority_queue(const _Compare& __x = _Compare(), 401 _Sequence&& __s = _Sequence()) 402 : c(std::move(__s)), comp(__x) 403 { std::make_heap(c.begin(), c.end(), comp); } 404#endif 405 406 /** 407 * @brief Builds a %queue from a range. 408 * @param first An input iterator. 409 * @param last An input iterator. 410 * @param x A comparison functor describing a strict weak ordering. 411 * @param s An initial sequence with which to start. 412 * 413 * Begins by copying @a s, inserting a copy of the elements 414 * from @a [first,last) into the copy of @a s, then ordering 415 * the copy according to @a x. 416 * 417 * For more information on function objects, see the 418 * documentation on @link functors functor base 419 * classes@endlink. 420 */ 421#ifndef __GXX_EXPERIMENTAL_CXX0X__ 422 template<typename _InputIterator> 423 priority_queue(_InputIterator __first, _InputIterator __last, 424 const _Compare& __x = _Compare(), 425 const _Sequence& __s = _Sequence()) 426 : c(__s), comp(__x) 427 { 428 __glibcxx_requires_valid_range(__first, __last); 429 c.insert(c.end(), __first, __last); 430 std::make_heap(c.begin(), c.end(), comp); 431 } 432#else 433 template<typename _InputIterator> 434 priority_queue(_InputIterator __first, _InputIterator __last, 435 const _Compare& __x, 436 const _Sequence& __s) 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 444 template<typename _InputIterator> 445 priority_queue(_InputIterator __first, _InputIterator __last, 446 const _Compare& __x = _Compare(), 447 _Sequence&& __s = _Sequence()) 448 : c(std::move(__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#endif 455 456 /** 457 * Returns true if the %queue is empty. 458 */ 459 bool 460 empty() const 461 { return c.empty(); } 462 463 /** Returns the number of elements in the %queue. */ 464 size_type 465 size() const 466 { return c.size(); } 467 468 /** 469 * Returns a read-only (constant) reference to the data at the first 470 * element of the %queue. 471 */ 472 const_reference 473 top() const 474 { 475 __glibcxx_requires_nonempty(); 476 return c.front(); 477 } 478 479 /** 480 * @brief Add data to the %queue. 481 * @param x Data to be added. 482 * 483 * This is a typical %queue operation. 484 * The time complexity of the operation depends on the underlying 485 * sequence. 486 */ 487 void 488 push(const value_type& __x) 489 { 490 c.push_back(__x); 491 std::push_heap(c.begin(), c.end(), comp); 492 } 493 494#ifdef __GXX_EXPERIMENTAL_CXX0X__ 495 void 496 push(value_type&& __x) 497 { 498 c.push_back(std::move(__x)); 499 std::push_heap(c.begin(), c.end(), comp); 500 } 501 502 template<typename... _Args> 503 void 504 emplace(_Args&&... __args) 505 { 506 c.emplace_back(std::forward<_Args>(__args)...); 507 std::push_heap(c.begin(), c.end(), comp); 508 } 509#endif 510 511 /** 512 * @brief Removes first element. 513 * 514 * This is a typical %queue operation. It shrinks the %queue 515 * by one. The time complexity of the operation depends on the 516 * underlying sequence. 517 * 518 * Note that no data is returned, and if the first element's 519 * data is needed, it should be retrieved before pop() is 520 * called. 521 */ 522 void 523 pop() 524 { 525 __glibcxx_requires_nonempty(); 526 std::pop_heap(c.begin(), c.end(), comp); 527 c.pop_back(); 528 } 529 530#ifdef __GXX_EXPERIMENTAL_CXX0X__ 531 void 532 swap(priority_queue& __pq) 533 { 534 using std::swap; 535 swap(c, __pq.c); 536 swap(comp, __pq.comp); 537 } 538#endif 539 }; 540 541 // No equality/comparison operators are provided for priority_queue. 542 543#ifdef __GXX_EXPERIMENTAL_CXX0X__ 544 template<typename _Tp, typename _Sequence, typename _Compare> 545 inline void 546 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 547 priority_queue<_Tp, _Sequence, _Compare>& __y) 548 { __x.swap(__y); } 549 550 template<typename _Tp, typename _Sequence, typename _Compare, 551 typename _Alloc> 552 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> 553 : public uses_allocator<_Sequence, _Alloc>::type { }; 554#endif 555 556_GLIBCXX_END_NAMESPACE_VERSION 557} // namespace 558 559#endif /* _STL_QUEUE_H */ 560