Line data Source code
1 : // Heap implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2021 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 : _GLIBCXX20_CONSTEXPR
74 : _Distance
75 : __is_heap_until(_RandomAccessIterator __first, _Distance __n,
76 : _Compare& __comp)
77 : {
78 : _Distance __parent = 0;
79 : for (_Distance __child = 1; __child < __n; ++__child)
80 : {
81 : if (__comp(__first + __parent, __first + __child))
82 : return __child;
83 : if ((__child & 1) == 0)
84 : ++__parent;
85 : }
86 : return __n;
87 : }
88 :
89 : // __is_heap, a predicate testing whether or not a range is a heap.
90 : // This function is an extension, not part of the C++ standard.
91 : template<typename _RandomAccessIterator, typename _Distance>
92 : _GLIBCXX20_CONSTEXPR
93 : inline bool
94 : __is_heap(_RandomAccessIterator __first, _Distance __n)
95 : {
96 : __gnu_cxx::__ops::_Iter_less_iter __comp;
97 : return std::__is_heap_until(__first, __n, __comp) == __n;
98 : }
99 :
100 : template<typename _RandomAccessIterator, typename _Compare,
101 : typename _Distance>
102 : _GLIBCXX20_CONSTEXPR
103 : inline bool
104 : __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
105 : {
106 : typedef __decltype(__comp) _Cmp;
107 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
108 : return std::__is_heap_until(__first, __n, __cmp) == __n;
109 : }
110 :
111 : template<typename _RandomAccessIterator>
112 : _GLIBCXX20_CONSTEXPR
113 : inline bool
114 : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
115 : { return std::__is_heap(__first, std::distance(__first, __last)); }
116 :
117 : template<typename _RandomAccessIterator, typename _Compare>
118 : _GLIBCXX20_CONSTEXPR
119 : inline bool
120 : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
121 : _Compare __comp)
122 : {
123 : return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
124 : std::distance(__first, __last));
125 : }
126 :
127 : // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
128 : // + is_heap and is_heap_until in C++0x.
129 :
130 : template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
131 : typename _Compare>
132 : _GLIBCXX20_CONSTEXPR
133 : void
134 0 : __push_heap(_RandomAccessIterator __first,
135 : _Distance __holeIndex, _Distance __topIndex, _Tp __value,
136 : _Compare& __comp)
137 : {
138 0 : _Distance __parent = (__holeIndex - 1) / 2;
139 0 : while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
140 : {
141 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
142 0 : __holeIndex = __parent;
143 0 : __parent = (__holeIndex - 1) / 2;
144 : }
145 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
146 0 : }
147 :
148 : /**
149 : * @brief Push an element onto a heap.
150 : * @param __first Start of heap.
151 : * @param __last End of heap + element.
152 : * @ingroup heap_algorithms
153 : *
154 : * This operation pushes the element at last-1 onto the valid heap
155 : * over the range [__first,__last-1). After completion,
156 : * [__first,__last) is a valid heap.
157 : */
158 : template<typename _RandomAccessIterator>
159 : _GLIBCXX20_CONSTEXPR
160 : inline void
161 : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
162 : {
163 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
164 : _ValueType;
165 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
166 : _DistanceType;
167 :
168 : // concept requirements
169 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
170 : _RandomAccessIterator>)
171 : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
172 : __glibcxx_requires_valid_range(__first, __last);
173 : __glibcxx_requires_irreflexive(__first, __last);
174 : __glibcxx_requires_heap(__first, __last - 1);
175 :
176 : __gnu_cxx::__ops::_Iter_less_val __comp;
177 : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
178 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
179 : _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
180 : }
181 :
182 : /**
183 : * @brief Push an element onto a heap using comparison functor.
184 : * @param __first Start of heap.
185 : * @param __last End of heap + element.
186 : * @param __comp Comparison functor.
187 : * @ingroup heap_algorithms
188 : *
189 : * This operation pushes the element at __last-1 onto the valid
190 : * heap over the range [__first,__last-1). After completion,
191 : * [__first,__last) is a valid heap. Compare operations are
192 : * performed using comp.
193 : */
194 : template<typename _RandomAccessIterator, typename _Compare>
195 : _GLIBCXX20_CONSTEXPR
196 : inline void
197 : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
198 : _Compare __comp)
199 : {
200 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
201 : _ValueType;
202 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
203 : _DistanceType;
204 :
205 : // concept requirements
206 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
207 : _RandomAccessIterator>)
208 : __glibcxx_requires_valid_range(__first, __last);
209 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
210 : __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
211 :
212 : __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
213 : __cmp(_GLIBCXX_MOVE(__comp));
214 : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
215 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
216 : _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
217 : }
218 :
219 : template<typename _RandomAccessIterator, typename _Distance,
220 : typename _Tp, typename _Compare>
221 : _GLIBCXX20_CONSTEXPR
222 : void
223 0 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
224 : _Distance __len, _Tp __value, _Compare __comp)
225 : {
226 0 : const _Distance __topIndex = __holeIndex;
227 0 : _Distance __secondChild = __holeIndex;
228 0 : while (__secondChild < (__len - 1) / 2)
229 : {
230 0 : __secondChild = 2 * (__secondChild + 1);
231 0 : if (__comp(__first + __secondChild,
232 : __first + (__secondChild - 1)))
233 0 : __secondChild--;
234 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
235 0 : __holeIndex = __secondChild;
236 : }
237 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
238 : {
239 0 : __secondChild = 2 * (__secondChild + 1);
240 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
241 : + (__secondChild - 1)));
242 0 : __holeIndex = __secondChild - 1;
243 : }
244 : __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
245 0 : __cmp(_GLIBCXX_MOVE(__comp));
246 0 : std::__push_heap(__first, __holeIndex, __topIndex,
247 0 : _GLIBCXX_MOVE(__value), __cmp);
248 0 : }
249 :
250 : template<typename _RandomAccessIterator, typename _Compare>
251 : _GLIBCXX20_CONSTEXPR
252 : inline void
253 0 : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
254 : _RandomAccessIterator __result, _Compare& __comp)
255 : {
256 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
257 : _ValueType;
258 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
259 : _DistanceType;
260 :
261 0 : _ValueType __value = _GLIBCXX_MOVE(*__result);
262 0 : *__result = _GLIBCXX_MOVE(*__first);
263 0 : std::__adjust_heap(__first, _DistanceType(0),
264 0 : _DistanceType(__last - __first),
265 0 : _GLIBCXX_MOVE(__value), __comp);
266 0 : }
267 :
268 : /**
269 : * @brief Pop an element off a heap.
270 : * @param __first Start of heap.
271 : * @param __last End of heap.
272 : * @pre [__first, __last) is a valid, non-empty range.
273 : * @ingroup heap_algorithms
274 : *
275 : * This operation pops the top of the heap. The elements __first
276 : * and __last-1 are swapped and [__first,__last-1) is made into a
277 : * heap.
278 : */
279 : template<typename _RandomAccessIterator>
280 : _GLIBCXX20_CONSTEXPR
281 : inline void
282 : pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
283 : {
284 : // concept requirements
285 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
286 : _RandomAccessIterator>)
287 : __glibcxx_function_requires(_LessThanComparableConcept<
288 : typename iterator_traits<_RandomAccessIterator>::value_type>)
289 : __glibcxx_requires_non_empty_range(__first, __last);
290 : __glibcxx_requires_valid_range(__first, __last);
291 : __glibcxx_requires_irreflexive(__first, __last);
292 : __glibcxx_requires_heap(__first, __last);
293 :
294 : if (__last - __first > 1)
295 : {
296 : --__last;
297 : __gnu_cxx::__ops::_Iter_less_iter __comp;
298 : std::__pop_heap(__first, __last, __last, __comp);
299 : }
300 : }
301 :
302 : /**
303 : * @brief Pop an element off a heap using comparison functor.
304 : * @param __first Start of heap.
305 : * @param __last End of heap.
306 : * @param __comp Comparison functor to use.
307 : * @ingroup heap_algorithms
308 : *
309 : * This operation pops the top of the heap. The elements __first
310 : * and __last-1 are swapped and [__first,__last-1) is made into a
311 : * heap. Comparisons are made using comp.
312 : */
313 : template<typename _RandomAccessIterator, typename _Compare>
314 : _GLIBCXX20_CONSTEXPR
315 : inline void
316 : pop_heap(_RandomAccessIterator __first,
317 : _RandomAccessIterator __last, _Compare __comp)
318 : {
319 : // concept requirements
320 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
321 : _RandomAccessIterator>)
322 : __glibcxx_requires_valid_range(__first, __last);
323 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
324 : __glibcxx_requires_non_empty_range(__first, __last);
325 : __glibcxx_requires_heap_pred(__first, __last, __comp);
326 :
327 : if (__last - __first > 1)
328 : {
329 : typedef __decltype(__comp) _Cmp;
330 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
331 : --__last;
332 : std::__pop_heap(__first, __last, __last, __cmp);
333 : }
334 : }
335 :
336 : template<typename _RandomAccessIterator, typename _Compare>
337 : _GLIBCXX20_CONSTEXPR
338 : void
339 0 : __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
340 : _Compare& __comp)
341 : {
342 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
343 : _ValueType;
344 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
345 : _DistanceType;
346 :
347 0 : if (__last - __first < 2)
348 0 : return;
349 :
350 0 : const _DistanceType __len = __last - __first;
351 0 : _DistanceType __parent = (__len - 2) / 2;
352 0 : while (true)
353 : {
354 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
355 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
356 : __comp);
357 0 : if (__parent == 0)
358 0 : return;
359 0 : __parent--;
360 : }
361 : }
362 :
363 : /**
364 : * @brief Construct a heap over a range.
365 : * @param __first Start of heap.
366 : * @param __last End of heap.
367 : * @ingroup heap_algorithms
368 : *
369 : * This operation makes the elements in [__first,__last) into a heap.
370 : */
371 : template<typename _RandomAccessIterator>
372 : _GLIBCXX20_CONSTEXPR
373 : inline void
374 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
375 : {
376 : // concept requirements
377 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
378 : _RandomAccessIterator>)
379 : __glibcxx_function_requires(_LessThanComparableConcept<
380 : typename iterator_traits<_RandomAccessIterator>::value_type>)
381 : __glibcxx_requires_valid_range(__first, __last);
382 : __glibcxx_requires_irreflexive(__first, __last);
383 :
384 : __gnu_cxx::__ops::_Iter_less_iter __comp;
385 : std::__make_heap(__first, __last, __comp);
386 : }
387 :
388 : /**
389 : * @brief Construct a heap over a range using comparison functor.
390 : * @param __first Start of heap.
391 : * @param __last End of heap.
392 : * @param __comp Comparison functor to use.
393 : * @ingroup heap_algorithms
394 : *
395 : * This operation makes the elements in [__first,__last) into a heap.
396 : * Comparisons are made using __comp.
397 : */
398 : template<typename _RandomAccessIterator, typename _Compare>
399 : _GLIBCXX20_CONSTEXPR
400 : inline void
401 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
402 : _Compare __comp)
403 : {
404 : // concept requirements
405 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
406 : _RandomAccessIterator>)
407 : __glibcxx_requires_valid_range(__first, __last);
408 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
409 :
410 : typedef __decltype(__comp) _Cmp;
411 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
412 : std::__make_heap(__first, __last, __cmp);
413 : }
414 :
415 : template<typename _RandomAccessIterator, typename _Compare>
416 : _GLIBCXX20_CONSTEXPR
417 : void
418 0 : __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
419 : _Compare& __comp)
420 : {
421 0 : while (__last - __first > 1)
422 : {
423 0 : --__last;
424 0 : std::__pop_heap(__first, __last, __last, __comp);
425 : }
426 0 : }
427 :
428 : /**
429 : * @brief Sort a heap.
430 : * @param __first Start of heap.
431 : * @param __last End of heap.
432 : * @ingroup heap_algorithms
433 : *
434 : * This operation sorts the valid heap in the range [__first,__last).
435 : */
436 : template<typename _RandomAccessIterator>
437 : _GLIBCXX20_CONSTEXPR
438 : inline void
439 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
440 : {
441 : // concept requirements
442 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
443 : _RandomAccessIterator>)
444 : __glibcxx_function_requires(_LessThanComparableConcept<
445 : typename iterator_traits<_RandomAccessIterator>::value_type>)
446 : __glibcxx_requires_valid_range(__first, __last);
447 : __glibcxx_requires_irreflexive(__first, __last);
448 : __glibcxx_requires_heap(__first, __last);
449 :
450 : __gnu_cxx::__ops::_Iter_less_iter __comp;
451 : std::__sort_heap(__first, __last, __comp);
452 : }
453 :
454 : /**
455 : * @brief Sort a heap using comparison functor.
456 : * @param __first Start of heap.
457 : * @param __last End of heap.
458 : * @param __comp Comparison functor to use.
459 : * @ingroup heap_algorithms
460 : *
461 : * This operation sorts the valid heap in the range [__first,__last).
462 : * Comparisons are made using __comp.
463 : */
464 : template<typename _RandomAccessIterator, typename _Compare>
465 : _GLIBCXX20_CONSTEXPR
466 : inline void
467 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
468 : _Compare __comp)
469 : {
470 : // concept requirements
471 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
472 : _RandomAccessIterator>)
473 : __glibcxx_requires_valid_range(__first, __last);
474 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
475 : __glibcxx_requires_heap_pred(__first, __last, __comp);
476 :
477 : typedef __decltype(__comp) _Cmp;
478 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
479 : std::__sort_heap(__first, __last, __cmp);
480 : }
481 :
482 : #if __cplusplus >= 201103L
483 : /**
484 : * @brief Search the end of a heap.
485 : * @param __first Start of range.
486 : * @param __last End of range.
487 : * @return An iterator pointing to the first element not in the heap.
488 : * @ingroup heap_algorithms
489 : *
490 : * This operation returns the last iterator i in [__first, __last) for which
491 : * the range [__first, i) is a heap.
492 : */
493 : template<typename _RandomAccessIterator>
494 : _GLIBCXX20_CONSTEXPR
495 : inline _RandomAccessIterator
496 : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
497 : {
498 : // concept requirements
499 : __glibcxx_function_requires(_RandomAccessIteratorConcept<
500 : _RandomAccessIterator>)
501 : __glibcxx_function_requires(_LessThanComparableConcept<
502 : typename iterator_traits<_RandomAccessIterator>::value_type>)
503 : __glibcxx_requires_valid_range(__first, __last);
504 : __glibcxx_requires_irreflexive(__first, __last);
505 :
506 : __gnu_cxx::__ops::_Iter_less_iter __comp;
507 : return __first +
508 : std::__is_heap_until(__first, std::distance(__first, __last), __comp);
509 : }
510 :
511 : /**
512 : * @brief Search the end of a heap using comparison functor.
513 : * @param __first Start of range.
514 : * @param __last End of range.
515 : * @param __comp Comparison functor to use.
516 : * @return An iterator pointing to the first element not in the heap.
517 : * @ingroup heap_algorithms
518 : *
519 : * This operation returns the last iterator i in [__first, __last) for which
520 : * the range [__first, i) is a heap. Comparisons are made using __comp.
521 : */
522 : template<typename _RandomAccessIterator, typename _Compare>
523 : _GLIBCXX20_CONSTEXPR
524 : inline _RandomAccessIterator
525 : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
526 : _Compare __comp)
527 : {
528 : // concept requirements
529 : __glibcxx_function_requires(_RandomAccessIteratorConcept<
530 : _RandomAccessIterator>)
531 : __glibcxx_requires_valid_range(__first, __last);
532 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
533 :
534 : typedef __decltype(__comp) _Cmp;
535 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
536 : return __first
537 : + std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
538 : }
539 :
540 : /**
541 : * @brief Determines whether a range is a heap.
542 : * @param __first Start of range.
543 : * @param __last End of range.
544 : * @return True if range is a heap, false otherwise.
545 : * @ingroup heap_algorithms
546 : */
547 : template<typename _RandomAccessIterator>
548 : _GLIBCXX20_CONSTEXPR
549 : inline bool
550 : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
551 : { return std::is_heap_until(__first, __last) == __last; }
552 :
553 : /**
554 : * @brief Determines whether a range is a heap using comparison functor.
555 : * @param __first Start of range.
556 : * @param __last End of range.
557 : * @param __comp Comparison functor to use.
558 : * @return True if range is a heap, false otherwise.
559 : * @ingroup heap_algorithms
560 : */
561 : template<typename _RandomAccessIterator, typename _Compare>
562 : _GLIBCXX20_CONSTEXPR
563 : inline bool
564 : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
565 : _Compare __comp)
566 : {
567 : // concept requirements
568 : __glibcxx_function_requires(_RandomAccessIteratorConcept<
569 : _RandomAccessIterator>)
570 : __glibcxx_requires_valid_range(__first, __last);
571 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
572 :
573 : const auto __dist = std::distance(__first, __last);
574 : typedef __decltype(__comp) _Cmp;
575 : __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
576 : return std::__is_heap_until(__first, __dist, __cmp) == __dist;
577 : }
578 : #endif
579 :
580 : _GLIBCXX_END_NAMESPACE_VERSION
581 : } // namespace
582 :
583 : #endif /* _STL_HEAP_H */
|
