sequence container — vector, deque, list কখন কোনটা

১ · Container মানে সংরক্ষণের একটি কৌশল

পর্ব ২৮ আর ২৯-এ আপনি template লিখতে শিখেছেন — একবার কোড লিখে যেকোনো টাইপে চালানো। এবার দেখবেন C++-এর standard library সেই ক্ষমতা দিয়ে কী বানিয়েছে। মডিউল ৫-এর বাকি পর্বগুলোর কেন্দ্রে আছে STL: তৈরি করা data structure আর algorithm-এর একটি বিশাল বাক্স, যা প্রায় প্রতিটি C++ প্রোগ্রামে ব্যবহার হয়।

একটি প্রশ্ন দিয়ে শুরু করি। একটি বাস কাউন্টারের যাত্রীদের তালিকা, একটি গানের playlist, একটি টেক্সট এডিটরের undo-ইতিহাস আর হাসপাতালের জরুরি বিভাগের রোগীর তালিকা — চারটিই “অনেকগুলো জিনিস একটার পর একটা”। তাহলে চারটিতেই কি একই ধরনের তালিকা চলবে? না। কারণ চারটিতে সবচেয়ে বেশি যে কাজটি হয়, তা আলাদা:

STL-এর তিন স্তম্ভ

STL-এর নকশার মূল চাল হলো তিনটি জিনিসকে আলাদা রাখা:

এই ভাগের লাভটা হিসাব করে দেখুন। ধরুন ৫টি container আর ৫০টি algorithm আছে। প্রতিটি জোড়ার জন্য আলাদা কোড লিখলে লাগত ৫ × ৫০ = ২৫০টি সংস্করণ। কিন্তু মাঝখানে iterator নামের একটি সাধারণ “সংযোগের ভাষা” থাকায় লাগে ৫ + ৫০টি। নতুন একটি container বানালে, iterator দিলেই সব algorithm তার ওপর চলে। এই চিন্তার নাম generic programming, আর এর হাতিয়ার আপনার চেনা template.

২ · std::vector — কেন সে ডিফল্ট

পর্ব ১৩-এ আপনি std::vector বিস্তারিত দেখেছেন, তাই এখানে শুধু এক অনুচ্ছেদের স্মরণ। vector উপাদান রাখে heap-এর একটি ফাঁকহীন ব্লকে — contiguous memory. ভেতরে তিনটি তথ্য: ব্লকের শুরু, কয়টি উপাদান আছে (size), আর কয়টির জায়গা আছে (capacity). শেষে যোগ করা গড়ে ধ্রুবক সময়ের কাজ — amortized O(1); জায়গা ফুরোলে বড় ব্লকে reallocation হয়, আর তখন পুরোনো সব iterator, pointer ও reference অচল হয়ে যায়। সূচক দিয়ে যেকোনো উপাদানে এক লাফে যাওয়া যায় — random access. কিন্তু মাঝখানে ঢোকালে বা মুছলে পেছনের সবাইকে সরতে হয়। আর আকার compile-এর সময়ই নির্দিষ্ট হলে std::array — একই ফাঁকহীন সারি, শুধু heap ছাড়া আর আকার বদলানোর ক্ষমতা ছাড়া।

এবার আসল প্রশ্ন: বইয়ে লেখা থাকে, linked list-এ মাঝখানে ঢোকানো O(1) আর vector-এ O(n). তাহলে বিশেষজ্ঞরা কেন বলেন “সন্দেহ হলে vector”? উত্তর লুকিয়ে আছে CPU কীভাবে মেমরি পড়ে, তার মধ্যে। CPU মেমরি থেকে একবারে একটি বাইট আনে না, আনে একটি ছোট টুকরো — cache line, সাধারণ কম্পিউটারে ৬৪ বাইট। নিচের stepper-এ একই আটটি সংখ্যা দুই রকম container-এ রেখে হেঁটে দেখুন।

ঠিকানা: 1000 1004 1008 1012 ...
       [10 ][20 ][30 ][40 ]
       [50 ][60 ][70 ][80 ]
<--- একটি 64-বাইট cache line --->
৮টি int = ৩২ বাইট, বাড়তি কিছু নেই

0x7a10 [prev|next|10] --> 0x3c40
0x3c40 [prev|next|20] --> 0x9f08
0x9f08 [prev|next|30] --> 0x1b70
0x1b70 [prev|next|40] --> ...
প্রতিটি node আলাদা জায়গায়,
প্রতিটিতে দুটি pointer বাড়তি

                vector    list
মেমরি (মোটামুটি)  32 B   >= 192 B
cache line আনা    1       up to 8
পরের ঠিকানা      জানা     আগে node পড়তে হয়
prefetch         হয়       প্রায় হয় না

৩ · std::deque — দুই মাথাতেই দ্রুত

বাস টার্মিনালের টিকিট কাউন্টারে লাইন। নতুন যাত্রী আসে পেছনে, টিকিট পেয়ে চলে যান সামনের জন। মাঝে মাঝে একজন বয়স্ক যাত্রী বা প্রতিবন্ধী যাত্রীকে সরাসরি সামনে দাঁড় করানো হয়। অর্থাৎ দুই মাথাতেই যোগ আর মোছা। vector-এ সামনে যোগ বা সামনে থেকে মোছা মানে বাকি সবাইকে এক ঘর সরানো — O(n). লাইনে হাজার জন থাকলে প্রতিবার হাজারটি সরানো।

std::deque (উচ্চারণ “ডেক”, পুরো নাম double-ended queue) এই সমস্যার জন্যই। সে উপাদান রাখে একটি বড় ব্লকে নয়, কয়েকটি সমান মাপের টুকরোয় (chunk). আর একটি ছোট সূচিপত্র — যাকে লাইব্রেরিগুলো “map” বলে — মনে রাখে কোন টুকরো কোথায়। সামনে জায়গা লাগলে সামনে নতুন টুকরো, পেছনে লাগলে পেছনে। পুরোনো উপাদান কখনো সরে না। নিচের stepper-এ টুকরোর মাপ বোঝার সুবিধার জন্য ৪টি int ধরা হয়েছে; আসল লাইব্রেরিতে টুকরো বড় (GCC-র লাইব্রেরিতে ৫১২ বাইট, অর্থাৎ ১২৮টি int).

1std::deque<int> d;2d.push_back(1); d.push_back(2);3d.push_back(3); d.push_back(4);4d.push_front(0); d.push_front(-1);5d.push_front(-2);6// aro 8ti push_front

শেষ ধাপটি deque-এর একটি সূক্ষ্ম নিয়ম, যা পরীক্ষায় আর ইন্টারভিউতে প্রায়ই আসে: deque-এর দুই মাথায় যোগ করলে সব iterator অচল হতে পারে, কিন্তু উপাদানের reference আর pointer ঠিক থাকে। আর মাঝখানে ঢোকালে বা মুছলে দুটোই অচল হয়। vector-এ reallocation-এ দুটোই যায়, list-এ কোনোটাই যায় না। কেন এমন — ভাবনার প্রশ্ন ০৩-এ বিস্তারিত।

৪ · std::list আর std::forward_list — শিকলের মতো জোড়া

std::list হলো একটি doubly linked list: প্রতিটি node নিজের মান রাখে, আর রাখে আগের ও পরের node-এর ঠিকানা। একে বলে node-based container. এই নকশা থেকেই তার তিনটি শক্তি আর তিনটি দুর্বলতা আসে।

Playlist সম্পাদনা — splice-এর আসল ব্যবহার

একটি গানের অ্যাপে আপনার playlist-এ ২০০টি গান। আপনি “বৃষ্টির গান” নামের ৩০টি গানের একটি অংশ টেনে playlist-এর শুরুতে নিয়ে যেতে চান। vector হলে: ৩০টি গান কপি বা move, তার আগের সব গান পেছনে সরানো। list-এ splice শুধু কয়েকটি pointer বদলায় — গানগুলো মেমরিতে যেখানে ছিল সেখানেই থাকে। আর যে স্ক্রিন একটি গানের দিকে iterator ধরে রেখেছিল (“এখন বাজছে”), সেটিও ঠিক থাকে।

std::list<std::string> playlist{"A", "B", "R1", "R2", "C"};
auto first = std::next(playlist.begin(), 2);   // "R1"
auto last  = std::next(first, 2);              // "C" (baad)
// [first, last) ongshoti shuru-te: kono gaan copy hoy na
playlist.splice(playlist.begin(), playlist, first, last);
// ekhon: R1 R2 A B C

একই list-এর ভেতরে splice সবসময় ধ্রুবক সময়ের কাজ। অন্য একটি list থেকে একটি অংশ আনলে লাইব্রেরিকে অংশটির দৈর্ঘ্য গুনতে হয় (কারণ C++11 থেকে size() O(1) হতে হবে), তাই সেটি অংশের দৈর্ঘ্যের সমানুপাতিক। কিন্তু খেয়াল করুন: first খুঁজতে আমরা শুরু থেকে হেঁটেছি — list-এ “জায়গাটি” খুঁজে পাওয়াই O(n). O(1) যোগ-মোছার সুবিধা তখনই সত্যি, যখন iterator আগে থেকেই হাতে আছে।

আরেকটি খুঁটিনাটি: std::sort random access চায়, তাই list-এ চলে না। list-এর নিজের l.sort() member আছে, যা node-গুলোর pointer বদলে সাজায় — উপাদান সরায় না। remove, unique, merge, reverse-ও list-এর নিজস্ব member হিসেবে আছে, একই কারণে।

std::forward_list — আরও হালকা শিকল

C++11-এ যোগ হয় std::forward_list: প্রতিটি node শুধু পরেরটির ঠিকানা রাখে। এক pointer কম, তাই মেমরি কম — কিন্তু পেছনে হাঁটা যায় না। নিজের আগের node জানে না বলে তার যোগ-মোছার ফাংশনের নাম insert_after আর erase_after: “এই node-এর পরে ঢোকাও”। আর তার size() member-ই নেই — standard ইচ্ছা করে রাখেনি, যাতে একটি গণনার সংখ্যা রাখার বাড়তি খরচও না লাগে। এর লক্ষ্য একটাই: হাতে লেখা C-ধাঁচের singly linked list-এর সমান খরচে নিরাপদ একটি container.

৫ · Container adaptor — stack, queue, priority_queue

এবার তিনটি পরিচিত নাম, যারা আসলে container নয়। এরা container adaptor: অন্য একটি container-এর ওপর বসানো একটি আবরণ, যা শুধু কয়েকটি কাজ করতে দেয় আর বাকিগুলো লুকিয়ে রাখে। উদ্দেশ্য — কোডের অর্থ স্পষ্ট করা আর ভুল ব্যবহার আটকানো।

তিনটিরই কোনো iterator নেই — ইচ্ছা করে। stack-এর মাঝখানে উঁকি দেওয়া মানেই সেটি আর stack নয়। আর খেয়াল করুন, pop() কিছু ফেরত দেয় না (void). ওপরের মান চাইলে আগে top(), তারপর pop(). দুটি আলাদা কেন — পরীক্ষার বাক্সে আর ভাবনার প্রশ্ন ০৫-এ উত্তর আছে। খালি stack বা queue-তে top(), front() বা pop() ডাকা undefined behavior — আগে empty() দেখুন।

নিচের প্রোগ্রামে বাস কাউন্টারের লাইন (deque, কারণ বয়স্ক যাত্রীকে সামনে আনতে হবে) আর একটি এডিটরের undo (stack) একসাথে দেখুন:

#include <deque>
#include <print>
#include <stack>
#include <string>

int main() {
    std::deque<std::string> line{"Rahim", "Karim"};
    line.push_back("Salma");            // shobar pichone
    line.push_front("Elder-Ali");       // boyoshko jatri shamne
    std::println("next = {}, waiting = {}", line.front(), line.size());
    line.pop_front();                   // ticket dewa holo
    std::println("next = {}, last = {}", line.front(), line.back());

    std::stack<std::string> undo;       // editor-er undo itihash
    for (auto op : {"type A", "type B", "bold"}) undo.push(op);
    std::println("undo -> {}", undo.top());
    undo.pop();
    std::println("undo -> {}, left = {}", undo.top(), undo.size());
}

priority_queue — জরুরি বিভাগের হিসাব

ঢাকা মেডিকেলের জরুরি বিভাগে রোগী আসেন যে ক্রমে, চিকিৎসা হয় সেই ক্রমে নয় — হয় অবস্থা কত গুরুতর, সেই অনুযায়ী। একে বলে triage. সফটওয়্যারে একই কাজ: অপারেটিং সিস্টেমের task scheduler, নেটওয়ার্কের জরুরি প্যাকেট, Dijkstra-র shortest path algorithm. প্রতিবার দরকার “এখন সবচেয়ে গুরুত্বপূর্ণটি কোনটি?” — আর নতুন রোগী আসছেন অবিরাম।

প্রতিবার পুরো তালিকা sort করলে খরচ অনেক। priority_queue ভেতরে রাখে একটি binary heap: vector-এর ভেতরে এমনভাবে সাজানো একটি গাছ, যেখানে প্রতিটি parent তার সন্তানদের চেয়ে বড়। সূচক i-এর সন্তান 2i+1 আর 2i+2, parent (i-1)/2 — pointer লাগে না, সূচকের হিসাবই যথেষ্ট। (এই heap আর মেমরির heap বা free store সম্পূর্ণ আলাদা জিনিস, নামটা কাকতালীয়।) গাছের উচ্চতা log n, তাই যোগ আর সরানো O(log n), আর সবচেয়ে বড়টি দেখা O(1). নিচে চার রোগীর গুরুত্বের মাত্রা (বড় সংখ্যা = বেশি গুরুতর) heap-এ ঢোকানো আর বের করা দেখুন:

1std::priority_queue<int> er;2er.push(2);3er.push(5);4er.push(1);5er.push(4);6er.pop();7er.top();   // ?

std::priority_queue<int> maxq;      // top = shobcheye boro
std::priority_queue<int, std::vector<int>,
                    std::greater<int>> minq;   // top = shobcheye choto

৬ · যোগ আর মোছা — emplace_back, erase-remove আর std::erase_if

push_back বনাম emplace_back

push_back(x) একটি তৈরি বস্তু নেয় আর সেটি container-এ কপি বা move করে। emplace_back(args...) constructor-এর argument নেয় আর বস্তুটি সরাসরি container-এর ঘরেই তৈরি করে। deque আর list-এ emplace_front, আর সব sequence container-এ emplace(pos, args...)-ও আছে।

struct Ticket { std::string name; int seat; };
std::vector<Ticket> t;
t.push_back(Ticket{"Rahim", 12});   // agey ekta Ticket, tarpor move
t.emplace_back("Karim", 14);        // ghorer moddhei toiri (C++20 theke
                                    // aggregate-eo chole)

std::vector<std::vector<int>> g;
g.push_back(1000000);     // compile hoy na: bhul dhora porlo
g.emplace_back(1000000);  // chupchap 10 lakh 0-er vector!

দুটি কথা মনে রাখুন। প্রথমত, হাতে আগে থেকেই একটি বস্তু থাকলে দুটোর মধ্যে কোনো পার্থক্য নেই — v.push_back(s) আর v.emplace_back(s) একই কাজ করে। দ্বিতীয়ত, emplace_back explicit constructor-ও চুপচাপ ডেকে ফেলে। ওপরের শেষ লাইনে push_back(1000000) compile হয় না (int থেকে vector-এ গোপন রূপান্তর নিষেধ), কিন্তু emplace_back(1000000) দশ লাখ শূন্যের একটি vector বানিয়ে ফেলে — সম্ভবত যা আপনি চাননি। তাই পেশাদার নিয়ম: নতুন বস্তু argument থেকে বানাতে emplace_back, তৈরি বস্তু রাখতে push_back; “emplace সবসময় দ্রুত” বিশ্বাস করবেন না।

শর্ত মেনে অনেকগুলো মোছা — লুপে erase কেন ভুল

ধরুন কাউন্টারের লাইন থেকে যাঁদের অপেক্ষা ৪০ মিনিটের বেশি, তাঁদের অন্য কাউন্টারে পাঠাতে হবে — অর্থাৎ vector থেকে মুছতে হবে। সহজ চিন্তা: লুপ চালান, শর্ত মিললে v.erase(it). কিন্তু vector-এ প্রতিটি erase তার পেছনের সবাইকে এক ঘর সামনে সরায় — O(n). n উপাদানের অর্ধেক মুছলে মোট কাজ প্রায় n²/4 সরানো। এক লাখ উপাদানে সেটা প্রায় আড়াইশো কোটি সরানো! তার ওপর erase-এর পরে iterator অচল, তাই সাবধানে না লিখলে বাগ।

STL-এর সমাধান এক পাসের একটি কৌশল — erase-remove idiom. std::remove_if আসলে কিছু মোছে না: সে যাদের রাখতে হবে, তাদের ক্রম ঠিক রেখে সামনে সরিয়ে আনে, আর “নতুন শেষ” কোথায় তা ফেরত দেয়। তারপর container-এর erase পেছনের অংশটি এক কোপে কেটে ফেলে। ধাপে ধাপে দেখুন:

1auto it = std::remove_if(2    v.begin(), v.end(), tooLong);3v.erase(it, v.end());4// C++20: ek line-e5auto n = std::erase_if(v, tooLong);

নিচের প্রোগ্রামে জরুরি বিভাগের ক্রম দুইভাবে (ডিফল্ট আর std::greater) আর অপেক্ষার তালিকা থেকে std::erase_if দিয়ে মোছা একসাথে দেখুন। std::println C++23 থেকে পুরো vector সরাসরি ছাপতে পারে:

#include <functional>
#include <print>
#include <queue>
#include <vector>

int main() {
    std::vector<int> severity{2, 5, 1, 4};      // ER-e asha rogi
    std::priority_queue<int> maxq(severity.begin(), severity.end());
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        minq(severity.begin(), severity.end());
    for (; !maxq.empty(); maxq.pop()) std::print("{} ", maxq.top());
    std::println("<- default (max first)");
    for (; !minq.empty(); minq.pop()) std::print("{} ", minq.top());
    std::println("<- std::greater (min first)");

    std::vector<int> wait{12, 45, 7, 60, 30};   // minute
    auto removed = std::erase_if(wait, [](int m) { return m > 40; });
    std::println("removed {}, left {}", removed, wait);
}

৭ · জটিলতার টেবিল — আর তার সীমা

এবার সব একসাথে। নিচের টেবিল Big-O-তে লেখা: n উপাদান থাকলে কাজটি কীভাবে বাড়ে। “—” মানে container সেই কাজের member দেয়ই না।

এই টেবিল পড়ার সময় তিনটি সতর্কতা মাথায় রাখুন।

• “iterator হাতে আছে” শর্তটাই সব। list-এর O(1) যোগ চমৎকার — কিন্তু বাস্তবে সাধারণত জায়গাটি আগে খুঁজতে হয়, আর list-এ খোঁজা O(n), তাও প্রতিটি ধাপে cache miss সহ। vector-এও খোঁজা O(n), কিন্তু ফাঁকহীন মেমরিতে সেই হাঁটা অনেক গুণ দ্রুত, আর সরানোর কাজটাও (memmove-এর মতো) একটানা মেমরিতে হয়।
• Big-O ধ্রুবক গুণক লুকায়। O(n)-এর একটি অ্যালগরিদম যদি প্রতি ধাপে ১ ন্যানোসেকেন্ড নেয় আর O(1)-এর আরেকটি প্রতিবার ১০০ ন্যানোসেকেন্ডের একটি cache miss খায়, তাহলে ছোট-মাঝারি n-এ প্রথমটিই জিতবে। Big-O বলে n অসীমের দিকে গেলে কী হয়; আপনার প্রোগ্রামের n অসীম নয়।
• মেপে দেখুন। Bjarne Stroustrup ২০১২ সালের GoingNative সম্মেলনের বক্তৃতায় একটি পরীক্ষা দেখান: এলোমেলো সংখ্যা সাজানো ক্রমে ঢোকানো, তারপর এলোমেলো জায়গা থেকে মোছা — অর্থাৎ ঠিক সেই কাজ, যেখানে বইয়ের হিসাবে list-এর জেতার কথা। তাঁর মাপা সব আকারে vector অনেক এগিয়ে ছিল। ব্যাখ্যা উপরের দুটি পয়েন্টেই। তবে এটিও একটি মাপ, চিরন্তন নিয়ম নয় — বড় বস্তু, ভারী কপি বা বিশেষ ব্যবহারের ধরনে ফল বদলাতে পারে। তাই আসল নিয়ম: নিজের ডেটায়, optimization চালু করে, মেপে দেখুন (পর্ব ৪৯-এ মাপার পদ্ধতি দেখবেন)।

৮ · কোনটি বেছে নেবেন — সিদ্ধান্তের পথ, আর std::span

সব মিলিয়ে একটি সহজ সিদ্ধান্তের পথ। ওপর থেকে নিচে পড়ুন, প্রথম যে প্রশ্নের উত্তর “হ্যাঁ”, সেখানেই থামুন:

খেয়াল করুন, ৫ নম্বর প্রশ্নে কতগুলো শর্ত। ঠিকানা স্থির রাখার দরকার হলেও অনেক সময় vector-এ সূচক রাখা, বা std::vector<std::unique_ptr<T>> (বস্তু heap-এ স্থির, vector-এ শুধু pointer) list-এর চেয়ে ভালো কাজ করে। আর মাঝখানে অল্প কয়েকবার ঢোকানো-মোছা vector-এর জন্য কোনো সমস্যাই নয়।

std::span — যেকোনো সারির দিকে একটি জানালা

একটি ফাংশন লিখছেন, যা কিছু সংখ্যার গড় বের করবে। ডাকতে পারে কেউ vector দিয়ে, কেউ std::array দিয়ে, কেউ C-array দিয়ে। প্রতিটির জন্য আলাদা overload? পর্ব ১৪-এ std::string_view একই সমস্যা লেখার জন্য সমাধান করেছিল — মালিক না হয়ে শুধু “শুরুর ঠিকানা আর দৈর্ঘ্য” দেখা। C++20-এর std::span একই কাজ করে যেকোনো ফাঁকহীন সারির জন্য — একটি non-owning view:

double average(std::span<const int> xs);   // vector, array, C-array - shobai chole

std::vector<int> a{1, 2, 3};
std::array<int, 2> b{4, 5};
average(a);  average(b);

লক্ষ করুন “ফাঁকহীন” শব্দটি: span-এর ভেতরে শুধু একটি pointer আর একটি সংখ্যা, তাই সে deque বা list দেখাতে পারে না — তাদের উপাদান এক সারিতে নেই। এটাও vector-এর পক্ষে আরেকটি যুক্তি: ফাঁকহীন সারি C API, span, SIMD আর GPU — সবার সাথে সহজে মেলে। span-এর খুঁটিনাটি আর তার dangling-এর বিপদ পর্ব ১৩-এ দেখেছেন; iterator আর range দিয়ে আরও সাধারণ “যেকোনো container নেওয়া” ফাংশন লিখবেন পর্ব ৩২ ও ৩৫-এ।

৯ · AI-এর যুগে — না মেপে list, লুপে erase আর উল্টো heap

AI টুলগুলো container বাছাইয়ে প্রায়ই পাঠ্যবইয়ের Big-O মুখস্থ করা ছাত্রের মতো আচরণ করে: “মাঝখানে ঢোকাতে হবে? তাহলে linked list.” তাদের কোড compile হয়, ছোট ইনপুটে ঠিক উত্তরও দেয় — সমস্যা ধরা পড়ে এক লাখ উপাদানে, যখন প্রোগ্রাম হঠাৎ কয়েক সেকেন্ড থেমে থাকে। সবচেয়ে সাধারণ ভুলগুলো:

AI-এর লেখা container-কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি container বাছাইয়ের পেছনে “সবচেয়ে বেশি যে কাজ” স্পষ্ট — না থাকলে vector
• std::list থাকলে তার কারণ লেখা (ঠিকানা স্থির, splice) আর অন্তত একবার মাপা হয়েছে
• লুপের ভেতরে কোনো erase নেই; শর্ত মেনে মোছা std::erase_if দিয়ে
• priority_queue-এর ক্রম হাতে একটি উদাহরণে মিলিয়ে দেখেছি — ছোট আগে চাইলে std::greater
• push, insert বা erase-এর পরে পুরোনো iterator ব্যবহার হয়নি; deque-এ reference আর iterator-এর পার্থক্য মাথায় রেখেছি
• খালি container-এ top(), front(), back() বা pop() নেই; edge case (খালি লাইন, একজন যাত্রী) চালিয়ে দেখেছি