array আর deque: যে size তুমি ঠিক করে দাও, আর যে লাইন দুই মাথাতেই বাড়ে

Kenji-র step counter প্রতিদিনের জন্য একটা করে সংখ্যা দেখায়, সোমবার থেকে রবিবার। দিন ঠিক সাতটা, আর program লেখার সময়েই ও সেটা জানে। Alice-এর সমস্যা আবার অন্যরকম। ওর দোকানের লাইনে customer পেছনে এসে দাঁড়ায়, সামনে থেকে সার্ভিস পায়, আর কোনো VIP এলে সোজা সামনে চলে যায়। এই lesson দুজনকেই মাপমতো একটা করে container দেবে: সপ্তাহের জন্য std::array, আর লাইনের জন্য std::deque।

দুইটা সমস্যা, যেখানে vector ঠিক খাপ খায় না

Kenji প্রথমে সপ্তাহটা রাখে একটা C array-তে, C track যেমন শিখিয়েছিল। তারপর ওটা একটা function-এ পাঠায়, আর array-টা নিজের size-ই ভুলে যায়।

#include <iostream>
using namespace std;

void show(int steps[]) {
    cout << "inside show: " << sizeof(steps) << " bytes\n";
}

int main() {
    int steps[7] = {3000, 4500, 12000, 8000, 12000, 2000, 6000};
    cout << "in main: " << sizeof(steps) << " bytes\n";
    show(steps);
    return 0;
}

in main: 28 bytes
inside show: 8 bytes

main-এ 4 byte করে সাতটা int মানে 28 byte। কিন্তু show-এর ভিতরে parameter-টা শুধু প্রথম বাক্সের একটা pointer, আর Playground-এ একটা pointer 8 byte। -Wall ছাড়াও GCC 12 এটা নিয়ে warning দেয়: warning: 'sizeof' on array function parameter 'steps' will return size of 'int*' [-Wsizeof-array-argument]। তাই function-এ পাঠালে C array নিজের size ফেলে রেখে যায়, আর C track-এ এর সমাধান ছিল গুনতির জন্য আলাদা একটা parameter।

Alice-এর লাইন একটা vector-এ রাখা যেত। পেছনে দাঁড়ানো মানে push_back, ওটা সস্তা। কিন্তু সামনে থেকে সার্ভিস দেওয়া মানে v.begin() erase করা, আর VIP মানে ঠিক ওখানেই insert। দুই ক্ষেত্রেই বাকি সব customer এক বাক্স করে সরে। Module 2-এর lesson 02-এ vector-এর সামনে 100,000টা insert মেপে পাওয়া গিয়েছিল প্রায় এক সেকেন্ডের তিন ভাগের এক ভাগ। তাই সপ্তাহের দরকার এমন একটা fixed size, যেটা type নিজেই মনে রাখে, আর লাইনের দরকার দুইটা সস্তা মাথা।

ছবিটা: deque মানে কয়েকটা block আর একটা map

Deque (উচ্চারণ "ডেক", double-ended queue-এর ছোট রূপ) এমন একটা sequence, যেটা দুই মাথাতেই বাড়ে। Vector-এর মতো ও একটা লম্বা block রাখে না। ও রাখে একই মাপের কয়েকটা ছোট block। আর pointer-এর একটা ছোট তালিকা, যার নাম map, বলে দেয় কোন block প্রথমে, কোনটা দ্বিতীয়, কোনটা তৃতীয়।

শেষের block ভরে গেলে push_back ওটার পরে নতুন একটা block জুড়ে দেয়। প্রথম block-এর সামনে জায়গা না থাকলে push_front ওটার আগে নতুন একটা block জুড়ে দেয়। দুই ক্ষেত্রেই কোনো element নড়ে না, map-এ শুধু একটা pointer বাড়ে। আর কোনো pop একটা block খালি করে দিলে deque ওই block-টা free করে দেয়।

এবার নড়াচড়াটা দেখো। নিচের প্রতিটা ধাপ একই deque-এর উপর একটা করে call। খেয়াল করো কখন পেছনে একটা block এসে জোড়ে, কখন সামনে একটা block খোলে, আর কোন দুইটা pop একটা করে block free করে দেয়।

এই ছবিতে প্রতি block-এ 4টা element, যাতে এক block থেকে আরেক block-এ যাওয়াটা চোখে পড়ে। GCC 12-এ আসল block 512 byte, তাতে ধরে 128টা int, আর ওর library প্রথম push-এর আগেই একটা block বানিয়ে রাখে। এসবই মেপে দেখাবে lesson 05। তাই deque সামনের দিকে বাড়ে সামনে একটা block জুড়ে দিয়ে, আর যা আগে থেকে রাখা আছে, তার কিছুই সরাতে হয় না।

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

#include <array>
#include <deque>

array<T, N> a{...};          N elements of T; N is fixed in the code
a[i]                          the element at index i, 0 to N - 1
a.size()                      N, always
a.at(i)                       like a[i], but checks i first
a == b                        true when every element is equal

deque<T> d;                   an empty deque of T
d.push_back(x);               add x at the back
d.push_front(x);              add x at the front
d.pop_back();                 remove the back element
d.pop_front();                remove the front element
d.front()   d.back()          the first and the last element
d[i]                          the element at index i, 0 to d.size() - 1
d.size()    d.empty()         how many, and whether there are none

তাই array declare হয় একটা type আর একটা গুনতি দিয়ে, আর deque-এর দুই মাথাতেই একটা করে সস্তা push আর pop আছে।

std::array: যে C array নিজের size জানে

একটা std::array ওর element-গুলো ঠিক C array-র মতোই একই বাক্সে রাখে। তফাতটা type-এ: গুনতিটা type-এরই অংশ। তাই যে function const array<int, 7>& নেয়, সে পুরো সপ্তাহটাই হাতে পায়, আর size() তখনো বলে 7।

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

int goal_days(const array<int, 7>& steps) {
    int count = 0;
    for (int s : steps) {
        if (s >= 10000) {
            count++;
        }
    }
    return count;
}

int main() {
    array<int, 7> steps{3000, 4500, 12000, 8000, 12000, 2000, 6000};
    cout << "days: " << steps.size() << '\n';
    cout << "Wednesday: " << steps[2] << '\n';
    cout << "days at 10000 or more: " << goal_days(steps) << '\n';
    cout << "sizeof: " << sizeof(steps) << " bytes\n";
    return 0;
}

days: 7
Wednesday: 12000
days at 10000 or more: 2
sizeof: 28 bytes

goal_days-এর ভিতরের range-for কাজ করে, কারণ function তখনো জানে সপ্তাহটা কোথায় শেষ। আর sizeof হলো 28, C array-র সমান: element-গুলোর পাশে লুকানো কোনো গুনতি রাখা নেই। 7 থাকে type-এ, আর type compiler জানে, তাই program চলার সময় এর জন্য কোনো memory খরচ হয় না।

তাই একটা std::array memory-তে C array-র মতোই, শুধু গুনতিটা ওর type-এ লেখা থাকে।

Array copy হয়, তুলনাও হয়

C array = দিয়ে copy করা যায় না। b = a;-এ এসে GCC 12 থেমে যায় error: invalid array assignment দিয়ে, আর দুইটা C array-তে == তুলনা করে ওদের address, বাক্সগুলো না। এখানে std::array চলে একটা int-এর মতো: = প্রতিটা element copy করে, আর == প্রতিটা element মিলিয়ে দেখে।

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

int main() {
    array<int, 3> monday{5, 7, 9};
    array<int, 3> copy = monday;
    copy[0] = 100;
    cout << monday[0] << ' ' << copy[0] << '\n';
    cout << (monday == copy) << '\n';
    copy[0] = 5;
    cout << (monday == copy) << '\n';
    return 0;
}

5 100
0
1

copy বদলানোয় monday-এ হাতই পড়েনি, তাই copy-টা সত্যিকারের। একটা element আলাদা থাকা পর্যন্ত তুলনা print করেছে 0 (মিথ্যা), আর তিনটাই মিলে যাওয়ার পরে 1 (সত্যি)। একে বলে value semantics: পুরো array-টা একটা সংখ্যার মতোই একটা মান। তাই শুধু পড়ার জন্য function-এ পাঠালে const& দিয়ে পাঠাও, নইলে আস্ত একটা copy তৈরি হবে।

Size হলো type-এর অংশ

array<int, 7> আর array<int, 8> দুইটা আলাদা type, ঠিক যেমন int আর double আলাদা। সপ্তাহের জন্য লেখা function আট দিন নেবে না। Bob উপরের goal_days দিয়ে চেষ্টা করে দেখে।

array<int, 8> eight{};
cout << goal_days(eight) << '\n';

GCC 12 রাজি হয় না: error: invalid initialization of reference of type 'const std::array<int, 7>&' from expression of type 'std::array<int, 8>'। এটা আসলে একটা উপহার। C-এর function যেকোনো int* নিয়ে নিত, আর শেষের পরেও পড়তে থাকত। তাই গুনতিটা compiler তোমার হয়ে check করে, আর সেজন্যই program compile হওয়ার সময়েই গুনতিটা জানা থাকতে হয়।

deque: যে লাইনের দুই মাথাই খোলা

Vector-এর খোলা মাথা একটা। Deque-এর দুইটাই খোলা। এই program widget-এর এগারোটা call আবার চালায়, আর কয়েকটা ধাপ পরপর লাইনটা print করে। Block না, মানগুলোর দিকে চোখ রাখো: deque ওর block তোমার কাছ থেকে লুকিয়ে রাখে।

#include <deque>
#include <iostream>
#include <string>
using namespace std;

void show(const string& call, const deque<int>& d) {
    cout << call << ":";
    for (int x : d) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    deque<int> d;
    for (int x = 10; x <= 50; x += 10) {
        d.push_back(x);
    }
    show("five push_back", d);
    d.push_front(5);
    d.push_front(1);
    show("two push_front", d);
    d.pop_back();
    show("pop_back", d);
    d.pop_front();
    d.pop_front();
    show("two pop_front", d);
    return 0;
}

five push_back: 10 20 30 40 50
two push_front: 1 5 10 20 30 40 50
pop_back: 1 5 10 20 30 40
two pop_front: 10 20 30 40

দ্বিতীয় push_front 1-কে বসিয়েছে 5-এর আগে, তাই সামনে সবসময় থাকে সবচেয়ে নতুন push_front। Vector-এর pop_back-এর মতোই দুই pop-ই শুধু সরায়, কিছু return করে না। তাই deque হলো এমন একটা vector, যার সামনে আরেকটা দরজা আছে।

Index দিয়ে পড়া এখনো চলে

Deque-এ d[i], d.at(i) আর d.size() সবই আছে, গোনা হয় সামনে থেকে, 0 থেকে d.size() - 1 পর্যন্ত। একটা push_front সবার নম্বর বদলে দেয়: পুরোনো d[0] হয়ে যায় d[1]।

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

int main() {
    deque<int> d{20, 30, 40};
    cout << "d[0] = " << d[0] << ", size " << d.size() << '\n';
    d.push_front(10);
    cout << "d[0] = " << d[0] << ", d[1] = " << d[1] << ", size " << d.size() << '\n';
    for (size_t i = 0; i < d.size(); i++) {
        d[i] *= 2;
    }
    cout << "last: " << d[d.size() - 1] << '\n';
    return 0;
}

d[0] = 20, size 3
d[0] = 10, d[1] = 20, size 4
last: 80

d[i]-এর পেছনে deque হিসাব করে বের করে, element i কোন block-এ আছে, আর সেই block-এর কোন slot-এ। তাই একটা read-এ দুই ধাপ লাগে, যেখানে vector-এর লাগে এক ধাপ। তবুও size যা-ই হোক, কাজটা একটা নির্দিষ্ট পরিমাণই। তাই vector-এর মতোই deque-এ index দিয়ে পড়ো, শুধু মনে রেখো সামনেটা সরে যায়।

খালি deque: Zara-র প্রথম test

Zara সবসময় খালি case আগে চালায়। ও একটা খালি লাইনকে জিজ্ঞেস করে, সামনে কে আছে।

deque<int> line;
cout << "first in line: " << line.front() << '\n';

Runner-এর flag-এ এটা কোনো বার্তা ছাড়াই compile হয়েছে। Compiler Explorer-এর GCC 12.2-এ একবার চালাতে print করেছে first in line: 0, আর স্বাভাবিকভাবেই শেষ হয়েছে। ওই 0 কোনো customer না। খালি deque-এ front() হলো undefined behaviour: কী হবে, standard কিছুই বলে না, তাই অন্য দিন অন্য সংখ্যা আসতে পারে, crash-ও হতে পারে। চুপচাপ একটা ভুল 0 সবচেয়ে খারাপ উত্তর। তাই front(), back() বা কোনো pop-এর আগে if (!line.empty()) check করো।

#include <array>
#include <iostream>
#include <string>
using namespace std;

int main() {
    array<string, 3> medals{"gold", "silver", "bronze"};
    for (size_t i = 0; i < medals.size(); i++) {
        cout << i + 1 << ": " << medals[i] << '\n';
    }
    return 0;
}

1: gold
2: silver
3: bronze

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

int main() {
    deque<int> d{20, 30};
    d.push_front(10);
    d.push_back(40);
    cout << "front " << d.front() << ", back " << d.back() << ", size " << d.size() << '\n';
    return 0;
}

front 10, back 40, size 4

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

int main() {
    deque<int> line;
    line.push_back(101);
    line.push_back(102);
    line.push_front(7);

    for (int turn = 1; turn <= 4; turn++) {
        if (line.empty()) {
            cout << "turn " << turn << ": nobody waiting\n";
        } else {
            cout << "turn " << turn << ": serving ticket " << line.front() << '\n';
            line.pop_front();
        }
    }
    return 0;
}

turn 1: serving ticket 7
turn 2: serving ticket 101
turn 3: serving ticket 102
turn 4: nobody waiting

int n;
cin >> n;
array<int, n> a{};

#include <iostream>
using namespace std;

int main() {
    array<int, 7> steps{};
    cout << steps.size() << '\n';
    return 0;
}

array<int, 7> week{};
array<int, 8> eight{};
week = eight;

deque<int> line;
line.pop_front();
cout << line.front() << '\n';

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

void c_week(int steps[7]) {
    cout << sizeof(steps) << '\n';
}

void std_week(const array<int, 7>& steps) {
    cout << sizeof(steps) << '\n';
}

int main() {
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    array<int, 7> b{1, 2, 3, 4, 5, 6, 7};
    c_week(a);
    std_week(b);
    return 0;
}

#include <array>
#include <iostream>
#include <string>
using namespace std;

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

    const array<string, 7> days{"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};

    int w = 0;
    cin >> w;
    for (int week = 0; week < w; week++) {
        array<int, 7> steps{};
        for (int d = 0; d < 7; d++) {
            cin >> steps[d];
        }

        // Print this week's total, one space, and the name of the day
        // with the most steps (the earliest such day on a tie).
    }
    return 0;
}

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

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

    int n;
    cin >> n;
    deque<int> row;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // Odd x goes to the front of row, even x to the back.
    }

    // Print row from front to back, separated by single spaces.

    return 0;
}

#include <array>
#include <iostream>
#include <string>
using namespace std;

int main() {
    const array<string, 7> days{"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    int k;
    cin >> k;
    array<int, 7> steps{};
    for (int& s : steps) {
        cin >> s;
    }

    // For each start day, add k days in a row, wrapping after Sunday.
    // Keep the best total and its start day (the earliest on a tie).

    return 0;
}

এরপর lesson 02 দুই container-এরই প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ।