libstdc++-v3/include/bits/stl_queue.h

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