1 | // Heap implementation -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2017 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /* |
26 | * |
27 | * Copyright (c) 1994 |
28 | * Hewlett-Packard Company |
29 | * |
30 | * Permission to use, copy, modify, distribute and sell this software |
31 | * and its documentation for any purpose is hereby granted without fee, |
32 | * provided that the above copyright notice appear in all copies and |
33 | * that both that copyright notice and this permission notice appear |
34 | * in supporting documentation. Hewlett-Packard Company makes no |
35 | * representations about the suitability of this software for any |
36 | * purpose. It is provided "as is" without express or implied warranty. |
37 | * |
38 | * Copyright (c) 1997 |
39 | * Silicon Graphics Computer Systems, Inc. |
40 | * |
41 | * Permission to use, copy, modify, distribute and sell this software |
42 | * and its documentation for any purpose is hereby granted without fee, |
43 | * provided that the above copyright notice appear in all copies and |
44 | * that both that copyright notice and this permission notice appear |
45 | * in supporting documentation. Silicon Graphics makes no |
46 | * representations about the suitability of this software for any |
47 | * purpose. It is provided "as is" without express or implied warranty. |
48 | */ |
49 | |
50 | /** @file bits/stl_heap.h |
51 | * This is an internal header file, included by other library headers. |
52 | * Do not attempt to use it directly. @headername{queue} |
53 | */ |
54 | |
55 | #ifndef _STL_HEAP_H |
56 | #define _STL_HEAP_H 1 |
57 | |
58 | #include <debug/debug.h> |
59 | #include <bits/move.h> |
60 | #include <bits/predefined_ops.h> |
61 | |
62 | namespace std _GLIBCXX_VISIBILITY(default) |
63 | { |
64 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
65 | |
66 | /** |
67 | * @defgroup heap_algorithms Heap |
68 | * @ingroup sorting_algorithms |
69 | */ |
70 | |
71 | template<typename _RandomAccessIterator, typename _Distance, |
72 | typename _Compare> |
73 | _Distance |
74 | __is_heap_until(_RandomAccessIterator __first, _Distance __n, |
75 | _Compare& __comp) |
76 | { |
77 | _Distance __parent = 0; |
78 | for (_Distance __child = 1; __child < __n; ++__child) |
79 | { |
80 | if (__comp(__first + __parent, __first + __child)) |
81 | return __child; |
82 | if ((__child & 1) == 0) |
83 | ++__parent; |
84 | } |
85 | return __n; |
86 | } |
87 | |
88 | // __is_heap, a predicate testing whether or not a range is a heap. |
89 | // This function is an extension, not part of the C++ standard. |
90 | template<typename _RandomAccessIterator, typename _Distance> |
91 | inline bool |
92 | __is_heap(_RandomAccessIterator __first, _Distance __n) |
93 | { |
94 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
95 | return std::__is_heap_until(__first, __n, __comp) == __n; |
96 | } |
97 | |
98 | template<typename _RandomAccessIterator, typename _Compare, |
99 | typename _Distance> |
100 | inline bool |
101 | __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) |
102 | { |
103 | typedef __decltype(__comp) _Cmp; |
104 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
105 | return std::__is_heap_until(__first, __n, __cmp) == __n; |
106 | } |
107 | |
108 | template<typename _RandomAccessIterator> |
109 | inline bool |
110 | __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
111 | { return std::__is_heap(__first, std::distance(__first, __last)); } |
112 | |
113 | template<typename _RandomAccessIterator, typename _Compare> |
114 | inline bool |
115 | __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
116 | _Compare __comp) |
117 | { |
118 | return std::__is_heap(__first, _GLIBCXX_MOVE(__comp), |
119 | std::distance(__first, __last)); |
120 | } |
121 | |
122 | // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, |
123 | // + is_heap and is_heap_until in C++0x. |
124 | |
125 | template<typename _RandomAccessIterator, typename _Distance, typename _Tp, |
126 | typename _Compare> |
127 | void |
128 | __push_heap(_RandomAccessIterator __first, |
129 | _Distance __holeIndex, _Distance __topIndex, _Tp __value, |
130 | _Compare& __comp) |
131 | { |
132 | _Distance __parent = (__holeIndex - 1) / 2; |
133 | while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) |
134 | { |
135 | *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); |
136 | __holeIndex = __parent; |
137 | __parent = (__holeIndex - 1) / 2; |
138 | } |
139 | *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); |
140 | } |
141 | |
142 | /** |
143 | * @brief Push an element onto a heap. |
144 | * @param __first Start of heap. |
145 | * @param __last End of heap + element. |
146 | * @ingroup heap_algorithms |
147 | * |
148 | * This operation pushes the element at last-1 onto the valid heap |
149 | * over the range [__first,__last-1). After completion, |
150 | * [__first,__last) is a valid heap. |
151 | */ |
152 | template<typename _RandomAccessIterator> |
153 | inline void |
154 | push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
155 | { |
156 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
157 | _ValueType; |
158 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
159 | _DistanceType; |
160 | |
161 | // concept requirements |
162 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
163 | _RandomAccessIterator>) |
164 | __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) |
165 | __glibcxx_requires_valid_range(__first, __last); |
166 | __glibcxx_requires_irreflexive(__first, __last); |
167 | __glibcxx_requires_heap(__first, __last - 1); |
168 | |
169 | __gnu_cxx::__ops::_Iter_less_val __comp; |
170 | _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); |
171 | std::__push_heap(__first, _DistanceType((__last - __first) - 1), |
172 | _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); |
173 | } |
174 | |
175 | /** |
176 | * @brief Push an element onto a heap using comparison functor. |
177 | * @param __first Start of heap. |
178 | * @param __last End of heap + element. |
179 | * @param __comp Comparison functor. |
180 | * @ingroup heap_algorithms |
181 | * |
182 | * This operation pushes the element at __last-1 onto the valid |
183 | * heap over the range [__first,__last-1). After completion, |
184 | * [__first,__last) is a valid heap. Compare operations are |
185 | * performed using comp. |
186 | */ |
187 | template<typename _RandomAccessIterator, typename _Compare> |
188 | inline void |
189 | push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
190 | _Compare __comp) |
191 | { |
192 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
193 | _ValueType; |
194 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
195 | _DistanceType; |
196 | |
197 | // concept requirements |
198 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
199 | _RandomAccessIterator>) |
200 | __glibcxx_requires_valid_range(__first, __last); |
201 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
202 | __glibcxx_requires_heap_pred(__first, __last - 1, __comp); |
203 | |
204 | __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) |
205 | __cmp(_GLIBCXX_MOVE(__comp)); |
206 | _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); |
207 | std::__push_heap(__first, _DistanceType((__last - __first) - 1), |
208 | _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp); |
209 | } |
210 | |
211 | template<typename _RandomAccessIterator, typename _Distance, |
212 | typename _Tp, typename _Compare> |
213 | void |
214 | __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, |
215 | _Distance __len, _Tp __value, _Compare __comp) |
216 | { |
217 | const _Distance __topIndex = __holeIndex; |
218 | _Distance __secondChild = __holeIndex; |
219 | while (__secondChild < (__len - 1) / 2) |
220 | { |
221 | __secondChild = 2 * (__secondChild + 1); |
222 | if (__comp(__first + __secondChild, |
223 | __first + (__secondChild - 1))) |
224 | __secondChild--; |
225 | *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); |
226 | __holeIndex = __secondChild; |
227 | } |
228 | if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) |
229 | { |
230 | __secondChild = 2 * (__secondChild + 1); |
231 | *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first |
232 | + (__secondChild - 1))); |
233 | __holeIndex = __secondChild - 1; |
234 | } |
235 | __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) |
236 | __cmp(_GLIBCXX_MOVE(__comp)); |
237 | std::__push_heap(__first, __holeIndex, __topIndex, |
238 | _GLIBCXX_MOVE(__value), __cmp); |
239 | } |
240 | |
241 | template<typename _RandomAccessIterator, typename _Compare> |
242 | inline void |
243 | __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
244 | _RandomAccessIterator __result, _Compare& __comp) |
245 | { |
246 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
247 | _ValueType; |
248 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
249 | _DistanceType; |
250 | |
251 | _ValueType __value = _GLIBCXX_MOVE(*__result); |
252 | *__result = _GLIBCXX_MOVE(*__first); |
253 | std::__adjust_heap(__first, _DistanceType(0), |
254 | _DistanceType(__last - __first), |
255 | _GLIBCXX_MOVE(__value), __comp); |
256 | } |
257 | |
258 | /** |
259 | * @brief Pop an element off a heap. |
260 | * @param __first Start of heap. |
261 | * @param __last End of heap. |
262 | * @pre [__first, __last) is a valid, non-empty range. |
263 | * @ingroup heap_algorithms |
264 | * |
265 | * This operation pops the top of the heap. The elements __first |
266 | * and __last-1 are swapped and [__first,__last-1) is made into a |
267 | * heap. |
268 | */ |
269 | template<typename _RandomAccessIterator> |
270 | inline void |
271 | pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
272 | { |
273 | // concept requirements |
274 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
275 | _RandomAccessIterator>) |
276 | __glibcxx_function_requires(_LessThanComparableConcept< |
277 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
278 | __glibcxx_requires_non_empty_range(__first, __last); |
279 | __glibcxx_requires_valid_range(__first, __last); |
280 | __glibcxx_requires_irreflexive(__first, __last); |
281 | __glibcxx_requires_heap(__first, __last); |
282 | |
283 | if (__last - __first > 1) |
284 | { |
285 | --__last; |
286 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
287 | std::__pop_heap(__first, __last, __last, __comp); |
288 | } |
289 | } |
290 | |
291 | /** |
292 | * @brief Pop an element off a heap using comparison functor. |
293 | * @param __first Start of heap. |
294 | * @param __last End of heap. |
295 | * @param __comp Comparison functor to use. |
296 | * @ingroup heap_algorithms |
297 | * |
298 | * This operation pops the top of the heap. The elements __first |
299 | * and __last-1 are swapped and [__first,__last-1) is made into a |
300 | * heap. Comparisons are made using comp. |
301 | */ |
302 | template<typename _RandomAccessIterator, typename _Compare> |
303 | inline void |
304 | pop_heap(_RandomAccessIterator __first, |
305 | _RandomAccessIterator __last, _Compare __comp) |
306 | { |
307 | // concept requirements |
308 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
309 | _RandomAccessIterator>) |
310 | __glibcxx_requires_valid_range(__first, __last); |
311 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
312 | __glibcxx_requires_non_empty_range(__first, __last); |
313 | __glibcxx_requires_heap_pred(__first, __last, __comp); |
314 | |
315 | if (__last - __first > 1) |
316 | { |
317 | typedef __decltype(__comp) _Cmp; |
318 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
319 | --__last; |
320 | std::__pop_heap(__first, __last, __last, __cmp); |
321 | } |
322 | } |
323 | |
324 | template<typename _RandomAccessIterator, typename _Compare> |
325 | void |
326 | __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
327 | _Compare& __comp) |
328 | { |
329 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
330 | _ValueType; |
331 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
332 | _DistanceType; |
333 | |
334 | if (__last - __first < 2) |
335 | return; |
336 | |
337 | const _DistanceType __len = __last - __first; |
338 | _DistanceType __parent = (__len - 2) / 2; |
339 | while (true) |
340 | { |
341 | _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); |
342 | std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), |
343 | __comp); |
344 | if (__parent == 0) |
345 | return; |
346 | __parent--; |
347 | } |
348 | } |
349 | |
350 | /** |
351 | * @brief Construct a heap over a range. |
352 | * @param __first Start of heap. |
353 | * @param __last End of heap. |
354 | * @ingroup heap_algorithms |
355 | * |
356 | * This operation makes the elements in [__first,__last) into a heap. |
357 | */ |
358 | template<typename _RandomAccessIterator> |
359 | inline void |
360 | make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
361 | { |
362 | // concept requirements |
363 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
364 | _RandomAccessIterator>) |
365 | __glibcxx_function_requires(_LessThanComparableConcept< |
366 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
367 | __glibcxx_requires_valid_range(__first, __last); |
368 | __glibcxx_requires_irreflexive(__first, __last); |
369 | |
370 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
371 | std::__make_heap(__first, __last, __comp); |
372 | } |
373 | |
374 | /** |
375 | * @brief Construct a heap over a range using comparison functor. |
376 | * @param __first Start of heap. |
377 | * @param __last End of heap. |
378 | * @param __comp Comparison functor to use. |
379 | * @ingroup heap_algorithms |
380 | * |
381 | * This operation makes the elements in [__first,__last) into a heap. |
382 | * Comparisons are made using __comp. |
383 | */ |
384 | template<typename _RandomAccessIterator, typename _Compare> |
385 | inline void |
386 | make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
387 | _Compare __comp) |
388 | { |
389 | // concept requirements |
390 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
391 | _RandomAccessIterator>) |
392 | __glibcxx_requires_valid_range(__first, __last); |
393 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
394 | |
395 | typedef __decltype(__comp) _Cmp; |
396 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
397 | std::__make_heap(__first, __last, __cmp); |
398 | } |
399 | |
400 | template<typename _RandomAccessIterator, typename _Compare> |
401 | void |
402 | __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
403 | _Compare& __comp) |
404 | { |
405 | while (__last - __first > 1) |
406 | { |
407 | --__last; |
408 | std::__pop_heap(__first, __last, __last, __comp); |
409 | } |
410 | } |
411 | |
412 | /** |
413 | * @brief Sort a heap. |
414 | * @param __first Start of heap. |
415 | * @param __last End of heap. |
416 | * @ingroup heap_algorithms |
417 | * |
418 | * This operation sorts the valid heap in the range [__first,__last). |
419 | */ |
420 | template<typename _RandomAccessIterator> |
421 | inline void |
422 | sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
423 | { |
424 | // concept requirements |
425 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
426 | _RandomAccessIterator>) |
427 | __glibcxx_function_requires(_LessThanComparableConcept< |
428 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
429 | __glibcxx_requires_valid_range(__first, __last); |
430 | __glibcxx_requires_irreflexive(__first, __last); |
431 | __glibcxx_requires_heap(__first, __last); |
432 | |
433 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
434 | std::__sort_heap(__first, __last, __comp); |
435 | } |
436 | |
437 | /** |
438 | * @brief Sort a heap using comparison functor. |
439 | * @param __first Start of heap. |
440 | * @param __last End of heap. |
441 | * @param __comp Comparison functor to use. |
442 | * @ingroup heap_algorithms |
443 | * |
444 | * This operation sorts the valid heap in the range [__first,__last). |
445 | * Comparisons are made using __comp. |
446 | */ |
447 | template<typename _RandomAccessIterator, typename _Compare> |
448 | inline void |
449 | sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
450 | _Compare __comp) |
451 | { |
452 | // concept requirements |
453 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
454 | _RandomAccessIterator>) |
455 | __glibcxx_requires_valid_range(__first, __last); |
456 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
457 | __glibcxx_requires_heap_pred(__first, __last, __comp); |
458 | |
459 | typedef __decltype(__comp) _Cmp; |
460 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
461 | std::__sort_heap(__first, __last, __cmp); |
462 | } |
463 | |
464 | #if __cplusplus >= 201103L |
465 | /** |
466 | * @brief Search the end of a heap. |
467 | * @param __first Start of range. |
468 | * @param __last End of range. |
469 | * @return An iterator pointing to the first element not in the heap. |
470 | * @ingroup heap_algorithms |
471 | * |
472 | * This operation returns the last iterator i in [__first, __last) for which |
473 | * the range [__first, i) is a heap. |
474 | */ |
475 | template<typename _RandomAccessIterator> |
476 | inline _RandomAccessIterator |
477 | is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) |
478 | { |
479 | // concept requirements |
480 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
481 | _RandomAccessIterator>) |
482 | __glibcxx_function_requires(_LessThanComparableConcept< |
483 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
484 | __glibcxx_requires_valid_range(__first, __last); |
485 | __glibcxx_requires_irreflexive(__first, __last); |
486 | |
487 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
488 | return __first + |
489 | std::__is_heap_until(__first, std::distance(__first, __last), __comp); |
490 | } |
491 | |
492 | /** |
493 | * @brief Search the end of a heap using comparison functor. |
494 | * @param __first Start of range. |
495 | * @param __last End of range. |
496 | * @param __comp Comparison functor to use. |
497 | * @return An iterator pointing to the first element not in the heap. |
498 | * @ingroup heap_algorithms |
499 | * |
500 | * This operation returns the last iterator i in [__first, __last) for which |
501 | * the range [__first, i) is a heap. Comparisons are made using __comp. |
502 | */ |
503 | template<typename _RandomAccessIterator, typename _Compare> |
504 | inline _RandomAccessIterator |
505 | is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, |
506 | _Compare __comp) |
507 | { |
508 | // concept requirements |
509 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
510 | _RandomAccessIterator>) |
511 | __glibcxx_requires_valid_range(__first, __last); |
512 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
513 | |
514 | typedef __decltype(__comp) _Cmp; |
515 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
516 | return __first |
517 | + std::__is_heap_until(__first, std::distance(__first, __last), __cmp); |
518 | } |
519 | |
520 | /** |
521 | * @brief Determines whether a range is a heap. |
522 | * @param __first Start of range. |
523 | * @param __last End of range. |
524 | * @return True if range is a heap, false otherwise. |
525 | * @ingroup heap_algorithms |
526 | */ |
527 | template<typename _RandomAccessIterator> |
528 | inline bool |
529 | is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
530 | { return std::is_heap_until(__first, __last) == __last; } |
531 | |
532 | /** |
533 | * @brief Determines whether a range is a heap using comparison functor. |
534 | * @param __first Start of range. |
535 | * @param __last End of range. |
536 | * @param __comp Comparison functor to use. |
537 | * @return True if range is a heap, false otherwise. |
538 | * @ingroup heap_algorithms |
539 | */ |
540 | template<typename _RandomAccessIterator, typename _Compare> |
541 | inline bool |
542 | is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
543 | _Compare __comp) |
544 | { |
545 | // concept requirements |
546 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
547 | _RandomAccessIterator>) |
548 | __glibcxx_requires_valid_range(__first, __last); |
549 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
550 | |
551 | const auto __dist = std::distance(__first, __last); |
552 | typedef __decltype(__comp) _Cmp; |
553 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
554 | return std::__is_heap_until(__first, __dist, __cmp) == __dist; |
555 | } |
556 | #endif |
557 | |
558 | _GLIBCXX_END_NAMESPACE_VERSION |
559 | } // namespace |
560 | |
561 | #endif /* _STL_HEAP_H */ |
562 | |