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

এক ছবিতে STL: চার রকম জিনিস

Freeপড়াlesson ১ / ৬

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

STL কী, এক বাক্যে বলে দিতে পারবে।
এর চার রকম জিনিসের নাম বলতে পারবে, প্রতিটার একটা করে উদাহরণসহ।
STL কী না, সেটা বুঝিয়ে বলতে পারবে, যাতে বাকিগুলো কোথায় খুঁজতে হবে জানো।

Maria-র একটা C program আছে, যেটা একটা দোকানের দামের তালিকা রাখে। এতে হাতে লেখা একটা বাড়তে থাকা array আছে, হাতে লেখা একটা linked list আছে, আর হাতে লেখা একটা sort। Program-টা প্রায় 300 লাইনের, আর এতে দুইটা bug আছে, যেগুলো সে এখনো খুঁজে পায়নি।

STL দিয়ে C++-এ একই program প্রায় 40 লাইন। দুইটা bug-ই উধাও। কেউ ওগুলো সারায়নি। যে লাইনগুলোতে bug ছিল, সেই লাইনগুলোই আর নেই, কারণ বাড়তে থাকা array, list আর sort এখন আসে library থেকে।

Maria তখন সেই প্রশ্নটা করে, যার উত্তর এই পুরো module: "কিন্তু যে code আমি নিজে লিখিনি, সেটাকে বিশ্বাস করব কেন?" উত্তরে যাওয়ার আগে তোমার হাতে একটা নকশা থাকা দরকার। এই lesson-টাই সেই নকশা।

STL কী, এক বাক্যে

STL (Standard Template Library) হলো C++ standard library-র সেই অংশ, যেটা container, iterator, algorithm আর function object দেয়, আর এগুলো বানানোই হয়েছে একটার সঙ্গে আরেকটা খাপে খাপে মেলার জন্য।

Standard library হলো সেই code, যেটা প্রতিটা C++ compiler-এর সঙ্গেই আসে, ঠিক যেমন প্রতিটা C compiler-এর সঙ্গে printf আর qsort আসে। এটা download করতে হয় না। একটা header include করো, তারপর ব্যবহার করো।

ডিজাইনটা Alexander Stepanov-এর। তিনি তখন Hewlett-Packard-এ Meng Lee-র সঙ্গে কাজ করছিলেন। 1994 সালে C++ standards committee ভোট দিয়ে এটাকে draft standard-এ ঢোকায়। প্রথম C++ standard, মানে C++98 থেকে শুরু করে প্রতিটা standard-এই এটা আছে। নামের "Template" শব্দটার মানে হলো, একই code যেকোনো type-এর element নিয়ে কাজ করে। হাতে কলমে এর মানে কী দাঁড়ায়, Module 1 সেটা দেখাবে।

তাহলে STL আলাদা কোনো product না। এটা কয়েকটা header, যেমন <vector> আর <algorithm>, যেগুলো তোমার compiler-এ আগে থেকেই আছে।

পুরো ছবিটা: চার রকম জিনিস

এই track-এর সবকিছু এই চার রকমের কোনো একটার মধ্যে পড়ে। ছবিটা এখনই মাথায় গেঁথে নাও। পরের প্রতিটা module ছবিটার কোনো একটা বাক্সে খুঁটিনাটি যোগ করবে, আর প্রতিটা module-এর শুরুতে তুমি এটা আবার দেখবে।

ছবি 1। চার রকম জিনিস। Container ধরে রাখে, iterator আঙুল রাখে, algorithm কাজ করে, function object বলে দেয় কীভাবে। এই track-এর প্রতিটা module এই ছবি দিয়েই শুরু হয়।

তীরগুলো বাম থেকে ডানে পড়ো। Container iterator দেয়। দুইটা iterator মিলে পরপর কয়েকটা element-এর একটা অংশ দাগিয়ে দেয়, এটাকে বলে range। Algorithm কাজ করে ওই range-এর উপর। আর তুমি যদি একটা function object পাঠাও, সেটা algorithm-কে বলে দেয় কীভাবে তুলনা করবে বা কী করবে।

তাই এই চারটা আলাদা আলাদা জিনিসের চারটা গাদা না। এরা একটা মেশিনের চারটা অংশ। মাঝখানের অংশটা হলো iterator, আর ওর জন্যই বাকি তিনটা একে অপরের সঙ্গে মিলতে পারে।

STL-এর একটা লাইন পড়া

std::sort(prices.begin(), prices.end(), std::greater<int>());

std:: বলে দেয়, নামটা standard library থেকে এসেছে। STL-এর প্রতিটা নাম ওখানেই থাকে।
sort হলো algorithm, মানে যে কাজটা করতে হবে।
prices হলো container, যেটা সংখ্যাগুলো ধরে রেখেছে।
prices.begin() আর prices.end() দুইটা iterator: range কোথায় শুরু, আর কোথায় শেষ তার ঠিক এক ঘর পরে।
std::greater<int>() একটা function object: "বড়টা আগে রাখো"।

Container জিনিস ধরে রাখে

Container এমন একটা object, যেটা অনেকগুলো element একসঙ্গে রাখে আর ওদের memory তোমার হয়ে সামলায়। তুমি এতে জিনিস যোগ করো, এখান থেকে বাদ দাও। এটা নিজে নিজেই বড় হয়, ছোট হয়, তাই এর জন্য তোমাকে কখনো malloc বা free call করতে হয় না।

std::vector-টাই তুমি সবচেয়ে বেশি ব্যবহার করবে। এটা একটা বাড়তে থাকা array: element-গুলো memory-তে পাশাপাশি বসে, ঠিক C array-র মতো, আর তুমি এখনো v[0] লিখতে পারো।

Example 1: একটা container

কাজের STL program-এর মধ্যে সবচেয়ে ছোটটা। তিনটা score ঢোকে, আর vector নিজেই গুনে রাখে।

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> scores;
    scores.push_back(72);
    scores.push_back(45);
    scores.push_back(90);
    std::cout << "I hold " << scores.size() << " scores\n";
    std::cout << "The first is " << scores[0] << '\n';
}

I hold 3 scores
The first is 72

push_back শেষে একটা element যোগ করে, আর size() বলে কয়টা আছে। Capacity-র হিসাব রাখতে হয় না, free করারও কিছু নেই। std::cout << যদি নতুন লাগে, আপাতত এটাকে printf ভেবে পড়ো; Module 1 এটা ঠিকমতো শেখাবে।

Compiler-এ চালাও

Iterator container-এর ভেতরে আঙুল রাখে

Iterator এমন একটা object, যেটা container-এর একটা element-এর উপর আঙুল রাখে, আর পরেরটায় সরে যেতে পারে। C-র pointer চিনলে ধারণাটা তুমি আগেই জানো: যে element-এ আঙুল আছে, *it সেটা পড়ে, আর ++it আঙুলটা এক ঘর সামনে সরায়।

প্রতিটা container এরকম দুইটা দেয়। begin() আঙুল রাখে প্রথম element-এ। end() আঙুল রাখে শেষ element-এর এক ঘর পরে, এমন একটা জায়গায় যেখানে কিছুই নেই। কেন এটাই ঠিক সিদ্ধান্ত, Lesson 4 সেটা বুঝিয়ে বলবে।

Example 2: একটা iterator

লম্বা type-এর নামটা এখানে একবার পুরো লেখা হলো, যাতে তুমি দেখতে পাও। Module 1 থেকে auto এটা তোমার হয়ে লিখে দেবে।

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> scores = {72, 45, 90};
    std::vector<int>::iterator it = scores.begin();
    std::cout << *it << '\n';
    ++it;
    std::cout << *it << '\n';
}

72
45

Iterator শুরু করেছিল 72-এ, এক ঘর সরল, তারপর পড়ল 45। তাহলে iterator হলো এমন একটা অবস্থান, যেটা পড়া যায় আর সরানো যায়। C array-র ভেতরে একটা pointer ঠিক এটাই।

Compiler-এ চালাও

Algorithm কাজ করে iterator দিয়ে

Algorithm হলো একটা function template, যেটা থাকে <algorithm>-এ (বা <numeric>-এ) আর একটা range-এর উপর একটাই কাজ করে: sort করা, খোঁজা, গোনা, উল্টে দেওয়া। এরকম algorithm একশোরও বেশি আছে।

এবার আসল কথাটা। Algorithm container নেয় না, নেয় দুইটা iterator। সে কখনো জিজ্ঞেস করে না, "এটা কি vector?"। সে শুধু প্রথম iterator থেকে দ্বিতীয়টা পর্যন্ত হেঁটে যায়। এজন্যই একটাই std::sort চলে vector-এ, সাধারণ array-তে, এমনকি সেইসব container-এও, যেগুলো লেখা হয়েছে এর বহু বছর পরে।

Example 3: একটা algorithm

একটা vector, দুইটা algorithm: std::sort ওটাকে সাজায়, আর std::count একটা মান কয়বার আছে গোনে।

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

int main()
{
    std::vector<int> scores = {72, 45, 90, 45, 61};
    std::sort(scores.begin(), scores.end());
    std::cout << "sorted:";
    for (int s : scores) std::cout << ' ' << s;
    std::cout << '\n';
    std::cout << "45 appears " << std::count(scores.begin(), scores.end(), 45) << " times\n";
}

sorted: 45 45 61 72 90
45 appears 2 times

for (int s : scores) লাইনটার মানে "scores-এর প্রতিটা element s-এর জন্য"। এটাকে বলে range-for, আর Module 1-এ এটার জন্য আলাদা একটা lesson আছে। খেয়াল করো, কোনো algorithm-কেই size বলে দেওয়া হয়নি: সেই খবরটা দুইটা iterator-ই বয়ে নিয়ে যায়।

Compiler-এ চালাও

Function object algorithm-কে বলে দেয় কীভাবে

Function object (আরেক নাম functor) হলো এমন যেকোনো জিনিস, যাকে function-এর মতো call করা যায়। Algorithm কীভাবে কাজ করবে সেটা বদলাতে তুমি ওকে একটা function object পাঠাও। std::sort নিজে থেকে ছোট element আগে রাখে; ওকে std::greater<int>() দাও, তখন বড়টা আগে রাখবে।

C-তে এই একই কাজ তুমি করতে একটা function pointer দিয়ে, মানে qsort-এ যে comparator পাঠাও সেটা দিয়ে। Function object ঠিক ওই কাজটাই করে, বাড়তি সুবিধা হলো type-টা compiler যাচাই করে দেয়। আজকাল সবচেয়ে বেশি দেখা যায় lambda, মানে ছোট একটা function, যেটা ঠিক যেখানে দরকার সেখানেই লিখে ফেলা হয়। Lambda শেখাবে Module 12; এখানে দেখলে চিনতে পারলেই চলবে।

Example 4: একটা function object

একই sort, দুইবার। দ্বিতীয় call-এ একটা function object দেওয়া হয়েছে, আর ক্রমটা উল্টে গেছে।

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

int main()
{
    std::vector<int> scores = {72, 45, 90, 61};
    std::sort(scores.begin(), scores.end());
    std::cout << "smallest first: " << scores[0] << '\n';
    std::sort(scores.begin(), scores.end(), std::greater<int>());
    std::cout << "biggest first:  " << scores[0] << '\n';
}

smallest first: 45
biggest first:  90

std::greater<int> থাকে <functional>-এ। যেকোনো দুইটা int পেলে এটা একটাই প্রশ্নের উত্তর দেয়: "প্রথমটা কি বড়?"। তাই sort বদলায়নি; বদলেছে শুধু তুলনার নিয়মটা।

Compiler-এ চালাও

চারটাই এক program-এ

এটাই Maria-র নতুন করে লেখা program-এর মূল অংশ: তার দামের তালিকা, সবচেয়ে দামি থেকে নিচের দিকে সাজানো, আর উপরের তিনটা ছাপানো। নিচের ব্যাখ্যা পড়ার আগে প্রতিটা লাইনে আঙুল রেখে বলো, ওটা কোন রকমের।

Example 5: Maria-র দামের তালিকা

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

int main()
{
    std::vector<int> prices = {450, 1200, 80, 990, 300, 640};
    std::sort(prices.begin(), prices.end(), std::greater<int>());

    std::cout << "Top three prices:\n";
    for (auto it = prices.begin(); it != prices.begin() + 3; ++it) {
        std::cout << "  " << *it << '\n';
    }
    std::cout << "Items over 500: "
              << std::count_if(prices.begin(), prices.end(), [](int p) { return p > 500; }) << '\n';
}

Top three prices:
  1200
  990
  640
Items over 500: 3

Vector হলো container। sort আর count_if হলো algorithm। begin() আর it হলো iterator, আর begin() + 3 মানে "শুরু থেকে তিন ঘর ভেতরে"। std::greater<int>() আর lambda [](int p) { return p > 500; } হলো function object। পনেরো লাইনের code, অথচ একটা লাইনও memory সামলাচ্ছে না।

Compiler-এ চালাও

STL কী না

সীমানাগুলো জানা থাকলে অনেক খোঁজাখুঁজি বাঁচে। তিনটা জিনিস মানুষ STL-এ পাবে বলে ধরে নেয়, কিন্তু ওখানে নেই।

GUI library না। এতে window, button বা ছবি কিছুই নেই। যে program-এ window থাকে, সেগুলো Qt-র মতো আলাদা একটা library ব্যবহার করে।
Network library না। Standard C++17 আর C++20-এ socket নেই, HTTP-ও নেই। একটা server হয় operating system-এর call ব্যবহার করে, নয়তো Boost.Asio-র মতো কোনো library।
পুরো standard library না। Input আর output (<iostream>), সময় (<chrono>), thread আর file, এগুলোও standard library-র অংশ। কিন্তু এই track যে container, iterator আর algorithm-এর ডিজাইন নিয়ে, এগুলো তার মধ্যে পড়ে না।

নামটা নিয়ে একটা সৎ কথা বলে রাখি। অনেক programmer "STL" বলতে পুরো standard library বোঝায়, তাই শব্দটা তুমি দুই অর্থেই শুনবে। এই track শব্দটা ব্যবহার করে উপরের চার রকম জিনিসের জন্য, সঙ্গে std::string, যেটা character-এর একটা container-এর মতোই আচরণ করে।

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

LLVM. Clang-এর পেছনের compiler toolkit-টা সব জায়গায় std::vector আর std::sort ব্যবহার করে। এর নিজের কিছু container-ও আছে, যেমন SmallVector। ওগুলো একই begin() আর end() দিয়ে বানানো, তাই standard algorithm-গুলো কোনো বদল ছাড়াই ওগুলোর উপর চলে।
Chromium. Chrome আর Edge-এর পেছনের browser-টা standard container ব্যবহার করে। যেখানে অন্যরকম কিছু দরকার হয়েছে, সেখানে ওর base library নিজের container যোগ করেছে, যেমন base::flat_map, একই iterator interface দিয়ে।
Unreal Engine, উল্টো উদাহরণ। এই game engine নিজের container নিয়ে আসে (TArray, TMap, TSet), আর এর code STL-এরগুলোর বদলে এগুলোই ব্যবহার করে। তবুও একটা TArray-এর begin() আর end() আছে, তাই চার রকম জিনিসের ছবিটা এখানেও খাটে।
Programming contest. ICPC আর Codeforces পুরো standard library সহ C++ compile করে। একজন contestant std::sort-এর একটা call দিয়েই দশ লাখ সংখ্যা sort করে ফেলে, আর বেঁচে যাওয়া সময়টা দেয় problem-টার পেছনে।

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

১. Container-এর ভেতরে sort খোঁজা।

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

GCC 12 বলে error: 'class std::vector<int>' has no member named 'sort'। Algorithm container-এর member না; ওরা আলাদা থাকে আর iterator নেয়। লেখো std::sort(v.begin(), v.end());। এই ভুলটা তুমি করবেই, কারণ পরে যে ভাষাগুলোর সঙ্গে দেখা হবে, তার বেশিরভাগই sort-কে list-এর গায়েই বসিয়ে রাখে।

২. Algorithm-এর header ভুলে যাওয়া।

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {3, 1, 2};
    std::sort(v.begin(), v.end());
}

Playground-এ GCC 12 বলে error: 'sort' is not a member of 'std'; did you mean 'qsort'?। Container-গুলোর নিজের নিজের header আছে, আর algorithm থাকে <algorithm>-এ। #include <algorithm> যোগ করো। অন্য কিছু compiler ঘটনাচক্রে এটা compile করে ফেলে, তাই যেদিন হঠাৎ কাজ করা বন্ধ করে, সেদিন মানুষ অবাক হয়।

৩. প্রশ্নটা না জেনেই container বেছে ফেলা।

Kenji-র প্রথম প্রশ্ন সব সময় একটাই: "কোন container সবচেয়ে দ্রুত?"। সব কাজে সবচেয়ে দ্রুত, এমন কোনো container নেই। একটা শেষে যোগ করতে দ্রুত, আরেকটা নাম খুঁজতে, আরেকটা জিনিস সাজিয়ে রাখতে। "কিসে দ্রুত?", এই প্রশ্নের উত্তরের table-টাই Lesson 3। আগে ঠিক করো data-কে কী জিজ্ঞেস করবে, তারপর বেছে নাও।

মাথা খাটাও

চারটা ছোট বর্ণনা। প্রতিটা কোন রকমের: container, iterator, algorithm নাকি function object?

এটা নামগুলো বর্ণমালার ক্রমে রাখে, আর কোনো নাম আছে কি না চট করে বলে দেয়।
এটা তাকের তিন নম্বর বইটার উপর দাঁড়িয়ে আছে, আর এক পা সরে চার নম্বরটায় যেতে পারে।
পরপর কয়েকটা element-এর যেকোনো অংশ দাও, এটা ওই অংশটা উল্টে শেষ থেকে শুরু করে দেবে।
দুইটা দাম দেখাও, এটা একটাই প্রশ্নের উত্তর দেবে: প্রথমটা কি দ্বিতীয়টার আগে বসবে?

প্রতিটাকে জিজ্ঞেস করো: এটা ধরে রাখে, আঙুল রাখে, কাজ করে, নাকি সিদ্ধান্ত দেয়? এদের মধ্যে শুধু একটার নিজের element আছে।

অনুশীলন ১সহজ

এই আটটা নাম চার রকমে ভাগ করো: std::vector, std::find, begin(), std::greater<int>, std::map, std::reverse, end(), std::less<int>।

নিজে যাচাই করো। প্রতিটা রকমে দুইটা করে নাম থাকার কথা। কোনো বাক্সে তিনটা হয়ে গেলে ছবি 1 আর উপরের syntax card আরেকবার দেখো।

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

Maria-র C program-এ হাতে লেখা তিনটা অংশ ছিল: একটা বাড়তে থাকা array, একটা linked list আর একটা sort। প্রতিটার জন্য লেখো, কোন STL নাম ওটার জায়গা নেয়, আর সেটা কোন রকমের।

নিয়ম। প্রতিটা অংশের জন্য এক লাইন। Lesson 3 পড়া থাকলে ওখানকার container-এর তালিকা ব্যবহার করতে পারো। না পড়লে list-টার নাম ওর কাজ দেখে অনুমান করো, পরে মিলিয়ে নিও।

নিজে যাচাই করো। তিনটা উত্তরের দুইটা container, একটা algorithm। Algorithm-এর কাজ করতে একটা container লাগে, কিন্তু নির্দিষ্ট কোনো একটা লাগে না।

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

এক অনুচ্ছেদে এই প্রশ্নের উত্তর লেখো: LLVM-এর SmallVector আসার দশ বছরেরও বেশি আগে std::sort লেখা হয়েছিল, তবুও এটা একটা SmallVector ঠিকঠাক sort করে। যে container function-টার লেখক কখনো চোখেই দেখেননি, সেটার উপর function-টা কাজ করে কীভাবে?

নিয়ম। "iterator" আর "range" শব্দ দুইটা ব্যবহার করতে হবে। "জাদু" শব্দটা চলবে না।

নিজে যাচাই করো। ভালো উত্তর বলবে, sort কখনো container দেখে না, দেখে শুধু দুইটা iterator। যে container ঠিক রকমের iterator দেয়, সেটাকেই sort করা যায়। ছবি 1-এর ভাঙা দাগের বাক্সটাই পুরো উত্তর।

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

STL কি আলাদা কিছু, যেটা install করতে হবে?

না। এটা standard library-র অংশ, যেটা প্রতিটা C++ compiler-এর সঙ্গেই আসে, Playground-এর GCC 12-ও তার মধ্যে আছে। <vector>-এর মতো একটা header include করো, ব্যস, পেয়ে গেলে।
STL শেখার আগে কি C++-এর class জানতে হবে?

না। Class তোমাকে ব্যবহার করতে হবে, লিখতে হবে না, আর ব্যবহারটা দেখতে এরকম: v.push_back(3)। এই track যে কয়েকটা C++ জিনিসের উপর দাঁড়িয়ে, Module 1 সেগুলো শেখায়। নিজের class আর template লেখা একটা C++ track-এর কাজ।
STL দিয়ে লেখা code কি হাতে লেখা C-র চেয়ে ধীর?

সাধারণত না, কখনো কখনো বরং দ্রুত। std::sort প্রায়ই qsort-এর চেয়ে দ্রুত, কারণ compiler তুলনার কাজটা inline করে ফেলতে পারে। STL কোথায় সত্যিই তোমার কাছ থেকে কিছু খরচ নেয়, Lesson 2 সেটা সৎভাবে বলে।
এটাকে "template" library বলে কেন?

কারণ প্রতিটা container আর algorithm একবারই লেখা হয়েছে template হিসেবে, মানে একটা ছাঁচ, যেটা compiler তোমার type দিয়ে ভরে নেয়। std::vector<int> আর std::vector<double> হলো দুইটা version, যেগুলো compiler তোমার হয়ে লিখে দেয়। Module 1-এ এই ধারণা নিয়ে একটা lesson আছে।

মূল কথা

STL হলো C++ standard library-র সেই অংশ, যেটা container, iterator, algorithm আর function object দেয়।
Container ধরে রাখে, iterator আঙুল রাখে, algorithm কাজ করে, function object বলে দেয় কীভাবে।
Algorithm নেয় দুইটা iterator, কখনো container না, তাই একটা algorithm অনেক container-এ চলে।
STL কোনো GUI না, network library না, পুরো standard library-ও না।
ছবি 1-ই নকশা: পরের প্রতিটা module ছবিটার একটা করে বাক্স ভরাট করবে।

এরপর দেখবে, এটা শেখা কেন কাজের। তিনটা program দুইবার করে লেখা, একবার C-তে আর একবার STL দিয়ে, পাশে সেই খরচগুলো, যেগুলোর কথা কেউ পোস্টারে লেখে না।

lesson ১ শেষ

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

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

পরের lesson