5.2.21
Intuition 30-second pictureEk iterator ek generalized pointer hota hai. Jaise ek pointer ko dereference kiya ja sakta hai (*p) aur aage badhaya ja sakta hai (++p), usi tarah ek iterator aapko kisi bhi container par — chahe vector ho, list ho, set ho, ya input stream — ek uniform tarike se chalane ka rasta deta hai. Iterator ki category batati hai ki woh kaunse operations support karta hai aur woh kitne fast hain . STL algorithms in categories ke upar likhe jaate hain, isliye ek hi std::find har jagah kaam karta hai.
Intuition Decoupling problemAlgorithms (sort, find, copy) aur containers (vector, list, map) ek M × N M × N glue layer hain: aap M N expose karta hai. Isse M × N M + N
Categories ka hierarchy kyun, ek hi type kyun nahi? Kyunki har container har operation saste mein nahi kar sakta. Ek linked list O ( 1 ) O ( 1 )
Definition Iterator categories (refinement chain)Har category pehle waali se capabilities ka ek strict superset (refinement) hoti hai:
Input/Output ⊂ Forward ⊂ Bidirectional ⊂ RandomAccess ⊂ Contiguous
Input *it (read), ++it, ==, !=. Ek baar aage badh gaye toh purani position invalid hai. Example : istream_iterator.Output *it = x, ++it. Example : ostream_iterator, back_insert_iterator.Forward Example : forward_list, unordered_set.Bidirectional --it (peeche step karna) add karta hai. Example : list, set, map.RandomAccess it + n, it - n, it[n], it1 - it2, aur <, > — sab O ( 1 ) Example : deque.Contiguous plus elements ek contiguous memory block mein rehte hain, toh &*(it+n) == &*it + n. Example : vector, array, string, raw pointers.
std::advance ke peeche ka mechanism
std::advance(it, n) ek iterator ko n steps move karta hai. vector ke liye yeh ek O ( 1 ) it += n). list ke liye ise ++it ko n O ( n ) Ek hi function sahi code kaise choose karta hai?
Har iterator type iterator_category define karta hai (ek tag struct). Library compile time par select hone waale overloads likhti hai:
template < class It > void advance_impl ( It & it , int n , std :: random_access_iterator_tag ) { it += n; // O(1) — only legal here } template < class It > void advance_impl ( It & it , int n , std :: bidirectional_iterator_tag ) { if (n >= 0 ) while (n -- ) ++ it; // O(n) else while (n ++ ) -- it; } template < class It > void advance_impl ( It & it , int n , std :: input_iterator_tag ) { while (n -- ) ++ it; // O(n), forward only } template < class It > void advance ( It & it , int n ) { advance_impl (it, n, typename std :: iterator_traits < It >:: iterator_category {}); }
Ye step kyun? Empty tag object ka type compile time par overload select karta hai — zero runtime cost, phir bhi har container ko uska optimal algorithm milta hai. Hierarchy ka poora point yahi hai.
Worked example 1 — INPUT iterator se numbers padhnastd :: istream_iterator < int > in ( std :: cin ), end; std :: vector < int > v ( in , end ); // reads until EOF Ye step kyun? istream_iterator single-pass input hai: har ++ stream se ek token consume karta hai. Aap wapas nahi ja sakte — ek baar pad liya toh gone. Yahi exactly input-iterator contract hai, jo stream ke physically kaam karne ke tarike se match karta hai.
Worked example 2 — OUTPUT iterator se likhnastd ::vector <int> v{ 1 , 2 , 3 }; std :: copy (v. begin (), v. end (), std :: ostream_iterator < int >( std ::cout, " " )); // prints "1 2 3 " Ye step kyun? ostream_iterator sirf *it = x (jo print karta hai) aur ++it support karta hai. std::copy ko destination ke liye sirf ek output iterator chahiye, isliye kaam karta hai. Aap kabhi isse padhte nahi.
Worked example 3 — Random access se binary-search ho sakti hai; bidirectional se nahistd ::vector <int> v{ 1 , 3 , 5 , 7 , 9 }; auto mid = v. begin () + v. size () / 2 ; // O(1): random access
std ::list <int> L{ 1 , 3 , 5 , 7 , 9 }; // auto m = L.begin() + 2; // COMPILE ERROR: list iterator has no + auto m = L. begin (); std :: advance (m, 2 ); // O(n) workaround Ye step kyun? std::sort ko random access chahiye kyunki yeh idhar-udhar jump karta hai (partitioning). Isliye std::list ka apna member L.sort() hota hai — uske iterators sirf bidirectional hain.
Worked example 4 — Contiguous: pointer arithmetic valid haistd ::vector <double> v{ 1.0 , 2.0 , 3.0 }; double* raw = & v[ 0 ]; assert ( &* (v. begin () + 2 ) == raw + 2 ); // guaranteed by contiguous category Ye step kyun? Sirf contiguous iterators promise karte hain ki elements ek memory block mein hain, isliye aap &v[0] kisi C API ko de sakte ho jo double* expect karta hai. std::deque random-access hai lekin contiguous nahi — yahan fail ho jaata.
std::list random access hai kyunki main iske upar loop kar sakta hoon."
Kyun sahi lagta hai: Aap har element visit kar sakte ho, toh lagta hai full access hai.
Fix: Looping sequential access hai (++ baar baar). Random access matlab O ( 1 ) it + n. List ke paas contiguous memory nahi, toh jump karna O ( n ) list::iterator sirf bidirectional hai, aur v.begin()+n list ke liye compile nahi hoga.
Common mistake "Random access ⇒ contiguous, toh main&deque[0] kisi C function ko pass kar sakta hoon."
Kyun sahi lagta hai: Dono it[n] ko O ( 1 ) Fix: deque fixed-size chunks mein store karta hai; element 5 aur 6 alag blocks mein ho sakte hain. &*(it+n) == &*it + n sirf contiguous ke liye guaranteed hai (vector, array, string, pointers). Random access zaruri hai lekin sufficient nahi.
istream_iterator ko do baar padh sakta hoon."
Kyun sahi lagta hai: vector iterator ke saath copy karna aur dobara padhna theek hai (multi-pass).
Fix: Input iterators single-pass hote hain. Ek copy banao aur ek copy aage badha do toh doosra invalid ho jaata hai — underlying stream already move ho chuka hai. Multi-pass sirf forward se shuru hota hai.
Common mistake "Output iterators ko== se compare kiya ja sakta hai."
Kyun sahi lagta hai: Input iterators end check ke liye ==/!= support karte hain.
Fix: Pure output iterators (jaise back_inserter) mein koi equality nahi aur koi end sentinel nahi; aapko pata hona chahiye kitna likhna hai ya source range ki length par rely karna chahiye.
Iterator kya hota hai, ek phrase mein? Ek generalized pointer jo container par uniform traversal deta hai.
Chha iterator categories refinement order mein batao. Input/Output → Forward → Bidirectional → RandomAccess → Contiguous.
Bidirectional, Forward ke upar kaunsa operation add karta hai? Backward stepping --it.
RandomAccess, Bidirectional ke upar kaunse operations add karta hai? it+n, it-n, it[n], it2-it1, ordering </>, sab O(1) mein.
Contiguous, RandomAccess ke upar kya extra guarantee add karta hai? Elements ek contiguous memory block mein hote hain: &*(it+n) == &*it + n.
Kaun sa container sirf bidirectional iterators rakhta hai, random access nahi? std::list (aur set, map bhi).
std::deque random-access kyun hai lekin contiguous nahi?Uski memory alag-alag fixed-size chunks mein split hai, toh addresses linear nahi hain.
"Single-pass" ka matlab kya hai aur kaunsi categories single-pass hain? Har element sirf ek baar visit ho sakta hai; purani positions invalid ho jaati hain. Input aur Output iterators.
Ek hi naam se std::advance vectors ke liye O(1) aur lists ke liye O(n) kaise karta hai? iterator_traits::iterator_category par tag dispatch compile time par overload choose karta hai.
Input iterator ka example? Output iterator ka? istream_iterator; ostream_iterator / back_insert_iterator.
std::sort, std::list par kyun kaam nahi karta?sort ko random-access iterators chahiye; list ke iterators bidirectional hain — list::sort() use karo.
Forward, input ke upar kya category add karta hai? Multi-pass: aap ek iterator copy karke re-traverse kar sakte ho.
Recall Feynman: 12-saal ke bacche ko samjhaoSocho alag-alag toy boxes hain. Ek kagaz ki scroll jo sirf ek baar padhte waqt unroll hoti hai — woh input iterator hai. Ek stamp jo sirf print karta hai, kabhi padhta nahi — woh output hai. Ek train jo ek-taraf ki track par hai aur shuru se dobara chadhi ja sake, woh forward hai. Ek train jo reverse bhi kar sake, woh bidirectional hai. Ek teleporter jo seedha seat #50 par jump kare, woh random access hai. Aur agar saari seats ek seedhi line mein bina kisi gap ke jadi hain, toh woh contiguous hai. Jitna fancy toy, utna zyada kar sakta hai — aur STL woh sabse sasta trick choose karta hai jo toy allow karta hai.
Mnemonic Order + capabilities"In Out, Free Bards Rap Continuously"
In put, Out put, F orward, B idirectional, R andom, C ontiguous.
Har word agla power deta hai: read-once → write-once → re-read → reverse → jump → laid-out-in-a-line.
Pointers and pointer arithmetic — iterators inhe generalize karte hain.STL Containers — vector, list, deque, map — har ek specific iterator category expose karta hai.STL Algorithms — sort, find, copy — iterator categories ke upar likhe gaye hain.Templates and Tag Dispatch — advance/distance ke peeche compile-time mechanism.iterator_traits and type introspection — category tag kaise padha jaata hai.Ranges library (C++20) — iterator concepts ke upar bana modern layer.
Iterator = generalized pointer
M + N via common interface
Input read-only single-pass
Output write-only single-pass
Elements in one memory block
