Iterators — input, output, forward, bidirectional, random access, contiguous: Exercises

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

Intuition Is page ko kaise use karein

Yeh ek self-testing ladder hai jo parent Iterators note pe bani hai. Har problem task clearly batati hai; answer ek collapsible [!recall]- box ke andar chhupa hai. Pehle khud try karo, phir reveal karo.

Levels Bloom's ladder pe chadhte hain:

L1 Recognition — kya tum category ka naam bata sakte ho?
L2 Application — kya tum sahi operation use kar sakte ho?
L3 Analysis — kya tum explain kar sakte ho kyun code compile hota ya fail karta hai?
L4 Synthesis — kya tum pieces se kuch bana sakte ho?
L5 Mastery — kya tum cost, dispatch, aur edge cases ke baare mein reason kar sakte ho?

Shuru karne se pehle, parent note se ek vocabulary reminder jo tumhare paas honi chahiye. Ek iterator ek "generalized pointer" hai: ek object it jise tum *it se dereference kar sakte ho (us element ko dekho jis pe yeh point kar raha hai) aur ++it se advance kar sakte ho (next element pe step karo). Ek category iterator type pe ek label hai jo batata hai kaun se operations legal hain aur kitne fast hain. Chhe categories, growing power ke order mein:

$Input/Output \subset Forward \subset Bidirectional \subset RandomAccess \subset Contiguous$

Neeche sab kuch usi ladder ko test karta hai. Agar tum atak jao toh prerequisites: Pointers and pointer arithmetic, STL Containers — vector, list, deque, map, iterator_traits and type introspection.

Reference figures

Pehla figure memory picture hai — woh ek fact jo vector (contiguous) ko deque (random access but chunked) se aur list (bidirectional, scattered) se alag karta hai. L3–L5 ke liye ise saamne rakkho.

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

Doosra figure capability ladder hai — har rung neeche wale rung ke upar exactly ek naya operation add karta hai. Jab bhi koi problem pooche "kaun si category X introduce karti hai?" toh ise refer karo.

L1 — Recognition

Recall Solution 1.1

(a) std::vector<int> → Contiguous — elements ek hi memory block mein hote hain. (b) std::list<int> → Bidirectional — ek doubly-linked list ++ aur -- step kar sakti hai, lekin jump nahi kar sakti. (c) std::deque<int> → RandomAccess — it + n $O (1)$ hai, lekin memory chunked hai, isliye contiguous nahi hai. (d) std::set<int> → Bidirectional — yeh ek balanced tree hai; tum dono directions mein walk kar sakte ho lekin index nahi kar sakte. (e) std::forward_list<int> → Forward — singly-linked, isliye yeh sirf aage step kar sakta hai aur re-traverse kar sakta hai.

Recall Solution 1.2

(a) std::istream_iterator<int> → Input — read-only, single-pass; har ++ stream se ek token pull karta hai. (b) std::ostream_iterator<int> → Output — write-only; *it = x print karta hai, ++it ek no-op hai. (c) std::back_insert_iterator → Output — *it = x container pe push_back(x) call karta hai; koi reading nahi, koi equality nahi.

Recall Solution 1.3

--it → Bidirectional (backward stepping).
it[n] → RandomAccess ( $O (1)$ indexing).
*it = v write → Output (writing output ki defining power hai; Forward ise rakhta hai).
multi-pass re-read → Forward (tum copy kar sakte ho aur revisit kar sakte ho).
&*(it+n) == &*it + n → Contiguous (linear address guarantee).

L2 — Application

Recall Solution 2.1

(a) vector (random access): it += 5; — ek single $O (1)$ pointer jump. (b) list (bidirectional): std::advance(it, 5); — internally ++it paanch baar loop karta hai, $O (5)$ . it += 5 compile nahi hoga. (c) istream_iterator (input): std::advance(it, 5); — ++it loop karta hai, 5 tokens consume karta hai, $O (5)$ , single-pass. Tum kabhi wapas nahi ja sakte.

std::advance har jagah safe choice hai; yeh tag dispatch use karta hai (dekho Templates and Tag Dispatch) jo automatically $O (1)$ vs $O (n)$ pick karta hai.

Recall Solution 2.2

(a) v.end() - v.begin() = 10, $O (1)$ mein compute hota hai: random-access iterators pointers jaisi subtract karte hain. (b) L.end() - L.begin() fail hoti hai kyunki subtraction ke liye random access chahiye. std::distance(L.begin(), L.end()) use karo = 10, $O (10)$ mein ++ steps count karke compute hota hai.

Recall Solution 2.3

std::sort(v.begin(), v.end()); — kaam karta hai kyunki std::sort ko random access chahiye (yeh partitioning karte waqt idhar-udhar jump karta hai).
L.sort(); — free std::sort L pe compile nahi hoga (sirf bidirectional), isliye list apna member sort laata hai jo pointer jumps ki jagah node pointers rewire karta hai.

L3 — Analysis

Worked example Problem 3.1 — Ek line compile kyun hoti hai aur doosri nahi?

std::vector<int> v{10,20,30,40};
std::list<int>   L{10,20,30,40};
auto a = v.begin() + 2;   // (A)
auto b = L.begin() + 2;   // (B)

Precisely explain karo kyun (A) compile hoti hai aur (B) compile error hai. *a kya hai?

Recall Solution 3.1

(A) compile hoti hai kyunki vector::iterator contiguous → random access hai, isliye yeh operator+(iterator, int) overload karta hai. *a == 30 (index 2 pe element). (B) fail hoti hai kyunki list::iterator bidirectional hai: yeh ++ aur -- define karta hai lekin operator+ nahi. Scattered nodes ke upar $O (1)$ mein n steps jump karne ka koi tarika nahi, isliye language syntax bhi provide nahi karta. Sahi rewrite hai auto b = L.begin(); std::advance(b, 2);.

Worked example Problem 3.2 — Contiguous vs random-access C-API trap

void c_api(double* data, int n);         // expects a raw array
std::vector<double> v{1,2,3,4};
std::deque<double>  d{1,2,3,4};
c_api(&v[0], 4);   // (A)
c_api(&d[0], 4);   // (B)

Kaun si call safe hai aur kaun si undefined behaviour hai? Memory picture (figure 1) use karke justify karo.

Recall Solution 3.2

(A) c_api(&v[0], 4) safe hai. vector contiguous hai: uske chaar doubles ek linear block mein hain, isliye &v[0] ke baad +1, +2, +3 real elements pe land karta hai — exactly &*(it+n) == &*it + n. (B) c_api(&d[0], 4) undefined behaviour hai. deque random-access lekin chunked hai (figure 1, right): elements 0–1 ek block mein ho sakte hain aur 2–3 doosre mein. &d[0] + 2 pehle block ke off-the-end area ko point karta hai, d[2] ko nahi. Random access ≠ contiguous.

Worked example Problem 3.3 — Single-pass invalidation

std::istringstream ss("5 6 7");
std::istream_iterator<int> it(ss), end;
auto copy = it;      // ek copy banao
int x = *it; ++it;   // 5 read karo, ORIGINAL ko advance karo
int y = *copy;       // y kya hai?

y mein kya value hai, aur yeh kaun sa general rule demonstrate karta hai?

Recall Solution 3.3

y wahi padhta hai jo stream original ke advance hone ke baad offer karta hai — copy invalidated ho jaati hai, isliye *copy reliably 5 wapas nahi deta. Practice mein yeh wahi value yield karta hai jo original ab dekh raha hai (ise rely karna undefined/unspecified hai). Yeh demonstrate karta hai ki input iterators single-pass hote hain: kisi bhi iterator ko advance karna stream ke upar shared underlying stream ko move karta hai, isliye copies position preserve nahi karti. Multi-pass (safe copying aur re-reading) sirf Forward se shuru hoti hai.

L4 — Synthesis

Recall Solution 4.1

template<class It>
void impl(It& it, int n, std::random_access_iterator_tag) {
    it += n;                          // O(1)
}
template<class It>
void impl(It& it, int n, std::bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++it;     // O(n) forward
    else        while (n++) --it;     // O(|n|) backward
}
template<class It>
void impl(It& it, int n, std::input_iterator_tag) {
    while (n--) ++it;                 // O(n), forward only, single-pass
}
template<class It>
void my_advance(It& it, int n) {
    impl(it, n,
         typename std::iterator_traits<It>::iterator_category{});
}

n = 0: har overload kuch nahi karta (it += 0, ya while kabhi nahi chalta). Correct no-op.
bidirectional pe negative n: else branch --it exactly |n| baar run karta hai. Ek input iterator pe negative n ill-formed hai (koi -- nahi), jo tag system correctly compile karne se refuse karta hai.

Dekho iterator_traits and type introspection ki iterator_category kaise extract hoti hai.

Recall Solution 4.2

std::copy(std::istream_iterator<int>(std::cin),   // INPUT source
          std::istream_iterator<int>(),           // end sentinel
          std::ostream_iterator<int>(std::cout, " ")); // OUTPUT sink

Kyun kaam karta hai: std::copy ko source ke liye sirf ek input iterator chahiye (read + ++) aur destination ke liye ek output iterator (*it = x + ++). Dono single-pass hain, jo sirf copy ko chahiye. Dekho STL Algorithms — sort, find, copy.

Recall Solution 4.3

Standard tool std::distance hai, jo khud tag-dispatched hai:

template<class It>
auto steps_to_end(It begin, It end) {
    return std::distance(begin, end);   // O(1) if random access, else O(n)
}

std::vector<int> v(7): steps_to_end(v.begin(), v.end()) = 7, $O (1)$ mein compute hota hai (subtraction).
std::forward_list<int> f{1,1,1}: = 3, $O (3)$ mein compute hota hai (++ counting).

L5 — Mastery

Worked example Problem 5.1 — Ek naive loop ka cost accounting

Ek student size $n$ ki std::list<int> L ke upar likhta hai:

for (int i = 0; i < n; ++i) {
    auto it = L.begin();
    std::advance(it, i);   // element i ko touch karo
    use(*it);
}

Total time complexity $n$ ke function ke roop mein do, aur fixed version batao.

Recall Solution 5.1

Har iteration std::advance(it, i) ek bidirectional iterator pe call karta hai, jiska cost $O (i)$ hai. Total: $\sum_{i = 0}^{n - 1} i = \frac{n ( n - 1 )}{2} = O (n^{2})$ $n = 100$ ke liye yeh $\frac{100 \cdot 99}{2} = 4950$ steps hain. Fix — ek baar walk karo, $O (n)$ :

for (auto it = L.begin(); it != L.end(); ++it)
    use(*it);

Recall Solution 5.2

Algorithm	Weakest category needed	Reason
`std::copy`	Input (source) + Output (dest)	single forward pass
`std::find`	Input	linear scan, read + `++`
`std::reverse`	Bidirectional	dono ends se andar swap karta hai, `--` chahiye
`std::binary_search`	$O (lo g n)$ ke liye Random access (Forward pe kaam karta hai lekin $O (n)$ walking pe degrade ho jaata hai)	midpoint jumps chahiye
`std::sort`	Random access	partition idhar-udhar jump karta hai

Isliye std::list (bidirectional) find/reverse kar sakta hai lekin sort nahi.

Recall Solution 5.3

std::vector<bool> ek specialization hai jo har element ko ek single bit mein pack karta hai, byte mein nahi. Isliye v[i] ek proxy object (ek bit reference) return karta hai, aur address lene ke liye koi addressable bool nahi hota — &v[0] bool* bhi yield nahi karta. Uska iterator isliye contiguous nahi hai (arguably ek true random-access-to-bool bhi nahi). Ek real contiguous bool buffer ke liye std::vector<char>, std::array<bool, N>, ya std::deque-free flat storage use karo.

Recall Solution 5.4

Nahi, iterators contiguous nahi ho sakte. Requirement (i) — dono ends pe cheap growth — storage ko separate blocks mein force karta hai (tum ek flat array nahi rakh sakte aur phir bhi front pe $O (1)$ mein insert kar sakte ho). Lekin (ii) un blocks ke across $O (1)$ indexing ek block map ke saath achievable hai. Isliye strongest category RandomAccess (lekin Contiguous nahi) hai — exactly jo std::deque provide karta hai. Yeh figure 1 ke middle panel ke peeche ka design hai.

Recall Self-test summary (finish karne ke baad reveal karo)

Kaun sa container random-access hai lekin contiguous nahi? ::: std::deque. List pe i=0..n-1 ke liye "begin se restart karo aur i advance karo" ki total cost? ::: $O (n^{2})$ , specifically $n (n - 1) /2$ . std::reverse ko weakest kaun si category chahiye? ::: Bidirectional (usse -- chahiye). &vector<bool>[0] ek bool* kyun nahi hai? ::: Yeh bits pack karta hai; [] ek proxy return karta hai, koi addressable byte-sized bool nahi. Tag dispatch kab resolve hota hai? ::: Compile time pe, tag ki type se — zero runtime cost.