cppreference পড়ব কীভাবে, আর O(log n) মানে আসলে কী promise

David std::vector নিয়ে পড়ছে। push_back-এর পাশে reference বলছে "constant, amortised"। আর insert-এর পাশে বলছে, খরচটা শেষ পর্যন্ত দূরত্বের সঙ্গে linear। সে সবচেয়ে সোজা প্রশ্নটাই করে: "তাহলে কেউ insert লিখবে কেন?"

প্রশ্নটা ভালো, আর উত্তরটা ওই একই page-এই আছে, যদি জানো কোথায় তাকাতে হবে। এই lesson তোমাকে ওই page পড়তে শেখাবে। এরপর এই track-এর প্রতিটা খরচ তুমি নিজেই যাচাই করতে পারবে, চোখ বুজে বিশ্বাস করতে হবে না।

যে reference প্রতিটা C++ programmer খুলে রাখে

STL-এর বর্ণনা আছে দুইটা document-এ। প্রথমটা C++ standard নিজে, সেই official ISO document, যেটা প্রতিটা compiler মেনে চলে। এটা নিখুঁত আর লম্বা, আর প্রকাশিত version কিনতে টাকা লাগে। Committee-র working draft-গুলো ফ্রি, আর মানুষ ওগুলোই পড়ে: N4659 হলো C++17-এর শেষ draft, N4861 হলো C++20-এর, আর eel.is/c++draft এখনকারটা web page হিসেবে দেখায়।

দ্বিতীয়টা cppreference.com, standard থেকে volunteer-দের লেখা একটা ফ্রি reference। এতে প্রতিটা function-এর জন্য একটা করে page, example সহ, আর প্রতিটা standard-এ কী বদলেছে সেটা চিহ্ন দিয়ে দেখানো। কাজ করা C++ programmer-রা এই page-টাই খুলে রাখে। রোজকার কাজে cppreference পড়ো, আর হুবহু শব্দগুলো দরকার হলে draft-এ যাও।

একটা reference page-এর গঠন

std::vector<T>::insert-এর page-টা খোলো। দেখতে ঠাসা লাগে, কিন্তু এতে সব সময় একই অংশ একই ক্রমে থাকে, আর ওদের চারটাতেই তোমার দরকারি প্রায় সবকিছু আছে।

1. Signature। এগুলো হলো declaration: function-টা call করার সবগুলো উপায়। insert-এর কয়েকটা আছে, (1), (2) এভাবে নম্বর দেওয়া, আর page-এর বাকিটা ওদের নম্বর ধরেই কথা বলে। এই হলো ওর C++17-এর form-গুলো:

iterator insert( const_iterator pos, const T& value );                    (1)
iterator insert( const_iterator pos, T&& value );                         (2)
iterator insert( const_iterator pos, size_type count, const T& value );   (3)
template< class InputIt >
iterator insert( const_iterator pos, InputIt first, InputIt last );       (4)
iterator insert( const_iterator pos, std::initializer_list<T> ilist );    (5)

প্রতিটা কী নেয় আর কী ফেরত দেয়, সেটা দেখে পড়ো। প্রতিটা form pos নেয়, একটা iterator, যেটা বলে কোথায় ঢোকাতে হবে, আর প্রতিটা form একটা iterator ফেরত দেয়। Form (3) একটা মানের count-টা কপি ঢোকায়।

2. Parameter। Signature-এ যত নাম আছে, প্রতিটার জন্য এক লাইন। এখানেই জানবে যে নতুন element-গুলো বসে pos-এর আগে, আর এটা ভুল আন্দাজ করা খুব সহজ।

3. Complexity। খরচ, প্রতিশ্রুতি হিসেবে লেখা। Form (1)-এর জন্য এটা constant, সঙ্গে pos থেকে শেষ পর্যন্ত দূরত্বের linear। সোজা কথায়, ঢোকানোর জায়গার পরের প্রতিটা element-কে জায়গা করে দিতে এক ঘর করে সরতে হয়।

4. Iterator invalidation। উপরের দিকে ছোট একটা অনুচ্ছেদ বলে, পুরনো কোন iterator-গুলো পরেও কাজ করে। insert-এর বেলায়: vector-কে যদি বড় হতে হয়, তাহলে ওর ভেতরের প্রতিটা iterator এখন অচল। নইলে অচল হয় শুধু ঢোকানোর জায়গায় আর তার পরে থাকা iterator-গুলো। এই ধারণার সঙ্গে দেখা হয়েছে Lesson 4-এর প্রশ্নগুলোতে, আর Module 11 এটাকে চলন্ত অবস্থায় দেখাবে।

তাহলে David-এর উত্তর page-এই আছে। insert আছে, কারণ কখনো কখনো মাঝখানে একটা element লাগেই, আর complexity লাইনটা ঠিক বলে দেয় তার খরচ কত।

auto it = v.insert(v.begin() + 1, 15);

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {10, 20, 30};
    auto it = v.insert(v.begin() + 1, 15);
    std::cout << "inserted " << *it << ", now:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
    v.insert(v.end(), 3, 99);
    std::cout << "three 99s at the end:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

inserted 15, now: 10 15 20 30
three 99s at the end: 10 15 20 30 99 99 99

Complexity-র শব্দগুলো

Reference page খরচ বোঝায় অল্প কয়েকটা বাঁধা শব্দে। Lesson 3 তোমাকে এর তিনটা দিয়েছে। এই track-এ যতগুলোর দেখা পাবে, পুরো set-টা নিচে আছে, প্রতিটার পাশে এমন একটা সত্যিকারের operation, যার খরচ ঠিক ওটাই।

শেষ সারিটা একটু কাছ থেকে দেখা দরকার, কারণ David ঠিক এটা নিয়েই প্রশ্ন করেছিল। Amortised মানে "অনেকবার call করলে গড়ে"। push_back-এর বেশিরভাগ call এক ধাপের। মাঝে মাঝে vector ভরে যায়, তখন সে memory-র একটা বড় জায়গায় সরে যায় আর প্রতিটা element কপি করে। ওই একটা call ধীর। কিন্তু capacity প্রতিবার কয়েক গুণ করে বাড়ে, তাই ধীর call-গুলো এত কম আসে যে গড়টা constant-ই থাকে।

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    std::size_t last = v.capacity();
    std::cout << "capacity changes:";
    for (int i = 1; i <= 100; i++) {
        v.push_back(i);
        if (v.capacity() != last) {
            last = v.capacity();
            std::cout << ' ' << last;
        }
    }
    std::cout << '\n';
}

capacity changes: 1 2 4 8 16 32 64 128

মেপে দেখে প্রতিশ্রুতি যাচাই

Complexity লাইন হলো বৃদ্ধি নিয়ে একটা প্রতিশ্রুতি, সেকেন্ডে মাপা কোনো সময় না। তাই সৎ পরীক্ষা হলো n বাড়ানো আর তাকিয়ে দেখা। এই program n-টা সংখ্যার একটা vector দুইবার বানায়। প্রথমে push_back দিয়ে, যার প্রতিটা amortised constant। তারপর প্রতিটা সংখ্যা সামনে insert করে, যার প্রতিটা linear, তাই পুরো কাজটা বাড়ে n-এর বর্গের মতো।

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

int main()
{
    for (int n : {1000, 10000, 100000}) {
        auto t0 = steady_clock::now();
        std::vector<int> back;
        for (int i = 0; i < n; i++) back.push_back(i);
        auto t1 = steady_clock::now();
        std::vector<int> front;
        for (int i = 0; i < n; i++) front.insert(front.begin(), i);
        auto t2 = steady_clock::now();
        std::cout << "n = " << n << ": push_back " << duration_cast<microseconds>(t1 - t0).count()
                  << " us, insert at front " << duration_cast<microseconds>(t2 - t1).count() << " us\n";
    }
}

n = 1000: push_back 7 us, insert at front 25 us
n = 10000: push_back 56 us, insert at front 1943 us
n = 100000: push_back 472 us, insert at front 308680 us

Chart-টা প্রতিশ্রুতির সঙ্গে মিলিয়ে পড়ো। Element দশ গুণ হওয়ায় push_back মোটামুটি 8 থেকে 10 গুণ ধীর হয়েছে: মোটের উপর linear, প্রতি call-এ constant। সামনে insert প্রথমবার 78 গুণ ধীর হয়েছে, তারপর 159 গুণ: প্রতিটা insert linear, তাই পুরো কাজটা n-এর বর্গের মতো বাড়ে। 100,000 element-এ এটা push_back-এর চেয়ে প্রায় 650 গুণ বেশি সময় নিয়েছে। Program-এ n ছাড়া কিছুই বদলায়নি, আর page তোমাকে আগেই বলে দিয়েছিল এমনটা হবে।

"Since C++20" আর তুমি আসলে যে compiler চালাও

C++ standard প্রতি তিন বছরে নতুন হয়: C++11, 14, 17, 20, 23। কোনো কিছু কবে এসেছে, reference page সেটা চিহ্ন দিয়ে দেখায়, যেমন একটা signature-এর পাশে (since C++20), বা একটা নামের পাশে ছোট করে (C++20)। এই track শেখায় C++17, কারণ যে university lab বা contest judge-এর সঙ্গে তোমার দেখা হওয়ার সম্ভাবনা আছে, সবগুলোই এটা চালায়।

যেখানে C++20 কিছু ভালো করে দেয়, lesson সেটা দেখায় "In C++20" নামের আলাদা একটা বাক্সে, C++17 version-এর ঠিক পরেই। ওই বাক্সের code Playground-এ চলে -std=c++20-এ। প্রথমটা দেখবে ঠিক নিচেই, আর Module 2 থেকে বেশিরভাগ module-এ একটা করে।

#include <iostream>
#include <set>

int main()
{
    std::set<int> seen = {30, 10, 20};
    if (seen.count(20) > 0) std::cout << "20 is in the set\n";
}

20 is in the set

#include <iostream>
#include <set>

int main()
{
    std::set<int> seen = {30, 10, 20};
    if (seen.contains(20)) std::cout << "20 is in the set\n";
}

20 is in the set

আরেকটা সৎ কথা। "Since C++20" চিহ্ন বলে standard-এ কী আছে, তোমার compiler কতটুকু বানিয়ে শেষ করেছে সেটা না। Playground চালায় GCC 12, আর C++20 যা যা প্রতিশ্রুতি দেয়, GCC 12-এ তার সবকিছু নেই। সবচেয়ে পরিচিত ফাঁকটা হলো std::format, formatted লেখা বানানোর C++20-এর একটা উপায়, যেটা এসেছে GCC 13-এ। কোনো lesson-এ এমন কিছু দরকার হলে সেটা C++17-এর উপায়টা দেখায়, আর নতুনটার নাম বলে দেয়, কোন compiler লাগবে সেটা সহ। cppreference-এর "compiler support" page প্রতিটা feature-এর জন্য বলে দেয়, কোন GCC version-এ সেটা প্রথম এসেছে।

std::vector<int> v = {1, 2, 3};
v.insert(2, 99);

#include <format>
#include <iostream>

int main() {
    std::cout << std::format("{} items\n", 3);
}

এতেই নকশাটা পুরো হলো। Module 1 এখন সেই কয়েকটা C++ জিনিস শেখাবে, যেগুলো track-এর বাকিটা ব্যবহার করে, শুরু হবে একই program C আর C++-এ লেখা দিয়ে।