# stl_queue.h

Go to the documentation of this file.

    00001 // Queue implementation -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /*
    00031  *
    00032  * Copyright (c) 1994
    00033  * Hewlett-Packard Company
    00034  *
    00035  * Permission to use, copy, modify, distribute and sell this software
    00036  * and its documentation for any purpose is hereby granted without fee,
    00037  * provided that the above copyright notice appear in all copies and
    00038  * that both that copyright notice and this permission notice appear
    00039  * in supporting documentation.  Hewlett-Packard Company makes no
    00040  * representations about the suitability of this software for any
    00041  * purpose.  It is provided "as is" without express or implied warranty.
    00042  *
    00043  *
    00044  * Copyright (c) 1996,1997
    00045  * Silicon Graphics Computer Systems, Inc.
    00046  *
    00047  * Permission to use, copy, modify, distribute and sell this software
    00048  * and its documentation for any purpose is hereby granted without fee,
    00049  * provided that the above copyright notice appear in all copies and
    00050  * that both that copyright notice and this permission notice appear
    00051  * in supporting documentation.  Silicon Graphics makes no
    00052  * representations about the suitability of this software for any
    00053  * purpose.  It is provided "as is" without express or implied warranty.
    00054  */
    00055
    00056 /** @file stl_queue.h
    00057  *  This is an internal header file, included by other library headers.
    00058  *  You should not attempt to use it directly.
    00059  */
    00060
    00061 #ifndef _QUEUE_H
    00062 #define _QUEUE_H 1
    00063
    00064 #include <bits/concept_check.h>
    00065 #include <debug/debug.h>
    00066
    00067 namespace std
    00068 {
    00069   // Forward declarations of operators < and ==, needed for friend declaration.
    00070   template<typename _Tp, typename _Sequence = deque<_Tp> >
    00071     class queue;
    00072
    00073   template<typename _Tp, typename _Seq>
    00074     inline bool
    00075     operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
    00076
    00077   template<typename _Tp, typename _Seq>
    00078     inline bool
    00079     operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
    00080
    00081   /**
    00082    *  @brief  A standard container giving FIFO behavior.
    00083    *
    00084    *  @ingroup Containers
    00085    *  @ingroup Sequences
    00086    *
    00087    *  Meets many of the requirements of a
    00088    *  <a href="tables.html#65">container</a>,
    00089    *  but does not define anything to do with iterators.  Very few of the
    00090    *  other standard container interfaces are defined.
    00091    *
    00092    *  This is not a true container, but an @e adaptor.  It holds another
    00093    *  container, and provides a wrapper interface to that container.  The
    00094    *  wrapper is what enforces strict first-in-first-out %queue behavior.
    00095    *
    00096    *  The second template parameter defines the type of the underlying
    00097    *  sequence/container.  It defaults to std::deque, but it can be any type
    00098    *  that supports @c front, @c back, @c push_back, and @c pop_front,
    00099    *  such as std::list or an appropriate user-defined type.
    00100    *
    00101    *  Members not found in "normal" containers are @c container_type,
    00102    *  which is a typedef for the second Sequence parameter, and @c push and
    00103    *  @c pop, which are standard %queue/FIFO operations.
    00104   */
    00105   template<typename _Tp, typename _Sequence>
    00106     class queue
    00107     {
    00108       // concept requirements
    00109       typedef typename _Sequence::value_type _Sequence_value_type;
    00110       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
    00111       __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
    00112       __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
    00113       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
    00114
    00115       template<typename _Tp1, typename _Seq1>
    00116         friend bool
    00117         operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
    00118
    00119       template<typename _Tp1, typename _Seq1>
    00120         friend bool
    00121         operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
    00122
    00123     public:
    00124       typedef typename _Sequence::value_type                value_type;
    00125       typedef typename _Sequence::reference                 reference;
    00126       typedef typename _Sequence::const_reference           const_reference;
    00127       typedef typename _Sequence::size_type                 size_type;
    00128       typedef          _Sequence                            container_type;
    00129
    00130     protected:
    00131       /**
    00132        *  'c' is the underlying container.  Maintainers wondering why
    00133        *  this isn't uglified as per style guidelines should note that
    00134        *  this name is specified in the standard, [23.2.3.1].  (Why?
    00135        *  Presumably for the same reason that it's protected instead
    00136        *  of private: to allow derivation.  But none of the other
    00137        *  containers allow for derivation.  Odd.)
    00138        */
    00139       _Sequence c;
    00140
    00141     public:
    00142       /**
    00143        *  @brief  Default constructor creates no elements.
    00144        */
    00145       explicit
    00146       queue(const _Sequence& __c = _Sequence()) : c(__c) {}
    00147
    00148       /**
    00149        *  Returns true if the %queue is empty.
    00150        */
    00151       bool
    00152       empty() const
    00153       { return c.empty(); }
    00154
    00155       /**  Returns the number of elements in the %queue.  */
    00156       size_type
    00157       size() const
    00158       { return c.size(); }
    00159
    00160       /**
    00161        *  Returns a read/write reference to the data at the first
    00162        *  element of the %queue.
    00163        */
    00164       reference
    00165       front()
    00166       {
    00167     __glibcxx_requires_nonempty();
    00168     return c.front();
    00169       }
    00170
    00171       /**
    00172        *  Returns a read-only (constant) reference to the data at the first
    00173        *  element of the %queue.
    00174        */
    00175       const_reference
    00176       front() const
    00177       {
    00178     __glibcxx_requires_nonempty();
    00179     return c.front();
    00180       }
    00181
    00182       /**
    00183        *  Returns a read/write reference to the data at the last
    00184        *  element of the %queue.
    00185        */
    00186       reference
    00187       back()
    00188       {
    00189     __glibcxx_requires_nonempty();
    00190     return c.back();
    00191       }
    00192
    00193       /**
    00194        *  Returns a read-only (constant) reference to the data at the last
    00195        *  element of the %queue.
    00196        */
    00197       const_reference
    00198       back() const
    00199       {
    00200     __glibcxx_requires_nonempty();
    00201     return c.back();
    00202       }
    00203
    00204       /**
    00205        *  @brief  Add data to the end of the %queue.
    00206        *  @param  x  Data to be added.
    00207        *
    00208        *  This is a typical %queue operation.  The function creates an
    00209        *  element at the end of the %queue and assigns the given data
    00210        *  to it.  The time complexity of the operation depends on the
    00211        *  underlying sequence.
    00212        */
    00213       void
    00214       push(const value_type& __x)
    00215       { c.push_back(__x); }
    00216
    00217       /**
    00218        *  @brief  Removes first element.
    00219        *
    00220        *  This is a typical %queue operation.  It shrinks the %queue by one.
    00221        *  The time complexity of the operation depends on the underlying
    00222        *  sequence.
    00223        *
    00224        *  Note that no data is returned, and if the first element's
    00225        *  data is needed, it should be retrieved before pop() is
    00226        *  called.
    00227        */
    00228       void
    00229       pop()
    00230       {
    00231     __glibcxx_requires_nonempty();
    00232     c.pop_front();
    00233       }
    00234     };
    00235
    00236
    00237   /**
    00238    *  @brief  Queue equality comparison.
    00239    *  @param  x  A %queue.
    00240    *  @param  y  A %queue of the same type as @a x.
    00241    *  @return  True iff the size and elements of the queues are equal.
    00242    *
    00243    *  This is an equivalence relation.  Complexity and semantics depend on the
    00244    *  underlying sequence type, but the expected rules are:  this relation is
    00245    *  linear in the size of the sequences, and queues are considered equivalent
    00246    *  if their sequences compare equal.
    00247   */
    00248   template<typename _Tp, typename _Sequence>
    00249     inline bool
    00250     operator==(const queue<_Tp,_Sequence>& __x,
    00251            const queue<_Tp,_Sequence>& __y)
    00252     { return __x.c == __y.c; }
    00253
    00254   /**
    00255    *  @brief  Queue ordering relation.
    00256    *  @param  x  A %queue.
    00257    *  @param  y  A %queue of the same type as @a x.
    00258    *  @return  True iff @a x is lexicographically less than @a y.
    00259    *
    00260    *  This is an total ordering relation.  Complexity and semantics
    00261    *  depend on the underlying sequence type, but the expected rules
    00262    *  are: this relation is linear in the size of the sequences, the
    00263    *  elements must be comparable with @c <, and
    00264    *  std::lexicographical_compare() is usually used to make the
    00265    *  determination.
    00266   */
    00267   template<typename _Tp, typename _Sequence>
    00268     inline bool
    00269     operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
    00270     { return __x.c < __y.c; }
    00271
    00272   /// Based on operator==
    00273   template<typename _Tp, typename _Sequence>
    00274     inline bool
    00275     operator!=(const queue<_Tp,_Sequence>& __x,
    00276            const queue<_Tp,_Sequence>& __y)
    00277     { return !(__x == __y); }
    00278
    00279   /// Based on operator<
    00280   template<typename _Tp, typename _Sequence>
    00281     inline bool
    00282     operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
    00283     { return __y < __x; }
    00284
    00285   /// Based on operator<
    00286   template<typename _Tp, typename _Sequence>
    00287     inline bool
    00288     operator<=(const queue<_Tp,_Sequence>& __x,
    00289            const queue<_Tp,_Sequence>& __y)
    00290     { return !(__y < __x); }
    00291
    00292   /// Based on operator<
    00293   template<typename _Tp, typename _Sequence>
    00294     inline bool
    00295     operator>=(const queue<_Tp,_Sequence>& __x,
    00296            const queue<_Tp,_Sequence>& __y)
    00297     { return !(__x < __y); }
    00298
    00299   /**
    00300    *  @brief  A standard container automatically sorting its contents.
    00301    *
    00302    *  @ingroup Containers
    00303    *  @ingroup Sequences
    00304    *
    00305    *  This is not a true container, but an @e adaptor.  It holds
    00306    *  another container, and provides a wrapper interface to that
    00307    *  container.  The wrapper is what enforces sorting and
    00308    *  first-in-first-out %queue behavior.  Very few of the standard
    00309    *  container/sequence interface requirements are met (e.g.,
    00310    *  iterators).
    00311    *
    00312    *  The second template parameter defines the type of the underlying
    00313    *  sequence/container.  It defaults to std::vector, but it can be
    00314    *  any type that supports @c front(), @c push_back, @c pop_back,
    00315    *  and random-access iterators, such as std::deque or an
    00316    *  appropriate user-defined type.
    00317    *
    00318    *  The third template parameter supplies the means of making
    00319    *  priority comparisons.  It defaults to @c less<value_type> but
    00320    *  can be anything defining a strict weak ordering.
    00321    *
    00322    *  Members not found in "normal" containers are @c container_type,
    00323    *  which is a typedef for the second Sequence parameter, and @c
    00324    *  push, @c pop, and @c top, which are standard %queue/FIFO
    00325    *  operations.
    00326    *
    00327    *  @note No equality/comparison operators are provided for
    00328    *  %priority_queue.
    00329    *
    00330    *  @note Sorting of the elements takes place as they are added to,
    00331    *  and removed from, the %priority_queue using the
    00332    *  %priority_queue's member functions.  If you access the elements
    00333    *  by other means, and change their data such that the sorting
    00334    *  order would be different, the %priority_queue will not re-sort
    00335    *  the elements for you.  (How could it know to do so?)
    00336   */
    00337   template<typename _Tp, typename _Sequence = vector<_Tp>,
    00338        typename _Compare  = less<typename _Sequence::value_type> >
    00339     class priority_queue
    00340     {
    00341       // concept requirements
    00342       typedef typename _Sequence::value_type _Sequence_value_type;
    00343       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
    00344       __glibcxx_class_requires(_Sequence, _SequenceConcept)
    00345       __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
    00346       __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
    00347       __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept)
    00348
    00349     public:
    00350       typedef typename _Sequence::value_type                value_type;
    00351       typedef typename _Sequence::reference                 reference;
    00352       typedef typename _Sequence::const_reference           const_reference;
    00353       typedef typename _Sequence::size_type                 size_type;
    00354       typedef          _Sequence                            container_type;
    00355
    00356     protected:
    00357       //  See queue::c for notes on these names.
    00358       _Sequence  c;
    00359       _Compare   comp;
    00360
    00361     public:
    00362       /**
    00363        *  @brief  Default constructor creates no elements.
    00364        */
    00365       explicit
    00366       priority_queue(const _Compare& __x = _Compare(),
    00367              const _Sequence& __s = _Sequence())
    00368       : c(__s), comp(__x)
    00369       { std::make_heap(c.begin(), c.end(), comp); }
    00370
    00371       /**
    00372        *  @brief  Builds a %queue from a range.
    00373        *  @param  first  An input iterator.
    00374        *  @param  last  An input iterator.
    00375        *  @param  x  A comparison functor describing a strict weak ordering.
    00376        *  @param  s  An initial sequence with which to start.
    00377        *
    00378        *  Begins by copying @a s, inserting a copy of the elements
    00379        *  from @a [first,last) into the copy of @a s, then ordering
    00380        *  the copy according to @a x.
    00381        *
    00382        *  For more information on function objects, see the
    00383        *  documentation on @link s20_3_1_base functor base
    00384        *  classes@endlink.
    00385        */
    00386       template<typename _InputIterator>
    00387         priority_queue(_InputIterator __first, _InputIterator __last,
    00388                const _Compare& __x = _Compare(),
    00389                const _Sequence& __s = _Sequence())
    00390     : c(__s), comp(__x)
    00391         {
    00392       __glibcxx_requires_valid_range(__first, __last);
    00393       c.insert(c.end(), __first, __last);
    00394       std::make_heap(c.begin(), c.end(), comp);
    00395     }
    00396
    00397       /**
    00398        *  Returns true if the %queue is empty.
    00399        */
    00400       bool
    00401       empty() const { return c.empty(); }
    00402
    00403       /**  Returns the number of elements in the %queue.  */
    00404       size_type
    00405       size() const { return c.size(); }
    00406
    00407       /**
    00408        *  Returns a read-only (constant) reference to the data at the first
    00409        *  element of the %queue.
    00410        */
    00411       const_reference
    00412       top() const
    00413       {
    00414     __glibcxx_requires_nonempty();
    00415     return c.front();
    00416       }
    00417
    00418       /**
    00419        *  @brief  Add data to the %queue.
    00420        *  @param  x  Data to be added.
    00421        *
    00422        *  This is a typical %queue operation.
    00423        *  The time complexity of the operation depends on the underlying
    00424        *  sequence.
    00425        */
    00426       void
    00427       push(const value_type& __x)
    00428       {
    00429     try
    00430         {
    00431           c.push_back(__x);
    00432           std::push_heap(c.begin(), c.end(), comp);
    00433         }
    00434     catch(...)
    00435         {
    00436           c.clear();
    00437           __throw_exception_again;
    00438         }
    00439       }
    00440
    00441       /**
    00442        *  @brief  Removes first element.
    00443        *
    00444        *  This is a typical %queue operation.  It shrinks the %queue
    00445        *  by one.  The time complexity of the operation depends on the
    00446        *  underlying sequence.
    00447        *
    00448        *  Note that no data is returned, and if the first element's
    00449        *  data is needed, it should be retrieved before pop() is
    00450        *  called.
    00451        */
    00452       void
    00453       pop()
    00454       {
    00455     __glibcxx_requires_nonempty();
    00456     try
    00457         {
    00458           std::pop_heap(c.begin(), c.end(), comp);
    00459           c.pop_back();
    00460         }
    00461     catch(...)
    00462         {
    00463           c.clear();
    00464           __throw_exception_again;
    00465         }
    00466       }
    00467     };
    00468
    00469   // No equality/comparison operators are provided for priority_queue.
    00470 } // namespace std
    00471
    00472 #endif /* _QUEUE_H */