vector কখন ব্যবহার করবে, আর কখন না

Maria সবসময় একটা sorted leaderboard রাখে। প্রতিটা নতুন score vector-এর মাঝখানে ওর ঠিক জায়গায় গিয়ে বসে, তাই তালিকা কখনো sort করতে হয় না। এটা কাজ করে, কিন্তু 200,000টা score হলে এক সেকেন্ডের বেশি লাগে। ওর code-এ কোনো ভুল নেই। ও বেছেছে ভুল container। কোনটা বাছা উচিত ছিল, যে প্রশ্নগুলো ওকে সেটা বলে দিত, এই lesson সেগুলোই তোমাকে দেবে।

তোমার data নিয়ে চারটা প্রশ্ন

একটা container মানে কোন কোন operation সস্তা, তার একটা প্রতিশ্রুতি। তাই container বাছো এটা জিজ্ঞেস করে যে তোমার program সবচেয়ে বেশি কী করে। প্রায় সব ক্ষেত্রে চারটা প্রশ্নই সিদ্ধান্তটা দিয়ে দেয়।

Maria-র উত্তর: হ্যাঁ, এটা একটা ক্রম, কিন্তু ও মান দিয়ে খোঁজে আর মাঝখানে insert করে। চারটার মধ্যে দুইটা উত্তর vector থেকে সরে একটা sorted container-এর দিকে দেখায়। তাই code লেখার আগেই প্রশ্নগুলো একটা container-এর নাম বলে দেয়।

তুলনার chart

Chart-টা vector-কে বসায় সেই চারটা container-এর পাশে, যাদের সাথে ওকে সবচেয়ে বেশি গুলিয়ে ফেলা হয়। খরচগুলো এসেছে cppreference-এ প্রতিটা container-এর page থেকে। Memory-র সারিটা মাপা: GCC 12-এ দশ লাখ int, প্রতিটা container যত byte চেয়েছে সব গুনে, Compiler Explorer-এ একবার চালিয়ে।

Vector-এর কলামটা উপর থেকে নিচে পড়ো: শেষে সস্তা, index-এ সস্তা, আর memory-তে সবচেয়ে কম খরচ। ওর দুর্বল সারি হলো সামনে, মাঝখানে আর খোঁজা। বাকি প্রতিটা কলাম এর কোনো একটায় জেতে, আর অন্য কিছুতে হারে। একটা list প্রতিটা int-এর পাশে দুইটা pointer রাখে, তাই memory লাগে ছয় গুণ। একটা set মানগুলো ক্রমে রাখে আর একটা মান খুঁজে পায় O(log n)-এ, কিন্তু memory লাগে দশ গুণ, আর কোনো index-ই নেই।

শেষ সারিটা খরচের মতোই জরুরি। Vector-এর কোনো element-এর দিকে একটা iterator, pointer বা reference ঠিক থাকে শুধু vector reallocate না হওয়া পর্যন্ত। তারপর সেটা দেখায় free হয়ে যাওয়া পুরোনো block-এর ভিতরে। Reallocation না হলেও মাঝখানে insert বা erase করলে পরের element-গুলো সরে যায়, তাই ওদের iterator-ও আর ঠিক থাকে না। List বা set একবার element রাখলে আর কখনো সেটা সরায় না। তাই vector ঠিক পছন্দ তখন, যখন vector বড় হওয়ার সময় কেউ ওর element ধরে বসে থাকে না।

সিদ্ধান্তের flowchart

একই চারটা ধারণা, এবার flowchart হিসেবে, যে ক্রমে জিজ্ঞেস করবে। উপর থেকে শুরু করো, আর নিজের উত্তর ধরে এগোও। প্রতিটা শেষ ঘর একটা container-এর নাম বলে, সাথে যে module সেটা শেখায়।

Maria-র পথ: প্রশ্ন 1, score-গুলোর জায়গা খুঁজতে ও মান দিয়ে খোঁজে, তাই হ্যাঁ। তীর বলে set, বা দুজন player-এর score সমান হতে পারলে multiset, Module 8। তাই flowchart ওকে একদম প্রথম ঘরেই vector থেকে সরিয়ে দেয়।

বদলটার দাম কত, এবার মেপে দেখো। এই program একই 200,000টা pseudo-random সংখ্যা insert করে একটা sorted vector-এ, প্রতিটা ওর জায়গায়, আর একটা multiset-এ। lower_bound একটা sorted range-এ জায়গাটা খুঁজে দেয়; Module 13 এটা শেখাবে, এখানে এটা শুধু বের করে কোথায় insert করতে হবে।

#include <algorithm>
#include <chrono>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    const int n = 200000;
    vector<int> input(n);
    unsigned x = 12345;
    for (int& v : input) {
        x = x * 1103515245u + 12345u;
        v = (int)(x >> 1);
    }

    auto t0 = chrono::steady_clock::now();
    vector<int> sorted_v;
    for (int v : input) {
        sorted_v.insert(lower_bound(sorted_v.begin(), sorted_v.end(), v), v);
    }
    auto t1 = chrono::steady_clock::now();
    multiset<int> s;
    for (int v : input) {
        s.insert(v);
    }
    auto t2 = chrono::steady_clock::now();

    chrono::duration<double, milli> a = t1 - t0, b = t2 - t1;
    cout << "sorted vector: " << a.count() << " ms\n";
    cout << "multiset:      " << b.count() << " ms\n";
    cout << (equal(sorted_v.begin(), sorted_v.end(), s.begin()) ? "same order\n" : "different\n");
    return 0;
}

sorted vector: 1217.13 ms
multiset:      44.6139 ms
same order

Compiler Explorer-এ একবার চালানো, GCC 12, -O2 -std=c++17। দুটোতেই একই সংখ্যা একই ক্রমে আছে। জায়গা খোঁজা দুটোতেই দ্রুত; vector-এর খরচ হলো প্রতিটা insert-এ গড়ে অর্ধেক element সরানো। তাই এখানে ঠিক container ছিল প্রায় 27 গুণ দ্রুত, code-ও আরও সহজ।

ভরসার default: vector, তারপর মেপে দেখো

Chart দেখে list-কে লোভনীয় মনে হতে পারে: যেকোনো জায়গায় O(1) insert। কিন্তু list প্রতিটা element রাখে নিজের ছোট একটা block-এ, allocator যেখানে জায়গা পায় সেখানে। ওর উপর দিয়ে হাঁটা মানে এক block থেকে আরেক block-এ লাফানো। Vector-এর element-গুলো পাশাপাশি বসে, আর processor memory পড়ে টুকরো টুকরো করে, তাই পরের element-টা সাধারণত আগেই হাতে চলে আসে।

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

int main() {
    const int n = 1000000;
    vector<int> v;
    list<int> l;
    for (int i = 0; i < n; i++) {
        v.push_back(i % 100);
        l.push_back(i % 100);
    }

    auto t0 = chrono::steady_clock::now();
    long long sv = 0;
    for (int x : v) sv += x;
    auto t1 = chrono::steady_clock::now();
    long long sl = 0;
    for (int x : l) sl += x;
    auto t2 = chrono::steady_clock::now();

    chrono::duration<double, milli> dv = t1 - t0, dl = t2 - t1;
    cout << "vector: sum " << sv << " in " << dv.count() << " ms\n";
    cout << "list:   sum " << sl << " in " << dl.count() << " ms\n";
    return 0;
}

vector: sum 49500000 in 0.736809 ms
list:   sum 49500000 in 4.59888 ms

একই দশ লাখ সংখ্যা, একই loop, Compiler Explorer-এ Playground-এর flag দিয়ে একবার চালানো: list-এর উপর দিয়ে হাঁটতে প্রায় ছয় গুণ বেশি সময় লেগেছে। এই প্রভাবটা, মানে cache, ঠিকমতো মেপে দেখাবে Module 17। এই track যে নিয়ম মানে, সেটা দেয় C++ Core Guidelines। Default হিসেবে vector নাও, আর বদলাও শুধু এমন কারণে, যেটার নাম বলতে পারো বা মেপে দেখাতে পারো।

বড় element: ওদের স্থির রাখো, index সরাও

প্রশ্ন 4 মাপ নিয়ে। একটা int সরালে copy হয় 4 byte। লম্বা বর্ণনাওয়ালা একটা record সরালে copy হয় পুরোটাই। বড় record যদি ঘন ঘন সাজাতে বা বদলাতে হয়, ওদের রাখো এমন একটা vector-এ, যেটা কখনো বদলায় না, আর দ্বিতীয় একটা vector-এ সরাও ছোট ছোট int index।

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

int main() {
    vector<string> books{
        "The C Programming Language, a long description...",
        "Structure and Interpretation of Computer Programs, a long description...",
        "Introduction to Algorithms, a long description...",
    };

    vector<int> reading_list{2, 0};
    reading_list.insert(reading_list.begin(), 1);

    for (int id : reading_list) {
        cout << id << ": " << books[id].substr(0, 20) << '\n';
    }
    return 0;
}

1: Structure and Interp
2: Introduction to Algo
0: The C Programming La

সামনে insert সরিয়েছে দুইটা int, দুইটা লম্বা string না। বইগুলো যেখানে ছিল সেখানেই থাকে, তাই books-এর ভিতরের কোনো index কখনো পুরোনো হয়ে যায় না। তাই বড় data এক জায়গায় থাকে, আর ওর ক্রম থাকে index-এর একটা vector-এ।

Function-এ vector পাঠানো

তুমি কীভাবে vector পাঠাচ্ছ, সেটাই বলে দেয় function ওটা দিয়ে কী করতে পারবে। উপায় তিনটা, আর প্রতিটা একটা প্রতিশ্রুতি।

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

int highest(const vector<int>& marks) {
    int best = marks[0];
    for (int m : marks) {
        if (m > best) {
            best = m;
        }
    }
    return best;
}

void add_bonus(vector<int>& marks, int bonus) {
    for (int& m : marks) {
        m += bonus;
    }
}

vector<int> passed(const vector<int>& marks) {
    vector<int> result;
    for (int m : marks) {
        if (m >= 50) {
            result.push_back(m);
        }
    }
    return result;
}

int main() {
    vector<int> marks{70, 45, 62, 38};
    add_bonus(marks, 5);
    cout << "highest " << highest(marks) << '\n';
    cout << "passed:";
    for (int m : passed(marks)) {
        cout << ' ' << m;
    }
    cout << '\n';
    return 0;
}

highest 75
passed: 75 50 67

passed-এর মতো value হিসেবে vector return করা সস্তা: compiler ফলাফলটা copy না করে move করে বের করে দেয়, lesson 05 এটা ব্যাখ্যা করবে। তাই পড়তে নাও const& দিয়ে, বদলাতে & দিয়ে, আর নতুন vector return করো value হিসেবে।

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

int total(span<const int> values) {
    int sum = 0;
    for (int x : values) {
        sum += x;
    }
    return sum;
}

int main() {
    vector<int> v{3, 1, 4, 1, 5};
    int a[3] = {9, 2, 6};
    cout << total(v) << ' ' << total(a) << '\n';
    cout << total(span<const int>(v).subspan(1, 3)) << '\n';
    return 0;
}

14 17
6

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

int main() {
    multiset<int> board;
    int scores[] = {310, 120, 455, 120, 280};
    for (int s : scores) {
        board.insert(s);
    }
    cout << "board:";
    for (int s : board) {
        cout << ' ' << s;
    }
    cout << "\nlowest " << *board.begin() << ", highest " << *board.rbegin() << '\n';
    return 0;
}

board: 120 120 280 310 455
lowest 120, highest 455

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

int main() {
    deque<string> line{"Bob", "Zara"};
    line.push_back("Kenji");
    while (!line.empty()) {
        cout << "serving " << line.front() << ", " << line.size() - 1 << " waiting\n";
        line.pop_front();
    }
    return 0;
}

serving Bob, 2 waiting
serving Zara, 1 waiting
serving Kenji, 0 waiting

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

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

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

    int coldest = temps[0];
    long long total = 0;
    for (int x : temps) {
        if (x < coldest) {
            coldest = x;
        }
        total += x;
    }
    cout << temps.size() << " readings, coldest " << coldest
         << ", average " << (double)total / temps.size() << '\n';
    return 0;
}

6 readings, coldest -3, average 2.5

void add_bonus(vector<int> marks) {
    for (int& m : marks) {
        m += 5;
    }
}

vector<int> marks{70, 85, 62};
int* first = &marks[0];
marks.push_back(91);
cout << "first mark: " << *first << '\n';

list<int> scores{70, 85, 62};
cout << scores[1] << '\n';

const vector<int>& make_marks() {
    vector<int> marks{70, 85, 62};
    return marks;
}

#include <vector>
using namespace std;

int main() {
    vector<bool> handed_in(100000);
    bool& first = handed_in[0];
    first = true;
    return 0;
}

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

// Return how many elements of v are greater than limit.
// The const& promises not to change v, and avoids a copy per call.
int count_above(const vector<int>& v, int limit) {
    return 0;
}

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

    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) {
        cin >> x;
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int limit;
        cin >> limit;
        cout << count_above(v, limit) << '\n';
    }
    return 0;
}

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

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string read, size, change;
        cin >> read >> size >> change;
        // Ask the flowchart's questions in its order, and print one word.
    }
    return 0;
}

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

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

    vector<int> sorted_v;
    vector<int> landed;
    int x;
    while (cin >> x) {
        // lower_bound(sorted_v.begin(), sorted_v.end(), x) is the first place
        // whose value is not less than x. Its distance from begin() is the index.
        // Insert x there, and remember the index.
    }
    // Print the indexes on one line, then the sorted list on the next.
    return 0;
}

এরপর Pro lesson 05 vector-টা খুলে দেখাবে: আমাদের compiler-এ capacity কীভাবে বাড়ে, আর একটা reallocation কী কী ভাঙে।