vector: যে বাক্সগুলো নিজে নিজে বাড়ে

Amara ক্লাসের নম্বরগুলো একটা program-এ তুলছে, এক লাইনে একটা করে, খাতার স্তূপ শেষ না হওয়া পর্যন্ত। খাতা কয়টা, ও জানে না। C track-এর Module 14-এ এই কাজে লেগেছিল malloc, realloc, একটা capacity variable, আর বেশিরভাগ মানুষের কপালে অন্তত একটা bug। C++-এ পুরো ব্যাপারটা loop-এর ভিতরে একটা লাইন: marks.push_back(x);। এই lesson ওই লাইনটা দেখাবে, আর তোমার চোখের আড়ালে ও কী করে, সেটাও।

সমস্যাটা: কয়টা আসবে, জানা নেই

C-এর array-এর size ঠিক হয়ে যায় program চলার আগেই। Input যদি array-এর চেয়ে লম্বা হয়, array overflow করে। ছোট হলে বাড়তি বাক্সগুলো অকারণে বসে থাকে। এর C++ উত্তর হলো vector: array-এর মতোই একই type-এর এক সারি বাক্স, কিন্তু শেষে কিছু যোগ করলে নিজে নিজেই বড় হয়। এটা থাকে <vector> header-এ, আর এর পুরো নাম std::vector।

এই হলো Amara-র program। Input শেষ না হওয়া পর্যন্ত নম্বর পড়ে, তারপর বলে কয়টা পড়ল আর ওদের গড় কত।

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

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

    vector<int> marks;
    int x;
    while (cin >> x) {
        marks.push_back(x);
    }

    long long total = 0;
    for (int m : marks) {
        total += m;
    }
    cout << marks.size() << " marks\n";
    cout << "average " << (double)total / marks.size() << '\n';
    return 0;
}

5 marks
average 71.2

ওই output-টা input 70 85 62 91 48-এর জন্য। পুরো program-এ কোথাও কোনো size লেখা নেই। Module 1-এ যেমন দেখেছ, input শেষ হলেই while (cin >> x) থেমে যায়, আর প্রতিটা push_back শেষে একটা করে নম্বর জুড়ে দেয়। তাই vector ঠিক input-এর সমান লম্বা হয়।

Zara সবসময় যা আগে করে, এবারও তাই করে: খালি input দিয়ে চালায়। Program print করে 0 marks, তারপর average -nan, কারণ 0.0 / 0 কোনো সংখ্যাই না। নিচের Example 2 আর 3 ভাগ করার বা পড়ার আগে দেখে নেয়, vector খালি কি না।

এক সারি বাক্স, যেটা নিজে বড় হয়

Vector ওর element-গুলো রাখে memory-র একটাই block-এ, পাশাপাশি, ঠিক C array-এর মতো। Element মানে একটা বাক্স। Block-এর শেষে সাধারণত কয়েকটা বাড়তি বাক্স থাকে, যাতে পরের push_back এসে জায়গা পায়।

তাই একটা vector-এর দুইটা সংখ্যা থাকে। ওর size মানে এই মুহূর্তে ও কয়টা element ধরে আছে। ওর capacity মানে block-এ কয়টা বাক্সের জায়গা আছে। Size কখনো capacity-র চেয়ে বেশি হয় না। C track-এ এই দুইটা সংখ্যা তুমি নিজে দুইটা variable-এ রাখতে, আর vector দুটোই তোমার হয়ে রাখে।

তাই size হলো তুমি কয়টা রেখেছ, আর capacity হলো vector আগে থেকেই কতটা জায়গা আলাদা করে রেখেছে।

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

#include <vector>

vector<T> v;                  an empty vector of T
vector<int> v(n, 0);          n elements, every one 0
vector<int> v{1, 2, 3};       exactly these three elements
v.push_back(x);               add x at the end
v[i]                          the element at index i, 0 to v.size() - 1
v.size()                      how many elements it holds
v.empty()                     true when it holds none

তাই vector declare করো angle bracket-এ element-এর type লিখে, আর বাকি সবকিছু হলো dot দিয়ে ওর উপর একটা call।

Vector বানানোর চার উপায়

Vector তুমি বানাবে চার রকম চেহারায়। এই program প্রতিটার একটা করে বানায়, তারপর ওদের size আর element-গুলো print করে।

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

void show(const char* name, const vector<int>& v) {
    cout << name << ": size " << v.size() << " [";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << " ]\n";
}

int main() {
    vector<int> empty_one;
    vector<int> zeros(5);
    vector<int> sevens(5, 7);
    vector<int> listed{3, 1, 4};

    show("empty_one", empty_one);
    show("zeros", zeros);
    show("sevens", sevens);
    show("listed", listed);
    return 0;
}

empty_one: size 0 [ ]
zeros: size 5 [ 0 0 0 0 0 ]
sevens: size 5 [ 7 7 7 7 7 ]
listed: size 3 [ 3 1 4 ]

চারটা লাইনের মানে নিচের table-এ।

Initialiser ছাড়া C array-তে garbage থাকতে পারে, কিন্তু vector<int> v(n)-এ কখনো garbage থাকে না, ওর element-গুলো শুরু হয় 0 দিয়ে। Helper show vector-টা নেয় const& দিয়ে, মানে Module 1-এর সেই read-only দ্বিতীয় নাম, তাই কোনো copy হয় না। তাই গোল bracket দেয় একটা গুনতি, আর braces দেয় একটা তালিকা। কথাটা মনে রেখো, মাথা খাটাও অংশে লাগবে।

push_back, আর input শেষ হওয়া পর্যন্ত পড়া

সবচেয়ে বেশি যে call লিখবে, সেটা push_back। Input-এর loop-এ ও "কয়টা আসবে জানি না"-কে বানিয়ে দেয় "জানার দরকারই নেই"। n জানা থাকলেও খালি vector-এ push_back দিয়ে পড়তে পারো, অথবা আগে size ঠিক করে index ধরে পড়তে পারো। দুটোই ঠিক।

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

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> b;
    int x;
    while (cin >> x) {
        b.push_back(x);
    }

    cout << "a has " << a.size() << ", b has " << b.size() << '\n';
    return 0;
}

a has 3, b has 4

ওই output-টা input 3, তারপর 10 20 30, তারপর 7 8 9 6-এর জন্য। প্রথম loop ঠিক n-টা মান পড়ে, এমন বাক্সে যেগুলো আগে থেকেই আছে। দ্বিতীয়টা বাকি যা থাকে, সব নিয়ে নেয়। তাই a[i] আগে থেকে থাকা একটা element ভরে, আর push_back একদম নতুন একটা বানায়।

জায়গা ফুরিয়ে গেলে ভিতরে কী হয়

Block ভরা থাকলে push_back ওটাকে টেনে লম্বা করতে পারে না, কারণ block-এর ঠিক পরের memory হয়তো অন্য কারও। তাই vector চারটা কাজ করে: নতুন, আরও বড় একটা block চায়, প্রতিটা element সেখানে copy করে, পুরোনো block-টা free করে, তারপর নতুন element-টা যোগ করে। এটাকেই বলে reallocation।

এবার নিজের চোখে দেখো। এই program একটা খালি vector-এ পাঁচটা নম্বর push করে। প্রতিটা call-এর পরে print করে size, capacity, আর element-গুলো এখন নতুন block-এ উঠেছে কি না। data() return করে block-টা কোথায় শুরু, তাই data() বদলে গেলে বুঝবে vector জায়গা বদলেছে।

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

int main() {
    vector<int> marks;
    int input[] = {70, 85, 62, 91, 48};
    for (int x : input) {
        const int* before = marks.data();
        marks.push_back(x);
        cout << "push_back(" << x << "): size " << marks.size()
             << ", capacity " << marks.capacity();
        if (marks.data() != before) {
            cout << ", new block";
        }
        cout << '\n';
    }
    return 0;
}

push_back(70): size 1, capacity 1, new block
push_back(85): size 2, capacity 2, new block
push_back(62): size 3, capacity 4, new block
push_back(91): size 4, capacity 4
push_back(48): size 5, capacity 8, new block

নিচে একই পাঁচটা call এক এক ধাপ করে চালিয়ে দেখো। প্রতিটা ধাপে দেখবে আগের আর পরের block, আর কয়টা element copy হলো।

আমাদের compiler-এ capacity দ্বিগুণ হয়: 1, 2, 4, 8, তারপর 16, 32, এভাবে। কত গুণ বাড়বে, C++ standard সেটা বেঁধে দেয় না। ও শুধু কথা দেয়, অনেকগুলো call মিলিয়ে ধরলে গড়ে push_back-এর খরচ constant time। তাই copy খুব কমই হয়: বেশিরভাগ call শুধু একটা ফাঁকা বাক্স ভরে। পুরো হিসাবটা করে দেখাবে lesson 05।

তাই push_back প্রায় প্রতিবারই সস্তা, শুধু মাঝে মাঝে পুরো vector-টা অন্য জায়গায় সরিয়ে নেয়।

Index, আর শেষ index

Vector-এর element-গুলোর নম্বর array-এর মতোই, শুরু 0 থেকে। n size-এর vector-এ index চলে 0 থেকে n - 1 পর্যন্ত। শেষ element হলো v[v.size() - 1], আর এর ছোট রূপ v.back() দেখাবে lesson 02।

Bob Amara-র নম্বরগুলো print করছে। শেষেরটা যেন কোনোভাবেই বাদ না পড়ে, তাই ও লেখে <=।

vector<int> marks{70, 85, 62, 91, 48};
for (int i = 0; i <= marks.size(); i++) {
    cout << marks[i] << ' ';
}

Playground-এ এটা কোনো বার্তা ছাড়াই compile হয়েছে, আর শেষ হয়েছে সফল badge নিয়ে। Print করেছে 70 85 62 91 48 0। শেষের 0-টা হলো marks[5], আর ওই বাক্সটা কোনো element না: block-এর ঠিক পরে memory-তে যা পড়ে ছিল, সেটাই। C track-এর array lesson-এর সেই একই নীরব bug, কারণ v[i] কিছুই check করে না। অন্য দিনে বা অন্য মেশিনে ওই 0 যেকোনো সংখ্যা হতে পারে, এমনকি program crash-ও করতে পারে।

ঠিক করতে লেখো i < marks.size()। তুমি <= লিখবে, কারণ "size পর্যন্ত" শুনলে মনে হয় size-ও তার মধ্যে পড়ে। তাই একটা index সীমার মধ্যে থাকে তখনই, যখন 0 <= i আর i < v.size()। যে at() নিজেই check করে, সেটা দেখাবে lesson 02।

size() একটা unsigned সংখ্যা

v.size() কোনো int return করে না। ও return করে size_t, একটা unsigned type: এমন পূর্ণসংখ্যা, যেটা কখনো negative হয় না। Playground-এ এটা 64 bit চওড়া। তাই 0-এর নিচে নামতে গেলে ঘুরে একদম উপরের মাথায় চলে যায়, C track-এর Module 2-এ unsigned সংখ্যা যেমন করেছিল।

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

int main() {
    vector<int> v;
    cout << "size: " << v.size() << '\n';
    cout << "size - 1: " << v.size() - 1 << '\n';
    return 0;
}

size: 0
size - 1: 18446744073709551615

Zara সবসময় আগে খালি input চালায়। এবার ও Bob-এর "শেষ index" loop-টা একটা খালি vector-এ চালিয়ে দেখে।

vector<int> v;
for (int i = 0; i <= v.size() - 1; i++) {
    cout << v[i] << '\n';
}

Bob ভেবেছিল loop একবারও চলবে না। কিন্তু v.size() - 1 হলো 18446744073709551615, তাই i <= ... test-টা সবসময় সত্যি থাকে, আর loop খালি vector ছাড়িয়ে বহু দূর পর্যন্ত পড়তে থাকে। Playground-এ কিছুই print না করে এটা শেষ হয়েছে Runtime error badge নিয়ে।

Playground -Wall ছাড়া compile করে, তাই কিছুই বলে না। নিজের মেশিনে -Wall -Wextra দিলে GCC 12 দুই রকম type মেশানো নিয়ে warning দেয়: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]। লেখো i < v.size(), যেটা দাঁড়ায় 0 < 0, মানে মিথ্যা, অথবা আগে v.empty() check করো। তাই vector খালি না, এটা নিশ্চিত হওয়ার আগে কখনো size() থেকে বিয়োগ কোরো না।

Range-for প্রতিটা element ঘুরে আসে

যখন প্রতিটা element ক্রম ধরে লাগবে, কিন্তু index লাগবে না, তখন Module 1-এর range-for-ই সবচেয়ে পরিষ্কার loop। for (int m : marks) তোমাকে প্রতিটা element-এর একটা copy দেয়। for (int& m : marks) দেয় প্রতিটার একটা দ্বিতীয় নাম, তাই যা বদলাবে, সেটা vector-এ গিয়ে পৌঁছাবে।

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

int main() {
    vector<int> marks{70, 85, 62};

    for (int m : marks) {
        m += 5;
    }
    cout << "after the copy loop:";
    for (int m : marks) {
        cout << ' ' << m;
    }
    cout << '\n';

    for (int& m : marks) {
        m += 5;
    }
    cout << "after the reference loop:";
    for (int m : marks) {
        cout << ' ' << m;
    }
    cout << '\n';
    return 0;
}

after the copy loop: 70 85 62
after the reference loop: 75 90 67

তাই শুধু পড়তে চাইলে int m (element বড় হলে const int& m), আর বদলাতে চাইলে int& m। Range-for কখনো শেষের বাইরে যায় না, তাই Bob-এর ভুলটা এখানে হতেই পারে না।

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

int main() {
    vector<double> temps;
    temps.push_back(21.5);
    temps.push_back(23.0);
    temps.push_back(19.75);

    cout << temps.size() << " readings\n";
    for (size_t i = 0; i < temps.size(); i++) {
        cout << "temps[" << i << "] = " << temps[i] << '\n';
    }
    return 0;
}

3 readings
temps[0] = 21.5
temps[1] = 23
temps[2] = 19.75

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

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

    vector<int> marks;
    int x;
    while (cin >> x) {
        marks.push_back(x);
    }
    if (marks.empty()) {
        cout << "no marks\n";
        return 0;
    }

    int best = marks[0];
    cout << "marks:";
    for (int m : marks) {
        cout << ' ' << m;
        if (m > best) {
            best = m;
        }
    }
    cout << '\n' << marks.size() << " marks, highest " << best << '\n';
    return 0;
}

marks: 70 85 62 91 48
5 marks, highest 91

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

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

    vector<int> prices;
    int p;
    while (cin >> p) {
        prices.push_back(p);
    }

    if (prices.empty()) {
        cout << "no prices\n";
        return 0;
    }

    long long total = 0;
    for (size_t i = 0; i < prices.size(); i++) {
        cout << "item " << i + 1 << ": " << prices[i] << '\n';
        total += prices[i];
    }
    cout << "total: " << total << '\n';
    cout << "last item: " << prices[prices.size() - 1] << '\n';
    return 0;
}

item 1: 120
item 2: 45
item 3: 300
item 4: 80
total: 545
last item: 80

vector<int> marks;
for (int i = 0; i < 3; i++) {
    cin >> marks[i];
}

#include <iostream>
using namespace std;

int main() {
    vector<int> marks;
}

int n = 3;
vector<int> marks(n);
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    marks.push_back(x);
}

vector<int> marks{70, 85};
cout << marks << '\n';

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

int main() {
    vector<int> kenji(5);
    vector<int> maria{5};
    cout << kenji.size() << ' ' << maria.size() << '\n';
    return 0;
}

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

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

    vector<int> marks;
    int x;
    while (cin >> x) {
        marks.push_back(x);
    }

    // Print the marks from the last element back to the first,
    // on one line, separated by single spaces.

    return 0;
}

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

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

    int n;
    cin >> n;
    vector<int> temps(n);
    for (int i = 0; i < n; i++) {
        cin >> temps[i];
    }

    // Pass 1: add every temperature into a long long.
    // Pass 2: print the ones above the average, or "none".

    return 0;
}

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

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

    long long k;
    cin >> k;
    vector<int> songs;
    int s;
    while (cin >> s) {
        songs.push_back(s);
    }

    // Print songs.size() songs, starting at index k % songs.size(),
    // wrapping back to index 0 after the last one.

    return 0;
}

এরপর Kenji-র program একটা loop-এ বারবার vector-এর সামনে insert করে, আর খুব ধীরে চলে। কেন, সেটা বের করতে lesson 02 প্রতিটা operation-এর খরচ মেপে দেখবে।