libstdc++
|
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 */