Iterators — input, output, forward, bidirectional, random access, contiguous: Worked examples

5.2.21 · D3 · Coding › C++ Programming › Iterators — input, output, forward, bidirectional, random ac

Kuch bhi shuru karne se pehle, do words jo hum baar baar use karte hain:

Definition Big-O: "cost kaise badhta hai"

Poore note mein hum $O (1)$ aur $O (n)$ likhte hain — yeh describe karta hai jab container $n$ elements tak badhta hai toh ek operation mein kitna kaam lagta hai — exact machine instructions ki count nahi, bas kaam kaise scale hota hai.

$O (1)$ — "constant time": kaam $n$ ke saath nahi badhta. Ek jump, khatam. Example: vector[500].
$O (n)$ — "linear time": kaam $n$ ke saath saath badhta hai. Saare $n$ boxes visit karna, ya $n$ links hop karna.
$O (lo g n)$ — "logarithmic time": kaam bahut dhire badhta hai; $n$ ko double karne se sirf ek extra step badhta hai. Yeh ek balanced tree ki height hai — Example 3 dekho.

Kyu zaroori hai? Poora iterator hierarchy isliye exist karta hai taaki compiler har container ke liye sabse sasta scaling pick kar sake. Agar ek list sirf $O (n)$ de sakti hai wahan $O (1)$ pick karna ek jhooth hoga jo type system batane se mana karta hai.

Scenario matrix

Har iterator exercise inhi cells mein se ek hoti hai. Hum har cell ko ek labelled example se cover karenge. "Negative move" cell mein hume aisa iterator chahiye jo peeche step kar sake — matlab bidirectional, random access, ya contiguous category (woh teen jo --it define karte hain).

Cell	Kya special hai	Degenerate / limit uske andar
A. Positive move, random access	`it += n`, ek $O (1)$ jump	`n = 0` (koi move nahi)
B. Positive move, bidirectional	loop `++it` karna padega, $O (n)$	exactly `end()` pe pahunchna
C. Negative move	`--it`, sirf bidirectional / random access / contiguous pe legal	`begin()` se pehle step nahi karna
D. Single-pass input	ek baar padho, wapas nahi ja sakte	copy-then-advance dusre ko invalidate karta hai
E. Output only	write-only, koi `==` nahi, koi end nahi	kitna likhna hai yeh jaanna
F. Contiguous vs merely random	`&(it+n) == &it + n`	`deque` isse tod deta hai
G. Empty / one-element range	`begin() == end()`	distance $= 0$ ; `--end()` illegal
H. Word problem	minimum category pick karo	over-constraining ek design bug hai
I. Exam twist	kaun si line compile nahi hogi aur kyun	tag-dispatch reasoning

Example 1 — Cell A: `vector` pe positive jump (aur `n = 0` limit)

Worked example Statement

std::vector<int> v{10, 20, 30, 40, 50};
auto it = v.begin();
std::advance(it, 3);      // 3 aage move karo
int a = *it;
std::advance(it, 0);      // 0 move karo — degenerate
int b = *it;

a aur b kya hain?

Forecast: aage padhne se pehle dono values guess karo.

v.begin() index 0 ko point karta hai, value 10. Yeh step kyun? Har walk ko ek known starting anchor chahiye; begin() by definition index 0 hai.
advance(it, 3) ek random-access iterator pe it += 3 ban jaata hai — index 3 tak ek single $O (1)$ jump. Yeh step kyun? Parent ka tag dispatch vector ke liye random_access overload pick karta hai. Kyunki vector ek flat block hai, address arithmetic index 3 ko bina index 1 ya 2 touch kiye dhundh leta hai — isliye cost constant rehti hai ( $O (1)$ ) chahe vector kitna bhi bada ho. Index $0 + 3 = 3$ , value 40. Toh a = 40.
advance(it, 0) zero steps move karta hai — loop body kabhi nahi chalta / it += 0 ek no-op hai. Yeh step kyun? Degenerate n = 0 ko iterator ko exactly wahan rakhna chahiye jahan tha; b = *it = 40.

Verify: index arithmetic $0 + 3 + 0 = 3$ ; v[3] = 40, toh a == b == 40. begin() se final it tak ki distance 3 hai. ✓

Example 2 — Cell B + G limit: `list` ko `end()` tak exactly walk karna

Worked example Statement

std::list<int> L{7, 8, 9};      // 3 elements
auto it = L.begin();
std::advance(it, 3);            // exactly end() pe land karo
bool atEnd = (it == L.end());

Kya it == L.end() true hai, aur actually kitne ++ operations chale?

Forecast: ++ calls ki number aur boolean guess karo.

list iterators sirf bidirectional hain, toh advance looping overload pick karta hai: while(n--) ++it;. Yeh step kyun? Linked list ke paas koi contiguous block nahi hai, toh koi += nahi; tumhe physically node by node hop karna padega — aur kyunki $n$ steps move karne ki cost $n$ separate hops hai, kaam $n$ ke saath badhta hai: yeh list ki $O (n)$ (linear) reality hai.
Loop n = 3 ke liye chalta hai: ++it 3 baar execute hota hai, last element ke ek baad land karke. Yeh step kyun? Size 3 ke container mein valid positions $0, 1, 2$ hain aur sentinel end() "position 3" pe hai. begin() se 3 baar step karne se exactly end() pe pahuncho.
it == L.end() true hai. Yeh step kyun? Yeh limit case hai: end() legal stopping point hai. Yahan *it read karna undefined hoga, lekin compare karna theek hai.

Figure aise samjho: bottom row ke teen mint boxes real elements hain positions 0, 1, 2 pe jo 7, 8, 9 hold karte hain. Bilkul right ki taraf butter box, position 3 pe end() label ke saath, sentinel hai — notice karo uske andar koi value nahi hai, yeh tumhara visual reminder hai ki ise dereference karna illegal hai. Position 0 pe girne wali lavender arrow woh jagah hai jahan begin() start hota hai. Ab top pe teen curved coral arrows count karo: har ek ek ++ hai. Unhe left se right trace karo aur dekho teesri arrow squarely empty end() box pe land kari — yeh landing poora answer hai. Yeh dono dikhata hai ki exactly teen ++ calls chale (teen arrows) aur kyun atEnd true hai (last arrow sentinel pe pahunchti hai, uske past nahi).

Figure — Iterators — input, output, forward, bidirectional, random access, contiguous

Verify: ++ calls ki number $= 3 =$ L ki size; distance begin()→end() size ke barabar hai, toh atEnd == true. ✓

Example 3 — Cell C: `bidirectional` pe negative move, `begin()` guard karna

Worked example Statement

std::set<int> s{5, 15, 25, 35};   // sorted: 5 15 25 35
auto it = s.end();
std::advance(it, -2);             // do baar peeche step karo
int val = *it;

val kya hai?

Forecast: end() se do backward steps kaunse element pe land karte hain?

set bidirectional hai, toh negative n while(n++) --it; pick karta hai. Yeh step kyun? Sirf bidirectional-or-better iterators -- define karte hain. Ek std::set ek balanced binary search tree mein store hota hai, aur --it in-order predecessor node pe jaata hai. Woh walk tree ke upar ya neeche ja sakta hai, toh iska worst-case cost tree height ke proportional hota hai, jo ek balanced tree ke liye $O (lo g n)$ hai — sasta, lekin not woh $O (1)$ jo vector deta hai. (Ek full front-to-back traversal har node ko exactly ek baar visit karta hai, toh yeh kul $O (n)$ total hai; baat yeh hai ki ek single -- tree height se bounded hai, constant nahi.) Kisi bhi tarah -- yahan legal hai, yahi Cell C ko chahiye.
end() last element 35 ke ek past hai. Pehla --it 35 pe land karta hai. Yeh step kyun? Tumhe kabhi end() dereference nahi karna chahiye, lekin tum ise decrement kar sakte ho — pehla -- real last element pe move karta hai.
Doosra --it 25 pe land karta hai. Yeh step kyun? Sentinel se do backward steps: 35 → 25. Toh val = 25.
Degenerate guard: hum room ke saath ruke. Agar humne advance(it, -5) likhte ek 4-element set ke end() se, toh hum begin() se pehle step karte — undefined behaviour. Yeh step kyun? Cell C ka chupaaya hua trap: backward moves range ko underflow nahi karne chahiye; standard koi safety net nahi deta.

Verify: sorted set {5,15,25,35}; end() se do steps peeche → element index size - 2 = 2 pe → value 25. ✓

Example 4 — Cell D: single-pass input, copy invalidate karta hai

Worked example Statement

std::istringstream ss("100 200 300");
std::istream_iterator<int> it(ss), end;
auto copy = it;      // ek "backup" banao
int first  = *it;    // padho
++it;                // ORIGINAL ko advance karo
int viaCopy = *copy; // backup padho — kya aayega?

viaCopy kya hai (bahut se beginners 100 expect karte hain)?

Forecast: viaCopy guess karo aur kya copy bharosemand hai.

istream_iterator ek input iterator hai: single-pass. Yeh step kyun? Yeh ek stream ka thin wrapper hai jo characters already consume kar chuka hai — koi rewind nahi hai, jo iske `iterator_category` input_iterator_tag hone se match karta hai.
*it 100 read karta hai lekin abhi remove nahi karta; first = 100. Yeh step kyun? Pehla token tab buffer mein aa gaya tha jab iterator construct hua tha.
++it shared stream se agla token consume karta hai. Yeh step kyun? Dono it aur copy ek hi underlying ss pe hain. Kisi ek ko advance karna dono ke liye stream move karta hai — copies input iterators ke liye independent nahi hote.
Advance ke baad *copy safe nahi hai use karna. Yeh step kyun? Standard ke input-iterator requirements (Cpp17InputIterator rules, [input.iterators]) validity sirf single pass ke liye guarantee karte hain: jab tum input iterator ki kisi bhi copy ko increment karo, baaki saari copies invalidate ho jaati hain, aur invalidated iterator ko dereference karna undefined behaviour hai — matlab program ka koi defined meaning hi nahi hai (yeh 200 print kar sakta hai, garbage print kar sakta hai, ya crash ho sakta hai). Yeh unspecified behaviour se zyada strong hai, jahan tumhe kam se kam koi valid value milti ek known set mein se. Safe conclusion hai: copy ko advance karne ke baad kabhi mat padho. Sirf forward iterators is guarantee ko multi-pass tak upgrade karte hain, jahan copies independent hoti hain.

Verify: checkable facts hain first == 100, aur category input (single-pass) hai, toh copy ke baare mein multi-pass reasoning invalid hai. ✓

Example 5 — Cell E: output-only, tumhe writes count karni hongi

Worked example Statement

std::vector<int> dst;                       // empty
auto out = std::back_inserter(dst);         // output iterator
for (int x : {1, 2, 3, 4}) { *out = x; ++out; }
int n = dst.size();

n kya hai, aur hum while (out != someEnd) kyun nahi likh sakte?

Forecast: dst.size() guess karo aur kyun koi end check nahi hai.

back_inserter ek pure output iterator hai. Yeh step kyun? *out = x ka matlab hai dst.push_back(x); koi == nahi, koi end sentinel nahi. Tum "kya main done hun?" nahi pooch sakte — tumhe count khud jaanna padega (yahan 4 loop items hain).
Har *out = x; ++out; ek element append karta hai. Yeh step kyun? Output iterators exactly *it = v aur ++it support karte hain; ++ ek formality hai (back-inserters ke liye no-op hai) jo algorithm ki shape uniform rakhti hai.
4 writes ke baad, dst = {1,2,3,4}, toh n = 4. Yeh step kyun? Likhi gayi count source items ki count ke barabar hai — ek maatra "length" information jo available hai.

Verify: ek empty vector mein 4 writes dst.size() == 4 aur dst == {1,2,3,4} dete hain. ✓

Example 6 — Cell F: contiguous apna promise rakhta hai, `deque` nahi rakhta

Worked example Statement

std::vector<double> v{1.0, 2.0, 3.0, 4.0};
bool vecOK = (&*(v.begin() + 2) == &*v.begin() + 2);

Kya vecOK true hai? Aur kya deque pe wahi test guaranteed hoga?

Forecast: boolean aur deque verdict guess karo.

vector contiguous hai, toh iske elements ek block mein rehte hain: element $k$ ka address base + k * sizeof(double) hai. Yeh step kyun? Contiguity woh ek guarantee hai jo random access se upar hai — parent ki table row "contiguous storage guarantee" dekho.
&*(v.begin()+2) v[2] ka address hai; &*v.begin() + 2 base address plus 2 elements hai. Yeh step kyun? Hum "iterator walk karo phir address lo" vs "base address lo phir 2 add karo" compare kar rahe hain — contiguity kehti hai yeh identical hain. Toh vecOK = true.
Ek deque it[2] $O (1)$ mein support karta hai (random access) lekin element 2 ek alag chunk mein store ho sakta hai. Yeh step kyun? Random access pointer arithmetic ke liye necessary but not sufficient hai. deque pe address equality silently fail kar sakti hai, isliye tum &v[0] (contiguous) to C API ko de sakte ho jo flat array expect kari ho lekin kabhi &deque[0] nahi — yeh fact pointer arithmetic se flow karta hai.

Figure aise samjho: dono rows ko box-for-box compare karo. Top lavender row vector hai. Iske char boxes v[0]..v[3] edge to edge hain bina gaps ke, aur unke neeche chhote grey labels base+0, base+1, base+2, base+3 likhte hain — perfectly linear. v[2] pe apni finger rakho aur uska label check karo: woh hai base+2, toh right side ka mint "✓" earned hai. Bottom row deque hai: do coral boxes (d[0], d[1]), phir ek labelled gap (visual cue ki ek naya memory chunk shuru hota hai), phir do butter boxes (d[2], d[3]). Ab d[2] pe apni finger rakho: woh gap ke across rehta hai, toh uska real address base+2 nahi hai — wahi tuti hui linearity hai jo coral "✗" warn karta hai. Dono rows mein ek hi difference — gap vs no gap — woh poora reason hai ki sirf contiguous storage base + n identity rakhta hai.

Verify: ek contiguous double array ke liye, &a[2] == a + 2 exactly pointer identity hai; vecOK == true. ✓

Example 7 — Cell G: empty aur single-element ranges

Worked example Statement

std::vector<int> empty;                       // size 0
int d0 = std::distance(empty.begin(), empty.end());
 
std::vector<int> one{99};                     // size 1
int d1 = std::distance(one.begin(), one.end());

d0 aur d1 kya hain? Yahan kaun sa decrement illegal hai?

Forecast: dono distances guess karo.

Empty container ke liye begin() == end() hota hai. Yeh step kyun? Koi jaghah point karne ki nahi hai, toh dono sentinels ek saath milte hain; equal iterators ke beech ki distance 0 hai. Toh d0 = 0.
Ek element ke liye, end() index 0 ke ek step past hai. Yeh step kyun? Distance = begin() se end() tak ++ ki count = size = 1. Toh d1 = 1.
Degenerate trap: empty vector pe, --empty.end() undefined hai — land karne ke liye koi element nahi hai. Yeh step kyun? Limit case: tum end() ko tabhi decrement kar sakte ho jab size >= 1 ho. Yeh Cell G ka chupaaya hua edge hai jo har exam ko pasand hai.

Verify: distance == size forward-or-better range ke liye, toh d0 == 0, d1 == 1. ✓

Example 8 — Cell H: word problem, minimum category pick karo

List the operations jo tum actually use karte ho: *it (read), ++it, it != Last. Yeh step kyun? Sahi category used operations se decide hoti hai, habit se nahi — over-constraining valid containers ko reject karta hai.
Tum kabhi peeche nahi jaate, kabhi jump nahi karte, har element ek baar padhte ho. Yeh step kyun? Koi --, koi +n nahi: bidirectional aur random access unnecessary hain. Single-pass read + != exactly input iterator contract hai.
Minimum = input iterator; passes = 1. Yeh step kyun? Accepted set ko random-access se input tak widen karna forward_list, istream, sab kuch work karne deta hai — yeh algorithm/iterator decoupling ka poora point hai. Teammate ka random_access constraint ek over-specification bug tha.

Verify: used operations = {read, ++, !=}; teeno provide karne wali least category input hai (multi-pass bhi required nahi), toh minimum category index = 1 (input), passes = 1. ✓

Example 9 — Cell I: exam twist, kaun si line fail hoti hai aur kyun

Worked example Statement

std::list<int> L{2, 4, 6, 8};
auto a = L.begin();
auto b = a + 2;                            // line X
std::advance(a, 2);                        // line Y
int gap = std::distance(L.begin(), a);     // line Z

X / Y / Z mein se exactly ek compile nahi hota. Kaun si line, kyun, aur — ise delete karne ke baad — gap kya hai?

Forecast: failing line ka naam batao aur gap ki value.

Line X a + 2 use karta hai. Yeh step kyun? Iterators pe + operator sirf random-access (aur contiguous) iterators ke liye exist karta hai. list iterator bidirectional hai, toh yeh ++/-- define karta hai lekin operator+ nahi. a + 2 ke liye koi valid overload nahi hai, toh compiler line X reject karta hai. Yahi failing line hai.
Line Y std::advance(a, 2) theek compile hoti hai. Yeh step kyun? advance sabhi iterator categories ke liye tag dispatch ke zariye defined hai; bidirectional iterator ke liye yeh silently ++a ko do baar loop karne pe fall back karta hai ( $O (n)$ ). Yeh kabhi operator+ nahi maangta, toh yeh wahan succeed karta hai jahan line X nahi kar sakta tha — yeh exactly parent note ka advance workaround hai.
Line Z std::distance(L.begin(), a) bhi compile hoti hai. Yeh step kyun? distance bhi category pe dispatch karta hai aur bidirectional ke liye ++ steps count karta hai; ise koi operator- nahi chahiye. Toh Z bhi theek hai.
Line X delete karo aur run karo. advance(a, 2) ke baad, a index 2 pe baitha hai (value 6), aur distance(begin(), a) 2 steps count karta hai. Yeh step kyun? Yeh intended answer confirm karta hai: sirf line X fail hoti hai, aur remove karne ke baad, gap = 2 aur *a == 6.

Verify: illegal + hatane ke baad, advance(a,2) a ko index 2 pe rakhta hai, toh gap == 2 aur *a == 6. ✓

Active recall

Recall Quick self-test

vector pe advance(it, 0) kya karta hai? ::: Kuch nahi — degenerate zero move iterator ko unchanged chhod deta hai. {5,15,25,35} ke set::end() se do -- kaunsi value dete hain? ::: 25 (index size−2). istream_iterator ki stale copy padhna kyun unsafe hai? ::: Input iterators single-pass hote hain; kisi bhi copy ko increment karna baaki sabko invalidate karta hai, aur invalidated iterator ko dereference karna undefined behaviour hai. Empty container ke liye distance(begin(), end()) kitna hota hai? ::: 0, kyunki begin() == end() hota hai. Ek range ek baar print karne ke liye minimum iterator category kaun si hai? ::: Input iterator. std::list ke liye L.begin() + 2 kyun fail hota hai? ::: operator+ sirf random-access/contiguous ke liye exist karta hai; list iterators bidirectional hain, toh unke paas koi + nahi. std::set pe single --it ka worst-case cost kya hai? ::: $O (lo g n)$ — balanced tree ki height se bounded, constant nahi. deque it[n] ko O(1) mein support karta hai — kya &*(it+n) == &*it + n guaranteed hai? ::: Nahi; us address identity ke liye contiguous category chahiye, jo deque ke paas nahi hai.