libstdc++
stl_queue.h
Go to the documentation of this file.
00001 // Queue implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
00004 // 2010, 2011
00005 // Free Software Foundation, Inc.
00006 //
00007 // This file is part of the GNU ISO C++ Library.  This library is free
00008 // software; you can redistribute it and/or modify it under the
00009 // terms of the GNU General Public License as published by the
00010 // Free Software Foundation; either version 3, or (at your option)
00011 // any later version.
00012 
00013 // This library is distributed in the hope that it will be useful,
00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 // GNU General Public License for more details.
00017 
00018 // Under Section 7 of GPL version 3, you are granted additional
00019 // permissions described in the GCC Runtime Library Exception, version
00020 // 3.1, as published by the Free Software Foundation.
00021 
00022 // You should have received a copy of the GNU General Public License and
00023 // a copy of the GCC Runtime Library Exception along with this program;
00024 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00025 // <http://www.gnu.org/licenses/>.
00026 
00027 /*
00028  *
00029  * Copyright (c) 1994
00030  * Hewlett-Packard Company
00031  *
00032  * Permission to use, copy, modify, distribute and sell this software
00033  * and its documentation for any purpose is hereby granted without fee,
00034  * provided that the above copyright notice appear in all copies and
00035  * that both that copyright notice and this permission notice appear
00036  * in supporting documentation.  Hewlett-Packard Company makes no
00037  * representations about the suitability of this software for any
00038  * purpose.  It is provided "as is" without express or implied warranty.
00039  *
00040  *
00041  * Copyright (c) 1996,1997
00042  * Silicon Graphics Computer Systems, Inc.
00043  *
00044  * Permission to use, copy, modify, distribute and sell this software
00045  * and its documentation for any purpose is hereby granted without fee,
00046  * provided that the above copyright notice appear in all copies and
00047  * that both that copyright notice and this permission notice appear
00048  * in supporting documentation.  Silicon Graphics makes no
00049  * representations about the suitability of this software for any
00050  * purpose.  It is provided "as is" without express or implied warranty.
00051  */
00052 
00053 /** @file bits/stl_queue.h
00054  *  This is an internal header file, included by other library headers.
00055  *  Do not attempt to use it directly. @headername{queue}
00056  */
00057 
00058 #ifndef _STL_QUEUE_H
00059 #define _STL_QUEUE_H 1
00060 
00061 #include <bits/concept_check.h>
00062 #include <debug/debug.h>
00063 
00064 namespace std _GLIBCXX_VISIBILITY(default)
00065 {
00066 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00067 
00068   /**
00069    *  @brief  A standard container giving FIFO behavior.
00070    *
00071    *  @ingroup sequences
00072    *
00073    *  Meets many of the requirements of a
00074    *  <a href="tables.html#65">container</a>,
00075    *  but does not define anything to do with iterators.  Very few of the
00076    *  other standard container interfaces are defined.
00077    *
00078    *  This is not a true container, but an @e adaptor.  It holds another
00079    *  container, and provides a wrapper interface to that container.  The
00080    *  wrapper is what enforces strict first-in-first-out %queue behavior.
00081    *
00082    *  The second template parameter defines the type of the underlying
00083    *  sequence/container.  It defaults to std::deque, but it can be any type
00084    *  that supports @c front, @c back, @c push_back, and @c pop_front,
00085    *  such as std::list or an appropriate user-defined type.
00086    *
00087    *  Members not found in @a normal containers are @c container_type,
00088    *  which is a typedef for the second Sequence parameter, and @c push and
00089    *  @c pop, which are standard %queue/FIFO operations.
00090   */
00091   template<typename _Tp, typename _Sequence = deque<_Tp> >
00092     class queue
00093     {
00094       // concept requirements
00095       typedef typename _Sequence::value_type _Sequence_value_type;
00096       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00097       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00098       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
00099       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00100 
00101       template<typename _Tp1, typename _Seq1>
00102         friend bool
00103         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00104 
00105       template<typename _Tp1, typename _Seq1>
00106         friend bool
00107         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00108 
00109     public:
00110       typedef typename _Sequence::value_type                value_type;
00111       typedef typename _Sequence::reference                 reference;
00112       typedef typename _Sequence::const_reference           const_reference;
00113       typedef typename _Sequence::size_type                 size_type;
00114       typedef          _Sequence                            container_type;
00115 
00116     protected:
00117       /**
00118        *  'c' is the underlying container.  Maintainers wondering why
00119        *  this isn't uglified as per style guidelines should note that
00120        *  this name is specified in the standard, [23.2.3.1].  (Why?
00121        *  Presumably for the same reason that it's protected instead
00122        *  of private: to allow derivation.  But none of the other
00123        *  containers allow for derivation.  Odd.)
00124        */
00125       _Sequence c;
00126 
00127     public:
00128       /**
00129        *  @brief  Default constructor creates no elements.
00130        */
00131 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00132       explicit
00133       queue(const _Sequence& __c = _Sequence())
00134       : c(__c) { }
00135 #else
00136       explicit
00137       queue(const _Sequence& __c)
00138       : c(__c) { }
00139 
00140       explicit
00141       queue(_Sequence&& __c = _Sequence())
00142       : c(std::move(__c)) { }
00143 #endif
00144 
00145       /**
00146        *  Returns true if the %queue is empty.
00147        */
00148       bool
00149       empty() const
00150       { return c.empty(); }
00151 
00152       /**  Returns the number of elements in the %queue.  */
00153       size_type
00154       size() const
00155       { return c.size(); }
00156 
00157       /**
00158        *  Returns a read/write reference to the data at the first
00159        *  element of the %queue.
00160        */
00161       reference
00162       front()
00163       {
00164     __glibcxx_requires_nonempty();
00165     return c.front();
00166       }
00167 
00168       /**
00169        *  Returns a read-only (constant) reference to the data at the first
00170        *  element of the %queue.
00171        */
00172       const_reference
00173       front() const
00174       {
00175     __glibcxx_requires_nonempty();
00176     return c.front();
00177       }
00178 
00179       /**
00180        *  Returns a read/write reference to the data at the last
00181        *  element of the %queue.
00182        */
00183       reference
00184       back()
00185       {
00186     __glibcxx_requires_nonempty();
00187     return c.back();
00188       }
00189 
00190       /**
00191        *  Returns a read-only (constant) reference to the data at the last
00192        *  element of the %queue.
00193        */
00194       const_reference
00195       back() const
00196       {
00197     __glibcxx_requires_nonempty();
00198     return c.back();
00199       }
00200 
00201       /**
00202        *  @brief  Add data to the end of the %queue.
00203        *  @param  __x  Data to be added.
00204        *
00205        *  This is a typical %queue operation.  The function creates an
00206        *  element at the end of the %queue and assigns the given data
00207        *  to it.  The time complexity of the operation depends on the
00208        *  underlying sequence.
00209        */
00210       void
00211       push(const value_type& __x)
00212       { c.push_back(__x); }
00213 
00214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00215       void
00216       push(value_type&& __x)
00217       { c.push_back(std::move(__x)); }
00218 
00219       template<typename... _Args>
00220         void
00221         emplace(_Args&&... __args)
00222     { c.emplace_back(std::forward<_Args>(__args)...); }
00223 #endif
00224 
00225       /**
00226        *  @brief  Removes first element.
00227        *
00228        *  This is a typical %queue operation.  It shrinks the %queue by one.
00229        *  The time complexity of the operation depends on the underlying
00230        *  sequence.
00231        *
00232        *  Note that no data is returned, and if the first element's
00233        *  data is needed, it should be retrieved before pop() is
00234        *  called.
00235        */
00236       void
00237       pop()
00238       {
00239     __glibcxx_requires_nonempty();
00240     c.pop_front();
00241       }
00242 
00243 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00244       void
00245       swap(queue& __q)
00246       noexcept(noexcept(swap(c, __q.c)))
00247       {
00248     using std::swap;
00249     swap(c, __q.c);
00250       }
00251 #endif
00252     };
00253 
00254   /**
00255    *  @brief  Queue equality comparison.
00256    *  @param  __x  A %queue.
00257    *  @param  __y  A %queue of the same type as @a __x.
00258    *  @return  True iff the size and elements of the queues are equal.
00259    *
00260    *  This is an equivalence relation.  Complexity and semantics depend on the
00261    *  underlying sequence type, but the expected rules are:  this relation is
00262    *  linear in the size of the sequences, and queues are considered equivalent
00263    *  if their sequences compare equal.
00264   */
00265   template<typename _Tp, typename _Seq>
00266     inline bool
00267     operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00268     { return __x.c == __y.c; }
00269 
00270   /**
00271    *  @brief  Queue ordering relation.
00272    *  @param  __x  A %queue.
00273    *  @param  __y  A %queue of the same type as @a x.
00274    *  @return  True iff @a __x is lexicographically less than @a __y.
00275    *
00276    *  This is an total ordering relation.  Complexity and semantics
00277    *  depend on the underlying sequence type, but the expected rules
00278    *  are: this relation is linear in the size of the sequences, the
00279    *  elements must be comparable with @c <, and
00280    *  std::lexicographical_compare() is usually used to make the
00281    *  determination.
00282   */
00283   template<typename _Tp, typename _Seq>
00284     inline bool
00285     operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00286     { return __x.c < __y.c; }
00287 
00288   /// Based on operator==
00289   template<typename _Tp, typename _Seq>
00290     inline bool
00291     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00292     { return !(__x == __y); }
00293 
00294   /// Based on operator<
00295   template<typename _Tp, typename _Seq>
00296     inline bool
00297     operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00298     { return __y < __x; }
00299 
00300   /// Based on operator<
00301   template<typename _Tp, typename _Seq>
00302     inline bool
00303     operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00304     { return !(__y < __x); }
00305 
00306   /// Based on operator<
00307   template<typename _Tp, typename _Seq>
00308     inline bool
00309     operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
00310     { return !(__x < __y); }
00311 
00312 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00313   template<typename _Tp, typename _Seq>
00314     inline void
00315     swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y)
00316     noexcept(noexcept(__x.swap(__y)))
00317     { __x.swap(__y); }
00318 
00319   template<typename _Tp, typename _Seq, typename _Alloc>
00320     struct uses_allocator<queue<_Tp, _Seq>, _Alloc>
00321     : public uses_allocator<_Seq, _Alloc>::type { };
00322 #endif
00323 
00324   /**
00325    *  @brief  A standard container automatically sorting its contents.
00326    *
00327    *  @ingroup sequences
00328    *
00329    *  This is not a true container, but an @e adaptor.  It holds
00330    *  another container, and provides a wrapper interface to that
00331    *  container.  The wrapper is what enforces priority-based sorting 
00332    *  and %queue behavior.  Very few of the standard container/sequence
00333    *  interface requirements are met (e.g., iterators).
00334    *
00335    *  The second template parameter defines the type of the underlying
00336    *  sequence/container.  It defaults to std::vector, but it can be
00337    *  any type that supports @c front(), @c push_back, @c pop_back,
00338    *  and random-access iterators, such as std::deque or an
00339    *  appropriate user-defined type.
00340    *
00341    *  The third template parameter supplies the means of making
00342    *  priority comparisons.  It defaults to @c less<value_type> but
00343    *  can be anything defining a strict weak ordering.
00344    *
00345    *  Members not found in @a normal containers are @c container_type,
00346    *  which is a typedef for the second Sequence parameter, and @c
00347    *  push, @c pop, and @c top, which are standard %queue operations.
00348    *
00349    *  @note No equality/comparison operators are provided for
00350    *  %priority_queue.
00351    *
00352    *  @note Sorting of the elements takes place as they are added to,
00353    *  and removed from, the %priority_queue using the
00354    *  %priority_queue's member functions.  If you access the elements
00355    *  by other means, and change their data such that the sorting
00356    *  order would be different, the %priority_queue will not re-sort
00357    *  the elements for you.  (How could it know to do so?)
00358   */
00359   template<typename _Tp, typename _Sequence = vector<_Tp>,
00360        typename _Compare  = less<typename _Sequence::value_type> >
00361     class priority_queue
00362     {
00363       // concept requirements
00364       typedef typename _Sequence::value_type _Sequence_value_type;
00365       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00366       __glibcxx_class_requires(_Sequence, _SequenceConcept)
00367       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
00368       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00369       __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp,
00370                 _BinaryFunctionConcept)
00371 
00372     public:
00373       typedef typename _Sequence::value_type                value_type;
00374       typedef typename _Sequence::reference                 reference;
00375       typedef typename _Sequence::const_reference           const_reference;
00376       typedef typename _Sequence::size_type                 size_type;
00377       typedef          _Sequence                            container_type;
00378 
00379     protected:
00380       //  See queue::c for notes on these names.
00381       _Sequence  c;
00382       _Compare   comp;
00383 
00384     public:
00385       /**
00386        *  @brief  Default constructor creates no elements.
00387        */
00388 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00389       explicit
00390       priority_queue(const _Compare& __x = _Compare(),
00391              const _Sequence& __s = _Sequence())
00392       : c(__s), comp(__x)
00393       { std::make_heap(c.begin(), c.end(), comp); }
00394 #else
00395       explicit
00396       priority_queue(const _Compare& __x,
00397              const _Sequence& __s)
00398       : c(__s), comp(__x)
00399       { std::make_heap(c.begin(), c.end(), comp); }
00400 
00401       explicit
00402       priority_queue(const _Compare& __x = _Compare(),
00403              _Sequence&& __s = _Sequence())
00404       : c(std::move(__s)), comp(__x)
00405       { std::make_heap(c.begin(), c.end(), comp); }
00406 #endif
00407 
00408       /**
00409        *  @brief  Builds a %queue from a range.
00410        *  @param  __first  An input iterator.
00411        *  @param  __last  An input iterator.
00412        *  @param  __x  A comparison functor describing a strict weak ordering.
00413        *  @param  __s  An initial sequence with which to start.
00414        *
00415        *  Begins by copying @a __s, inserting a copy of the elements
00416        *  from @a [first,last) into the copy of @a __s, then ordering
00417        *  the copy according to @a __x.
00418        *
00419        *  For more information on function objects, see the
00420        *  documentation on @link functors functor base
00421        *  classes@endlink.
00422        */
00423 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00424       template<typename _InputIterator>
00425         priority_queue(_InputIterator __first, _InputIterator __last,
00426                const _Compare& __x = _Compare(),
00427                const _Sequence& __s = _Sequence())
00428     : c(__s), comp(__x)
00429         {
00430       __glibcxx_requires_valid_range(__first, __last);
00431       c.insert(c.end(), __first, __last);
00432       std::make_heap(c.begin(), c.end(), comp);
00433     }
00434 #else
00435       template<typename _InputIterator>
00436         priority_queue(_InputIterator __first, _InputIterator __last,
00437                const _Compare& __x,
00438                const _Sequence& __s)
00439     : c(__s), comp(__x)
00440         {
00441       __glibcxx_requires_valid_range(__first, __last);
00442       c.insert(c.end(), __first, __last);
00443       std::make_heap(c.begin(), c.end(), comp);
00444     }
00445 
00446       template<typename _InputIterator>
00447         priority_queue(_InputIterator __first, _InputIterator __last,
00448                const _Compare& __x = _Compare(),
00449                _Sequence&& __s = _Sequence())
00450     : c(std::move(__s)), comp(__x)
00451         {
00452       __glibcxx_requires_valid_range(__first, __last);
00453       c.insert(c.end(), __first, __last);
00454       std::make_heap(c.begin(), c.end(), comp);
00455     }
00456 #endif
00457 
00458       /**
00459        *  Returns true if the %queue is empty.
00460        */
00461       bool
00462       empty() const
00463       { return c.empty(); }
00464 
00465       /**  Returns the number of elements in the %queue.  */
00466       size_type
00467       size() const
00468       { return c.size(); }
00469 
00470       /**
00471        *  Returns a read-only (constant) reference to the data at the first
00472        *  element of the %queue.
00473        */
00474       const_reference
00475       top() const
00476       {
00477     __glibcxx_requires_nonempty();
00478     return c.front();
00479       }
00480 
00481       /**
00482        *  @brief  Add data to the %queue.
00483        *  @param  __x  Data to be added.
00484        *
00485        *  This is a typical %queue operation.
00486        *  The time complexity of the operation depends on the underlying
00487        *  sequence.
00488        */
00489       void
00490       push(const value_type& __x)
00491       {
00492     c.push_back(__x);
00493     std::push_heap(c.begin(), c.end(), comp);
00494       }
00495 
00496 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00497       void
00498       push(value_type&& __x)
00499       {
00500     c.push_back(std::move(__x));
00501     std::push_heap(c.begin(), c.end(), comp);
00502       }
00503 
00504       template<typename... _Args>
00505         void
00506         emplace(_Args&&... __args)
00507     {
00508       c.emplace_back(std::forward<_Args>(__args)...);
00509       std::push_heap(c.begin(), c.end(), comp);
00510     }
00511 #endif
00512 
00513       /**
00514        *  @brief  Removes first element.
00515        *
00516        *  This is a typical %queue operation.  It shrinks the %queue
00517        *  by one.  The time complexity of the operation depends on the
00518        *  underlying sequence.
00519        *
00520        *  Note that no data is returned, and if the first element's
00521        *  data is needed, it should be retrieved before pop() is
00522        *  called.
00523        */
00524       void
00525       pop()
00526       {
00527     __glibcxx_requires_nonempty();
00528     std::pop_heap(c.begin(), c.end(), comp);
00529     c.pop_back();
00530       }
00531 
00532 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00533       void
00534       swap(priority_queue& __pq)
00535       noexcept(noexcept(swap(c, __pq.c)) && noexcept(swap(comp, __pq.comp)))
00536       {
00537     using std::swap;
00538     swap(c, __pq.c);
00539     swap(comp, __pq.comp);
00540       }
00541 #endif
00542     };
00543 
00544   // No equality/comparison operators are provided for priority_queue.
00545 
00546 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00547   template<typename _Tp, typename _Sequence, typename _Compare>
00548     inline void
00549     swap(priority_queue<_Tp, _Sequence, _Compare>& __x,
00550      priority_queue<_Tp, _Sequence, _Compare>& __y)
00551     noexcept(noexcept(__x.swap(__y)))
00552     { __x.swap(__y); }
00553 
00554   template<typename _Tp, typename _Sequence, typename _Compare,
00555        typename _Alloc>
00556     struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
00557     : public uses_allocator<_Sequence, _Alloc>::type { };
00558 #endif
00559 
00560 _GLIBCXX_END_NAMESPACE_VERSION
00561 } // namespace
00562 
00563 #endif /* _STL_QUEUE_H */