Question bank — STL algorithms — sort, find, transform, accumulate, copy, all_of, any_of

auto it = find(v.begin(), v.end(), 7);
if (it == nullptr) { /* not found */ }
``` ::: `find` returns an **iterator**, never a pointer, so the "absent" sentinel is `v.end()`, not `nullptr`. Fix: `if (it == v.end())`.
 
```cpp
vector<int> dst;
copy(src.begin(), src.end(), dst.begin());
``` ::: `dst` has size 0, so `dst.begin() == dst.end()` — there are no slots to assign into (undefined behaviour). Fix: `copy(src.begin(), src.end(), back_inserter(dst));`.
 
```cpp
double avg = accumulate(v.begin(), v.end(), 0) / v.size();
``` ::: Two bugs: `init = 0` truncates a `double` sum to `int`, and `v.size()` is unsigned so the division is integer division. Fix: `accumulate(..., 0.0) / v.size()` (or cast).
 
```cpp
auto end2 = find(v.begin(), v.end(), x);
size_t idx = end2 - w.begin();
``` ::: The iterator came from range `v` but is subtracted from a **different** container `w`'s `begin()`. Index arithmetic is only meaningful within the *same* container. Fix: subtract `v.begin()`.
 
```cpp
sort(v.begin(), v.end(), [](int a, int b){ return a >= b; });
``` ::: `>=` returns `true` for equal elements, violating strict weak ordering (`cmp(a,a)` must be `false`). Fix: use `>` for descending order.
 
```cpp
transform(a.begin(), a.end(), b.begin(), out.begin(), plus<>{});
// a has 5 elements, b has 3
``` ::: The binary `transform` reads from `b` in lockstep with `a` but only stops at `a.end()`; with `b` shorter it walks past `b`'s end — undefined behaviour. The two input ranges must be at least as long as the first.
 
```cpp
list<int> L{3,1,2};
sort(L.begin(), L.end());
``` ::: `std::sort` requires random-access iterators; a list only offers bidirectional ones, so this won't compile. Fix: `L.sort();` (the member function).
 
---
 
## Why questions
 
Why is the range half-open `[first, last)` rather than `[first, last]`? ::: So the size is exactly `last - first` (no `+1`), an empty range is naturally `first == last`, and "not found" can return the always-valid sentinel `last`. See [[Iterators and ranges]].
 
Why does `transform` return "one past the last written" element instead of nothing? ::: So you can **chain**: that iterator is exactly where the next algorithm should start writing, keeping the whole library consistent with the `[first, last)` philosophy.
 
Why must `accumulate`'s `init` be the operation's *identity*? ::: The fold starts from `init` and applies `op` to every element. For `+` the identity is `0`; for `*` it's `1`. A wrong `init` (e.g. `0` for a product) poisons the whole result to `0`.
 
Why do we say STL algorithms are "declarative"? ::: You state **what** you want (`sort`, `find`, `all_of`) instead of hand-writing **how** to loop. That removes off-by-one bugs and makes intent readable at a glance — the parent's core "big picture" idea.
 
Why can `sort` guarantee $O(n\log n)$ worst case when quicksort alone can't? ::: `std::sort` is **introsort**: it starts as quicksort but detects bad recursion depth and switches to heapsort, which is $O(n\log n)$ worst case. See [[Time complexity Big-O]].
 
Why does passing a *functor* sometimes beat a plain function pointer to `sort`? ::: A function object's `operator()` can be **inlined** by the compiler (its type is known at compile time), while a function pointer often forces an indirect call. See [[Function objects (functors)]].
 
Why prefer `all_of(...)` over a hand-written loop with a flag? ::: It names the intent ("are all even?"), short-circuits automatically, and can't have the classic bug of forgetting to `break` or initialising the flag wrong.
 
---
 
## Edge cases
 
`sort` on a range of size 0 or 1 — what happens? ::: Nothing to reorder; it's a valid no-op. Algorithms are written so degenerate ranges "just work" thanks to the `[first, last)` convention.
 
`accumulate` over an empty range — what comes back? ::: Exactly `init`, untouched. The fold applies `op` zero times, so the starting value is the answer.
 
`find` on an empty range — what does it return? ::: `last` (which equals `first` here), i.e. "not found", consistent with the general sentinel rule.
 
`copy` when source and destination are the **same** range — safe? ::: Copying onto itself with identical iterators is harmless, but **overlapping** ranges where `dest` is inside `[first, last)` and ahead of `first` is undefined — use `copy_backward` or `std::move` semantics carefully.
 
`all_of` when the range has exactly one failing element at the very front — cost? ::: $O(1)$ effective: it short-circuits on the first element and returns `false` immediately without scanning the rest.
 
`transform` with `dest` pointing into the middle of the source range — safe? ::: Not generally. In-place is only guaranteed safe when `dest == first` (element read then written before advancing). An overlapping offset can clobber not-yet-read inputs — undefined behaviour.
 
`any_of` on a range where the predicate throws for some element before a match — what happens? ::: The exception propagates out of `any_of` immediately; there is no "swallow and continue." Predicates should be total (not throw) for these quantifiers.
 
The C++20 ranges versions (`std::ranges::sort(v)`) — what boundary annoyance do they remove? ::: You pass the container directly instead of `v.begin(), v.end()`, eliminating mismatched-iterator bugs (mixing `v.begin()` with `w.end()`). See [[Ranges library (C++20)]].
 
---
 
> [!recall]- One-line survival rules
> Range is `[first, last)` — last excluded ::: Size is `last - first`, empty is `first == last`, "not found" is `last`.
> `find` fails with ::: `last`, never `nullptr`.
> `accumulate` result type is ::: the type of `init` — use `0.0` for doubles.
> `copy` into empty vector needs ::: `back_inserter(dst)`.
> `all_of` on empty is ::: `true` (vacuous); `any_of` on empty is `false`.
> `sort` needs ::: random-access iterators (not on `std::list`).