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