stl_queue.h

Go to the documentation of this file.
00001 // Queue implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001 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 00061 #ifndef __GLIBCPP_INTERNAL_QUEUE_H 00062 #define __GLIBCPP_INTERNAL_QUEUE_H 00063 00064 #include <bits/concept_check.h> 00065 00066 namespace std 00067 { 00068 00069 // Forward declarations of operators < and ==, needed for friend declaration. 00070 00071 template <class _Tp, 00072 class _Sequence = deque<_Tp> > 00073 class queue; 00074 00075 template <class _Tp, class _Seq> 00076 inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); 00077 00078 template <class _Tp, class _Seq> 00079 inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); 00080 00081 00082 template <class _Tp, class _Sequence> 00083 class queue 00084 { 00085 // concept requirements 00086 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00087 __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept) 00088 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept) 00089 typedef typename _Sequence::value_type _Sequence_value_type; 00090 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept); 00091 00092 template <class _Tp1, class _Seq1> 00093 friend bool operator== (const queue<_Tp1, _Seq1>&, 00094 const queue<_Tp1, _Seq1>&); 00095 template <class _Tp1, class _Seq1> 00096 friend bool operator< (const queue<_Tp1, _Seq1>&, 00097 const queue<_Tp1, _Seq1>&); 00098 public: 00099 typedef typename _Sequence::value_type value_type; 00100 typedef typename _Sequence::size_type size_type; 00101 typedef _Sequence container_type; 00102 00103 typedef typename _Sequence::reference reference; 00104 typedef typename _Sequence::const_reference const_reference; 00105 protected: 00106 _Sequence c; 00107 public: 00108 explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {} 00109 00110 bool empty() const { return c.empty(); } 00111 size_type size() const { return c.size(); } 00112 reference front() { return c.front(); } 00113 const_reference front() const { return c.front(); } 00114 reference back() { return c.back(); } 00115 const_reference back() const { return c.back(); } 00116 void push(const value_type& __x) { c.push_back(__x); } 00117 void pop() { c.pop_front(); } 00118 }; 00119 00120 template <class _Tp, class _Sequence> 00121 bool 00122 operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 00123 { 00124 return __x.c == __y.c; 00125 } 00126 00127 template <class _Tp, class _Sequence> 00128 bool 00129 operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 00130 { 00131 return __x.c < __y.c; 00132 } 00133 00134 template <class _Tp, class _Sequence> 00135 bool 00136 operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 00137 { 00138 return !(__x == __y); 00139 } 00140 00141 template <class _Tp, class _Sequence> 00142 bool 00143 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 00144 { 00145 return __y < __x; 00146 } 00147 00148 template <class _Tp, class _Sequence> 00149 bool 00150 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 00151 { 00152 return !(__y < __x); 00153 } 00154 00155 template <class _Tp, class _Sequence> 00156 bool 00157 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 00158 { 00159 return !(__x < __y); 00160 } 00161 00162 template <class _Tp, 00163 class _Sequence = vector<_Tp>, 00164 class _Compare = less<typename _Sequence::value_type> > 00165 class priority_queue 00166 { 00167 // concept requirements 00168 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 00169 __glibcpp_class_requires(_Sequence, _SequenceConcept) 00170 __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept) 00171 typedef typename _Sequence::value_type _Sequence_value_type; 00172 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept); 00173 __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept); 00174 00175 public: 00176 typedef typename _Sequence::value_type value_type; 00177 typedef typename _Sequence::size_type size_type; 00178 typedef _Sequence container_type; 00179 00180 typedef typename _Sequence::reference reference; 00181 typedef typename _Sequence::const_reference const_reference; 00182 protected: 00183 _Sequence c; 00184 _Compare comp; 00185 public: 00186 explicit priority_queue(const _Compare& __x = _Compare(), 00187 const _Sequence& __s = _Sequence()) 00188 : c(__s), comp(__x) 00189 { make_heap(c.begin(), c.end(), comp); } 00190 00191 template <class _InputIterator> 00192 priority_queue(_InputIterator __first, _InputIterator __last, 00193 const _Compare& __x = _Compare(), 00194 const _Sequence& __s = _Sequence()) 00195 : c(__s), comp(__x) 00196 { 00197 c.insert(c.end(), __first, __last); 00198 make_heap(c.begin(), c.end(), comp); 00199 } 00200 00201 bool empty() const { return c.empty(); } 00202 size_type size() const { return c.size(); } 00203 const_reference top() const { return c.front(); } 00204 00205 void 00206 push(const value_type& __x) 00207 { 00208 try 00209 { 00210 c.push_back(__x); 00211 push_heap(c.begin(), c.end(), comp); 00212 } 00213 catch(...) 00214 { 00215 c.clear(); 00216 __throw_exception_again; 00217 } 00218 } 00219 00220 void 00221 pop() 00222 { 00223 try 00224 { 00225 pop_heap(c.begin(), c.end(), comp); 00226 c.pop_back(); 00227 } 00228 catch(...) 00229 { 00230 c.clear(); 00231 __throw_exception_again; 00232 } 00233 } 00234 }; 00235 00236 // no equality is provided 00237 00238 } // namespace std 00239 00240 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */ 00241 00242 // Local Variables: 00243 // mode:C++ 00244 // End:

Generated on Wed Sep 29 13:54:52 2004 for libstdc++-v3 Source by doxygen 1.3.7