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