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

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

Freeপড়াlesson ৩ / ৬

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

এই track যে container-গুলো শেখায়, সেগুলোকে তিনটা পরিবারে ভাগ করে বলতে পারবে।
প্রতিটা container কোন একটা প্রশ্নের উত্তর সবচেয়ে দ্রুত দেয়, সেটা বলতে পারবে।
O(1), O(log n) আর O(n) দিয়ে লেখা খরচের table পড়তে পারবে, কোনো container ভেতরে কীভাবে কাজ করে সেটা না জেনেই।

Kenji Lesson 1 পড়ে ফেলেছে, আর তার একটাই প্রশ্ন: "কোন container সবচেয়ে দ্রুত?" Team-এ সবচেয়ে পরিষ্কার code লেখে Amara। সে উল্টো একটা প্রশ্ন করে: "কিসে দ্রুত?"

যে container এক ধাপে শেষে যোগ করে, একটা মান খুঁজতে তার হয়তো দশ লাখ ধাপ লাগে। যে container 20 ধাপে একটা মান খুঁজে দেয়, সে 5 নম্বর জায়গায় কী আছে সেটা চট করে বলতে পারে না। এই lesson-টাই Amara-র উত্তর: প্রতিটা container, কোন প্রশ্নের জন্য সেটা বানানো, আর খরচের একটা table।

কোনোটা ভেতরে কীভাবে কাজ করে, সেটা এখনই শিখবে না। ওটার জন্য আছে Module 2 থেকে 10। এখানে পুরো তাকটা একসঙ্গে পাবে, যাতে পরের প্রতিটা module এমন একটা ছবি ভরাট করে, যেটা তোমার মাথায় আগে থেকেই আছে।

Container-এর তিনটা পরিবার

Element-গুলো কীভাবে সাজায়, সেই হিসাবে container তিনটা পরিবারে ভাগ হয়।

Sequence container element-গুলো রাখে ঠিক যে ক্রমে তুমি ঢুকিয়েছ: vector, string, array, deque আর list।
Container adaptor একটা sequence container-কে মুড়ে রাখে, আর তোমাকে শুধু এক বা দুই মাথা ছুঁতে দেয়: stack, queue আর priority_queue।
Associative container element-গুলো সাজায় ওদের মান দেখে, যাতে একটা দ্রুত খুঁজে পাও। এরা হলো set আর map, ওদের multi রূপ, যেখানে একই মান বারবার রাখা যায়, আর ওদের unordered রূপ, যেগুলো ক্রমের বদলে hashing ব্যবহার করে।

পার্থক্যগুলো যাতে সহজে চোখে পড়ে, তাই নিচের প্রতিটা example একই তিনটা সংখ্যা একই ক্রমে ঢোকায়: প্রথমে 30, তারপর 10, তারপর 20। খেয়াল রাখো, ওরা কোন ক্রমে বেরিয়ে আসে। শুধু ওই ক্রমটাই প্রতিটা container সম্পর্কে অনেক কিছু বলে দেয়।

যেকোনো container declare করা

std::vector<int> marks;
std::map<std::string, int> price;

std::vector, std::map: container-এর নাম, যেটা আসে ওর নিজের header থেকে (<vector>, <map>)।
<int>: এটা কোন type-এর element ধরে রাখে, angle bracket-এর ভেতরে লেখা।
<std::string, int>: map জোড়া ধরে রাখে, তাই ওর দুইটা type লাগে, key আর value।
marks, price: নামটা তুমি বাছো। নতুন container শুরু হয় ফাঁকা অবস্থায়।

Sequence container: যে ক্রমে রেখেছ, সেই ক্রমে

এই পাঁচটা তোমার element-গুলো এক সারিতে রাখে। পার্থক্য হলো, কোথায় যোগ করা সস্তা, আর size বদলানো যায় কি না।

Example 1: vector, বাড়তে থাকা array

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    v.push_back(30);
    v.push_back(10);
    v.push_back(20);
    std::cout << "vector:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << " | v[1] = " << v[1] << '\n';
}

vector: 30 10 20 | v[1] = 10

ওর প্রশ্ন: "i নম্বর জায়গায় কী আছে?", উত্তর এক ধাপে, সঙ্গে শেষে সস্তায় যোগ করা। এটাই default container, আর সবার আগে হাত বাড়াবে এটার দিকেই।

Compiler-এ চালাও

Example 2: string, character-এর একটা vector

#include <iostream>
#include <string>

int main()
{
    std::string s = "cat";
    s += "fish";
    s.push_back('!');
    std::cout << "string: " << s << " | size " << s.size() << " | s[0] = " << s[0] << '\n';
}

string: catfish! | size 8 | s[0] = c

ওর প্রশ্ন: vector-এরটাই, শুধু লেখার জন্য। লেখা নিয়ে কিছু কাজও এটা জানে, যেমন += দিয়ে জোড়া লাগানো আর একটা শব্দ খোঁজা। কোনো '\0' সামলাতে হয় না, উপচে পড়তে পারে এমন কোনো buffer-ও নেই।

Compiler-এ চালাও

Example 3: array, মাপ বাঁধা, আর নিজের size নিজেই জানে

#include <array>
#include <iostream>

int main()
{
    std::array<int, 3> a = {30, 10, 20};
    std::cout << "array:";
    for (int x : a) std::cout << ' ' << x;
    std::cout << " | size is always " << a.size() << '\n';
}

array: 30 10 20 | size is always 3

ওর প্রশ্ন: i নম্বর জায়গা, এমন একটা সংখ্যার জন্য, যেটা program লেখার সময়ই তুমি জানো। এটা এমন একটা C array, যেটা নিজের size জানে, আর একটুও বাড়ে না।

Compiler-এ চালাও

Example 4: deque, দুই মাথাতেই সস্তা

#include <deque>
#include <iostream>

int main()
{
    std::deque<int> d;
    d.push_back(30);
    d.push_front(10);
    d.push_back(20);
    std::cout << "deque:";
    for (int x : d) std::cout << ' ' << x;
    std::cout << " | d[0] = " << d[0] << '\n';
}

deque: 10 30 20 | d[0] = 10

ওর প্রশ্ন: "যেকোনো মাথায় যোগ করো বা বাদ দাও", প্রতিটা এক ধাপে, আর i নম্বর জায়গাও পাওয়া যায়। deque (উচ্চারণ "ডেক", মানে double-ended queue) হলো এমন একটা vector, যার সামনে যোগ করাটাও সস্তা।

Compiler-এ চালাও

Example 5: list, মাঝখানে সস্তা

#include <iostream>
#include <list>

int main()
{
    std::list<int> l = {30, 20};
    auto it = l.begin();
    ++it;
    l.insert(it, 10);
    std::cout << "list:";
    for (int x : l) std::cout << ' ' << x;
    std::cout << '\n';
}

list: 30 10 20

ওর প্রশ্ন: "ঠিক এখানে ঢোকাও বা বাদ দাও", যেখানে তুমি আগে থেকেই দাঁড়িয়ে আছ, অন্য কোনো element না সরিয়ে। "i নম্বর জায়গায় কী আছে?", এই প্রশ্নের দ্রুত উত্তর এটা দিতে পারে না: এর কোনো l[1]-ই নেই। C-তে তুমি হাতে যে linked list লিখেছিলে, এটা সেটাই।

Compiler-এ চালাও

Adaptor: এক দরজায় ঢোকা, এক দরজায় বেরোনো

Adaptor একটা sequence container নেয়, আর ওর বেশিরভাগটাই লুকিয়ে ফেলে। যে মাথাগুলোয় সে অনুমতি দেয়, শুধু সেখানেই তুমি যোগ বা বাদ দিতে পারো। এটা দুর্বলতা না। তোমার problem-এ যদি সব সময় শুধু সবচেয়ে নতুন বা সবচেয়ে পুরনো জিনিসটা লাগে, তাহলে adaptor বাকি সব রকম ভুল অসম্ভব করে দেয়।

Example 6: stack, শেষে ঢুকলে আগে বেরোয়

#include <iostream>
#include <stack>

int main()
{
    std::stack<int> s;
    s.push(30);
    s.push(10);
    s.push(20);
    std::cout << "stack pops:";
    while (!s.empty()) {
        std::cout << ' ' << s.top();
        s.pop();
    }
    std::cout << '\n';
}

stack pops: 20 10 30

ওর প্রশ্ন: "সবার শেষে কী যোগ হয়েছিল?"। থালার একটা স্তূপের মতো: শেষে যেটা রাখা হয়, সেটাই আগে নামে। Undo button, আর C track-এ যে C call stack দেখেছিলে, দুইটাই এভাবে কাজ করে।

Compiler-এ চালাও

Example 7: queue, আগে ঢুকলে আগে বেরোয়

#include <iostream>
#include <queue>

int main()
{
    std::queue<int> q;
    q.push(30);
    q.push(10);
    q.push(20);
    std::cout << "queue pops:";
    while (!q.empty()) {
        std::cout << ' ' << q.front();
        q.pop();
    }
    std::cout << '\n';
}

queue pops: 30 10 20

ওর প্রশ্ন: "সবার আগে কী যোগ হয়েছিল?"। দোকানের কাউন্টারের লাইনের মতো: যে আগে এসেছে, সে আগে পায়।

Compiler-এ চালাও

Example 8: priority_queue, সবচেয়ে বড়টা আগে

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(20);
    std::cout << "priority_queue pops:";
    while (!pq.empty()) {
        std::cout << ' ' << pq.top();
        pq.pop();
    }
    std::cout << '\n';
}

priority_queue pops: 30 20 10

ওর প্রশ্ন: "এই মুহূর্তে সবচেয়ে বড় কোনটা?", নতুন element আসতে থাকলেও। হাসপাতালের emergency-র মতো: যার অবস্থা সবচেয়ে জরুরি, সে আগে যায়, কে আগে এসেছে তাতে কিছু যায় আসে না।

Compiler-এ চালাও

Associative container: মান দিয়ে খোঁজা

এরা তোমার ক্রম একদমই রাখে না। এরা element এমনভাবে সাজায়, যাতে "এই মানটা কি আছে?" প্রশ্নটার উত্তর দ্রুত মেলে। ক্রম রাখা container-গুলো (set, map) element সাজিয়ে রাখে; unordered-গুলো গড়ে আরো দ্রুত হওয়ার জন্য ক্রমটা ছেড়ে দেয়।

Example 9: set আর multiset, সাজানো আর খোঁজা যায়

#include <iostream>
#include <set>

int main()
{
    std::set<int> s = {30, 10, 20, 10};
    std::multiset<int> m = {30, 10, 20, 10};
    std::cout << "set:";
    for (int x : s) std::cout << ' ' << x;
    std::cout << " | multiset:";
    for (int x : m) std::cout << ' ' << x;
    std::cout << " | is 20 in the set? " << s.count(20) << '\n';
}

set: 10 20 30 | multiset: 10 10 20 30 | is 20 in the set? 1

ওর প্রশ্ন: "x কি আছে?", দ্রুত, আর সবকিছু সাজানো থাকে। set প্রতিটা মানের একটাই কপি রাখে, তাই দ্বিতীয় 10-টা বাদ পড়েছে। multiset একই মান বারবার রাখে।

Compiler-এ চালাও

Example 10: map, প্রতিটা key-এর একটা value

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> price;
    price["tea"] = 30;
    price["bun"] = 10;
    price["egg"] = 20;
    std::cout << "map:";
    for (const auto& p : price) std::cout << ' ' << p.first << '=' << p.second;
    std::cout << " | egg costs " << price["egg"] << '\n';
}

map: bun=10 egg=20 tea=30 | egg costs 20

ওর প্রশ্ন: "এই key-এর সঙ্গে কী আছে?"। map হলো কিছু key-এর একটা set, প্রতিটা key একটা করে value বয়ে বেড়ায়, আর সব key অনুযায়ী সাজানো থাকে: bun সবার আগে বেরোয়, কারণ বর্ণমালায় ওটাই প্রথম। multimap-এ একটা key একাধিকবার থাকতে পারে।

Compiler-এ চালাও

Example 11: unordered_set আর unordered_map, কোনো ক্রম নেই, গড়ে সবচেয়ে দ্রুত

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>

int main()
{
    std::unordered_set<int> seen = {30, 10, 20};
    std::unordered_map<std::string, int> stock = {{"tea", 30}, {"bun", 10}};
    std::cout << "unordered_set:";
    for (int x : seen) std::cout << ' ' << x;
    std::cout << " | is 10 seen? " << seen.count(10);
    std::cout << " | buns in stock: " << stock["bun"] << '\n';
}

unordered_set: 20 10 30 | is 10 seen? 1 | buns in stock: 10

ওর প্রশ্ন: set আর map-এরটাই, গড়ে আরো দ্রুত, যখন element-গুলো কখনো ক্রমে লাগে না। এরা যে ক্রমে ছাপে, সেটা আসে hashing থেকে, তোমার কাছ থেকে না, sort থেকেও না। অন্য compiler-এর library হয়তো অন্য ক্রমে ছাপবে, তাই এই ক্রমের উপর কখনো ভরসা কোরো না।

Compiler-এ চালাও

খরচের table

এই track-এ খরচ লেখা হয় big-O notation-এ, যেখানে n হলো container-এ কয়টা element আছে। আপাতত এর তিনটা জানলেই চলবে, নিচে সোজা ভাষায় বলা হলো।

O(1), constant: n বাড়লেও খরচ বাড়ে না। 10টা element-এ এক ধাপ, এক কোটি element-এও এক ধাপ।
O(log n), logarithmic: খরচ বাড়ে ধীরে। n দ্বিগুণ হলে মোটামুটি এক ধাপ বাড়ে, তাই দশ লাখ element-এ লাগে প্রায় 20 ধাপ।
O(n), linear: n যত বাড়ে, খরচও তত বাড়ে। দশ গুণ element, দশ গুণ কাজ।

ছবি 1। 1 থেকে 1,000,000 element পর্যন্ত তিনটা খরচ। তিনটাকেই এক ছবিতে ধরাতে দুইটা অক্ষই দশের গুণে টেনে লম্বা করা হয়েছে। দশ লাখ element-এ O(log n) প্রায় 20 ধাপ, আর O(n) দশ লাখ।

এবার table-টা। একটা সারি এভাবে পড়ো: "এই container-কে এই প্রশ্ন করলে খরচ এতটা"। একটা dash (-) মানে container-টা ওই কাজটা দেয়ই না। শেষ তিনটা সারিতে "যোগ" করার কোনো শেষ বা সামনে নেই। একটা element যায় ওর মান যেখানে বলে সেখানে, তাই যোগ করার খরচ বসানো হয়েছে প্রথম column-এ। Amortised মানে "অনেকবার call করলে গড়ে"; Lesson 5 এটা বুঝিয়ে বলবে।

Container	শেষে যোগ	সামনে যোগ	মাঝে যোগ	একটা মান খোঁজা	i নম্বর element	সাজানো ক্রমে পুরোটা ঘোরা
`vector`, `string`	O(1) amortised	O(n)	O(n)	O(n)	O(1)	না
`array`	-	-	-	O(n)	O(1)	না
`deque`	O(1)	O(1)	O(n)	O(n)	O(1)	না
`list`	O(1)	O(1)	O(1), যেখানে দাঁড়িয়ে আছ	O(n)	O(n)	না
`stack`	O(1), শুধু top-এ	-	-	-	-	না
`queue`	O(1)	-	-	-	-	না
`priority_queue`	O(log n), নিজের জায়গায় গিয়ে বসে	-	-	শুধু সবচেয়ে বড়টা, O(1)	-	না
`set`, `map` আর ওদের `multi` রূপ	O(log n), সাজানো জায়গায় গিয়ে বসে	-	-	O(log n)	-	হ্যাঁ, সবগুলোর জন্য O(n)
`unordered_set`, `unordered_map`	গড়ে O(1)	-	-	গড়ে O(1)	-	না

Table-এর দুইটা লাইন আরেকবার দেখার মতো। list মাঝখানে O(1)-এ যোগ করে, কিন্তু শুধু তখনই, যখন তুমি ওখানে দাঁড়িয়ে আছ; জায়গাটা পর্যন্ত হেঁটে যেতে লাগে O(n)। আর unordered container-গুলোর "গড়ে" কথাটা একটা সত্যিকারের শর্ত: খারাপ data পেলে ওদের O(1) হয়ে যায় O(n)। সেই data দেখতে কেমন, Module 10 দেখাবে।

তাই "কোনটা সবচেয়ে দ্রুত?" প্রশ্নের কোনো উত্তর নেই। কিন্তু "key দিয়ে খোঁজায় সবচেয়ে দ্রুত, সাজানো ক্রমে?" প্রশ্নের একটা উত্তর আছে: map। Amara-র পুরো কথাটা এটাই।

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

Linux-এর CFS scheduler. Kernel 2.6.23 থেকে 6.5 পর্যন্ত scheduler চলার জন্য তৈরি task-গুলো একটা red-black tree-তে রাখত, কে কতটা CPU সময় খরচ করেছে সেই ক্রমে। GCC-র library ঠিক এই balanced tree-র উপরেই std::set আর std::map বানায়।
Redis sorted set. Game-এর leaderboard বানানোর চেনা উপায়। এরা member-দের score অনুযায়ী সাজিয়ে রাখে, আবার নাম দিয়ে একজন member-কে দ্রুত খুঁজেও দেয়। এই দুইটা প্রশ্নের উত্তরই দেয় একটা map, আর Redis এগুলোর জন্য ব্যবহার করে একটা skip list আর একটা hash table।
Hunspell. LibreOffice আর Firefox যে spell checker ব্যবহার করে, সেটা নিজের dictionary একটা hash table-এ load করে। "এই শব্দটা কি dictionary-তে আছে?", এটাই unordered_set-এর প্রশ্ন, আর তুমি যত শব্দ টাইপ করো, প্রতিটার জন্য একবার করে এটা জিজ্ঞেস করা হয়।
Emacs আর VS Code. Text editor সারাক্ষণ লেখার মাঝখানে কিছু ঢোকায়, আর ঠিক এই একটা কাজেই সাধারণ vector ধীর। Emacs রাখে একটা gap buffer, আর VS Code একটা piece tree, দুইটাই বানানো ওই ঢোকানোটা সস্তা করার জন্য।

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

১. যে container-এ জায়গার নম্বর নেই, সেখানে index দিয়ে ঢোকা।

std::stack<int> s;
s.push(1);
std::cout << s[0] << "\n";

GCC 12 বলে error: no match for 'operator[]' (operand types are 'std::stack<int>' and 'int')। Stack শুধু ওর top দেখায়, s.top() দিয়ে। list, set আর queue-এর বেলাতেও একই message আসে। i নম্বর জায়গা লাগলে তোমার লাগবে vector, deque বা array।

২. Unordered container সাজানো অবস্থায় বেরোবে, এটা আশা করা।

Example 11-এ ঢোকানো হয়েছিল 30, 10, 20, আর ছাপা হলো 20 10 30। এই ক্রমটা তোমারও না, সাজানোও না, আর container বড় হলে এটা বদলেও যেতে পারে। Output যদি ক্রমে লাগেই, set বা map ব্যবহার করো, নয়তো element-গুলো একটা vector-এ কপি করে sort করো।

৩. শুধু গতি দেখে বাছা।

Kenji একটা leaderboard বানায় unordered_map দিয়ে, কারণ ওটা "সবচেয়ে দ্রুত"। তারপর দেখে, প্রতিটা game-এর পর তাকে সেরা দশজনকে ক্রম অনুযায়ী ছাপাতে হবে। দ্রুত খোঁজা তার কোনো কাজে আসে না, আর প্রতিবার পুরো board sort করতে হয়। Table যেমন করে, তুমিও প্রশ্ন থেকে শুরু করো, container নিজেই বাছাই হয়ে যাবে।

মাথা খাটাও

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

একটা text editor-এর Undo button।
একটাই printer, আর তার জন্য অপেক্ষায় থাকা print job-গুলো।
হাসপাতালের emergency ঠিক করছে, এরপর কাকে দেখা হবে।
এক কোটি username-এর মধ্যে একটা নাম আগেই নেওয়া হয়ে গেছে কি না দেখা, কোনো ক্রমের দরকার নেই।
এমন একটা dictionary, যেটা A থেকে Z পর্যন্ত প্রতিটা শব্দ তার মানে সহ ছাপে।

প্রতিটা কাজের জন্য জিজ্ঞেস করো, এরপর তার কোন জিনিসটা লাগবে: সবচেয়ে নতুনটা, সবচেয়ে পুরনোটা, সবচেয়ে বড়টা, নাম ধরে একটা, নাকি সবগুলো ক্রমে।

অনুশীলন ১সহজ

Example 1, 6, 7, 8 আর 9-এর output দেখো। পাঁচটা container-কেই 30, 10, 20 ঠিক এই ক্রমে দেওয়া হয়েছিল। প্রতিটার জন্য এক বাক্যে লেখো, সংখ্যাগুলো কেন ওই ক্রমে বেরোল।

নিজে যাচাই করো। পাঁচটা আলাদা কারণ পাওয়ার কথা: যে ক্রমে যোগ করেছ, সবচেয়ে নতুনটা আগে, সবচেয়ে পুরনোটা আগে, সবচেয়ে বড়টা আগে, আর সাজানো।

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

Example 10 Playground-এ খোলো। Egg-এর লাইনের পরে চতুর্থ একটা item যোগ করো: price["apple"] = 50;। চালানোর আগে লিখে রাখো, কোন লাইনটা আশা করছ।

নিয়ম। তারপর std::map বদলে std::unordered_map করো, আর #include <unordered_map> যোগ করো। আবার চালাও, আর ক্রমটা মিলিয়ে দেখো।

নিজে যাচাই করো। Map-এ apple=50 সবার আগে আসে। Unordered map-এ ক্রমটা hashing যা দেয় তাই, আর সেটা বর্ণমালার ক্রম না।

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

একটা web browser-এ একটা Back button আর একটা Forward button আছে। নতুন page-এ গেলে Forward-এর history মুছে যায়। কোন container, বা কোন কোন container ব্যবহার করবে বাছো, আর table দেখিয়ে এক অনুচ্ছেদে তোমার পছন্দটা বুঝিয়ে বলো।

নিয়ম। Back চাপলে, Forward চাপলে আর নতুন page-এ গেলে প্রতিটা container-এর কী হয়, সেটা বলো।

নিজে যাচাই করো। একটা ভালো উত্তর হলো দুইটা stack: Back একটা থেকে pop করে অন্যটায় push করে, আর নতুন page Forward stack-টা খালি করে দেয়। একটা position সহ একটা deque-ও চলে। যেভাবেই করো, প্রতিটা কাজ O(1)।

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

এই table কি মুখস্থ করতে হবে?

না। Module 10 শেষ হতে হতে তুমি প্রতিটা সারি জানবে, কারণ তখন বুঝবে প্রতিটা container কীভাবে বানানো। আপাতত page-টা খোলা রাখো, আর বাছার সময় এটা দেখে নাও।
stack আর queue-কে container না বলে adaptor বলে কেন?

কারণ ওরা নিজেরা কিছুই ধরে রাখে না। Default হিসেবে একটা stack-এর নিচে আসলে একটা deque থাকে, top ছাড়া বাকি সব কাজ লুকিয়ে রাখা। নিচে কী থাকবে সেটা কীভাবে বাছবে, Module 6 দেখাবে।
unordered_map যদি O(1) আর map O(log n) হয়, তাহলে map কেন ব্যবহার করব?

কারণ map ওর key-গুলো সাজিয়ে রাখে, আর কিছু কাজে ওই ক্রমটা লাগে। তাছাড়া দশ লাখ key-এর জন্য O(log n) মানে প্রায় 20 ধাপ, যেটা এমনিতেই খুব দ্রুত। আর table যেমন বলে, unordered map-এর O(1) শুধু একটা গড়।
std::string কি সত্যিই একটা container?

এটা container-এর মতোই আচরণ করে। Character-গুলো এক সারিতে ধরে রাখে, এর begin() আর end() আছে, আর প্রতিটা algorithm ওটার উপর চলে। এটা আলাদাভাবে ডিজাইন করা হয়েছিল, পরে STL পরিবারে যোগ দিয়েছে। এজন্যই ওটার কাছে লেখা নিয়ে কাজের বাড়তি কিছু function আছে, যেগুলো vector-এর নেই।

মূল কথা

Sequence container তোমার ক্রম রাখে; adaptor শুধু এক বা দুই মাথা খোলা রাখে; associative container মান দেখে সাজায়।
প্রতিটা container একটা প্রশ্নের দ্রুত উত্তর দেওয়ার জন্য বানানো, আর সব কাজে সবচেয়ে দ্রুত এমন কোনো container নেই।
O(1) n-এর সঙ্গে বাড়ে না, O(log n) ধীরে বাড়ে, O(n) n-এর সঙ্গে সমান তালে বাড়ে।
ক্রম রাখা container (set, map) element সাজিয়ে রাখে; unordered-গুলো গড়ে দ্রুত, কিন্তু ভরসা করার মতো কোনো ক্রম রাখে না।
আগে প্রশ্নটা বাছো, তারপর container।

এরপর দেখবে সেই সুতোটা, যেটা এই সব container-কে algorithm-এর সঙ্গে বেঁধে রাখে: iterator, আর সে কীভাবে চলে।

lesson ৩ শেষ

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

পরেরটা: iterator আর algorithm: টুকরোগুলো জোড়া লাগে কীভাবে

পরের lesson