iterator — container-এর ভেতর দিয়ে হাঁটা

১ · সমস্যাটা আগে — একটি কাজ, অনেক রকম container

আগের দুটি পর্বে আপনি অনেক container দেখেছেন: পাশাপাশি সাজানো std::vector, শিকলের মতো std::list, দুই মাথা খোলা std::deque, key দিয়ে সাজানো std::map, hash দিয়ে রাখা std::unordered_map. এখন একটি সাধারণ কাজ ভাবুন: “সব উপাদানের যোগফল বের করো।” অথবা “প্রথম যে উপাদান ১০০-এর বেশি, সেটি খুঁজে দাও।”

প্রতিটি container-এর জন্য আলাদা করে লিখলে কী হয়? vector-এ index দিয়ে v[i], list-এ এক node থেকে পরের node-এ যাওয়া, map-এ একটি গাছের (tree) ভেতর দিয়ে বাঁয়ে-ডানে ঘোরা। মোটামুটি দশটি container আর শ-খানেক কাজ (খোঁজা, গোনা, কপি, সাজানো…) থাকলে লিখতে হতো হাজারখানেক ফাংশন। প্রতিটি নতুন container এলে আবার সব কাজ নতুন করে লেখা। এটাকে বলা যায় M × N সমস্যা: M রকম container আর N রকম কাজ মানে M × N টুকরো কোড।

iterator-এর ধারণাটি নতুন নয় — পর্ব ১৫-এ আপনি pointer দিয়ে array-এর ভেতর দিয়ে হেঁটেছেন। একটি C-ধাঁচের array আর একটি vector পাশাপাশি দেখুন:

int a[3] = {31, 33, 30};
for (int* p = a; p != a + 3; ++p) sum += *p;      // pointer দিয়ে হাঁটা

std::vector<int> v = {31, 33, 30};
for (auto it = v.begin(); it != v.end(); ++it) sum += *it;   // iterator দিয়ে

std::list<int> l = {31, 33, 30};
for (auto it = l.begin(); it != l.end(); ++it) sum += *it;   // হুবহু একই আকার!

তিনটি লুপের চেহারা এক। * দিয়ে উপাদান পড়া, ++ দিয়ে পরেরটিতে যাওয়া, != দিয়ে শেষ হলো কি না দেখা। pointer-এর বেলায় ++p মানে মেমরিতে পাশের ঘর; list-এর iterator-এর বেলায় ++it মানে ভেতরে লুকানো “next” ঠিকানা ধরে পরের node-এ যাওয়া। কীভাবে যাবে, সেটা iterator জানে; লুপকে জানতে হয় না। এই কারণে iterator-কে বলা হয় সাধারণীকৃত pointer — pointer-এর মতো আচরণ, কিন্তু যেকোনো গঠনের ডেটার জন্য।

২ · begin(), end() আর half-open range

প্রতিটি standard container-এর দুটি member function আছে। begin() দেয় প্রথম উপাদানের iterator. end() দেয় এমন একটি iterator, যা শেষ উপাদানের ঠিক পরের জায়গা দেখায় — কোনো উপাদানকে নয়। এই দুটি মিলে একটি range বোঝায়, যা গণিতের ভাষায় লেখা হয় [begin, end): বাঁ দিকে বন্ধনী বর্গাকার, মানে begin ভেতরে; ডান দিকে গোল, মানে end বাইরে। একে বলে half-open range, আর end-কে বলে past-the-end iterator.

প্রথমবার দেখলে মনে হতে পারে, শেষ উপাদানটিকেই কেন end বলা হলো না? নিচের ধাপগুলো দেখুন — একটি তাপমাত্রা-সেন্সরের তিনটি রিডিং, আর তারপর একটি খালি vector:

1std::vector<int> t = {31, 33, 30};2for (auto it = t.begin(); it != t.end(); ++it)3    std::print("{} ", *it);4std::vector<int> none;          // খালি5// none.begin() == none.end()

half-open range-এর তিনটি সুবিধা মনে রাখুন। এক, খালি range লেখা যায় স্বাভাবিকভাবে: begin == end. দুই, উপাদানের সংখ্যা = end − begin, কোনো +1 বা −1 ছাড়া। তিন, একটি range-কে মাঝখান থেকে ভাগ করলে [begin, mid) আর [mid, end) — দুটি অংশ একটি উপাদানও ভাগাভাগি করে না, একটিও বাদ পড়ে না। binary search বা merge sort-এর মতো ভাগ-করা algorithm এতে অনেক সহজ হয়। এর পেছনের ইতিহাস ভাবনার প্রশ্ন ০২-এ।

C-ধাঁচের array-এর নিজের member function নেই, তাই free function std::begin(a) আর std::end(a) ব্যবহার করুন — এরা array, vector, যেকোনো container-এ কাজ করে। generic কোডে (যেমন template-এর ভেতরে) v.begin()-এর চেয়ে এটি বেশি নমনীয়।

৩ · তিনটি কাজ — *it, ++it, it != end — আর range-for-এর আসল রূপ

প্রায় সব iterator-এর মৌলিক কাজ তিনটি:

লুপের শর্তে it < end নয়, it != end লেখার অভ্যাস করুন। < শুধু vector-এর মতো container-এর iterator-এ চলে; list বা map-এর iterator জানেই না কে “বড়”, তারা শুধু জানে দুটি জায়গা এক কি না। আর it++-এর বদলে ++it: postfix increment পুরোনো মানের একটি কপি ফেরত দেয়, যা জটিল iterator-এ অকারণ কাজ। সাধারণ ক্ষেত্রে compiler দুটিকে একই করে ফেলে, তবু ++it লেখাই প্রচলিত রীতি।

range-for — compiler আপনার জন্য iterator লুপ লেখে

পর্ব ৮-এ আপনি range-for শিখেছেন: for (auto x : v). এটি কোনো আলাদা যন্ত্র নয়। C++ standard বলে দিয়েছে, compiler এই লুপকে কোন iterator কোডে বদলে নেবে। একটি গানের playlist (std::list) দিয়ে ধাপে ধাপে দেখুন:

1for (const auto& song : playlist) std::println("{}", song);2// compiler-এর চোখে (C++17 থেকে) প্রায় এমন:3{   auto&& __range = playlist;4    auto __begin = __range.begin();5    auto __end   = __range.end();6    for ( ; __begin != __end; ++__begin) {7        const auto& song = *__begin;8        std::println("{}", song);9    }10}

C++17 থেকে __begin আর __end-এর টাইপ আলাদা হতে পারে — শুধু != দিয়ে তুলনা করা গেলেই হলো। ছোট এই পরিবর্তনটির পেছনে বড় একটি ধারণা আছে (sentinel), যা ৯ নম্বর অংশের শেষে দেখবেন।

৪ · শুধু পড়ার iterator আর উল্টো দিকে হাঁটা

const_iterator — “দেখব, ছোঁব না”

সাধারণ iterator দিয়ে *it = 0; লিখে উপাদান বদলানো যায়। const_iterator দিয়ে যায় না — শুধু পড়া চলে। cbegin() আর cend() সবসময় const_iterator দেয়, container নিজে const না হলেও। কোনো ফাংশন যদি শুধু হিসাব করে, তাকে const_iterator দিন: ভুল করে কেউ ডেটা বদলালে compiler তখনই error দেবে। এটি পর্ব ৫-এর const-এর সেই একই নীতি — অনুমতি যত কম, ভুলের সুযোগ তত কম।

reverse iterator — শেষ থেকে শুরুর দিকে

ধরুন একটি সেন্সর প্রতি মিনিটে তাপমাত্রা লিখে রাখে, পুরোনো রিডিং আগে। আপনি দেখতে চান সাম্প্রতিক রিডিংগুলো আগে। reverse iterator ঠিক এই কাজ করে: rbegin() শেষ উপাদানে দাঁড়ায়, আর ++ করলে সে পেছনে যায়। rend() হলো প্রথম উপাদানেরও আগের কাল্পনিক জায়গা। অর্থাৎ উল্টো দিকেও সেই একই half-open range, একই !=, একই ++ — তাই যে algorithm সামনে হাঁটতে জানে, সে কোনো বদল ছাড়াই পেছনেও হাঁটতে পারে। শুধু-পড়ার উল্টো সংস্করণ crbegin()/crend().

এবার এ পর্যন্ত যা দেখলেন, সব একটি প্রোগ্রামে। একটি template ফাংশন (পর্ব ২৮) শুধু দুটি iterator নেয় — সে জানে না কোন container থেকে এসেছে:

#include <list>
#include <print>
#include <vector>

template <typename It>                 // It = any iterator type
int total(It first, It last) {
    int sum = 0;
    for (It it = first; it != last; ++it) sum += *it;   // only *, ++, !=
    return sum;
}

int main() {
    std::list<int> playlist = {215, 187, 242};   // song lengths (s)
    std::vector<int> temp = {31, 33, 30, 36};    // sensor log, oldest first
    std::println("playlist: {} s", total(playlist.begin(), playlist.end()));
    std::println("sensor sum: {}", total(temp.cbegin(), temp.cend()));
    std::println("empty range: {}", total(temp.end(), temp.end()));
    std::print("newest first:");
    for (auto r = temp.crbegin(); r != temp.crend(); ++r) std::print(" {}", *r);
    std::println("");
}

একটি খুঁটিনাটি, যা পরে কাজে লাগবে: reverse iterator ভেতরে একটি সাধারণ iterator রাখে, যা পাওয়া যায় r.base() দিয়ে। কিন্তু base() একঘর সরে থাকে — rbegin().base() হলো end(). half-open range-কে উল্টে দিলে এই এক ঘরের ফাঁক অনিবার্য, তাই reverse iterator থেকে erase করার সময় সাবধান থাকুন।

৫ · iterator category — কে কতটা পারে

ডাকপিয়নের উপমায় ফিরে যান। সোজা রাস্তার নম্বর দেওয়া বাড়িতে সরাসরি ৫০ নম্বরে যাওয়া যায়; গ্রামের পথে ৫০ নম্বরে যেতে হলে ৪৯টি বাড়ি পার হতে হয়। iterator-ও তেমন — container-এর গঠন যা সস্তায় করতে দেয়, iterator শুধু সেটুকুই দেয়। C++ এই ক্ষমতাগুলোকে কয়েকটি ধাপে ভাগ করেছে, যাকে বলে iterator category. প্রতিটি ধাপ আগের ধাপের সব ক্ষমতা রাখে, সাথে কিছু যোগ করে:

কেন std::sort list-এ চলে না

std::sort ভেতরে সাধারণত introsort নামের একটি কৌশল চালায় — quicksort-এর ধাঁচে মাঝখানের উপাদান বেছে নেওয়া, দূরের দুটি উপাদান অদলবদল করা, দুই প্রান্ত থেকে একসাথে ভেতরে আসা। এসব কাজে বারবার দরকার “এক লাফে i নম্বর ঘরে যাও”, যা শুধু random access iterator সস্তায় পারে। তাই standard বলে দিয়েছে, std::sort-এর দুটি iterator অবশ্যই random access হবে। list-এর iterator দিলে compile error আসে — প্রায়ই লাইব্রেরির গভীর থেকে আসা কয়েক পর্দা লম্বা error, যার কোথাও লেখা থাকে operator- পাওয়া যায়নি।

std::list<int> marks = {72, 58, 91};
// std::sort(marks.begin(), marks.end());   // error: list-এর iterator random access নয়
marks.sort();                               // ঠিক: list-এর নিজের sort

তাহলে list কি সাজানো যায় না? যায় — list-এর নিজের member function list::sort() আছে। সেটি merge sort-এর ধাঁচে কাজ করে, আর উপাদান কপি না করে শুধু node-এর লিংক বদলে দেয়। এটাই নকশার শিক্ষা: যে কাজ একটি container-এর গঠনে বিশেষভাবে ভালো করা যায়, সেটি member function; বাকি সব সাধারণ algorithm. iterator category সেই সীমারেখা compiler-কে দিয়ে পাহারা দেওয়ায় — ধীর পথে চুপচাপ চলার বদলে আগেই থামিয়ে দেয়। C++20-এর std::ranges::sort (পর্ব ৩৩, ৩৫) একই নিয়ম concept দিয়ে লেখে, তাই error অনেক ছোট আর পরিষ্কার হয়।

৬ · advance, next, prev, distance — যেকোনো iterator-এ দূরত্বের কাজ

list-এ it + 3 লেখা যায় না, কিন্তু তিন ঘর এগোনোর দরকার তো হয়ই। <iterator> header-এর চারটি ফাংশন যেকোনো category-তে এই কাজগুলো করে দেয়, আর iterator যতটা পারে, ততটা দ্রুত পথ বেছে নেয়:

std::list<std::string> playlist = {"Shada Kalo", "Pagla Hawa", "Lal Paharir"};
auto third = std::next(playlist.begin(), 2);    // "Lal Paharir"
auto last  = std::prev(playlist.end());         // শেষ গান — *end() নয়!
auto n = std::distance(playlist.begin(), third);  // 2

ভেতরে এরা iterator-এর category দেখে আলাদা কোড বেছে নেয়: random access হলে সরাসরি it += n, নাহলে লুপে n বার ++it. আপনি একটিই নাম লেখেন, compiler সেরা পথটি বসিয়ে দেয় — এটাই generic programming-এর ক্ষমতা। কিন্তু দুটি সতর্কতা আছে। এক, এরা সীমানা পরীক্ষা করে না: তিনটি গানের list-এ std::next(begin, 5) লিখলে end পেরিয়ে যায় — undefined behavior. দুই, list-এ এরা “দেখতে এক লাইন” হলেও আসলে লুপ; একটি বড় লুপের ভেতরে বারবার std::distance ডাকলে পুরো কাজ নিঃশব্দে O(n²) হয়ে যেতে পারে (Big-O, পর্ব ৮)।

৭ · iterator invalidation — বুকমার্ক যখন ভুল পাতায়

iterator একটি জায়গার স্মৃতি। container নিজের ডেটা সরিয়ে ফেললে সেই স্মৃতি মিথ্যা হয়ে যায়। একে বলে iterator invalidation, আর পর্ব ১৩ ও ১৮-এ আপনি এর মূল কারণ দেখেছেন: vector-এর ধারণক্ষমতা (capacity) ফুরালে সে নতুন, বড় জায়গায় সব ডেটা সরিয়ে নেয় — reallocation. পুরোনো জায়গার দিকে তাকানো iterator তখন একটি dangling pointer-এর মতো। একই কাজ list-এ করলে কী হয়, পাশাপাশি দেখুন (ঠিকানাগুলো উদাহরণমাত্র; বিপজ্জনক লাইনগুলো চালানোর জন্য নয়):

std::vector<int> v = {10, 20, 30};
auto it = v.begin();          // it ──► @A000 (মান 10)

@A000: [10][20][30]           ← খালি ঘর আর নেই

জায়গা নেই → নতুন বড় ব্লক নেওয়া হলো:
@B000: [10][20][30][40][  ][  ]
পুরোনো @A000 ফেরত দেওয়া হলো (free)

it এখনো ধরে আছে @A000 — যে মেমরি আর v-এর নয়

std::print("{}", *it);    // চালাবেন না

হয়তো 10 দেখাবে, হয়তো আবর্জনা, হয়তো crash হবে।
সবচেয়ে খারাপ: নিজের মেশিনে “ঠিকঠাক” চলে, পরে ব্যবহারকারীর মেশিনে ভাঙে।
AddressSanitizer দিলে: heap-use-after-free

std::list<int> l = {10, 20, 30};
auto it = l.begin();          // it ──► node @C100 (মান 10)
l.push_back(40);              // নতুন node @D700, শুধু লিংক জোড়া হলো

@C100[10] ⇄ @C2F0[20] ⇄ @C580[30] ⇄ @D700[40]
*it  →  10                    // সম্পূর্ণ বৈধ

vector-এ:
  v.push_back(40);
  it = v.begin();             // বদলের পরে আবার নাও
  // অথবা iterator-এর বদলে index (size_t i) মনে রাখো
  // অথবা আগে থেকে v.reserve(n) — যতক্ষণ size ≤ capacity

list-এ: যে উপাদান মুছেছেন, শুধু তার iterator অকেজো

লুপের ভেতরে মোছা — সবচেয়ে প্রচলিত ফাঁদ

একটি vector থেকে সব ঋণাত্মক রিডিং (ভুল মাপ) বাদ দিতে হবে। প্রথম যে কোড মাথায় আসে, আর AI-ও প্রায়ই যা লেখে:

// ভুল — চালাবেন না
for (auto it = v.begin(); it != v.end(); ++it)
    if (*it < 0) v.erase(it);        // erase-এর পরে it মৃত, তবু ++it

// ঠিক — erase যে নতুন iterator ফেরত দেয়, সেটি নিন
for (auto it = v.begin(); it != v.end(); )
    if (*it < 0) it = v.erase(it);   // মোছা উপাদানের পরেরটি
    else ++it;

// সবচেয়ে সহজ (C++20 থেকে)
std::erase_if(v, [](int x) { return x < 0; });

প্রথম লুপে erase(it)-এর পরে it অকেজো, অথচ লুপ তার ওপরই ++it করে — undefined behavior. দ্বিতীয় লুপ erase-এর ফেরত দেওয়া iterator ব্যবহার করে, যা মোছা উপাদানের ঠিক পরেরটিকে দেখায়; তাই মুছলে ++it করা হয় না। তৃতীয়টি — std::erase_if — পুরো কাজ একবারে করে, সব container-এর জন্য সঠিক কৌশলে। আর মনে রাখুন, range-for-এর ভেতরে container-এ erase বা push_back একেবারেই নয়: আপনি ভেতরের __begin/__end দেখতে পান না, তাই ঠিক করারও উপায় নেই। lifetime আর dangling নিয়ে বিস্তারিত পর্ব ১৮-এ।

৮ · inserter আর stream iterator — iterator, কিন্তু container নয়

iterator-এর ধারণা এতটাই সাধারণ যে, এমন জিনিসও iterator হতে পারে, যার পেছনে কোনো সাজানো ডেটাই নেই। দুটি উদাহরণ দেখুন।

std::back_inserter — লিখলেই push_back

std::copy(first, last, out) একটি range-এর প্রতিটি উপাদান out-এ লেখে, আর প্রতিবার ++out করে। লক্ষ্য যদি একটি খালি vector হয়, সাধারণ dst.begin() দিলে সর্বনাশ — সেখানে লেখার মতো কোনো ঘর নেই। std::back_inserter(dst) একটি output iterator দেয়, যার ওপর *out = x লেখা মানে আসলে dst.push_back(x):

std::list<int> today = {31, 33, 30};
std::vector<int> archive;                                       // খালি
std::copy(today.begin(), today.end(), std::back_inserter(archive));  // archive = 31 33 30

এভাবে algorithm জানে না যে সে আসলে container বড় করছে — সে শুধু “লিখছে আর এগোচ্ছে”। একইভাবে std::front_inserter (সামনে যোগ) আর std::inserter (নির্দিষ্ট জায়গায়) আছে।

stream iterator — কনসোলকেও range ভাবা

std::ostream_iterator একটি output iterator, যাতে লিখলে মান চলে যায় একটি stream-এ, যেমন std::cout. আর std::istream_iterator একটি input iterator, যা প্রতিবার ++-এ stream থেকে একটি মান পড়ে; ইনপুট ফুরালে সে একটি বিশেষ “শেষ” iterator-এর সমান হয়ে যায়।

std::vector<int> marks(std::istream_iterator<int>(std::cin), {});  // ইনপুট শেষ পর্যন্ত পড়ো
std::copy(marks.begin(), marks.end(), std::ostream_iterator<int>(std::cout, " "));

এখানে ইনপুট-স্রোতই একটি range: begin হলো “পড়তে থাকা iterator”, end হলো “ইনপুট শেষ” অবস্থা। এগুলো input iterator-এর আসল উদাহরণ — একবার পড়া সংখ্যা আর ফেরানো যায় না। আধুনিক কোডে ছাপার কাজে std::println আর পর্ব ৩৫-এর views বেশি পরিষ্কার, কিন্তু পুরোনো কোডে এগুলো প্রায়ই দেখবেন।

৯ · নিজের iterator — একটি লঞ্চ-টাইমারের Countdown

range-for-এর বিস্তার মনে আছে? চাই শুধু begin(), end(), আর iterator-এ *, ++ ও !=. তাহলে এমন একটি “range” বানানো যায়, যার পেছনে কোনো container নেই — যেমন রকেট উৎক্ষেপণের কাউন্টডাউন: 10, 9, …, 1. সংখ্যাগুলো কোথাও জমা থাকবে না; iterator প্রতিবার হিসাব করে পরেরটি দেবে।

#include <print>

class Countdown {                       // Countdown(10): 10, 9, ..., 1
    int from_;
public:
    explicit Countdown(int from) : from_(from) {}
    struct Iter {
        int n;
        int operator*() const { return n; }
        Iter& operator++() { --n; return *this; }      // count down
        bool operator!=(const Iter& o) const { return n != o.n; }
    };
    Iter begin() const { return {from_}; }
    Iter end() const { return {0}; }    // one past the last value (1)
};

int main() {
    for (int s : Countdown(10)) std::print("{} ", s);
    std::println("LIFTOFF");
    for (int s : Countdown(0)) std::print("{} ", s);   // begin == end
    std::println("(empty range)");
}

এটি range-for-এর জন্য যথেষ্ট, কিন্তু একটি “পূর্ণাঙ্গ” standard iterator নয়। std::sort বা std::distance-এর মতো algorithm-এ দিতে হলে আরও কিছু লাগে: ==, postfix ++, আর কিছু টাইপ-তথ্য (value_type, difference_type, আর category জানানো) — যা লাইব্রেরি iterator_traits দিয়ে পড়ে। আর একটি ফাঁদ আছে, যা অনুশীলন ৪-এ ধরবেন: Countdown(-3) দিলে কী হবে?

C++20-এর sentinel — end সবসময় iterator না-ও হতে পারে

উপরের end() একটি পুরো Iter বানায়, শুধু তুলনা করার জন্য। কিন্তু কিছু range-এর শেষ আগে থেকে কোনো জায়গা নয়, বরং একটি শর্ত: C-string-এর শেষ মানে “'\0' অক্ষর পাওয়া গেলে”, কীবোর্ডের ইনপুটের শেষ মানে “আর কিছু নেই”। C++20 এর জন্য এনেছে sentinel: end-এর জায়গায় এমন একটি আলাদা টাইপ, যার সাথে iterator-কে তুলনা করা যায়, কিন্তু যা নিজে কোথাও দাঁড়িয়ে নেই। Countdown-এ চাইলে end() একটি খালি struct Done {} ফেরত দিতে পারত, আর তুলনা হতো “n কি 0 হয়ে গেছে?”। C++17 থেকে range-for আলাদা টাইপের begin/end মেনে নেয় ঠিক এই কারণেই। পর্ব ৩৫-এর ranges আর views এই ধারণার ওপরই দাঁড়িয়ে।

১০ · AI-এর যুগে — iterator-এর ভুল ধরা

iterator-এর ভুলগুলোর একটি বিশেষ বৈশিষ্ট্য আছে: বেশিরভাগই compile হয়, ছোট পরীক্ষায় ঠিকঠাক চলে, আর ভাঙে পরে — বড় ডেটায়, অন্য compiler-এ, বা reallocation ঠিক কোন মুহূর্তে হলো তার ওপর নির্ভর করে। AI টুল এখানে বিশেষ ঝুঁকিপূর্ণ, কারণ অনলাইনে লুপের ভেতরে erase করার ভুল উদাহরণ প্রচুর, আর AI প্রায়ই এক container-এর অভ্যাস (vector-এর it + 5) অন্য container-এ (list) চালিয়ে দেয়। সাধারণ ভুলগুলো:

AI-এর iterator কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি range-for-এর দেহ খুঁজেছি — container-এ কোনো erase, insert বা push_back নেই
• প্রতিটি erase-এর পরে তার ফেরত দেওয়া iterator ব্যবহার হয়েছে, অথবা std::erase_if
• প্রতিটি range-এর begin আর end একই container থেকে এসেছে
• it + n বা std::next-এর আগে যথেষ্ট উপাদান আছে কি না যাচাই হয়েছে; *end() কোথাও নেই
• কোনো iterator struct, map বা member-এ জমা রেখে পরে সেই container বদলানো হয়নি
• -fsanitize=address দিয়ে বড় ইনপুটে চালিয়েছি — কোনো use-after-free রিপোর্ট আসেনি