Module ০ · STL জিনিসটা কী, আর এটা C++ লেখার ধরনটাই পাল্টে দেয় কেন

কেন দরকার: কম লাইন, কম bug, আর খরচ আগে থেকেই জানা

Freeপড়াlesson ২ / ৬

এই lesson-এ যা শিখবে

STL শেখা কেন কাজের, তার তিনটা সৎ কারণ বলতে পারবে, প্রতিটার পেছনে একটা করে program সহ।
একটা C program-কে তার STL version-এর পাশে রেখে গুনে বলতে পারবে, কোন কাজগুলো আর হাতে লিখতে হচ্ছে না।
STL-এর খরচগুলোর নাম বলতে পারবে, যাতে বুঝতে পারো কখন হাতে লেখা C এখনো ঠিক পছন্দ।

Bob তার নম্বর রাখার program-এর জন্য C-তে একটা বাড়তে থাকা array লিখেছে। সোমবার সেটা ঠিকঠাক চলে। মঙ্গলবার এক বন্ধু ছয়টা নম্বর যোগ করে, আর তার দুইটা ফেরত আসে শূন্য হয়ে।

Bob-এর resize-এর code একটা element কম copy করে। তাই array যতবার বড় হয়, শেষ নম্বরটা হারিয়ে যায়। Compiler কিছুই বলেনি, program-ও একবারও crash করেনি। vector::push_back ঠিক এই কাজটাই লাখ লাখ program-এ করে। ওতে Bob-এর মতো একটা bug থাকলে অনেক আগেই কেউ ধরে ফেলত, সারিয়েও ফেলত।

STL কেন জরুরি, এটা তার প্রথম কারণ। আরো দুইটা আছে, আর খরচও আছে। এই lesson-এ সবগুলোই পাবে। যে library শুধু নিজের গুণ গায়, সে তো পুরো গল্পটা বলছে না।

কারণ এক: ঠিকঠাক code, যেটা তোমাকে লিখতে হয় না

তুমি যত লাইন লেখো, তার প্রতিটাই ভুল হতে পারে। STL-এর container আর algorithm প্রতিটা C++ compiler-এর সঙ্গেই আসে, আর একই code রোজ লাখ লাখ program-এ চলে। push_back-এ একটা bug থাকলে কয়েক ঘণ্টার মধ্যেই সেটা ধরা পড়ত, আর ধরত অন্য কেউ।

একই কাজ দুইবার করে দেখা যাক: 1 থেকে 5-এর বর্গগুলো একটা বাড়তে থাকা array-তে রাখো, তারপর ছাপাও। প্রথমে C-তে, পুরো নিয়ম মেনে: array বাড়ানোর অংশ আর memory না পেলে কী হবে তার check, দুইটাই রেখে।

Example 1: C-তে একটা বাড়তে থাকা array

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int *a = NULL;
    size_t n = 0, cap = 0;
    for (int x = 1; x <= 5; x++) {
        if (n == cap) {
            cap = cap ? cap * 2 : 1;
            int *p = realloc(a, cap * sizeof *a);
            if (p == NULL) { free(a); return 1; }
            a = p;
        }
        a[n++] = x * x;
    }
    for (size_t i = 0; i < n; i++) printf("%d\n", a[i]);
    free(a);
    return 0;
}

এটা ঠিকঠাক C। এটা একটা count আর একটা capacity রাখে, জায়গা ভরে গেলে capacity দ্বিগুণ করে, realloc কাজ করল কি না দেখে, আর শেষে memory ছেড়ে দেয়। এর প্রতিটা জায়গাতেই Bob-এর মতো bug লুকিয়ে থাকতে পারে।

Compiler-এ চালাও

Example 2: একই কাজ, vector দিয়ে

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> a;
    for (int x = 1; x <= 5; x++) {
        a.push_back(x * x);
    }
    for (int v : a) std::cout << v << '\n';
}

Output একই। Count, capacity, বাড়ানোর নিয়ম, ব্যর্থ হলে কী হবে তার check, আর free, সবই এখনো হচ্ছে, তবে std::vector-এর ভেতরে। তোমাকে শুধু আর লিখতে হচ্ছে না। তাই ওই লাইনগুলোতে যে bug থাকত, তাদের থাকার জায়গাটাই আর নেই।

Compiler-এ চালাও

কারণ দুই: প্রতিটা operation-এর খরচ আগে থেকেই জানা

C++ standard শুধু এটা বলে না যে push_back কী করে। কাজটায় কতক্ষণ লাগতে পারে, সেটাও বলে দেয়, একটা complexity হিসেবে (container বড় হলে কাজ কীভাবে বাড়ে)। push_back-এর বেলায় কথা দেওয়া আছে "amortised constant": গড়ে একটা element যোগ করার খরচ একই, vector-এ দশটা থাকুক বা এক কোটি।

তোমার নিজের C array এমন কোনো কথা দেয় না, যদি না তুমি বসে হিসাবটা নিজে বের করো। STL-এর কথাগুলো লিখে রাখা আছে, সব compiler-এর জন্য একই। একটা লাইন লেখার আগেই তুমি ওগুলো দেখে নিতে পারো। কোথায় দেখবে, Lesson 5 সেটা দেখাবে।

এবার একটা search, এটাও দুইবার। নম্বরের একটা list-এ 90 কোথায় আছে, খুঁজে বের করো।

Example 3: C-তে linear search

#include <stdio.h>

int main(void)
{
    int marks[] = {72, 45, 90, 61, 88};
    int n = sizeof marks / sizeof marks[0];
    int where = -1;
    for (int i = 0; i < n; i++) {
        if (marks[i] == 90) { where = i; break; }
    }
    if (where >= 0) printf("90 is at index %d\n", where);
    else printf("90 is not there\n");
    return 0;
}

90 is at index 2

Loop-টা ছোট, কিন্তু তিনটা জিনিস তুমিই বেছেছ: loop-এর সীমা, "পাওয়া যায়নি" বোঝাতে -1, আর break। তিনটার যেকোনো একটা ভুল হলে উত্তরও ভুল।

Compiler-এ চালাও

Example 4: একই search, std::find দিয়ে

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> marks = {72, 45, 90, 61, 88};
    auto it = std::find(marks.begin(), marks.end(), 90);
    if (it != marks.end())
        std::cout << "90 is at index " << (it - marks.begin()) << '\n';
    else
        std::cout << "90 is not there\n";
}

90 is at index 2

std::find প্রথম মিলটার দিকে একটা iterator ফেরত দেয়, আর কিছু না মিললে দেয় end()। তাই "পাওয়া যায়নি" বোঝাতে তোমাকে কোনো সংখ্যা বানাতে হয় না। এর খরচও standard-এ লেখা: প্রতিটা element-এর জন্য বড়জোর একটা তুলনা, মানে linear। auto compiler-কে বলে, iterator-এর type-টা তোমার হয়ে লিখে দিতে; এটা আসছে Module 1-এ।

Compiler-এ চালাও

কারণ তিন: এমন code, যেটা অন্যরাও পড়তে পারে

একজন C++ programmer std::sort(v.begin(), v.end()) পড়লেই জানে এটা কী করে, কত খরচ, আর এটা যে ঠিক। আগে বসে একটা sorting function পড়তে হয় না। নামগুলো পৃথিবীর সব C++ programmer-এর চেনা, ঠিক যেমন printf সব C programmer-এর চেনা।

Sorting-এ এটা সবচেয়ে ভালো বোঝা যায়। C-তে তোমাকে একটা comparison function লিখতে হয়। সেটা void pointer নেয়, সেগুলোকে cast করে, তারপর একটা negative, শূন্য বা positive সংখ্যা ফেরত দেয়।

Example 5: C-তে qsort দিয়ে sort

#include <stdio.h>
#include <stdlib.h>

int by_value(const void *a, const void *b)
{
    int x = *(const int *)a, y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void)
{
    int marks[] = {72, 45, 90, 61, 88};
    size_t n = sizeof marks / sizeof marks[0];
    qsort(marks, n, sizeof marks[0], by_value);
    printf("sorted:");
    for (size_t i = 0; i < n; i++) printf(" %d", marks[i]);
    printf("\n");
    return 0;
}

sorted: 45 61 72 88 90

এই comparator চিরচেনা return x - y; এড়িয়ে গেছে, কারণ খুব বড় আর খুব ছোট int-এ ওটা overflow করে। তবুও এটাকে বিশ্বাস করার আগে পাঠককে cast, element-এর size আর count মিলিয়ে দেখতে হয়।

Compiler-এ চালাও

Example 6: একই sort, std::sort দিয়ে

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> marks = {72, 45, 90, 61, 88};
    std::sort(marks.begin(), marks.end());
    std::cout << "sorted:";
    for (int m : marks) std::cout << ' ' << m;
    std::cout << '\n';
}

sorted: 45 61 72 88 90

কোনো size নেই, কোনো cast নেই, সাধারণ ক্রমে সাজাতে কোনো comparator-ও নেই। Compiler element-এর type জানে। তাই string-কে int-এর তুলনা দিয়ে sort করার মতো ভুল করলে সেটা compile error হয়ে ধরা পড়ে, ভুল উত্তর হয়ে না।

Compiler-এ চালাও

তিন জোড়া, গুনে দেখা

উপরের ছয়টা program, দুইভাবে মাপা। প্রথম মাপ হলো code-এর লাইন, ফাঁকা লাইন বাদ দিয়ে। দ্বিতীয় মাপ হলো সেই খুঁটিনাটিগুলো, যেগুলো তোমাকে হাতে ঠিক রাখতে হয়। Table-এ প্রতিটার নাম দেওয়া আছে, যাতে গোনাটা তুমি নিজেই মিলিয়ে নিতে পারো।

ছবি 1। Example 1 থেকে 6-এর code-এর লাইন, মাপ মেনে আঁকা। যেখানে C-তে হিসাব রাখার কাজ সবচেয়ে বেশি ছিল, ফারাকটাও সেখানেই সবচেয়ে বড়।

জোড়া	C-তে যে খুঁটিনাটি হাতে ঠিক রাখতে হয়	STL দিয়ে
বাড়তে থাকা array	5: count, capacity, বাড়ানোর নিয়ম, `realloc` ব্যর্থ হলে কী হবে, `free`	0
Search	4: element-এর সংখ্যা, loop-এর সীমা, "পাওয়া যায়নি"-এর মান, `break`	1: `end()`-এর সঙ্গে তুলনা
Sort	4: element-এর সংখ্যা, element-এর size, `void` pointer-এর cast, negative, শূন্য আর positive ফেরত দেওয়ার নিয়ম	0

লাইন গোনাটা মোটা দাগের মাপ, আর search-এর বেলায় ফারাকটা সামান্যই। আসল কলাম হলো দ্বিতীয়টা। হাতে রাখা 13টা খুঁটিনাটি কমে হয় মাত্র একটা। আর যে খুঁটিনাটি সরে গেল, সেখানে bug হওয়ার আর কোনো সুযোগই থাকল না।

STL-এর জন্য তোমাকে কী দিতে হয়

ফ্রিতে কিছুই আসে না। নিচে চারটা খরচ, সোজাসুজি বলা, যাতে তুমি নিজেই পাল্লায় তুলে দেখতে পারো।

Compile time। Compiler Explorer-এ GCC 12.2, runner-এর flag-এর সঙ্গে -E দিয়ে চালালে (এটা শুধু header-গুলো ভেতরে বসিয়ে দেয়), দুইটা C header সহ Example 1 ফুলে হয় 665 লাইন। <iostream> আর <vector> সহ Example 2 ফুলে হয় 32,394 লাইন। বড় project-এ এটা টের পাওয়া যায় ধীর build হিসেবে।
Error message। Template ভুলভাবে ব্যবহার করলে message-টা library-র ভেতরের কয়েক ডজন লাইন জুড়ে চলতে পারে। দরকারি লাইনটা কীভাবে খুঁজে বের করবে, Module 1 সেটা শেখাবে।
শিখতে সময় লাগে। কোন কাজে কোন container মানায়, আর প্রতিটা operation-এর খরচ কত, এগুলো শিখতে হবে। এই track সেজন্যই, আর এতে কয়েক সপ্তাহ লাগে, এক বিকেলে হয় না।
নিয়ন্ত্রণ কম। Vector নিজেই ঠিক করে কতটা বাড়বে, আর কখন তার element-গুলো সরাবে। আগে থেকে জায়গা reserve করতে বলতে পারো, কিন্তু বাড়ার নিয়মটা তুমি বেছে দিতে পারো না। যে code-কে প্রতিটা byte-এর হিসাব রাখতে হয়, যেমন ছোট্ট কোনো device-এর firmware, সেটা এই কারণেই প্রায়ই সাধারণ C array ব্যবহার করে।

তাহলে সৎ সারকথা এটা। এই track-এ তুমি যত program লিখবে, contest-এ হোক বা অফিসে, প্রায় সবগুলোতেই STL জেতে। যেখানে জেতে না, সেখানে কেন জেতে না তুমি বুঝবে, কারণ এর খরচগুলো তোমার জানা।

এটা কোথায় কাজে লাগছে

C++ Core Guidelines. Bjarne Stroustrup আর Herb Sutter-এর সম্পাদনা করা এই guideline বলে, standard container-ই আগে বেছে নাও। Rule SL.con.1 বলে C array-র বদলে std::array বা std::vector নিতে, আর SL.con.2 vector-কে default বানায়।
LLVM-এর ADT library. LLVM নিজেদের কিছু container লিখেছে, যেমন SmallVector, আর কেন লিখেছে সেটা ওদের Programmer's Manual-এ বলা আছে। একটা SmallVector তার প্রথম কয়েকটা element নিজের ভেতরেই রাখে, তাই ছোট size-এ heap থেকে memory চাইতে হয় না। মানে "নিয়ন্ত্রণ কম" খরচটা একটা project ইচ্ছা করেই ফেরত কিনে নিয়েছে, আগে মেপে দেখে।
Google-এর C++ Style Guide. Google-এর code-এ standard container আর algorithm খোলা হাতে ব্যবহার হয়। Guide-টা পুরো STL নিষেধ করে না। নিষেধ করে শুধু standard library-র ছোট একটা তালিকা, যেমন <ratio> আর <filesystem>।

যে ভুলগুলো সবাই করে

১. STL সব bug দূর করে দেয়, এটা বিশ্বাস করা।

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {10, 20, 30};
    std::cout << v.at(10) << '\n';
}

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

STL হিসাব রাখার bug সরায়, logic-এর bug না। তিন element-এর vector-এর কাছে element 10 চাওয়া এখনো ভুল। v.at(10) উপরের message দিয়ে program থামিয়ে দেয়, আর এটাই ভালো ফল। v[10] কোনো check-ই করে না, ওই জায়গার memory-তে যা আছে তাই পড়ে ফেলে। শেখার সময়টায় at() ব্যবহার করো।

২. নিজে বাড়তে থাকা array লেখা, আর একটা element কম copy করা।

void push(int x)
{
    if (n == cap) {                         /* full: grow by two */
        int *bigger = calloc(cap + 2, sizeof *bigger);
        for (int i = 0; i < n - 1; i++) bigger[i] = a[i];
        free(a);
        a = bigger;
        cap += 2;
    }
    a[n++] = x;
}

এটাই Bob-এর function। GCC কোনো message-ই দেয় না। 1 থেকে 6 push করে ছাপাও, output আসবে 1 0 3 0 5 6: array যতবার বড় হয়, শেষ element-টা হারিয়ে যায়, কারণ copy থেমে যায় n - 1-এ। সমাধান হলো i < n, আর তার চেয়েও ভালো সমাধান std::vector। এই bug তুমিও লিখবে, কারণ off-by-one-এর চেয়ে বেশি হয় এমন কোনো bug নেই।

৩. std::find-এর উত্তরকে true বা false ধরে নেওয়া।

if (std::find(v.begin(), v.end(), 8)) {
    std::cout << "found\n";
}

GCC 12 বলে (মাঝখানটা ছোট করে দেখানো) error: could not convert 'std::find<...>(...)' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >' to 'bool'। find হ্যাঁ বা না ফেরত দেয় না, দেয় একটা iterator। লেখো if (std::find(v.begin(), v.end(), 8) != v.end())। C-র "শূন্য মানে না" অভ্যাসটার জন্যই এখানে সবাই ধরা খায়।

মাথা খাটাও

এই program-টা valid C, আবার valid C++-ও। একবার C হিসেবে compile করো, তারপর C++ হিসেবে। দুইবারই কি একই সংখ্যা ছাপবে?

#include <stdio.h>

int main(void)
{
    printf("%zu\n", sizeof('a'));
    return 0;
}

আসল প্রশ্নটা হলো 'a'-এর type কী। দুই ভাষাতেই "character literal" খুঁজে দেখো, আর মনে করো Playground-এ একটা int কত বড়।

অনুশীলন ১সহজ

Example 1 আর 2 Playground-এ চালাও। তারপর দুইটাই এমনভাবে বদলাও, যাতে 1 থেকে 5-এর বদলে 1 থেকে 8-এর বর্গ রাখে।

নিজে যাচাই করো। প্রতিটা program-এ কয়টা লাইন বদলাতে হলো, গুনে দেখো। C version-এ array বাড়ানোর code বদলায়নি, আর কেন বদলায়নি সেটা তোমার বলতে পারার কথা: ওটা আগে থেকেই যত সংখ্যাই আসুক সামলাতে পারত।

অনুশীলন ২মাঝারি

"যে ভুলগুলো সবাই করে" অংশ থেকে Bob-এর push নাও। না চালিয়ে, খাতায় 1 থেকে 6 পর্যন্ত push হাতে ধরে চালাও: প্রতিটা push-এর পর n, cap আর array-র ভেতরে কী আছে লিখে রাখো।

নিয়ম। calloc-এর কথাটা কাজে লাগাও: নতুন memory শুরুতে পুরোটাই শূন্য থাকে। যে push-গুলোতে array বড় হয়, সেগুলো দাগিয়ে রাখো।

নিজে যাচাই করো। তোমার শেষ লাইন 1 0 3 0 5 6-এর সঙ্গে মিলতে হবে। Array বড় হয় push 1, 3 আর 5-এ, আর তিনটার মধ্যে মাত্র দুইটায় একটা element হারায়। প্রথমটায় কেন হারায় না, বুঝিয়ে বলো।

অনুশীলন ৩কঠিন

Kenji একটা sensor-এর firmware লিখছে। Sensor-টার memory 2 KB, আর কোনো operating system নেই। সে std::vector ব্যবহার করবে কি না, উপরের চারটা খরচ দিয়ে এক অনুচ্ছেদে লেখো।

নিয়ম। অন্তত দুইটা খরচের নাম বলো, আর প্রতিটা তার device-এ আদৌ গুরুত্বপূর্ণ কি না, সেটাও বলো।

নিজে যাচাই করো। ভালো উত্তরের নজর থাকে নিয়ন্ত্রণের উপর। Vector যখনই বড় হয়, heap-এর কাছে memory চায়। 2 KB-তে, কোনো system ছাড়া, ওই চাওয়া ব্যর্থ হতে পারে, আর তখন সামলানোর কোনো উপায় থাকে না। ওখানে compile time প্রায় কোনো ব্যাপারই না। একটা নির্দিষ্ট মাপের array, বা Lesson 3-এর std::array, সাধারণত এখানে বেছে নেওয়া হয়।

যে প্রশ্নগুলো সবার মনে আসে

STL এত ভালো হলে C programmer-রা এখনো নিজেদের array নিজেরা লেখে কেন?

C-তে STL নেই, তাই C-তে বাছার কিছু নেই। C++-এ আছে। নিজে লেখার সাধারণ কারণগুলো "STL-এর জন্য তোমাকে কী দিতে হয়" অংশে আছে: memory খুব কম, পুরো নিয়ন্ত্রণ দরকার, বা LLVM-এর SmallVector-এর মতো কোনো বিশেষ চাহিদা।
std::sort কি সত্যিই qsort-এর চেয়ে দ্রুত?

সাধারণত, হ্যাঁ। qsort প্রতিটা তুলনার জন্য একটা function pointer দিয়ে তোমার comparator call করে। std::sort একটা template, তাই compiler তুলনাটা দেখতে পায়, আর সেটা সরাসরি loop-এর ভেতরে বসিয়ে দিতে পারে। এ ধরনের জিনিস তুমি নিজে মেপে দেখবে Module 17-এ।
Compile বড় হলে কি program-ও ধীর হয়?

না। ওই 32,394 লাইন হলো declaration, যেগুলো compiler পড়ে নেয়; ওদের প্রায় কোনোটাই তোমার program-এর code হয়ে যায় না। খরচটা build time-এ, run time-এ না।
Contest-এ কি STL-এর উপর ভরসা করা যায়?

হ্যাঁ। ICPC আর Codeforces দুই জায়গাতেই GCC আর তার standard library পাবে, Playground যেটা চালায়, আর contest-এর solution-এ এটা সারাক্ষণই ব্যবহার হয়। Contest-এ যে খরচগুলো আসলে গুরুত্বপূর্ণ, সেগুলো হলো complexity, আর এই track প্রতিটা operation-এর complexity শেখায়।

মূল কথা

STL তোমাকে পরীক্ষিত code দেয়: হিসাব রাখার যে লাইনগুলোতে bug থাকে, সেগুলো তোমার program থেকে উধাও।
প্রতিটা STL operation-এর খরচ standard-এ লেখা, তাই কিছু চালানোর আগেই তুমি সেটা জানতে পারো।
সবার চেনা নাম code-কে পড়ার মতো করে: std::sort কী করে, সব C++ programmer জানে।
খরচগুলো সত্যি: লম্বা compile, লম্বা error message, শিখতে সময় লাগা, আর কম নিয়ন্ত্রণ।
STL হিসাব রাখার bug সরায়, logic-এর bug না; at() ভুল index ধরে, [] ধরে না।

পরের lesson-এ আসছে সব container-এর পুরো তালিকা, এক table-এ, আর প্রতিটা কোন প্রশ্নের উত্তর সবচেয়ে দ্রুত দেয়।

lesson ২ শেষ

শেষ হলে চিহ্ন দিন, অগ্রগতি আপনার সাথে থাকবে।

পরেরটা: container-গুলো এক নজরে: কোনটা কী কাজে ভালো

পরের lesson