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