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