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