queue 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742
  1. // -*- C++ -*-
  2. //===--------------------------- queue ------------------------------------===//
  3. //
  4. // The LLVM Compiler Infrastructure
  5. //
  6. // This file is dual licensed under the MIT and the University of Illinois Open
  7. // Source Licenses. See LICENSE.TXT for details.
  8. //
  9. //===----------------------------------------------------------------------===//
  10. #ifndef _LIBCPP_QUEUE
  11. #define _LIBCPP_QUEUE
  12. /*
  13. queue synopsis
  14. namespace std
  15. {
  16. template <class T, class Container = deque<T>>
  17. class queue
  18. {
  19. public:
  20. typedef Container container_type;
  21. typedef typename container_type::value_type value_type;
  22. typedef typename container_type::reference reference;
  23. typedef typename container_type::const_reference const_reference;
  24. typedef typename container_type::size_type size_type;
  25. protected:
  26. container_type c;
  27. public:
  28. queue() = default;
  29. ~queue() = default;
  30. queue(const queue& q) = default;
  31. queue(queue&& q) = default;
  32. queue& operator=(const queue& q) = default;
  33. queue& operator=(queue&& q) = default;
  34. explicit queue(const container_type& c);
  35. explicit queue(container_type&& c)
  36. template <class Alloc>
  37. explicit queue(const Alloc& a);
  38. template <class Alloc>
  39. queue(const container_type& c, const Alloc& a);
  40. template <class Alloc>
  41. queue(container_type&& c, const Alloc& a);
  42. template <class Alloc>
  43. queue(const queue& q, const Alloc& a);
  44. template <class Alloc>
  45. queue(queue&& q, const Alloc& a);
  46. bool empty() const;
  47. size_type size() const;
  48. reference front();
  49. const_reference front() const;
  50. reference back();
  51. const_reference back() const;
  52. void push(const value_type& v);
  53. void push(value_type&& v);
  54. template <class... Args> void emplace(Args&&... args);
  55. void pop();
  56. void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
  57. };
  58. template <class T, class Container>
  59. bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
  60. template <class T, class Container>
  61. bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
  62. template <class T, class Container>
  63. bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
  64. template <class T, class Container>
  65. bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
  66. template <class T, class Container>
  67. bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
  68. template <class T, class Container>
  69. bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
  70. template <class T, class Container>
  71. void swap(queue<T, Container>& x, queue<T, Container>& y)
  72. noexcept(noexcept(x.swap(y)));
  73. template <class T, class Container = vector<T>,
  74. class Compare = less<typename Container::value_type>>
  75. class priority_queue
  76. {
  77. public:
  78. typedef Container container_type;
  79. typedef typename container_type::value_type value_type;
  80. typedef typename container_type::reference reference;
  81. typedef typename container_type::const_reference const_reference;
  82. typedef typename container_type::size_type size_type;
  83. protected:
  84. container_type c;
  85. Compare comp;
  86. public:
  87. priority_queue() = default;
  88. ~priority_queue() = default;
  89. priority_queue(const priority_queue& q) = default;
  90. priority_queue(priority_queue&& q) = default;
  91. priority_queue& operator=(const priority_queue& q) = default;
  92. priority_queue& operator=(priority_queue&& q) = default;
  93. explicit priority_queue(const Compare& comp);
  94. priority_queue(const Compare& comp, const container_type& c);
  95. explicit priority_queue(const Compare& comp, container_type&& c);
  96. template <class InputIterator>
  97. priority_queue(InputIterator first, InputIterator last,
  98. const Compare& comp = Compare());
  99. template <class InputIterator>
  100. priority_queue(InputIterator first, InputIterator last,
  101. const Compare& comp, const container_type& c);
  102. template <class InputIterator>
  103. priority_queue(InputIterator first, InputIterator last,
  104. const Compare& comp, container_type&& c);
  105. template <class Alloc>
  106. explicit priority_queue(const Alloc& a);
  107. template <class Alloc>
  108. priority_queue(const Compare& comp, const Alloc& a);
  109. template <class Alloc>
  110. priority_queue(const Compare& comp, const container_type& c,
  111. const Alloc& a);
  112. template <class Alloc>
  113. priority_queue(const Compare& comp, container_type&& c,
  114. const Alloc& a);
  115. template <class Alloc>
  116. priority_queue(const priority_queue& q, const Alloc& a);
  117. template <class Alloc>
  118. priority_queue(priority_queue&& q, const Alloc& a);
  119. bool empty() const;
  120. size_type size() const;
  121. const_reference top() const;
  122. void push(const value_type& v);
  123. void push(value_type&& v);
  124. template <class... Args> void emplace(Args&&... args);
  125. void pop();
  126. void swap(priority_queue& q)
  127. noexcept(is_nothrow_swappable_v<Container> &&
  128. is_nothrow_swappable_v<Comp>)
  129. };
  130. template <class T, class Container, class Compare>
  131. void swap(priority_queue<T, Container, Compare>& x,
  132. priority_queue<T, Container, Compare>& y)
  133. noexcept(noexcept(x.swap(y)));
  134. } // std
  135. */
  136. #include <__config>
  137. #include <deque>
  138. #include <vector>
  139. #include <functional>
  140. #include <algorithm>
  141. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  142. #pragma GCC system_header
  143. #endif
  144. _LIBCPP_BEGIN_NAMESPACE_STD
  145. template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TYPE_VIS_ONLY queue;
  146. template <class _Tp, class _Container>
  147. _LIBCPP_INLINE_VISIBILITY
  148. bool
  149. operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
  150. template <class _Tp, class _Container>
  151. _LIBCPP_INLINE_VISIBILITY
  152. bool
  153. operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y);
  154. template <class _Tp, class _Container /*= deque<_Tp>*/>
  155. class _LIBCPP_TYPE_VIS_ONLY queue
  156. {
  157. public:
  158. typedef _Container container_type;
  159. typedef typename container_type::value_type value_type;
  160. typedef typename container_type::reference reference;
  161. typedef typename container_type::const_reference const_reference;
  162. typedef typename container_type::size_type size_type;
  163. static_assert((is_same<_Tp, value_type>::value), "" );
  164. protected:
  165. container_type c;
  166. public:
  167. _LIBCPP_INLINE_VISIBILITY
  168. queue()
  169. _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
  170. : c() {}
  171. _LIBCPP_INLINE_VISIBILITY
  172. queue(const queue& __q) : c(__q.c) {}
  173. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  174. _LIBCPP_INLINE_VISIBILITY
  175. queue(queue&& __q)
  176. _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
  177. : c(_VSTD::move(__q.c)) {}
  178. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  179. _LIBCPP_INLINE_VISIBILITY
  180. queue& operator=(const queue& __q) {c = __q.c; return *this;}
  181. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  182. _LIBCPP_INLINE_VISIBILITY
  183. queue& operator=(queue&& __q)
  184. _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
  185. {c = _VSTD::move(__q.c); return *this;}
  186. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  187. _LIBCPP_INLINE_VISIBILITY
  188. explicit queue(const container_type& __c) : c(__c) {}
  189. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  190. _LIBCPP_INLINE_VISIBILITY
  191. explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
  192. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  193. template <class _Alloc>
  194. _LIBCPP_INLINE_VISIBILITY
  195. explicit queue(const _Alloc& __a,
  196. typename enable_if<uses_allocator<container_type,
  197. _Alloc>::value>::type* = 0)
  198. : c(__a) {}
  199. template <class _Alloc>
  200. _LIBCPP_INLINE_VISIBILITY
  201. queue(const queue& __q, const _Alloc& __a,
  202. typename enable_if<uses_allocator<container_type,
  203. _Alloc>::value>::type* = 0)
  204. : c(__q.c, __a) {}
  205. template <class _Alloc>
  206. _LIBCPP_INLINE_VISIBILITY
  207. queue(const container_type& __c, const _Alloc& __a,
  208. typename enable_if<uses_allocator<container_type,
  209. _Alloc>::value>::type* = 0)
  210. : c(__c, __a) {}
  211. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  212. template <class _Alloc>
  213. _LIBCPP_INLINE_VISIBILITY
  214. queue(container_type&& __c, const _Alloc& __a,
  215. typename enable_if<uses_allocator<container_type,
  216. _Alloc>::value>::type* = 0)
  217. : c(_VSTD::move(__c), __a) {}
  218. template <class _Alloc>
  219. _LIBCPP_INLINE_VISIBILITY
  220. queue(queue&& __q, const _Alloc& __a,
  221. typename enable_if<uses_allocator<container_type,
  222. _Alloc>::value>::type* = 0)
  223. : c(_VSTD::move(__q.c), __a) {}
  224. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  225. _LIBCPP_INLINE_VISIBILITY
  226. bool empty() const {return c.empty();}
  227. _LIBCPP_INLINE_VISIBILITY
  228. size_type size() const {return c.size();}
  229. _LIBCPP_INLINE_VISIBILITY
  230. reference front() {return c.front();}
  231. _LIBCPP_INLINE_VISIBILITY
  232. const_reference front() const {return c.front();}
  233. _LIBCPP_INLINE_VISIBILITY
  234. reference back() {return c.back();}
  235. _LIBCPP_INLINE_VISIBILITY
  236. const_reference back() const {return c.back();}
  237. _LIBCPP_INLINE_VISIBILITY
  238. void push(const value_type& __v) {c.push_back(__v);}
  239. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  240. _LIBCPP_INLINE_VISIBILITY
  241. void push(value_type&& __v) {c.push_back(_VSTD::move(__v));}
  242. #ifndef _LIBCPP_HAS_NO_VARIADICS
  243. template <class... _Args>
  244. _LIBCPP_INLINE_VISIBILITY
  245. void emplace(_Args&&... __args)
  246. {c.emplace_back(_VSTD::forward<_Args>(__args)...);}
  247. #endif // _LIBCPP_HAS_NO_VARIADICS
  248. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  249. _LIBCPP_INLINE_VISIBILITY
  250. void pop() {c.pop_front();}
  251. _LIBCPP_INLINE_VISIBILITY
  252. void swap(queue& __q)
  253. _NOEXCEPT_(__is_nothrow_swappable<container_type>::value)
  254. {
  255. using _VSTD::swap;
  256. swap(c, __q.c);
  257. }
  258. template <class _T1, class _C1>
  259. friend
  260. _LIBCPP_INLINE_VISIBILITY
  261. bool
  262. operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
  263. template <class _T1, class _C1>
  264. friend
  265. _LIBCPP_INLINE_VISIBILITY
  266. bool
  267. operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
  268. };
  269. template <class _Tp, class _Container>
  270. inline _LIBCPP_INLINE_VISIBILITY
  271. bool
  272. operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
  273. {
  274. return __x.c == __y.c;
  275. }
  276. template <class _Tp, class _Container>
  277. inline _LIBCPP_INLINE_VISIBILITY
  278. bool
  279. operator< (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
  280. {
  281. return __x.c < __y.c;
  282. }
  283. template <class _Tp, class _Container>
  284. inline _LIBCPP_INLINE_VISIBILITY
  285. bool
  286. operator!=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
  287. {
  288. return !(__x == __y);
  289. }
  290. template <class _Tp, class _Container>
  291. inline _LIBCPP_INLINE_VISIBILITY
  292. bool
  293. operator> (const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
  294. {
  295. return __y < __x;
  296. }
  297. template <class _Tp, class _Container>
  298. inline _LIBCPP_INLINE_VISIBILITY
  299. bool
  300. operator>=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
  301. {
  302. return !(__x < __y);
  303. }
  304. template <class _Tp, class _Container>
  305. inline _LIBCPP_INLINE_VISIBILITY
  306. bool
  307. operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
  308. {
  309. return !(__y < __x);
  310. }
  311. template <class _Tp, class _Container>
  312. inline _LIBCPP_INLINE_VISIBILITY
  313. typename enable_if<
  314. __is_swappable<_Container>::value,
  315. void
  316. >::type
  317. swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
  318. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  319. {
  320. __x.swap(__y);
  321. }
  322. template <class _Tp, class _Container, class _Alloc>
  323. struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<queue<_Tp, _Container>, _Alloc>
  324. : public uses_allocator<_Container, _Alloc>
  325. {
  326. };
  327. template <class _Tp, class _Container = vector<_Tp>,
  328. class _Compare = less<typename _Container::value_type> >
  329. class _LIBCPP_TYPE_VIS_ONLY priority_queue
  330. {
  331. public:
  332. typedef _Container container_type;
  333. typedef _Compare value_compare;
  334. typedef typename container_type::value_type value_type;
  335. typedef typename container_type::reference reference;
  336. typedef typename container_type::const_reference const_reference;
  337. typedef typename container_type::size_type size_type;
  338. static_assert((is_same<_Tp, value_type>::value), "" );
  339. protected:
  340. container_type c;
  341. value_compare comp;
  342. public:
  343. _LIBCPP_INLINE_VISIBILITY
  344. priority_queue()
  345. _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value &&
  346. is_nothrow_default_constructible<value_compare>::value)
  347. : c(), comp() {}
  348. _LIBCPP_INLINE_VISIBILITY
  349. priority_queue(const priority_queue& __q) : c(__q.c), comp(__q.comp) {}
  350. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  351. _LIBCPP_INLINE_VISIBILITY
  352. priority_queue(priority_queue&& __q)
  353. _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value &&
  354. is_nothrow_move_constructible<value_compare>::value)
  355. : c(_VSTD::move(__q.c)), comp(_VSTD::move(__q.comp)) {}
  356. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  357. _LIBCPP_INLINE_VISIBILITY
  358. priority_queue& operator=(const priority_queue& __q)
  359. {c = __q.c; comp = __q.comp; return *this;}
  360. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  361. _LIBCPP_INLINE_VISIBILITY
  362. priority_queue& operator=(priority_queue&& __q)
  363. _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value &&
  364. is_nothrow_move_assignable<value_compare>::value)
  365. {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}
  366. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  367. _LIBCPP_INLINE_VISIBILITY
  368. explicit priority_queue(const value_compare& __comp)
  369. : c(), comp(__comp) {}
  370. _LIBCPP_INLINE_VISIBILITY
  371. priority_queue(const value_compare& __comp, const container_type& __c);
  372. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  373. _LIBCPP_INLINE_VISIBILITY
  374. explicit priority_queue(const value_compare& __comp, container_type&& __c);
  375. #endif
  376. template <class _InputIter>
  377. _LIBCPP_INLINE_VISIBILITY
  378. priority_queue(_InputIter __f, _InputIter __l,
  379. const value_compare& __comp = value_compare());
  380. template <class _InputIter>
  381. _LIBCPP_INLINE_VISIBILITY
  382. priority_queue(_InputIter __f, _InputIter __l,
  383. const value_compare& __comp, const container_type& __c);
  384. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  385. template <class _InputIter>
  386. _LIBCPP_INLINE_VISIBILITY
  387. priority_queue(_InputIter __f, _InputIter __l,
  388. const value_compare& __comp, container_type&& __c);
  389. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  390. template <class _Alloc>
  391. _LIBCPP_INLINE_VISIBILITY
  392. explicit priority_queue(const _Alloc& __a,
  393. typename enable_if<uses_allocator<container_type,
  394. _Alloc>::value>::type* = 0);
  395. template <class _Alloc>
  396. _LIBCPP_INLINE_VISIBILITY
  397. priority_queue(const value_compare& __comp, const _Alloc& __a,
  398. typename enable_if<uses_allocator<container_type,
  399. _Alloc>::value>::type* = 0);
  400. template <class _Alloc>
  401. _LIBCPP_INLINE_VISIBILITY
  402. priority_queue(const value_compare& __comp, const container_type& __c,
  403. const _Alloc& __a,
  404. typename enable_if<uses_allocator<container_type,
  405. _Alloc>::value>::type* = 0);
  406. template <class _Alloc>
  407. _LIBCPP_INLINE_VISIBILITY
  408. priority_queue(const priority_queue& __q, const _Alloc& __a,
  409. typename enable_if<uses_allocator<container_type,
  410. _Alloc>::value>::type* = 0);
  411. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  412. template <class _Alloc>
  413. _LIBCPP_INLINE_VISIBILITY
  414. priority_queue(const value_compare& __comp, container_type&& __c,
  415. const _Alloc& __a,
  416. typename enable_if<uses_allocator<container_type,
  417. _Alloc>::value>::type* = 0);
  418. template <class _Alloc>
  419. _LIBCPP_INLINE_VISIBILITY
  420. priority_queue(priority_queue&& __q, const _Alloc& __a,
  421. typename enable_if<uses_allocator<container_type,
  422. _Alloc>::value>::type* = 0);
  423. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  424. _LIBCPP_INLINE_VISIBILITY
  425. bool empty() const {return c.empty();}
  426. _LIBCPP_INLINE_VISIBILITY
  427. size_type size() const {return c.size();}
  428. _LIBCPP_INLINE_VISIBILITY
  429. const_reference top() const {return c.front();}
  430. _LIBCPP_INLINE_VISIBILITY
  431. void push(const value_type& __v);
  432. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  433. _LIBCPP_INLINE_VISIBILITY
  434. void push(value_type&& __v);
  435. #ifndef _LIBCPP_HAS_NO_VARIADICS
  436. template <class... _Args> _LIBCPP_INLINE_VISIBILITY void emplace(_Args&&... __args);
  437. #endif
  438. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  439. _LIBCPP_INLINE_VISIBILITY
  440. void pop();
  441. _LIBCPP_INLINE_VISIBILITY
  442. void swap(priority_queue& __q)
  443. _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
  444. __is_nothrow_swappable<value_compare>::value);
  445. };
  446. template <class _Tp, class _Container, class _Compare>
  447. inline
  448. priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,
  449. const container_type& __c)
  450. : c(__c),
  451. comp(__comp)
  452. {
  453. _VSTD::make_heap(c.begin(), c.end(), comp);
  454. }
  455. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  456. template <class _Tp, class _Container, class _Compare>
  457. inline
  458. priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
  459. container_type&& __c)
  460. : c(_VSTD::move(__c)),
  461. comp(__comp)
  462. {
  463. _VSTD::make_heap(c.begin(), c.end(), comp);
  464. }
  465. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  466. template <class _Tp, class _Container, class _Compare>
  467. template <class _InputIter>
  468. inline
  469. priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
  470. const value_compare& __comp)
  471. : c(__f, __l),
  472. comp(__comp)
  473. {
  474. _VSTD::make_heap(c.begin(), c.end(), comp);
  475. }
  476. template <class _Tp, class _Container, class _Compare>
  477. template <class _InputIter>
  478. inline
  479. priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
  480. const value_compare& __comp,
  481. const container_type& __c)
  482. : c(__c),
  483. comp(__comp)
  484. {
  485. c.insert(c.end(), __f, __l);
  486. _VSTD::make_heap(c.begin(), c.end(), comp);
  487. }
  488. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  489. template <class _Tp, class _Container, class _Compare>
  490. template <class _InputIter>
  491. inline
  492. priority_queue<_Tp, _Container, _Compare>::priority_queue(_InputIter __f, _InputIter __l,
  493. const value_compare& __comp,
  494. container_type&& __c)
  495. : c(_VSTD::move(__c)),
  496. comp(__comp)
  497. {
  498. c.insert(c.end(), __f, __l);
  499. _VSTD::make_heap(c.begin(), c.end(), comp);
  500. }
  501. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  502. template <class _Tp, class _Container, class _Compare>
  503. template <class _Alloc>
  504. inline
  505. priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Alloc& __a,
  506. typename enable_if<uses_allocator<container_type,
  507. _Alloc>::value>::type*)
  508. : c(__a)
  509. {
  510. }
  511. template <class _Tp, class _Container, class _Compare>
  512. template <class _Alloc>
  513. inline
  514. priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
  515. const _Alloc& __a,
  516. typename enable_if<uses_allocator<container_type,
  517. _Alloc>::value>::type*)
  518. : c(__a),
  519. comp(__comp)
  520. {
  521. }
  522. template <class _Tp, class _Container, class _Compare>
  523. template <class _Alloc>
  524. inline
  525. priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
  526. const container_type& __c,
  527. const _Alloc& __a,
  528. typename enable_if<uses_allocator<container_type,
  529. _Alloc>::value>::type*)
  530. : c(__c, __a),
  531. comp(__comp)
  532. {
  533. _VSTD::make_heap(c.begin(), c.end(), comp);
  534. }
  535. template <class _Tp, class _Container, class _Compare>
  536. template <class _Alloc>
  537. inline
  538. priority_queue<_Tp, _Container, _Compare>::priority_queue(const priority_queue& __q,
  539. const _Alloc& __a,
  540. typename enable_if<uses_allocator<container_type,
  541. _Alloc>::value>::type*)
  542. : c(__q.c, __a),
  543. comp(__q.comp)
  544. {
  545. _VSTD::make_heap(c.begin(), c.end(), comp);
  546. }
  547. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  548. template <class _Tp, class _Container, class _Compare>
  549. template <class _Alloc>
  550. inline
  551. priority_queue<_Tp, _Container, _Compare>::priority_queue(const value_compare& __comp,
  552. container_type&& __c,
  553. const _Alloc& __a,
  554. typename enable_if<uses_allocator<container_type,
  555. _Alloc>::value>::type*)
  556. : c(_VSTD::move(__c), __a),
  557. comp(__comp)
  558. {
  559. _VSTD::make_heap(c.begin(), c.end(), comp);
  560. }
  561. template <class _Tp, class _Container, class _Compare>
  562. template <class _Alloc>
  563. inline
  564. priority_queue<_Tp, _Container, _Compare>::priority_queue(priority_queue&& __q,
  565. const _Alloc& __a,
  566. typename enable_if<uses_allocator<container_type,
  567. _Alloc>::value>::type*)
  568. : c(_VSTD::move(__q.c), __a),
  569. comp(_VSTD::move(__q.comp))
  570. {
  571. _VSTD::make_heap(c.begin(), c.end(), comp);
  572. }
  573. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  574. template <class _Tp, class _Container, class _Compare>
  575. inline
  576. void
  577. priority_queue<_Tp, _Container, _Compare>::push(const value_type& __v)
  578. {
  579. c.push_back(__v);
  580. _VSTD::push_heap(c.begin(), c.end(), comp);
  581. }
  582. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  583. template <class _Tp, class _Container, class _Compare>
  584. inline
  585. void
  586. priority_queue<_Tp, _Container, _Compare>::push(value_type&& __v)
  587. {
  588. c.push_back(_VSTD::move(__v));
  589. _VSTD::push_heap(c.begin(), c.end(), comp);
  590. }
  591. #ifndef _LIBCPP_HAS_NO_VARIADICS
  592. template <class _Tp, class _Container, class _Compare>
  593. template <class... _Args>
  594. inline
  595. void
  596. priority_queue<_Tp, _Container, _Compare>::emplace(_Args&&... __args)
  597. {
  598. c.emplace_back(_VSTD::forward<_Args>(__args)...);
  599. _VSTD::push_heap(c.begin(), c.end(), comp);
  600. }
  601. #endif // _LIBCPP_HAS_NO_VARIADICS
  602. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  603. template <class _Tp, class _Container, class _Compare>
  604. inline
  605. void
  606. priority_queue<_Tp, _Container, _Compare>::pop()
  607. {
  608. _VSTD::pop_heap(c.begin(), c.end(), comp);
  609. c.pop_back();
  610. }
  611. template <class _Tp, class _Container, class _Compare>
  612. inline
  613. void
  614. priority_queue<_Tp, _Container, _Compare>::swap(priority_queue& __q)
  615. _NOEXCEPT_(__is_nothrow_swappable<container_type>::value &&
  616. __is_nothrow_swappable<value_compare>::value)
  617. {
  618. using _VSTD::swap;
  619. swap(c, __q.c);
  620. swap(comp, __q.comp);
  621. }
  622. template <class _Tp, class _Container, class _Compare>
  623. inline _LIBCPP_INLINE_VISIBILITY
  624. typename enable_if<
  625. __is_swappable<_Container>::value
  626. && __is_swappable<_Compare>::value,
  627. void
  628. >::type
  629. swap(priority_queue<_Tp, _Container, _Compare>& __x,
  630. priority_queue<_Tp, _Container, _Compare>& __y)
  631. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  632. {
  633. __x.swap(__y);
  634. }
  635. template <class _Tp, class _Container, class _Compare, class _Alloc>
  636. struct _LIBCPP_TYPE_VIS_ONLY uses_allocator<priority_queue<_Tp, _Container, _Compare>, _Alloc>
  637. : public uses_allocator<_Container, _Alloc>
  638. {
  639. };
  640. _LIBCPP_END_NAMESPACE_STD
  641. #endif // _LIBCPP_QUEUE