Exercises — STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of

Algorithm: ==sort== — specifically sort(v.begin(), v.end()). Returns: nothing (void). It rearranges the elements in place; the container itself is the result. Why not the others? find locates one element, transform maps a function, copy duplicates — none of them reorder. Only sort reorders a range.

Algorithm: ==all_of== with predicate [](int s){ return s >= 40; }. Returns: a bool. true only if every element passes; on an empty vector it returns true (vacuous truth — no failing student exists). any_of would answer "is there at least one passer", which is a different question.

#include <vector>
#include <algorithm>
using namespace std;
// ...
sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
// v = {9, 8, 5, 3, 2, 1}

Why a > b? The comparator cmp(a,b) must return true when a should come before b. "Bigger comes first" is exactly a > b, giving descending order. The default operator< gives ascending. See the comparator figure below.

#include <vector>
#include <numeric>
using namespace std;
// ...
double s = accumulate(v.begin(), v.end(), 0.0);  // s == 7.0

The bug with 0: the accumulator's type equals the type of init. With int init = 0, every partial sum is stored in an int: $0+1.5\to 1$ (truncated), $1+2.5\to 3$, $3+3.0\to 6$. You'd get 6, not 7.0. Fix: pass 0.0 so the accumulator is double. The correct total is $1.5+2.5+3.0=7.0$.

#include <vector>
#include <algorithm>
#include <iterator>     // <-- needed for back_inserter
using namespace std;
// ...
vector<int> w;                       // starts empty (size 0)
transform(v.begin(), v.end(),
          back_inserter(w),          // grows w via push_back (see funnel figure)
          [](int x){ return x*x*x; });
// w = {1, 8, 27, 64, 125}

Why back_inserter(w)? transform assigns into dest; it does not grow the container. Since w is empty, w.begin() points nowhere valid. A back_inserter — defined in <iterator> — turns each write into a push_back, growing w safely. Cubes: $1,8,27,64,125$.

On an empty range:

• all_of → ==true==. It AND-folds starting from true: $\text{true}\wedge (\text{nothing})=\text{true}$. No element can be a counterexample, so "all pass" holds vacuously.
• any_of → ==false==. It OR-folds starting from false: $\text{false}\vee (\text{nothing})=\text{false}$. There is no element to make it true. Mental model: all_of is $\wedge$ with identity true; any_of is $\vee$ with identity false. The start value is the empty-range answer — see the fold figure.

25 is not in v, so find returns v.end() — one past the last element. Then $\text{idx}=\text{v.end()}-\text{v.begin()}=\text{size}=4.$ So idx == 4. The danger: the code did not check it != v.end() first. It silently produced 4, an index that looks like a real position but is actually the "not found" sentinel turned into a number. Always test if (it != v.end()) before dereferencing or measuring position.

accumulate is a left fold: it applies op(acc, e) walking left to right, starting from init. ${\text{acc}}_0=10,{\text{acc}}_1=10-1=9,{\text{acc}}_2=9-2=7,{\text{acc}}_3=7-3=4.$ Result = 4. Why the direction matters: subtraction is not associative. A right fold $1-(2-(3-10))$ would give a different number ($1-(2-(-7))=1-9=-8$). Because accumulate fixes the direction (left), op is evaluated as ((10-1)-2)-3. Never assume commutativity/associativity when you pass a non-+ op.

Idea: map each element to itself-if->4-else-0, then sum.

#include <vector>
#include <algorithm>   // transform
#include <numeric>     // accumulate
#include <iterator>    // back_inserter
using namespace std;
// ...
vector<int> masked;
transform(v.begin(), v.end(), back_inserter(masked),
          [](int x){ return x > 4 ? x : 0; });
// masked = {0, 7, 0, 9, 5, 0}
int total = accumulate(masked.begin(), masked.end(), 0); // 21

Kept: $7,9,5$. Sum $=7+9+5=21$. Why this pipeline? transform zeroes out the elements we don't want (0 is the identity for +, so they vanish in the sum), and accumulate folds them. Alternatively accumulate with a custom op a + (b>4 ? b : 0) does it in one pass — same answer, 21.

#include <vector>
#include <algorithm>   // copy, sort
#include <iterator>    // back_inserter
using namespace std;
// ...
vector<int> s;
copy(v.begin(), v.end(), back_inserter(s)); // s is a copy of v (grows via push_back)
sort(s.begin(), s.end());                    // sort the copy only
// s = {1, 3, 3, 5, 8, 8}, v unchanged

Sorted copy: {1, 3, 3, 5, 8, 8}. The "is it sorted?" check is true — after sort it is by construction non-decreasing. v still equals {3,8,3,5,8,1}. Why copy first? sort mutates in place. To preserve the original you must sort a duplicate; copy with a back_inserter builds that duplicate safely into an empty vector.

#include <string>
#include <algorithm>   // copy, equal, all_of
#include <iterator>    // back_inserter
using namespace std;
 
bool isPalindromeDigits(int n) {
    string s = to_string(n);            // "0" for n==0, never empty
    string r;                           // reversed copy, built via back_inserter
    copy(s.rbegin(), s.rend(),          // rbegin/rend walk s backwards
         back_inserter(r));             // append each char -> r is s reversed
    // Compare the forward and reversed digit sequences element-by-element:
    return equal(s.begin(), s.end(), r.begin());   // true iff every position matches
}

std::equal(first1, last1, first2) walks both ranges in lockstep and returns true iff every pair of corresponding elements is equal — exactly the "read the same forwards and backwards" test. Because r is the reverse of s, equal succeeds precisely when s is a palindrome. all_of-based cross-check (same idea by index): position i must match position d-1-i.

#include <numeric>     // iota
#include <vector>
bool isPalDigits2(int n) {
    string s = to_string(n);
    size_t d = s.size();
    vector<size_t> idx(d);
    iota(idx.begin(), idx.end(), 0);          // idx = {0,1,...,d-1}
    return all_of(idx.begin(), idx.end(),
                  [&](size_t i){ return s[i] == s[d-1-i]; });
}

all_of AND-folds "does character i mirror character d-1-i?" over all positions — true only if every mirror-pair matches. On an empty index list it is vacuously true, but to_string never yields an empty string so we never hit that. Test values:

• n = 0 → s = "0", r = "0" → equal compares one char, matches → true.
• n = 12321 → s = "12321", r = "12321" → true.
• n = 12345 → s = "12345", r = "54321" → first pair '1' vs '5' differs → false. Cost: let $d$ = number of digits ($d=\lfloor {\log }_{10}n\rfloor +1$). to_string is $O(d)$, the reversed copy is $O(d)$, equal is $O(d)$. Total $O(d)=O(\log n)$ — see Time complexity Big-O. All cases covered: single digit (always true), even/odd digit counts (equal handles both), leading-zero worry (there is none — integers have no leading zeros).

all_of sees one element at a time, so we hand it the index of each left-hand neighbour and let the predicate look at both v[i] and v[i+1]. The predicate must fail only on a strict decrease:

#include <vector>
#include <algorithm>   // all_of
#include <numeric>     // iota
using namespace std;
 
bool sortedNondec(const vector<int>& v){
    if (v.size() < 2) return true;             // empty / single -> vacuously sorted
    vector<size_t> idx(v.size() - 1);          // one slot per adjacent pair
    iota(idx.begin(), idx.end(), 0);           // idx = {0,1,...,n-2}
    return all_of(idx.begin(), idx.end(),
                  [&](size_t i){ return v[i] <= v[i+1]; });  // no descent
}

all_of AND-folds "is each pair non-decreasing (v[i] <= v[i+1])?" — it short-circuits at the first descent. This is exactly what the library's is_sorted computes internally; here we build it so the mechanism is visible.

• {1, 3, 3, 5}: pairs (1,3),(3,3),(3,5) all satisfy <= (note 3 <= 3 is true, equal neighbours allowed) → true.
• {1, 3, 2, 5}: pair (3,2) fails 3 <= 2 → all_of returns false. Cost: one pass, $n-1$ predicate calls ⇒ $O(n)$, far cheaper than the $O(n\log n)$ of re-sorting — and it detects disorder instead of erasing it. Edge cases: empty vector and single element return true (guarded by v.size() < 2, matching vacuous "sorted"). Using <= (not <) in the predicate is what allows equal adjacent values in a non-decreasing sequence.

Empty range: all_of ::: true Empty range: any_of ::: false find miss on a 4-element vector, then it - begin() ::: 4 (the size / end() position) accumulate(v, 0.0) vs accumulate(v, 0) on doubles ::: 0.0 keeps precision; 0 truncates each partial sum to int What grows an empty destination during copy/transform? ::: back_inserter(dst) (from <iterator>) — it push_backs each write Compare forward vs reversed digit sequence ::: std::equal(s.begin(), s.end(), r.begin()) Preserve original before sorting ::: copy (or copy-construct) then sort the copy