iterator: এমন একটা position, যে নিজেই সরতে জানে

Kenji প্রতি ঘণ্টায় স্কুলের বৃষ্টির পানির ট্যাংকে পানি কতটা উঁচু, সেটা মাপে, আর মাপগুলো রাখে একটা vector<int>-এ। ওর function printGaps(v) v[i] - v[i - 1] দিয়ে print করে, প্রতি ঘণ্টায় পানি কতটা বাড়ল বা কমল। Maria নিজের ট্যাংকের জন্যও ঠিক এই report চায়। ওর log-এ দেরিতে আসা মাপ মাঝখানে ঢোকাতে হয়, তাই ও রাখে একটা std::list-এ, আর একদম প্রথম l[1]-এই GCC 12 আটকে দেয়। তাহলে কি প্রতিটা container-এর জন্য function-টা আলাদা করে লিখতে হবে?

একটা function, vector আর list দুটোর জন্যই

Maria-র প্রথম চেষ্টা হলো Kenji-র index দিয়ে পড়াটাই, ওর list<int> l-এ: cout << l[1] - l[0];। Runner-এর flag-এ এটা error দিয়ে থেমে যায়, প্রতিটা index-এর জন্য একবার করে: error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int')। List-এর কোনো [] নেই, কারণ হেঁটে না গিয়ে ও position 1-এ লাফ দিতে পারে না। তবে দুই container-এরই যেটা আছে, সেটা হলো একটা iterator: এমন একটা position, যেটা সেখানকার element পড়তে পারে আর পরেরটায় সরে যেতে পারে।

তাই Kenji printGaps নতুন করে লেখে: এবার vector না নিয়ে নেয় দুইটা iterator, first আর last। template <typename It> লাইনটা বলে, It যেকোনো iterator type হতে পারে। তখন compiler নিজেই একটা copy লেখে vector-এর iterator-এর জন্য, আরেকটা list-এর জন্য। আইডিয়াটা Module 1-এর lesson 05 দেখিয়েছিল, আর এই track শুধু ওটার এই ছোট রূপটাই লেখে।

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
using namespace std;

template <typename It>
void printGaps(It first, It last) {
    cout << "gaps:";
    if (first != last) {
        It before = first;
        ++first;
        while (first != last) {
            cout << ' ' << *first - *before;
            before = first;
            ++first;
        }
    }
    cout << '\n';
}

int main() {
    vector<int> kenji{12, 15, 11, 18, 18};
    list<int> maria{12, 15, 11, 18, 18};
    maria.insert(next(maria.begin(), 2), 20);
    printGaps(kenji.begin(), kenji.end());
    printGaps(maria.begin(), maria.end());
    return 0;
}

gaps: 3 -4 7 0
gaps: 3 5 -9 7 0

ভেতরে function-টা শুধু != দিয়ে দুইটা iterator মেলায়, * দিয়ে পড়ে, আর ++ দিয়ে এক পা এগোয়। দুই container-ই এই তিনটা কাজ পারে, তাই একই লেখা দুটোর জন্যই compile হয়ে গেল। Maria-র list মাঝখানে 20 নিয়েছে, আর ওর gap-গুলোও সেই হিসেবে বদলে গেছে। তাই দুইটা iterator-এর উপর লেখা function চলে প্রতিটা container-এ, যেটা হাঁটতে জানে।

begin() আর end(), তিন রকম memory-তে

Module 0-এর lesson 04-এ হাঁটাটা দেখা হয়ে গেছে। begin() হলো প্রথম element, end() হলো শেষটার ঠিক পরের খালি ঘর, আর loop চলে যতক্ষণ it != end()। দুটো মিলে হয় half-open range [begin, end), যেটা যেকোনো algorithm যেকোনো container থেকে নিতে পারে। Container বদলালে যা বদলায়, তা হলো হাঁটার নিচের memory। Widget-টা একই চারটা value-এর উপর একটা loop চালায় তিনটা container-এ, প্রতিটায় পাঁচবার থেমে।

Vector ওর চারটা value পাশাপাশি রাখে একটাই block-এ, তাই ++ চলে যায় পরের ঠিকানায়। Deque রাখে নির্দিষ্ট মাপের কয়েকটা block। ছবিতে block-এ 2টা করে, কিন্তু GCC 12-এর আসল block-এ 128টা int ধরে, তাই ++ নতুন block-এ লাফ দেয় শুধু block-এর কিনারায় এসে। List-এর প্রতিটা node আলাদা করে নেওয়া memory, যেখানে খালি জায়গা মিলেছে সেখানেই, তাই ++ একটা link ধরে এগোয়। Compiler Explorer-এ একটা program তিনটার জন্যই একই হাঁটা print করেছে: 12 15 11 18, তারপর end()।

তাই loop দেখতে সব জায়গায় একই, কিন্তু একটা ++ প্রতিটা container-এ আলাদা একটা move। এই পার্থক্যই ঠিক করে দেয়, একটা iterator কোন কোন move পারবে।

পাঁচটা category: একটা iterator কী কী পারে

C++ standard iterator-গুলোকে পাঁচটা category-তে ভাগ করে, কে কোন move পারে সেই হিসেবে। প্রতিটা container-এর iterator এদের কোনো একটায় পড়ে। GCC 12 সেটা জানায় std::iterator_traits দিয়ে, যেটা lesson 02-এ চালিয়ে দেখা হবে। এই table-টা হাতের কাছে রেখো।

"Key বাদে" মানে set-এর element আর map-এর key শুধু পড়া যায়, Module 8 আর 10 যেমন দেখিয়েছে; map-এর value অবশ্য লেখা যায়। একবারই মানে iterator এগিয়ে গেলে value-টা আর থাকে না: keyboard থেকে পড়া একটা সংখ্যা দ্বিতীয়বার পড়া যায় না। Table-টা নিচ থেকে উপরে পড়ো। Random access iterator সব পারে, আর উপরের প্রতিটা row কিছু না কিছু ছেড়ে দেয়।

বাক্সগুলো একটার ভেতরে আরেকটা, কারণ প্রতিটা category ওর ভেতরেরটার সব কাজ পারে। তাই std::find, যার শুধু একটা input iterator লাগে, যেকোনো container নিয়ে চলে। std::sort চায় random access, তাই list ওটা ব্যবহার করতে পারে না, নিজেই নিজেকে sort করে, Module 5 যেমন দেখিয়েছে। সাধারণ pointer-ও random access, এজন্যই C array প্রতিটা algorithm-এর সাথে চলে।

#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>
using namespace std;

int main() {
    cout << contiguous_iterator<vector<int>::iterator> << ' '
         << random_access_iterator<vector<int>::iterator> << ' '
         << random_access_iterator<list<int>::iterator> << ' '
         << bidirectional_iterator<list<int>::iterator> << ' '
         << bidirectional_iterator<forward_list<int>::iterator> << '\n';
    return 0;
}

1 1 0 1 0

চারটা প্রান্ত: begin, end, rbegin আর rend

যে container পেছনের দিকে হাঁটতে পারে, সে আরও দুইটা প্রান্ত দেয়। rbegin() হলো শেষ element-এর উপর বসা একটা reverse iterator, আর rend() হলো প্রথমটার আগের খালি ঘর। Reverse iterator ++-কে উল্টে দেয়, তাই প্রতিটা ++ এক element করে সামনের দিকে সরে। পেছনের loop মানে সামনের loop-ই, শুধু দুইটা নামের আগে একটা r বসানো।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{12, 15, 11, 18};
    cout << "*begin() " << *v.begin() << ", *rbegin() " << *v.rbegin() << '\n';
    cout << "forward: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << ' ' << *it;
    }
    cout << "\nbackward:";
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << ' ' << *it;
    }
    cout << '\n';
    cout << "end() - begin() = " << v.end() - v.begin() << ", rend() - rbegin() = " << v.rend() - v.rbegin() << '\n';
    return 0;
}

*begin() 12, *rbegin() 18
forward:  12 15 11 18
backward: 18 11 15 12
end() - begin() = 4, rend() - rbegin() = 4

*rbegin() পড়েছে 18, শেষ value, আর পেছনের হাঁটা rend()-এ এসে সেটা না পড়েই থেমেছে। দুই range-এই চারটা করে element: rend() - rbegin() হলো 4, ঠিক end() - begin()-এর মতো। যে container-এর iterator bidirectional বা random access, তার সবারই rbegin() আছে। forward_list-এর নেই: GCC 12 বলে error: 'class std::forward_list<int>' has no member named 'rbegin'; did you mean 'begin'?, আর একটা unordered_set-ও একই উত্তর পায়। তাই পেছনে হাঁটো rbegin() আর rend() দিয়ে, আর test হিসেবে !=-ই রাখো।

cbegin(): যে হাঁটা শুধু পড়ে

cbegin() আর cend() হলো এমন হাঁটার begin() আর end(), যেটা কথা দেয় কিছু লিখবে না। এরা ফেরত দেয় একটা const_iterator, যেটা *it পড়ে কিন্তু *it = x মানে না। crbegin() আর crend() একই কথা দেয় পেছনের দিকে। Loop যখন শুধু দেখে, তখন এগুলো নাও, আর compiler তোমাকে কথাটা রাখতে বাধ্য করবে। নিচের Example 3 GCC 12-এর নিজের ভাষায় সেই না-টা দেখায়।

List-এর iterator যা করতে রাজি না

List-এর iterator bidirectional: ও ++ আর -- দিয়ে চলে, একবারে এক link। ওর কোনো + n নেই, <-ও নেই, কারণ এর কোনোটাই link ধরে এক পা না। GCC 12 l.begin() + 2 আর it < l.end() বাতিল করে দেয়, আর ভুল 2 আর 3 ওর বার্তাগুলো তুলে দেখায়। এর বদলে k পা সরতে লেখো std::next(it, k), আর প্রতিটা loop শেষ করো != দিয়ে।

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main() {
    list<int> l{12, 15, 11, 18};
    auto third = next(l.begin(), 2);
    cout << "third: " << *third << '\n';
    --third;
    cout << "one back: " << *third << '\n';
    int steps = 0;
    for (auto it = l.begin(); it != l.end(); ++it) {
        steps++;
    }
    cout << "steps to end(): " << steps << '\n';
    return 0;
}

third: 11
one back: 15
steps to end(): 4

next(l.begin(), 2) দুইটা link পেরিয়ে 11-এ পৌঁছেছে, আর --third এক পা পিছিয়ে 15-এ এসেছে। != দেওয়া loop end()-এ পৌঁছাতে চার পা নিয়েছে। Vector-এ next এক লাফে যায়, আর list-এ হেঁটে যায়; পার্থক্যটা lesson 02 মেপে দেখাবে। তাই next আর != লেখো, তাহলে একই code প্রতিটা container-এ চলবে।

Iterator কখন আর valid থাকে না

Iterator শুধুই একটা position। Container যদি ওর element-গুলো সরিয়ে ফেলে, আগে রাখা iterator তখনো পুরোনো জায়গাটাই দেখায়, আর সেটা হয়ে যায় invalidated। ওটা দিয়ে পড়া undefined behaviour: তখন কী হবে, C++ standard তার কোনো কথাই দেয় না। Vector নিজের block ছাড়িয়ে বড় হলে সবকিছু সরিয়ে নেয়, Module 2 যেমন দেখিয়েছে। এই program একটা vector-কে ওর capacity 4 পর্যন্ত ভরে, তারপর পঞ্চম একটা value যোগ করে।

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    v.reserve(4);
    for (int x : {10, 20, 30, 40}) v.push_back(x);
    const int* before = v.data();
    cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
    v.push_back(50);
    cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
    cout << "first element moved: " << (v.data() != before) << '\n';
    return 0;
}

size 4, capacity 4
size 5, capacity 8
first element moved: 1

পঞ্চম value-টা আর ধরেনি, তাই vector 8-এর একটা নতুন block নিয়েছে, চারটা value সেখানে সরিয়েছে, আর পুরোনো block ছেড়ে দিয়েছে। push_back(50)-এর আগে রাখা একটা iterator এখনো সেই ছেড়ে দেওয়া block-এর দিকেই তাকিয়ে আছে। কেউ সাবধান করবে না, আর কপাল ভালো থাকলে program হয়তো পুরোনো value-টাই print করে দেবে। তাই vector বড় হতে পারে এমন যেকোনো কাজের পরে begin() থেকে নতুন iterator নাও। প্রতিটা container-এর নিয়ম দেবে lesson 02, আর lesson 05 সরানোটা ধাপে ধাপে আবার দেখাবে।

প্রথম দিনেই যে syntax লাগবে

c.begin()    c.end()          the first element, and the empty slot past the last
c.rbegin()   c.rend()         the last element, and the empty slot before the first
c.cbegin()   c.cend()         begin and end for a walk that only reads
*it                           the element it points at (never *c.end())
++it                          one step forward, on every container
--it                          one step back (not forward_list, not unordered)
it != c.end()                 the loop test that works on every container
next(it, k)   prev(it, k)     a copy of it moved k steps forward or back

template <typename It>
void f(It first, It last)     one function for any container's range

তাই একটাই loop-এর ছাঁচ, begin() থেকে end(), সাথে != আর ++, এই track-এর প্রতিটা container-এ হাঁটে।

#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <vector>
using namespace std;

template <typename It>
void printAll(It first, It last) {
    cout << '[';
    for (It it = first; it != last; ++it) {
        if (it != first) {
            cout << ", ";
        }
        cout << *it;
    }
    cout << "]\n";
}

int main() {
    vector<int> marks{4, 8, 15};
    list<string> snacks{"tea", "bun", "jam"};
    printAll(marks.begin(), marks.end());
    printAll(snacks.begin(), snacks.end());
    printAll(next(snacks.begin()), snacks.end());
    printAll(marks.end(), marks.end());
    return 0;
}

[4, 8, 15]
[tea, bun, jam]
[bun, jam]
[]

#include <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> history{"home", "news", "maps", "mail"};
    history.push_back("music");
    cout << "newest first:\n";
    int n = 1;
    for (auto it = history.rbegin(); it != history.rend(); ++it) {
        cout << n << ". " << *it << '\n';
        n++;
    }
    cout << "now on " << *history.rbegin() << ", Back goes to " << *next(history.rbegin()) << '\n';
    return 0;
}

newest first:
1. music
2. mail
3. maps
4. news
5. home
now on music, Back goes to mail

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 45, 80, 300, 60};
    int total = 0;
    int over100 = 0;
    for (auto it = price.cbegin(); it != price.cend(); ++it) {
        total += *it;
        if (*it > 100) {
            over100++;
        }
    }
    cout << "total " << total << ", over 100: " << over100 << '\n';
    cout << "first price still " << price[0] << '\n';
    return 0;
}

total 605, over 100: 2
first price still 120

list<int> l{12, 15, 11, 18};
cout << l[1] - l[0] << '\n';

list<int> l{12, 15, 11, 18};
auto it = l.begin() + 2;

for (auto it = l.begin(); it < l.end(); ++it) {
    cout << *it << ' ';
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{10, 20, 30, 40};
    cout << *v.rbegin() << ' ' << (v.rbegin().base() == v.end()) << '\n';
    return 0;
}

#include <deque>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Every height until the input ends: lesson 02 explains this line.
    vector<int> height(istream_iterator<int>(cin), {});

    deque<int> view;   // the positions with a sea view, west to east
    // Walk from the sea end with a reverse iterator and keep the tallest
    // height seen so far. A building taller than all of them has the view:
    // put its position, counted from 1, at the front of view.

    cout << view.size() << '\n';
    // Print the positions in view, separated by single spaces.
    return 0;
}

#include <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;

int main() {
    string line;
    cin >> line;
    list<char> days(line.begin(), line.end());   // one letter per day

    // Walk days with an iterator. For every run of equal letters, print the
    // letter and the length of the run, the runs separated by single spaces.

    return 0;
}

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> readings(n);
    for (int& x : readings) {
        cin >> x;
    }

    // Walk readings with an iterator. Between two neighbours that differ by
    // more than d, insert their average (their sum divided by 2, rounded
    // down). A value you inserted is never compared again. Then print
    // readings on one line, separated by single spaces.

    return 0;
}

এরপর lesson 02 iterator-এর প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটা category-তে কোনটার খরচ কত, সেটাসহ।