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

Algorithm: ==sort== — specifically sort(v.begin(), v.end()). Returns: kuch nahi (void). Ye elements ko in place rearrange karta hai; container khud result hai. Baaki kyun nahi? find ek element locate karta hai, transform ek function map karta hai, copy duplicate karta hai — inme se koi bhi reorder nahi karta. Sirf sort hi ek range ko reorder karta hai.

Algorithm: ==all_of== with predicate [](int s){ return s >= 40; }. Returns: ek bool. true sirf tab jab har element pass kare; ek empty vector pe ye true return karta hai (vacuous truth — koi failing student exist nahi karta). any_of ye answer deta ki "kya kam se kam ek passer hai", jo alag sawaal hai.

#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}

a > b kyun? Comparator cmp(a,b) ko true return karna chahiye jab a ko b se pehle aana chahiye. "Bada pehle aata hai" exactly a > b hai, jo descending order deta hai. Default operator< ascending deta hai. Neeche comparator figure dekho.

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

0 ke saath bug: accumulator ka type init ke type ke barabar hota hai. int init = 0 ke saath, har partial sum ek int mein store hota hai: $0+1.5\to 1$ (truncated), $1+2.5\to 3$, $3+3.0\to 6$. Tumhe 6 milta, 7.0 nahi. Fix: 0.0 pass karo taaki accumulator double ho. Sahi total hai $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}

back_inserter(w) kyun? transform dest mein assign karta hai; wo container ko grow nahi karta. Kyunki w empty hai, w.begin() kisi valid jagah point nahi karta. Ek back_inserter — jo <iterator> mein defined hai — har write ko ek push_back mein convert karta hai, w ko safely grow karta hai. Cubes: $1,8,27,64,125$.

Empty range pe:

• all_of → ==true==. Ye true se AND-fold karta hai: $\text{true}\wedge (\text{nothing})=\text{true}$. Koi element counterexample nahi ho sakta, isliye "all pass" vacuously hold karta hai.
• any_of → ==false==. Ye false se OR-fold karta hai: $\text{false}\vee (\text{nothing})=\text{false}$. Koi element nahi hai jo ise true kare. Mental model: all_of $\wedge$ hai identity true ke saath; any_of $\vee$ hai identity false ke saath. Start value hi empty-range answer hai — fold figure dekho.

25 v mein nahi hai, isliye find v.end() return karta hai — last element se ek aage. Tab $\text{idx}=\text{v.end()}-\text{v.begin()}=\text{size}=4.$ Toh idx == 4. Khatre ki baat: code ne pehle it != v.end() check nahi kiya. Silently 4 produce ho gaya, ek index jo real position jaisa lagta hai lekin actually "not found" sentinel hai jo number mein convert ho gaya. Dereference ya position measure karne se pehle hamesha if (it != v.end()) test karo.

accumulate ek left fold hai: ye op(acc, e) apply karta hai left se right chalte hue, init se start karke. ${\text{acc}}_0=10,{\text{acc}}_1=10-1=9,{\text{acc}}_2=9-2=7,{\text{acc}}_3=7-3=4.$ Result = 4. Direction kyun matter karta hai: subtraction associative nahi hai. Ek right fold $1-(2-(3-10))$ alag number deta ($1-(2-(-7))=1-9=-8$). Kyunki accumulate direction fix karta hai (left), op evaluate hota hai ((10-1)-2)-3 ki tarah. Jab bhi non-+ op pass karo, commutativity/associativity assume mat karo.

Idea: har element ko khud map karo agar >4 ho, warna 0, phir sum karo.

#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

Rakhe gaye: $7,9,5$. Sum $=7+9+5=21$. Ye pipeline kyun? transform unhe elements ko zero kar deta hai jo hum nahi chahte (0 + ka identity hai, isliye wo sum mein vanish ho jaate hain), aur accumulate unhe fold karta hai. Alternatively ek custom op a + (b>4 ? b : 0) ke saath accumulate ek pass mein kaam karta hai — wahi 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}. "Sorted hai kya?" check true hai — sort ke baad by construction non-decreasing hai. v abhi bhi {3,8,3,5,8,1} ke barabar hai. copy pehle kyun? sort in place mutate karta hai. Original preserve karne ke liye tumhe ek duplicate sort karna hoga; copy with back_inserter woh duplicate ek empty vector mein safely build karta hai.

#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
    // Forward aur reversed digit sequences ko element-by-element compare karo:
    return equal(s.begin(), s.end(), r.begin());   // true iff every position matches
}

std::equal(first1, last1, first2) dono ranges ko lockstep mein chalata hai aur true return karta hai tab aur sirf tab jab har corresponding elements ka pair equal ho — exactly wahi "aage se aur peeche se same padhna" test hai. Kyunki r s ka reverse hai, equal tab succeed karta hai jab s palindrome ho. all_of-based cross-check (same idea by index): position i position d-1-i se match karni chahiye.

#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 "kya character i character d-1-i ko mirror karta hai?" ko saare positions ke upar AND-fold karta hai — true sirf tab jab har mirror-pair match kare. Ek empty index list pe ye vacuously true hota, lekin to_string kabhi empty string nahi deta isliye hum wahan pahunch hi nahi sakte. Test values:

• n = 0 → s = "0", r = "0" → equal ek char compare karta hai, match → true.
• n = 12321 → s = "12321", r = "12321" → true.
• n = 12345 → s = "12345", r = "54321" → pehla pair '1' vs '5' differ karta hai → false. Cost: maano $d$ = number of digits ($d=\lfloor {\log }_{10}n\rfloor +1$). to_string $O(d)$ hai, reversed copy $O(d)$ hai, equal $O(d)$ hai. Total $O(d)=O(\log n)$ — Time complexity Big-O dekho. Saare cases covered: single digit (hamesha true), even/odd digit counts (equal dono handle karta hai), leading-zero ki chinta (koi nahi — integers mein leading zeros nahi hote).

all_of ek time pe ek element dekhta hai, isliye hum ise har left-hand neighbour ka index dete hain aur predicate ko v[i] aur v[i+1] dono dekhne dete hain. Predicate sirf ek strict decrease pe fail karna chahiye:

#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 "kya har pair non-decreasing (v[i] <= v[i+1]) hai?" ko AND-fold karta hai — ye pehle descent pe short-circuit karta hai. Ye exactly wahi hai jo library ka is_sorted internally compute karta hai; yahan hum ise build karte hain taaki mechanism visible ho.

• {1, 3, 3, 5}: pairs (1,3),(3,3),(3,5) sab <= satisfy karte hain (note 3 <= 3 true hai, equal neighbours allowed hain) → true.
• {1, 3, 2, 5}: pair (3,2) 3 <= 2 fail karta hai → all_of false return karta hai. Cost: ek pass, $n-1$ predicate calls ⇒ $O(n)$, re-sorting ke $O(n\log n)$ se bahut sasta — aur ye disorder ko erase karne ki jagah detect karta hai. Edge cases: empty vector aur single element true return karte hain (v.size() < 2 se guarded, vacuous "sorted" se match karta hai). Predicate mein <= (< nahi) use karna hi woh hai jo non-decreasing sequence mein equal adjacent values allow karta hai.

Empty range: all_of ::: true Empty range: any_of ::: false 4-element vector pe find miss, phir it - begin() ::: 4 (size / end() position) accumulate(v, 0.0) vs accumulate(v, 0) doubles pe ::: 0.0 precision rakhta hai; 0 har partial sum ko int mein truncate karta hai copy/transform ke dauran ek empty destination ko kya grow karta hai? ::: back_inserter(dst) (<iterator> se) — ye har write ko push_back karta hai Forward vs reversed digit sequence compare karo ::: std::equal(s.begin(), s.end(), r.begin()) Sort karne se pehle original preserve karo ::: copy (ya copy-construct) karo phir copy ko sort karo