iterator আর algorithm: টুকরোগুলো জোড়া লাগে কীভাবে

পরীক্ষার নম্বর রাখা একটা vector-এর জন্য Zara যত্ন করে একটা search লিখেছিল। অভ্যাসমতো সে আগে ফাঁকা vector দিয়ে পরীক্ষা করেছে, আর সেটা pass করেছে। তারপর তার team নম্বরগুলো একটা deque-এ সরিয়ে নিল। Zara দীর্ঘশ্বাস ফেলল: search-টা আবার লিখতে হবে।

লিখতে হয়নি। তার search ছিল std::find, আর std::find জানেই না vector কী জিনিস। সে শুধু জানে এক iterator থেকে আরেক iterator পর্যন্ত কীভাবে হাঁটতে হয়। Container বদলাও, একই লাইন কাজ করেই যায়।

এই lesson ওই হাঁটা নিয়েই। Lesson 3-এর প্রতিটা container-কে এই track-এর প্রতিটা algorithm-এর সঙ্গে জোড়ে এটাই। তাই চলতে দেখার মতো ছবি যদি একটাই থাকে, সেটা এটা।

একটা iterator তুমি আগে থেকেই চেনো: pointer

C-তে তুমি pointer দিয়ে array-র উপর দিয়ে হেঁটেছ। প্রথম element থেকে শুরু করেছ, *p দিয়ে পড়েছ, ++p দিয়ে এগিয়েছ, আর থেমেছ শেষ element-এর এক ঘর পরের একটা pointer-এ। ওই pointer-টাই একটা iterator: এমন কিছু, যেটা একটা element-এ আঙুল রাখে আর পরেরটায় সরে যেতে পারে।

STL code-এ এই হাঁটার চেহারা সব সময় একই। নিচে প্রতিটা অংশের নাম দেওয়া আছে; তারপর Example 1 একই জিনিস সাধারণ pointer দিয়ে দেখায়।

for (auto it = c.begin(); it != c.end(); ++it) { use(*it); }

#include <iostream>

int main()
{
    int marks[] = {72, 45, 90, 61};
    int *first = marks;
    int *last = marks + 4;
    std::cout << "marks:";
    for (int *p = first; p != last; ++p) std::cout << ' ' << *p;
    std::cout << '\n';
}

marks: 72 45 90 61

begin() আর end(): যেকোনো container-এ একই হাঁটা

প্রতিটা STL container দুইটা iterator দেয়। begin() আঙুল রাখে প্রথম element-এ। end() আঙুল রাখে শেষ element-এর এক ঘর পরে, উপরের last-এর মতো সেই একই ফাঁকা ঘরে। end() থেকে তুমি কখনো কিছু পড়ো না; ওখানে পৌঁছালে শুধু থামো।

Container-এর iterator সব সময় সাধারণ pointer না। একটা list iterator একটা link ধরে পরের node-এ যায়, আর একটা deque iterator memory-র এক block থেকে পরের block-এ লাফ দিতে পারে। তবে সবগুলোই একই তিনটা অনুরোধের জবাব দেয়: পড়া (*it), এগোনো (++it), আর তুলনা (it != end)।

এই যে সেই হাঁটা, এবার চলন্ত। আগে vector-এ ধাপে ধাপে চালাও, তারপর deque-এ। শেষ ধাপটা খেয়াল করো: iterator এসে পড়ে end()-এ, loop থেমে যায়, আর ওখানে কিছুই পড়া হয় না।

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {72, 45, 90, 61};
    std::cout << "v:";
    for (auto it = v.begin(); it != v.end(); ++it) std::cout << ' ' << *it;
    std::cout << '\n';
    std::cout << "size from the iterators: " << (v.end() - v.begin()) << '\n';
}

v: 72 45 90 61
size from the iterators: 4

Half-open range [begin, end)

দুইটা iterator, first আর last, মিলে একটা range বোঝায়: first থেকে শুরু করে last-এর ঠিক আগ পর্যন্ত প্রতিটা element, ওটাকে বাদ দিয়ে। অঙ্কে এটাকে লেখা হয় [first, last), আর এর নাম half-open range: তৃতীয় বন্ধনী [ মানে "ভেতরে আছে", আর প্রথম বন্ধনী ) মানে "ভেতরে নেই"।

তাহলে end() শেষ element-এ আঙুল রাখে না কেন? কারণ তিনটা, আর তার দুইটা তুমি এর মধ্যেই দেখে ফেলেছ।

• গোনা মানে একটা বিয়োগ। end() - begin() হলো element-এর সংখ্যা, মনে রাখার মতো কোনো + 1 নেই।
• ফাঁকার জন্য আলাদা কোনো case লাগে না। ফাঁকা container-এ begin() == end()। Loop-এর শর্ত শুরুতেই false, আর প্রতিটা algorithm কিছুই করে না, যেটা ঠিকই। Zara-র ফাঁকা vector-এর পরীক্ষা কোনো বাড়তি code ছাড়াই pass করে।
• "পাওয়া যায়নি"-এর একটা ঠিকানা আছে। মানটা না থাকলে std::find ফেরত দেয় end(), এমন একটা অবস্থান যেটা কখনো আসল উত্তর হতে পারে না।

তাই range মানে সব সময় "এখান থেকে ওখান পর্যন্ত, তবে ওখানটা বাদে"। এই track-এর প্রতিটা algorithm তার range এভাবেই নেয়।

এক algorithm, সব container

একটা algorithm দুইটা iterator পায়, আর তাদের মাঝখান দিয়ে হাঁটে। Container-টা সে কখনো পায় না। তাই element-গুলো vector-এ আছে, deque-এ, নাকি সাধারণ একটা array-তে, সেটা সে বলতে পারে না, আর তার মাথাব্যথাও নেই। তার দরকার শুধু এমন একটা iterator, যেটা algorithm-এর চাওয়া কাজগুলো করতে পারে।

#include <algorithm>
#include <iostream>

int main()
{
    int marks[] = {72, 45, 90, 61};
    std::sort(marks, marks + 4);
    std::cout << "sorted:";
    for (int m : marks) std::cout << ' ' << m;
    std::cout << '\n';
}

sorted: 45 61 72 90

এবার একটা vector-এ চারটা algorithm। sort range-টা সাজায়, আর find একটা মানের দিকে iterator ফেরত দেয় (বা end())। count গোনে একটা মান কতবার আছে, আর reverse range-টা উল্টে দেয়।

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> c = {61, 72, 45, 90, 45};
    std::sort(c.begin(), c.end());
    auto it = std::find(c.begin(), c.end(), 72);
    std::cout << "72 found: " << (it != c.end()) << '\n';
    std::cout << "45 count: " << std::count(c.begin(), c.end(), 45) << '\n';
    std::reverse(c.begin(), c.end());
    std::cout << "reversed:";
    for (int x : c) std::cout << ' ' << x;
    std::cout << '\n';
}

72 found: 1
45 count: 2
reversed: 90 72 61 45 45

#include <algorithm>
#include <deque>
#include <iostream>

int main()
{
    std::deque<int> c = {61, 72, 45, 90, 45};
    std::sort(c.begin(), c.end());
    auto it = std::find(c.begin(), c.end(), 72);
    std::cout << "72 found: " << (it != c.end()) << '\n';
    std::cout << "45 count: " << std::count(c.begin(), c.end(), 45) << '\n';
    std::reverse(c.begin(), c.end());
    std::cout << "reversed:";
    for (int x : c) std::cout << ' ' << x;
    std::cout << '\n';
}

72 found: 1
45 count: 2
reversed: 90 72 61 45 45

Container-এর একটা অংশও একটা range

Algorithm যেকোনো দুইটা iterator নেয় বলে তুমি তাকে container-এর একটা অংশও দিতে পারো। v.begin() + 3 মানে "তিন ঘর ভেতরে", তাই [v.begin(), v.begin() + 3) হলো প্রথম তিনটা element।

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {90, 72, 61, 45, 10};
    std::sort(v.begin(), v.begin() + 3);
    std::cout << "first three sorted:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';

    std::vector<int> empty;
    std::sort(empty.begin(), empty.end());
    std::cout << "empty: begin == end is " << (empty.begin() == empty.end()) << '\n';
}

first three sorted: 61 72 90 45 10
empty: begin == end is 1

এখান থেকেই আসে সেই নিয়ম, যেটা এই পুরো track ধরে রাখে: algorithm কখনো জানে না সে কোন container-এর উপর দিয়ে হাঁটছে। সে জানে দুইটা iterator, আর কাজটা।

for (auto it = v.begin(); it <= v.end(); ++it)
    std::cout << *it << ' ';

std::list<int> l = {3, 1, 2};
std::sort(l.begin(), l.end());

std::vector<int> a = {3, 1, 2};
std::vector<int> b = {9, 8};
std::sort(a.begin(), b.end());

পরের lesson-এ তুমি সেই reference খুলবে, যেটা প্রতিটা C++ programmer খুলে রাখে। শিখবে, এখানকার প্রতিটা operation-এর জন্য ওটা যে খরচের কথা দেয়, সেটা কীভাবে পড়তে হয়।