Variadic templates — parameter packs, fold expressions: Visual walkthrough

5.2.16 · D2 · Coding › C++ Programming › Variadic templates — parameter packs, fold expressions

Hum folds ke baare mein ek sabse important fact derive karenge: $(x s + \dots) turns x_{1}, x_{2}, \dots, x_{n} into one value, nesting from the right.$

Iske saath saath tum dekhoge kyun left aur right matter karta hai, aur kya toot jaata hai jab pile empty hoti hai.

Step 1 — "Arguments ki pile" kya hoti hai?

KYA: hum pile ko ek naam dete hain, xs, aur har box ko label karte hain.

KYUN: kisi cheez ko fold karne ke liye pehle usse point karna zaroori hai. Koi bhi operator pile ko touch kare usse pehle, hum agree karte hain ki xs ek number nahi hai — yeh numbers ki ek row hai. (xs ko single value ki tarah treat karna parent note mein beginners ki #1 galti hai.)

PICTURE: ek row mein teen chalk boxes, har ek par uski position tag ke saath.

Figure — Variadic templates — parameter packs, fold expressions

C++ mein yeh pile ek template parameter pack se janam leti hai:

\underbrace{\texttt{auto sum(Ts... xs)}}_{\text{xs = pile of values}}$$ - `typename... Ts` — naam ke **pehle** `...` ka matlab hai *types ki pile declare karo*. - `Ts... xs` — **values** ki pile declare karo jiska naam `xs` hai. --- ## Step 2 — Operator `+` kya chahta hai? > [!definition] Binary operator > **Binary operator** ek aisa symbol hai jo exactly **do** cheezein khaata hai aur **ek** return karta hai. > Plus yahi karta hai: $a + b \to$ ek number. "Binary" ka sirf matlab hai "do leta hai". Dekho [[Operator Overloading]] ki `+` tumhare khud ke types par bhi yahi kaam kar sakta hai. **KYA:** hum ek mismatch notice karte hain. Hamare paas $n$ boxes hain, lekin `+` sirf **do** ko ek saath swallow karna jaanta hai. **KYUN yeh tool, loop nahi?** Ek fold exactly us sawaal ka jawaab hai — *"mere paas ek operator hai jo 2 leta hai, aur n size ki pile hai — main ise n−1 baar kaise apply karoon taaki 1 result mile?"* Yahi `+ ...` automate karega. Hum `+` use karte hain (naaki for-loop) kyunki hum chahte hain ki compiler chain ko *compile time par generate* kare — runtime counter ki zaroorat nahi. **PICTURE:** `+` symbol ko ek mooh ki tarah draw kiya jaata hai jo sirf do boxes bite kar sakta hai; ek arrow dikhata hai ki do boxes ek ban jaate hain. ![[deepdives/dd-coding-5.2.16-d2-s02.png]] Toh plan force ho gaya: `+` baar baar apply karo, har baar pile ek se chhhoti hoti jaye. --- ## Step 3 — `...` kahan jaata hai, aur iska kya matlab hai? > [!definition] Fold mein ellipsis > Ek operator ke paas parentheses ke andar `...` ka matlab hai **"is operator ko pile ke har box par > repeat karo"**. Jis taraf `...` baitha hai, woh taraf puri pile mein khulti hai. **KYA:** hum fold expression likhte hain aur har piece ko label karte hain. **KYUN parentheses mandatory hain:** wahi `...` aur jagahon par bhi use hota hai (packs declare/expand karne ke liye), isliye C++ fold ke around `(...)` force karta hai taaki koi doubt na rahe. Inhe drop karna compile error hai. **PICTURE:** `(xs + ...)` expression jisme har symbol annotated hai: kaunsa part pile ko naam deta hai, kaunsa part operator hai, kaunsa part "aur aage" hai. ![[deepdives/dd-coding-5.2.16-d2-s03.png]] $$\big(\;\underbrace{xs}_{\text{the pile}}\;\underbrace{+}_{\text{operator to repeat}}\;\underbrace{\dots}_{\text{"and the rest"}}\;\big)$$ Kyunki `...` pack ke **right** side par hai, yeh ek **unary right fold** hai. "Unary" = koi extra starting value nahi; "right" = right end se shuru hoke nest karta hai. Yeh hum aage prove karte hain. --- ## Step 4 — Right fold ko nest hote dekho (core derivation) > [!formula] Unary right fold, exact meaning > $$(\,xs + \dots\,)\;=\;x_1 + \big(x_2 + (\;\dots\; + x_n)\big)$$ > Padho aise: **sabse right wala** pair pehle jodta hai, phir uske left wala agla pair uske around wrap hota hai. **KYA:** concrete pile $xs = 1, 2, 3$ lo aur use collapse karo. **KYUN right-first:** right fold mein sabse gehre parentheses **aakhri** box ko huggte hain, isliye evaluation $x_n$ se shuru hoke left ki taraf chalti hai. Daayein taraf ka `...` tumhara visual cue hai: *woh* taraf sabse gehri jaati hai. **PICTURE:** teen frames. Frame 1: puri nesting $1 + (2 + 3)$ jisme sabse inner pair circled. Frame 2: inner pair $5$ mein collapse hota hai. Frame 3: outer pair $6$ mein collapse hota hai. ![[deepdives/dd-coding-5.2.16-d2-s04.png]] Term by term:

(xs + \dots);\to; \underbrace{1}{x_1} + \big(\underbrace{2}{x_2} + \underbrace{3}{x_3}\big) ;=; 1 + \underbrace{5}{\text{rightmost pair first}} ;=; \boxed{6}

- $\;2 + 3\;$ pehle evaluate hota hai — yeh sabse gehre parentheses (right end) ke andar hai. - $\;1 + 5\;$ doosre evaluate hota hai — outer wrap. - Ek box, value $6$, bachta hai. Fold ho gaya. > [!example] Poora function > ```cpp > template<typename... Ts> > auto sum(Ts... xs) { return (xs + ...); } // sum(1,2,3) == 6 > ``` --- ## Step 5 — Kyun "left" ek *alag* machine hai (non-associative ops) > [!definition] Associative > Ek operator **associative** hota hai agar grouping se answer nahi badalta: $(a+b)+c = a+(b+c)$. > Plus associative hai, isliye Step 4 mein $6$ kisi bhi direction se milta hai. **Subtraction nahi hai.** **KYA:** wahi pile ko `-` se dono taraf fold karo aur **do alag answers** pao. **KYUN matter karta hai:** agar tum blindly `-`, `/`, ya string-building ke liye `+` fold copy karo, toh *direction* silently tumhara result badal deta hai. Left vs right choose karna ek real decision hai, decoration nahi. **PICTURE:** $1,2,3$ ke liye side by side do nesting trees: left fold **pehla** pair pehle group karta hai; right fold **aakhri** pair pehle group karta hai. Alag circled starting points → alag totals. ![[deepdives/dd-coding-5.2.16-d2-s05.png]]

\underbrace{(,\dots - xs,)}{\text{left, }...\text{ on left}} = (1 - 2) - 3 = -4 \qquad\neq\qquad \underbrace{(,xs - \dots,)}{\text{right, }...\text{ on right}} = 1 - (2 - 3) = 2

- **Left fold** $(\dots - xs)$: `...` left par → leftmost pair $1-2$ pehle bind hota hai → $-1$, phir $-1-3=-4$. - **Right fold** $(xs - \dots)$: `...` right par → rightmost pair $2-3$ pehle bind hota hai → $-1$, phir $1-(-1)=2$. > [!mnemonic] Kaunsi side gehri jaati hai? > **Dots pile ki taraf point karte hain; jis bhi side par dots hain woh side sabse gehri nest karti hai.** --- ## Step 6 — Empty pile (degenerate case) > [!definition] Empty pack > **Zero** boxes wali pile. `sum()` bina kisi argument ke call kiya. `+` ke liye kuch bhi bite karne ko nahi. **KYA:** pucho ki $(xs + \dots)$ ka kya matlab hai jab koi box nahi hai. **KYUN toot jaata hai:** `+` ko ek starting value (ek *identity*) chahiye jo empty pile par return kare. C++ standard `+` ke liye khud se koi value invent karne se mana kar deta hai, isliye empty pack par **unary** fold ek **compile error** hai. Sirf teen operators ke paas built-in empty answers hain. **PICTURE:** ek empty dashed frame. Teen operators use survive karne ki permission hai; baaki sab ek red chalk ✗ se takraate hain. ![[deepdives/dd-coding-5.2.16-d2-s06.png]] > [!formula] Sirf yahi legal empty unary folds hain > $$(\,\dots\;\&\&\;args\,)=\texttt{true},\qquad(\,\dots\;||\;args\,)=\texttt{false},\qquad(\,\dots,\,args\,)=\texttt{void()}$$ --- ## Step 7 — Fix: seed value ke saath binary fold > [!definition] Binary fold > Ek fold jisme ek starting value hoti hai jise `init` (the **seed**) kehte hain. Likha jaata hai > $(\,init + \dots + xs\,)$. Ab empty pile ka bhi ek answer hai: sirf `init`. **KYA:** $0$ ka seed add karo taaki empty sum $0$ return kare failure ki jagah. **KYUN $0$?** $0$ `+` ke liye **identity** hai — jab boxes exist hain tab kuch nahi badalta, aur "empty sum = 0" ka samjhdaar answer deta hai jab nahi hote. Yeh [[constexpr and Compile-time Computation|compile-time]] safe hai aur kabhi error nahi deta. **PICTURE:** seed box $0$ left mein rakha; boxes ek ek karke uspe jodaate jaate hain; jab pile empty hoti hai sirf seed $0$ bachta hai. ![[deepdives/dd-coding-5.2.16-d2-s07.png]]

(,\underbrace{0}_{\text{seed}} + \dots + xs,);\text{on }1,2,3 = ((0 + 1) + 2) + 3 = 6, \qquad\text{on empty} = 0

- Boxes ke saath: seed $0$ kuch cost nahi karta, answer phir bhi $6$ hai. - Empty: koi box attach nahi hota, expression *hai hi* seed → $0$. **Koi error nahi.** > [!example] Safe sum > ```cpp > template<typename... Ts> > auto safe_sum(Ts... xs) { return (0 + ... + xs); } // safe_sum() == 0 > ``` --- ## Ek-picture summary Yeh final board saaton steps compress karta hai: ek pile ko naam diya jaata hai, ek operator choose kiya jaata hai jo do khaata hai, `...` kehta hai "repeat karo", nesting direction fix hoti hai is baat se ki dots kis side par hain, empty pile trap hai, aur seed uska cure hai. ![[deepdives/dd-coding-5.2.16-d2-s08.png]] > [!recall]- Feynman retelling — poora walkthrough seedhe simple words mein > Tumhare paas boxes ki ek row hai aur poori row ke liye ek naam hai, `xs` (Step 1). Tumhare paas ek > `+` button bhi hai jo sirf **do** boxes ko ek mein squish karna jaanta hai (Step 2). `(xs + ...)` likhne > se machine ko bolta hai "poori row par `+` press karte raho" — aur **right** par dots ka matlab hai > **right** end se squishing shuru karo (Steps 3–4). Plus ke liye koi end se shuru karo koi fark nahi > padta, lekin minus ke liye bilkul padta hai: left se shuru karo toh $-4$ milta hai, right se shuru > karo toh $2$ milta hai (Step 5). Machine ko todne ka ek tarika hai isko empty row do — `+` ke paas > "kuch nahi" ka koi jawaab nahi, isliye error aata hai (Step 6). Fix hai ek starting box — seed jaise > $0$ — row mein daalna; ab empty row bhi "$0$" jawaab deti hai, aur bhari hui row phir bhi sahi > jawaab deti hai (Step 7). Poora idea yahi hai: ek two-input button, pile par repeat kiya, ek direction > jo tum choose karte ho, aur safety ke liye ek seed. > [!recall]- > Right fold `(xs + ...)` on 1,2,3 kaunsa pair pehle nest karta hai? ::: Sabse rightmost, `2 + 3`, giving `1 + (2 + 3) = 6`. > `(xs + ...)` empty pack par kyun fail hota hai? ::: `+` ke paas empty case ke liye koi identity value defined nahi hai; sirf `&&`, `||`, `,` ke paas hoti hai. > Empty-safe sum kaise banate hain? ::: Seed ke saath binary fold: `(0 + ... + xs)`. > Non-associative op jaise `-` ke liye direction carefully kyun choose karo? ::: Left aur right alag results dete hain, jaise $-4$ vs $2$. --- Related: [[Function Templates]] · [[Templates and Generics]] · [[Recursion]] · [[std::tuple]] · [[Perfect Forwarding]] · [[Operator Overloading]]