vector-এর প্রতিটা operation, একটা একটা করে, খরচসহ

Kenji 100,000টা সংখ্যা পড়ে, আর ওর সেগুলো লাগবে উল্টো ক্রমে। তাই ও প্রতিটা নতুন সংখ্যা vector-এর সামনে insert করে, আর ওর program নেয় প্রায় এক সেকেন্ডের তিন ভাগের এক ভাগ। Amara লেখে push_back, তারপর vector-টা পেছন থেকে হাঁটে। ওরটা নেয় আধা millisecond, মানে প্রায় ছয়শো গুণ দ্রুত। দুটো program-ই ঠিক। তফাতটা এই lesson-এর একটা লাইনে: প্রতিটা call-এর খরচ।

খরচের লাইন কীভাবে পড়বে

নিচের প্রতিটা operation শেষ হয় এক সারির একটা table দিয়ে: call, তার খরচ, আর কেন। খরচ লেখা হয় big-O notation-এ। এটা বলে vector বড় হলে কাজ কীভাবে বাড়ে, কত nanosecond লাগে সেটা না।

এখানে প্রতিটা খরচ C++ standard নিজেই বেঁধে দেয়, আর Module 0-এ যেমন দেখেছ, cppreference-এর page-এ প্রতিটা মিলিয়ে নিতে পারো। তাই খরচের লাইন হলো কাজ কীভাবে বাড়বে তার একটা প্রতিশ্রুতি, যেটা প্রতিটা compiler-এ সত্যি।

push_back আর pop_back

push_back(x) শেষ element-এর পরে x যোগ করে। pop_back() শেষ element-টা সরিয়ে দেয়, আর কিছুই return করে না। শেষ মানটা কাজে লাগাতে চাইলে আগে back() দিয়ে পড়ে নাও।

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

int main() {
    vector<int> v{10, 20};
    v.push_back(30);
    cout << "after push_back: size " << v.size() << ", last " << v.back() << '\n';
    v.pop_back();
    cout << "after pop_back: size " << v.size() << ", last " << v.back() << '\n';
    return 0;
}

after push_back: size 3, last 30
after pop_back: size 2, last 20

সাবধান: খালি vector-এ pop_back() undefined behaviour। Playground-এ এটা শেষ হয়েছে সফল badge নিয়ে, আর পরে size() print করেছে 18446744073709551615। Vector-এর শেষটা ওর শুরুরও এক ধাপ আগে সরে গেছে, আর কেউ থামায়নি। যে pop_back-এর input তোমার হাতে নেই, তার আগে প্রতিবার !v.empty() check করো।

emplace_back(args) হলো push_back-এর ভাই। এটা element-টা ওর অংশগুলো থেকে সরাসরি জায়গাতেই বানায়, তাই v.emplace_back(3, 4) একটা vector<pair<int, int>>-এ pair (3, 4) যোগ করে। খরচ একই। তাই দুটো call-ই শেষে যোগ করে, আর সস্তা শুধু শেষ মাথাটাই।

size, empty আর capacity

যেকোনো vector-কে এই তিনটা প্রশ্ন করা যায়, আর প্রতিটার উত্তর আসে handle থেকেই, element-গুলো না ছুঁয়ে।

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

int main() {
    vector<int> v;
    cout << v.size() << ' ' << v.empty() << ' ' << v.capacity() << '\n';
    v.push_back(7);
    v.push_back(8);
    v.push_back(9);
    cout << v.size() << ' ' << v.empty() << ' ' << v.capacity() << '\n';
    return 0;
}

0 1 0
3 0 4

সাবধান: empty() print হয় 1 বা 0 হিসেবে, কারণ এটা একটা bool। এটা কিছুই খালি করে না; সেটা করে clear()। তাই if (v.empty()) একটা প্রশ্ন, কোনো কাজ না।

operator[] আর at

দুটোই index i-এর element পড়ে বা লেখে। v[i] তোমার কথায় বিশ্বাস করে। v.at(i) আগে দেখে নেয় i size()-এর চেয়ে ছোট কি না, আর ছোট না হলে একটা exception দিয়ে program থামিয়ে দেয়।

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

int main() {
    vector<int> v{10, 20, 30, 40, 50};
    v[1] = 25;
    v.at(2) = 35;
    cout << v[1] << ' ' << v.at(2) << '\n';
    cout << v.at(5) << '\n';
    return 0;
}

Playground-এ run-টা শেষ হয়েছে Runtime error badge নিয়ে। Output pane ছিল খালি, আর error stream-এ এসেছে এটা:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)

দ্বিতীয় লাইনটা পড়ো: তুমি কোন index চেয়েছিলে, আর কোন size-এ গিয়ে আটকেছে। এমনকি 25 35-ও কখনো screen-এ আসেনি। Program থামার সময় cout ওই লাইনটা তখনো buffer-এ ধরে রেখেছিল, আর crash হলে flush বাদ পড়ে যায়, Module 1-এর fast input আর output-এর lesson যেমন সাবধান করেছিল। Lesson 01-এ Bob-এর v[v.size()]-এর সাথে মিলিয়ে দেখো: ওটা চুপচাপ একটা 0 print করে সফল হয়েছিল। দেখতে ঠিক অথচ ভুল উত্তরের চেয়ে জোরে থেমে যাওয়া অনেক ভালো।

সাবধান: code লেখা আর test করার সময় at() ব্যবহার করো, বিশেষ করে যখন index input থেকে হিসাব করে বের করা। Contest-এর code-এ চলে [], কারণ check করা index প্রতিবার access-এ একটা তুলনা খরচ করে। তাই [] দ্রুত, কিন্তু তোমার কথায় বিশ্বাস করে চলে; আর at() নিজে যাচাই করে নেয়।

front আর back

v.front() হলো প্রথম element, v[0]। v.back() হলো শেষটা, v[v.size() - 1], কিন্তু যে বিয়োগে ভুল হতে পারে সেটা ছাড়াই।

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

int main() {
    vector<int> temps{18, 21, 25, 19};
    cout << "first " << temps.front() << ", last " << temps.back() << '\n';
    temps.back() = 20;
    cout << "last now " << temps.back() << '\n';
    return 0;
}

first 18, last 19
last now 20

সাবধান: Zara-র প্রথম test সবসময় একটা খালি vector। খালি temps-এ temps.front() কোনো বার্তা ছাড়াই compile হয়েছে। Playground-এ শেষ হয়েছে Runtime error badge নিয়ে, আর কিছুই print করেনি, এমনকি আগের লেখাটাও না। খালি vector-এ back()-ও ঠিক একই কাণ্ড করেছে। তাই খালি vector-এ দুটোই undefined, আর ওদের বাঁচাতে পারে শুধু একটা empty() check।

একটা position-এ insert

v.insert(pos, x) x বসায় pos position-এর ঠিক আগে। Position হলো একটা iterator, মানে vector-এর একটা জায়গার চিহ্ন। আপাতত এটা লেখো v.begin() + i হিসেবে, মানে "index i-এর জায়গা"। Iterator ঠিকমতো বুঝিয়ে বলবে Module 11।

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

int main() {
    vector<int> v{10, 20, 40};
    v.insert(v.begin() + 2, 30);
    v.insert(v.begin(), 5);
    v.insert(v.end(), 50);
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 5 10 20 30 40 50

Index i-এ জায়গা বানাতে i থেকে শেষ পর্যন্ত প্রতিটা element এক বাক্স ডানে সরে। v.begin()-এ insert করলে সবগুলোই সরে। v.end()-এ insert করলে একটাও সরে না, আর সেটা push_back-এর মতোই।

সাবধান: v.end()-এর পরের কোনো position undefined, আর কেউ এটা check করে না। তিনটা element-এর vector-এ v.insert(v.begin() + 5, 99) Playground-এ সফল হয়েছে আর size বলেছে 4, যদিও index 5 বলে কিছু ছিলই না। তাই position বানাও এমন index থেকে, যেটা তুমি check করে নিয়েছ: 0 থেকে size() পর্যন্ত, দুই মাথাসহ।

একটা position-এ erase, আর loop-এর ভিতরে erase

v.erase(pos) pos-এর element-টা সরিয়ে দেয়। v.erase(first, last) একটা range সরায়: first থেকে শুরু, last-এর ঠিক আগে শেষ। দুটোই একটা iterator return করে, যেটা দেখায় সরানো element-এর জায়গায় এখন যে element বসে আছে।

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

int main() {
    vector<int> v{5, 10, 20, 30, 40, 50};
    v.erase(v.begin());
    v.erase(v.begin() + 1, v.begin() + 3);
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 10 40 50

প্রথম call 5-কে সরিয়েছে। দ্বিতীয়টা, যা বাকি ছিল তার index 1 আর 2, মানে 20 আর 30 সরিয়েছে। সরানো element-এর পরের সবকিছু বাঁয়ে সরে এসে ফাঁকটা ভরে দেয়।

এবার {2, 4, 5, 6} থেকে সব জোড় সংখ্যা সরাও। Bob সেই loop-টাই লেখে, যেটা ও একটা array-এর জন্য লিখত।

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

int main() {
    vector<int> v{2, 4, 5, 6};
    for (size_t i = 0; i < v.size(); i++) {
        if (v[i] % 2 == 0) {
            v.erase(v.begin() + i);
        }
    }
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 4 5

4 বেঁচে গেছে। Index 0-এ 2 erase হওয়ার পরে 4 সরে এসে বসেছে index 0-এ, আর loop ততক্ষণে চলে গেছে index 1-এ। তাই প্রতিটা erase করা element-এর ঠিক পরেরটা কখনো test-ই হয় না।

নিরাপদ loop erase-এর return করা মানটা কাজে লাগায়। Erase করলে যেখানে আছ সেখানেই থাকো; নইলে এক ধাপ সামনে যাও।

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

int main() {
    vector<int> v{2, 4, 5, 6};
    for (auto it = v.begin(); it != v.end();) {
        if (*it % 2 == 0) {
            it = v.erase(it);
        } else {
            ++it;
        }
    }
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 5

*it পড়ে iterator যে element দেখায় সেটা, ঠিক যেমন *p একটা pointer দিয়ে পড়ে। এই loop ঠিক আছে, কিন্তু প্রতিটা erase তবুও বাকিগুলোকে সরায়, তাই অনেকগুলো erase হলে প্রতিটার খরচ O(n)। Amara সবকিছু এক pass-এ সরায় erase-remove idiom দিয়ে। <algorithm>-এর remove_if যে element-গুলো রাখতে হবে সেগুলো সামনে এনে জড়ো করে, আর বলে দেয় ওরা কোথায় শেষ। তারপর একটা erase লেজটা কেটে ফেলে।

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

bool is_even(int x) {
    return x % 2 == 0;
}

int main() {
    vector<int> v{2, 4, 5, 6, 7, 8};
    v.erase(remove_if(v.begin(), v.end(), is_even), v.end());
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

v: 5 7

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

int main() {
    vector<int> v{3, -1, 4, -1, -5, 9, 2};
    auto removed = erase_if(v, [](int x) { return x < 0; });
    cout << "removed " << removed << '\n';
    erase(v, 4);
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

removed 3
v: 3 9 2

তাই erase পরের position return করে, loop-কে সেটা ব্যবহার করতেই হবে, আর একসাথে অনেকগুলো সরাতে একটাই erase-remove।

clear

v.clear() সব element সরিয়ে দেয়। Size হয়ে যায় 0। Block থেকে যায়, তাই capacity বদলায় না।

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

int main() {
    vector<int> v(1000, 1);
    v.clear();
    cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
    return 0;
}

size 0, capacity 1000

সাবধান: clear() memory রেখে দেয়, আর loop-এ বারবার vector ভরার সময় তুমি ঠিক এটাই চাও। তাই clear করা vector খালি, কিন্তু ছোট না।

resize আর assign

v.resize(n) size-কে ঠিক n বানায়। বাড়লে যোগ হয় 0, অথবা তুমি যে মান দাও তার copy। কমলে শেষ থেকে কাটা পড়ে। v.assign(n, x) পুরোনো element-গুলো ফেলে দিয়ে x-এর n-টা copy বসায়।

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

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

int main() {
    vector<int> v{1, 2, 3};
    v.resize(5);
    show(v);
    v.resize(7, 9);
    show(v);
    v.resize(2);
    show(v);
    v.assign(4, 8);
    show(v);
    return 0;
}

1 2 3 0 0 (size 5)
1 2 3 0 0 9 9 (size 7)
1 2 (size 2)
8 8 8 8 (size 4)

সাবধান: resize(7, 9) শুধু নতুন বাক্সগুলো 9 দিয়ে ভরে; পুরোনো element-গুলোর মান যেমন ছিল তেমনই থাকে। তাই resize লম্বাই বদলায়, আর assign ভিতরের সব মান বদলে দেয়।

reserve আর shrink_to_fitIntermediate

v.reserve(n) capacity-কে অন্তত n বানায়, তাই এরপর n পর্যন্ত push করলে কখনো reallocate হয় না। Size এতে বদলায় না। v.shrink_to_fit() vector-কে বলে বাড়তি বাক্সগুলো ফেরত দিতে।

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

int main() {
    vector<int> v;
    v.reserve(100);
    cout << "after reserve: size " << v.size() << ", capacity " << v.capacity() << '\n';
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }
    cout << "after 10 pushes: size " << v.size() << ", capacity " << v.capacity() << '\n';
    v.shrink_to_fit();
    cout << "after shrink_to_fit: size " << v.size() << ", capacity " << v.capacity() << '\n';
    return 0;
}

after reserve: size 0, capacity 100
after 10 pushes: size 10, capacity 100
after shrink_to_fit: size 10, capacity 10

সাবধান: reserve জায়গা বানায়, element না। Kenji লিখেছিল v.reserve(5); v[0] = 42;। Playground-এ এটা সফল হয়েছে, size print করেছে 0, আর v-এর উপর range-for কিছুই print করেনি। 42 গিয়ে পড়েছে এমন একটা ফাঁকা বাক্সে, যেটা element না। Element চাইলে resize বা v(n) constructor ব্যবহার করো। shrink_to_fit শুধু একটা অনুরোধ; GCC-র library সেটা রাখে, কিন্তু standard অনুযায়ী কোনো library চাইলে এটা উপেক্ষাও করতে পারে।

swap

a.swap(b), অথবা swap(a, b), একই type-এর দুইটা vector-এর ভিতরের জিনিস অদলবদল করে।

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

int main() {
    vector<int> today{1, 2, 3};
    vector<int> tomorrow(100000, 7);
    today.swap(tomorrow);
    cout << today.size() << ' ' << tomorrow.size() << '\n';
    return 0;
}

100000 3

সাবধান: 100,000টা element swap করতে যা খরচ, 3টা swap করতেও তাই। তাই swap হলো handle-এর অদলবদল, copy না।

begin, end আর dataIntermediate

v.begin() চিহ্ন দেয় প্রথম element-এ, আর v.end() শেষটার ঠিক পরের জায়গায়। Part Four-এর algorithm-গুলো এদের একটা জোড়া নেয়। v.data() প্রথম element-এর একটা সাধারণ pointer return করে, যে code একটা C array চায় তার জন্য।

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

int main() {
    vector<int> v{40, 10, 30, 20};
    sort(v.begin(), v.end());
    const int* p = v.data();
    printf("%d %d %d %d\n", p[0], p[1], p[2], p[3]);
    printf("end - begin = %d\n", (int)(v.end() - v.begin()));
    return 0;
}

10 20 30 40
end - begin = 4

সাবধান: v.end() শেষ element-এর পরে, তাই *v.end() এমন একটা বাক্স পড়ে, যেটা নেই। দূরত্ব end - begin হলো size। তাই begin(), end() জোড়া দিয়েই প্রতিটা algorithm বলে "পুরো vector"।

সব খরচ এক table-এ, আর Kenji-র মাপ

এবার Kenji-র প্রশ্নটা মেপে দেখা যাক। নিচের program সামনে 100,000টা সংখ্যা insert করে, আর loop-টার সময় মাপে <chrono> দিয়ে, যেটা standard-এর ঘড়ি। আমরা এটা Compiler Explorer-এ তিনবার চালিয়েছি, Playground-এর -O2 -std=c++17-এ GCC 12, প্রতিবার একটা করে run। বাকি দুই run-এ বদলেছে শুধু loop-এর লাইনটা: একবার v.push_back(i);, আরেকবার v.insert(v.begin() + v.size() / 2, i);।

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

int main() {
    const int n = 100000;
    auto start = chrono::steady_clock::now();
    vector<int> v;
    for (int i = 0; i < n; i++) {
        v.insert(v.begin(), i);
    }
    auto stop = chrono::steady_clock::now();
    chrono::duration<double, milli> took = stop - start;
    cout << v.size() << " elements in " << took.count() << " ms\n";
    return 0;
}

100000 elements in 308.871 ms

সামনে insert মোট প্রায় n² / 2টা element সরিয়েছে, মানে প্রায় 500 কোটি। মাঝখানেরটা সরিয়েছে তার অর্ধেক, আর ওর সময়ও অর্ধেক। push_back প্রায় কিছুই সরায়নি, আর ছিল প্রায় ছয়শো গুণ দ্রুত। তাই খরচের লাইনগুলো শুধু তত্ত্ব না: মাপের চেহারাটাই ওরা।

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

int main() {
    vector<string> history;
    history.push_back("draw circle");
    history.push_back("fill blue");
    history.push_back("draw square");

    for (int undo = 0; undo < 4; undo++) {
        if (history.empty()) {
            cout << "nothing to undo\n";
        } else {
            cout << "undo: " << history.back() << '\n';
            history.pop_back();
        }
    }
    cout << history.size() << " actions left\n";
    return 0;
}

undo: draw square
undo: fill blue
undo: draw circle
nothing to undo
0 actions left

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

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

    vector<int> v;
    int x;
    while (cin >> x) {
        v.push_back(x);
    }
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        cout << v[i] << (i > 0 ? ' ' : '\n');
    }
    return 0;
}

9 7 5 3 1

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

bool too_short(int seconds) {
    return seconds < 60;
}

int main() {
    vector<int> songs{215, 45, 190, 30, 260, 58, 175};
    songs.erase(remove_if(songs.begin(), songs.end(), too_short), songs.end());
    songs.insert(songs.begin(), 30);

    int total = 0;
    cout << "playlist:";
    for (int s : songs) {
        cout << ' ' << s;
        total += s;
    }
    cout << '\n' << songs.size() << " songs, " << total / 60 << " min " << total % 60 << " s\n";
    return 0;
}

playlist: 30 215 190 260 175
5 songs, 14 min 30 s

int last = history.pop_back();

for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it);
    }
}

vector<int> v;
v.reserve(5);
v[0] = 42;

vector<int> temps;
cout << "first reading: " << temps.front() << '\n';

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

int main() {
    vector<int> v{-1, -2, 3};
    for (size_t i = 0; i < v.size(); i++) {
        if (v[i] < 0) {
            v.erase(v.begin() + i);
        }
    }
    cout << "v:";
    for (int x : v) {
        cout << ' ' << x;
    }
    cout << '\n';
    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> marks(n);
    for (int i = 0; i < n; i++) {
        cin >> marks[i];
    }
    int k, x;
    cin >> k >> x;

    // Insert x so that it becomes the k-th value, counting from 1,
    // then print all n + 1 values on one line.

    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> readings(n);
    for (int i = 0; i < n; i++) {
        cin >> readings[i];
    }

    // Remove every negative reading with erase, without skipping any,
    // then print the rest on one line, or "empty".

    return 0;
}

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

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

    int n;
    cin >> n;
    vector<int> list;
    for (int i = 0; i < n; i++) {
        string command;
        cin >> command;
        // "push": read x and add it at the end.
        // "pop": remove the last value, only if there is one.
        // "print": print the list on one line, or "empty".
    }
    return 0;
}

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

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

    int n, m;
    cin >> n >> m;
    vector<int> items(n);
    for (int& x : items) {
        cin >> x;
    }
    vector<int> places(m);
    for (int& p : places) {
        cin >> p;
    }

    // Keep a second index that says where the next kept value goes,
    // copy each kept value there, then resize the vector once.

    return 0;
}

এরপর lesson 03 এই operation-গুলো কাজে লাগাবে ছয়টা সম্পূর্ণ program-এ, পাঁচ লাইনের একটা program থেকে শুরু করে সত্যিকারের একটা marks report পর্যন্ত।