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