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