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 { 00247 using std::swap; 00248 swap(c, __q.c); 00249 } 00250 #endif 00251 }; 00252 00253 /** 00254 * @brief Queue equality comparison. 00255 * @param x A %queue. 00256 * @param y A %queue of the same type as @a x. 00257 * @return True iff the size and elements of the queues are equal. 00258 * 00259 * This is an equivalence relation. Complexity and semantics depend on the 00260 * underlying sequence type, but the expected rules are: this relation is 00261 * linear in the size of the sequences, and queues are considered equivalent 00262 * if their sequences compare equal. 00263 */ 00264 template<typename _Tp, typename _Seq> 00265 inline bool 00266 operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00267 { return __x.c == __y.c; } 00268 00269 /** 00270 * @brief Queue ordering relation. 00271 * @param x A %queue. 00272 * @param y A %queue of the same type as @a x. 00273 * @return True iff @a x is lexicographically less than @a y. 00274 * 00275 * This is an total ordering relation. Complexity and semantics 00276 * depend on the underlying sequence type, but the expected rules 00277 * are: this relation is linear in the size of the sequences, the 00278 * elements must be comparable with @c <, and 00279 * std::lexicographical_compare() is usually used to make the 00280 * determination. 00281 */ 00282 template<typename _Tp, typename _Seq> 00283 inline bool 00284 operator<(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00285 { return __x.c < __y.c; } 00286 00287 /// Based on operator== 00288 template<typename _Tp, typename _Seq> 00289 inline bool 00290 operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00291 { return !(__x == __y); } 00292 00293 /// Based on operator< 00294 template<typename _Tp, typename _Seq> 00295 inline bool 00296 operator>(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00297 { return __y < __x; } 00298 00299 /// Based on operator< 00300 template<typename _Tp, typename _Seq> 00301 inline bool 00302 operator<=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00303 { return !(__y < __x); } 00304 00305 /// Based on operator< 00306 template<typename _Tp, typename _Seq> 00307 inline bool 00308 operator>=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y) 00309 { return !(__x < __y); } 00310 00311 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00312 template<typename _Tp, typename _Seq> 00313 inline void 00314 swap(queue<_Tp, _Seq>& __x, queue<_Tp, _Seq>& __y) 00315 { __x.swap(__y); } 00316 00317 template<typename _Tp, typename _Seq, typename _Alloc> 00318 struct uses_allocator<queue<_Tp, _Seq>, _Alloc> 00319 : public uses_allocator<_Seq, _Alloc>::type { }; 00320 #endif 00321 00322 /** 00323 * @brief A standard container automatically sorting its contents. 00324 * 00325 * @ingroup sequences 00326 * 00327 * This is not a true container, but an @e adaptor. It holds 00328 * another container, and provides a wrapper interface to that 00329 * container. The wrapper is what enforces priority-based sorting 00330 * and %queue behavior. Very few of the standard container/sequence 00331 * interface requirements are met (e.g., iterators). 00332 * 00333 * The second template parameter defines the type of the underlying 00334 * sequence/container. It defaults to std::vector, but it can be 00335 * any type that supports @c front(), @c push_back, @c pop_back, 00336 * and random-access iterators, such as std::deque or an 00337 * appropriate user-defined type. 00338 * 00339 * The third template parameter supplies the means of making 00340 * priority comparisons. It defaults to @c less<value_type> but 00341 * can be anything defining a strict weak ordering. 00342 * 00343 * Members not found in @a normal containers are @c container_type, 00344 * which is a typedef for the second Sequence parameter, and @c 00345 * push, @c pop, and @c top, which are standard %queue operations. 00346 * 00347 * @note No equality/comparison operators are provided for 00348 * %priority_queue. 00349 * 00350 * @note Sorting of the elements takes place as they are added to, 00351 * and removed from, the %priority_queue using the 00352 * %priority_queue's member functions. If you access the elements 00353 * by other means, and change their data such that the sorting 00354 * order would be different, the %priority_queue will not re-sort 00355 * the elements for you. (How could it know to do so?) 00356 */ 00357 template<typename _Tp, typename _Sequence = vector<_Tp>, 00358 typename _Compare = less<typename _Sequence::value_type> > 00359 class priority_queue 00360 { 00361 // concept requirements 00362 typedef typename _Sequence::value_type _Sequence_value_type; 00363 __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 00364 __glibcxx_class_requires(_Sequence, _SequenceConcept) 00365 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept) 00366 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 00367 __glibcxx_class_requires4(_Compare, bool, _Tp, _Tp, 00368 _BinaryFunctionConcept) 00369 00370 public: 00371 typedef typename _Sequence::value_type value_type; 00372 typedef typename _Sequence::reference reference; 00373 typedef typename _Sequence::const_reference const_reference; 00374 typedef typename _Sequence::size_type size_type; 00375 typedef _Sequence container_type; 00376 00377 protected: 00378 // See queue::c for notes on these names. 00379 _Sequence c; 00380 _Compare comp; 00381 00382 public: 00383 /** 00384 * @brief Default constructor creates no elements. 00385 */ 00386 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00387 explicit 00388 priority_queue(const _Compare& __x = _Compare(), 00389 const _Sequence& __s = _Sequence()) 00390 : c(__s), comp(__x) 00391 { std::make_heap(c.begin(), c.end(), comp); } 00392 #else 00393 explicit 00394 priority_queue(const _Compare& __x, 00395 const _Sequence& __s) 00396 : c(__s), comp(__x) 00397 { std::make_heap(c.begin(), c.end(), comp); } 00398 00399 explicit 00400 priority_queue(const _Compare& __x = _Compare(), 00401 _Sequence&& __s = _Sequence()) 00402 : c(std::move(__s)), comp(__x) 00403 { std::make_heap(c.begin(), c.end(), comp); } 00404 #endif 00405 00406 /** 00407 * @brief Builds a %queue from a range. 00408 * @param first An input iterator. 00409 * @param last An input iterator. 00410 * @param x A comparison functor describing a strict weak ordering. 00411 * @param s An initial sequence with which to start. 00412 * 00413 * Begins by copying @a s, inserting a copy of the elements 00414 * from @a [first,last) into the copy of @a s, then ordering 00415 * the copy according to @a x. 00416 * 00417 * For more information on function objects, see the 00418 * documentation on @link functors functor base 00419 * classes@endlink. 00420 */ 00421 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00422 template<typename _InputIterator> 00423 priority_queue(_InputIterator __first, _InputIterator __last, 00424 const _Compare& __x = _Compare(), 00425 const _Sequence& __s = _Sequence()) 00426 : c(__s), comp(__x) 00427 { 00428 __glibcxx_requires_valid_range(__first, __last); 00429 c.insert(c.end(), __first, __last); 00430 std::make_heap(c.begin(), c.end(), comp); 00431 } 00432 #else 00433 template<typename _InputIterator> 00434 priority_queue(_InputIterator __first, _InputIterator __last, 00435 const _Compare& __x, 00436 const _Sequence& __s) 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 00444 template<typename _InputIterator> 00445 priority_queue(_InputIterator __first, _InputIterator __last, 00446 const _Compare& __x = _Compare(), 00447 _Sequence&& __s = _Sequence()) 00448 : c(std::move(__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 #endif 00455 00456 /** 00457 * Returns true if the %queue is empty. 00458 */ 00459 bool 00460 empty() const 00461 { return c.empty(); } 00462 00463 /** Returns the number of elements in the %queue. */ 00464 size_type 00465 size() const 00466 { return c.size(); } 00467 00468 /** 00469 * Returns a read-only (constant) reference to the data at the first 00470 * element of the %queue. 00471 */ 00472 const_reference 00473 top() const 00474 { 00475 __glibcxx_requires_nonempty(); 00476 return c.front(); 00477 } 00478 00479 /** 00480 * @brief Add data to the %queue. 00481 * @param x Data to be added. 00482 * 00483 * This is a typical %queue operation. 00484 * The time complexity of the operation depends on the underlying 00485 * sequence. 00486 */ 00487 void 00488 push(const value_type& __x) 00489 { 00490 c.push_back(__x); 00491 std::push_heap(c.begin(), c.end(), comp); 00492 } 00493 00494 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00495 void 00496 push(value_type&& __x) 00497 { 00498 c.push_back(std::move(__x)); 00499 std::push_heap(c.begin(), c.end(), comp); 00500 } 00501 00502 template<typename... _Args> 00503 void 00504 emplace(_Args&&... __args) 00505 { 00506 c.emplace_back(std::forward<_Args>(__args)...); 00507 std::push_heap(c.begin(), c.end(), comp); 00508 } 00509 #endif 00510 00511 /** 00512 * @brief Removes first element. 00513 * 00514 * This is a typical %queue operation. It shrinks the %queue 00515 * by one. The time complexity of the operation depends on the 00516 * underlying sequence. 00517 * 00518 * Note that no data is returned, and if the first element's 00519 * data is needed, it should be retrieved before pop() is 00520 * called. 00521 */ 00522 void 00523 pop() 00524 { 00525 __glibcxx_requires_nonempty(); 00526 std::pop_heap(c.begin(), c.end(), comp); 00527 c.pop_back(); 00528 } 00529 00530 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00531 void 00532 swap(priority_queue& __pq) 00533 { 00534 using std::swap; 00535 swap(c, __pq.c); 00536 swap(comp, __pq.comp); 00537 } 00538 #endif 00539 }; 00540 00541 // No equality/comparison operators are provided for priority_queue. 00542 00543 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00544 template<typename _Tp, typename _Sequence, typename _Compare> 00545 inline void 00546 swap(priority_queue<_Tp, _Sequence, _Compare>& __x, 00547 priority_queue<_Tp, _Sequence, _Compare>& __y) 00548 { __x.swap(__y); } 00549 00550 template<typename _Tp, typename _Sequence, typename _Compare, 00551 typename _Alloc> 00552 struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc> 00553 : public uses_allocator<_Sequence, _Alloc>::type { }; 00554 #endif 00555 00556 _GLIBCXX_END_NAMESPACE_VERSION 00557 } // namespace 00558 00559 #endif /* _STL_QUEUE_H */