RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://cplusplus.com/reference/algorithm/is_heap_until/ below:

function template

std::is_heap_until default (1)

template <class RandomAccessIterator>  RandomAccessIterator is_heap_until (RandomAccessIterator first,                                      RandomAccessIterator last);

custom (2)

template <class RandomAccessIterator, class Compare>  RandomAccessIterator is_heap_until (RandomAccessIterator first,                                      RandomAccessIterator last                                      Compare comp);

Find first element not in heap order

Returns an iterator to the first element in the range [first,last) which is not in a valid position if the range is considered a heap (as if constructed with make_heap).

The range between first and the iterator returned is a heap.

If the entire range is a valid heap, the function returns last.

The elements are compared using operator< for the first version, and comp for the second.

Parameters

first, last: Random-access iterators to the initial and final positions in a sequence. The range checked is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
comp: Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

Return value An iterator to the first element in the range which is not in a valid position for the range to be a heap, or last if all elements are validly positioned or if the range contains less than two elements.

Example

// is_heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::is_heap_until, std::sort, std::reverse
#include <vector>       // std::vector

int main () {
  std::vector<int> foo {2,6,9,3,8,4,5,1,7};

  std::sort(foo.begin(),foo.end());
  std::reverse(foo.begin(),foo.end());

  auto last = std::is_heap_until (foo.begin(),foo.end());

  std::cout << "The " << (last-foo.begin()) << " first elements are a valid heap:";
  for (auto it=foo.begin(); it!=last; ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Most implementations consider a range sorted in reverse order a valid heap:
Possible output:

The 9 first elements are a valid heap: 9 8 7 6 5 4 3 2 1

Complexity Up to linear in the distance between first and last: Compares elements until a mismatch is found.

Data races The objects in the range [first,last) are accessed.

Exceptions Throws if either comp or an operation on an iterator throws.
Note that invalid parameters cause undefined behavior.

See also

is_heap: Test if range is heap (function template)

make_heap: Make heap from range (function template)

is_sorted_until: Find first unsorted element in range (function template)

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4