Skip to content

← Containers, Strings, Algorithms step 4 of 5

Medium Primitives

Summarize a range with standard algorithms

Standard algorithms give common operations recognizable names. They can replace indexing and bookkeeping, but callers still need to choose the right operation, supply a suitable predicate and handle its result correctly.

Consider this maximum calculation:

int best = 0;
for (int value : values) {
    if (value > best) {
        best = value;
    }
}

For [-5, -2, -9], it incorrectly returns zero because no value exceeds the initial value. std::ranges::max_element(values) instead identifies an element from the range. It returns the first maximum, or values.end() when the vector is empty. You must check for that empty result before dereferencing it; the compiler does not enforce the check.

Useful operations

Algorithm Result or effect
max_element, min_element Iterator to the first maximum or minimum; end for an empty range
find, find_if Iterator to the first match; end if none matches
count, count_if Number of matches
any_of, all_of, none_of Whether any, all or none of the elements satisfy a predicate
accumulate Combine elements with an initial value, in order
sort Order the range; equivalent elements need not retain their order
stable_sort Order the range while preserving the order of equivalent elements
transform Write mapped results to an output range

A predicate is a function that tests an element and returns a boolean. For an empty range, any_of is false, while all_of and none_of are true.

Range and iterator forms

C++20 provides range overloads for many algorithms in <algorithm>:

std::ranges::max_element(values);
std::max_element(values.begin(), values.end());

Passing the whole vector avoids manually pairing its begin and end iterators. Iterator forms remain useful for subranges and for operations without a C++20 ranges counterpart, such as std::accumulate from <numeric>.

Choose the accumulator type

std::accumulate(values.begin(), values.end(), 0);    // int accumulator
std::accumulate(values.begin(), values.end(), 0LL);  // long long accumulator

The initial value determines the accumulator type. On a system with 32-bit int, summing [2000000000, 2000000000] needs more than an int; a long long accumulator can represent 4000000000. Assigning an int-based accumulation to a long long afterwards does not prevent overflow during the additions. The chosen type must fit every intermediate total.

Your task

std::vector<long long> summarize(const std::vector<int>& values, int threshold);

Return four numbers in this order, without modifying values:

  1. The largest value, or 0 if the vector is empty.
  2. The zero-based index of the first value strictly greater than threshold, or -1 if no value qualifies.
  3. The number of values strictly greater than threshold.
  4. The sum of all values using a long long accumulator.

For [1, 7, 3, 9, 2] and threshold 4, return [9, 1, 2, 22]. For an empty vector, return [0, -1, 0, 0]. Counts, indices and intermediate sums in the test inputs fit in long long.

Fix the starter's maximum initialization and its search that keeps replacing the first matching index with later matches. Use the standard algorithms to express maximum, first match, count and sum. Separate linear passes still take O(n) total work for these four operations; they are not automatically faster than a carefully written combined loop.