libstdc++-v3/include/bits/stl_heap.h

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