C++ STL আর Python-এর কালেকশন — তৈরি ডেটা স্ট্রাকচার

১ · তৈরি কালেকশন কেন — চাকা নতুন করে বানাবেন না

আগের পর্বগুলোতে আমরা array, linked list, stack আর queue নিজের হাতে বানিয়েছি। সেটি জরুরি ছিল — ভেতরের কলকবজা না বুঝলে কোন কাজ কেন ধীর, তা বোঝা যায় না। কিন্তু বাস্তবে প্রতিটি প্রোগ্রামে নিজের linked list লেখা মানে প্রতিবার রান্নার আগে নিজের হাতে মসলা পেষা। বাজারে ভালো মানের গুঁড়া মসলা আছে; ভালো রাঁধুনি জানেন কোন মসলা কোন রান্নায়, কতটুকু দিতে হয়। প্রোগ্রামিংয়েও তাই।

C++-এ এই “তৈরি মসলার তাক” হলো STL (Standard Template Library), আর Python-এ ভাষার ভেতরেই থাকা list, dict, set এবং collections, heapq, bisect-এর মতো মডিউল। এগুলোর প্রতিটি একটি data structure-এর পরীক্ষিত বাস্তবায়ন — লাখো প্রোগ্রামার বহু বছর ধরে ব্যবহার করেছেন, বাগ খুঁজে ঠিক করেছেন, গতি বাড়িয়েছেন। কনটেস্টে বা ইন্টারভিউতে আধা ঘণ্টায় নিজের লেখা red-black tree-র চেয়ে std::map প্রায় সবসময় বেশি নির্ভরযোগ্য।

পর্ব ০১-এ দেখেছিলেন abstract data type (ADT) আর বাস্তবায়নের পার্থক্য: ADT বলে “কী করা যায়”, বাস্তবায়ন বলে “কীভাবে”। এই পর্বের পুরো মানচিত্রটি সেই ভাগ মেনে চলে:

এর সাথে আছে তৈরি অ্যালগরিদম — sort, lower_bound, next_permutation, accumulate; Python-এ sorted, bisect, heapq.nlargest. STL-এ অ্যালগরিদম আর container-কে জোড়া দেয় iterator — একটি “আঙুল”, যা container-এর কোনো একটি ঘরের দিকে নির্দেশ করে আর পরের ঘরে সরতে পারে। iterator-এর কারণেই একই sort ফাংশন vector, deque বা সাধারণ array — সবকিছুতে চলে।

২ · Sequence container — vector, deque আর list

std::vector হলো STL-এর সবচেয়ে বেশি ব্যবহৃত container — একটি dynamic array. উপাদানগুলো মেমরিতে পাশাপাশি থাকে (পর্ব ১০), তাই v[i] পড়া O(1), আর পরপর ঘোরা CPU cache-এর জন্য অত্যন্ত দ্রুত। শেষে যোগ (push_back) সাধারণত O(1); কিন্তু জায়গা ফুরিয়ে গেলে vector বড় একটি নতুন ব্লক নেয়, পুরোনো সব উপাদান সেখানে সরায়, আর পুরোনো ব্লক ছেড়ে দেয়। নিচে দেখুন GCC-র লাইব্রেরি (libstdc++) কীভাবে ধারণক্ষমতা (capacity) দ্বিগুণ করে:

দ্বিগুণ করাই কেন? যদি প্রতিবার মাত্র ১০টি করে ঘর বাড়ানো হতো, তাহলে n টি push-এ মোট সরানো হতো প্রায় n²/20 — অর্থাৎ Θ(n²). গুণিতক হারে বাড়ালে (২ গুণ, বা Microsoft-এর লাইব্রেরির মতো ১.৫ গুণ) মোট খরচ Θ(n) থাকে। এর পূর্ণ প্রমাণ পর্ব ৬০-এ (amortized analysis). আগে থেকে আকার জানা থাকলে v.reserve(n) লিখুন — একবারেই জায়গা নেওয়া হবে, মাঝপথে কোনো সরানো নেই।

std::deque (double-ended queue, উচ্চারণ “ডেক”) দেখতে vector-এর মতো — d[i] O(1) — কিন্তু ভেতরে একটানা একটি ব্লক নয়, বরং অনেকগুলো ছোট নির্দিষ্ট-আকারের ব্লক আর সেগুলোর ঠিকানার একটি তালিকা। তাই সামনে আর পেছনে দুই দিকেই যোগ-বাদ O(1). ট্রেনের বগির মতো ভাবুন: দুই মাথাতেই নতুন বগি জোড়া যায়, পুরো ট্রেন সরাতে হয় না। দাম: প্রতিটি d[i]-এ একটি বাড়তি ঠিকানা-হিসাব, আর মেমরি পাশাপাশি না থাকায় vector-এর চেয়ে কিছুটা ধীর।

std::list হলো doubly linked list (পর্ব ১২). কোনো জায়গার iterator হাতে থাকলে সেখানে যোগ বা মুছে ফেলা O(1), আর splice দিয়ে এক list-এর অংশ আরেক list-এ O(1)-এ সরানো যায়। কিন্তু i-তম উপাদানে যেতে O(n) হাঁটতে হয়, প্রতিটি node আলাদা মেমরিতে থাকায় cache-এর সুবিধা নেই, আর প্রতি উপাদানে দুটি pointer-এর বাড়তি জায়গা লাগে। বাস্তবে তাই অনেক অভিজ্ঞ প্রোগ্রামার বলেন, “সন্দেহ হলে vector নিন” — মাঝখানে যোগ O(n) হলেও ছোট-মাঝারি n-এ পাশাপাশি মেমরির গতি প্রায়ই list-কে হারিয়ে দেয়।

আরও দুটি নাম জেনে রাখুন। std::array<int, N> হলো compile-এর সময় আকার জানা একটি সাধারণ array, যা vector-এর মতো আচরণ করে কিন্তু আকার বদলায় না। আর std::string আসলে অক্ষরের একটি vector-ই, বাড়তি কিছু ফাংশনসহ (পর্ব ১১).

৩ · Adapter — stack, queue, priority_queue আর pair/tuple

কখনো কখনো আমরা ইচ্ছা করেই ক্ষমতা কমাতে চাই। ট্রেনের টিকিটের লাইনে মাঝখান থেকে কাউকে ঢুকতে দেওয়া হয় না — নিয়মটাই লাইনের শক্তি। STL-এর container adapter ঠিক এই কাজ করে: একটি সাধারণ container (ডিফল্টে deque বা vector) নিয়ে তার ওপর শুধু কয়েকটি কাজের অনুমতি দেয়।

Stack আর queue আপনি পর্ব ১৩ ও ১৪-এ বানিয়েছেন। নতুন হলো priority queue: হাসপাতালের জরুরি বিভাগের কথা ভাবুন — যে আগে এসেছে সে নয়, যার অবস্থা সবচেয়ে গুরুতর, তাঁকে আগে দেখা হয়। ভেতরে আছে একটি heap (পর্ব ২৩): একটি array, যেখানে প্রতিটি ঘরের মান তার “সন্তান” ঘরগুলোর চেয়ে বড় বা সমান। তাই সবচেয়ে বড়টি সবসময় সামনে, আর নতুন যোগ বা সামনেরটি বাদ দিতে শুধু গাছের উচ্চতা বরাবর — O(log n) — ঠিকঠাক করতে হয়।

priority_queue<int> mx;                              // max-heap: top() = largest
priority_queue<int, vector<int>, greater<int>> mn;   // min-heap: top() = smallest
for (int x : {5, 1, 8, 3}) { mx.push(x); mn.push(x); }
// mx.top() == 8, mn.top() == 1

// pairs compare lexicographically: first, then second
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // (dist, node)
pq.push({4, 2}); pq.push({1, 7}); pq.push({1, 3});
auto [d, v] = pq.top();                              // d == 1, v == 3

pair আর tuple — ছোট দলবদ্ধ মান

pair<int, string> দুটি মান একসাথে রাখে (.first, .second), আর tuple<int, int, string> যেকোনো সংখ্যক। এদের সবচেয়ে কাজের বৈশিষ্ট্য: তুলনা হয় lexicographic ক্রমে — আগে প্রথম মান, সমান হলে দ্বিতীয়, এভাবে — অভিধানে শব্দ সাজানোর মতো। তাই vector<pair<int,int>>-এ সরাসরি sort করলে প্রথম মান ধরে, সমান হলে দ্বিতীয় মান ধরে সাজানো হয়। C++17-এর structured binding (auto [d, v] = p;) দিয়ে খুলে নেওয়াও সহজ। Python-এর tuple একইভাবে তুলনা হয়, আর এটি পরিবর্তন করা যায় না (immutable) বলে dict-এর key বা set-এর সদস্য হতে পারে — অংশ ৯-এ এর গুরুত্ব দেখবেন।

৪ · Ordered container — set, multiset, map, multimap

একটি লাইব্রেরির তাক ভাবুন, যেখানে বইগুলো সবসময় লেখকের নাম অনুযায়ী বর্ণানুক্রমে সাজানো। নতুন বই এলে ঠিক জায়গায় ঢোকানো হয়; কোনো বই খুঁজতে মাঝখান থেকে শুরু করে বাঁয়ে-ডানে যাওয়া যায়; আর “R অক্ষর থেকে শুরু হওয়া প্রথম লেখক কে?” — এই প্রশ্নের উত্তরও দ্রুত মেলে। C++-এর ordered associative container-গুলো ঠিক এই তাক।

• set<T> — ভিন্ন ভিন্ন key, সাজানো। একই মান দ্বিতীয়বার যোগ করলে কিছু হয় না।
• multiset<T> — একই key একাধিকবার থাকতে পারে (multiset).
• map<K, V> — প্রতিটি ভিন্ন key-এর সাথে একটি মান; key অনুযায়ী সাজানো। ফোনবুকের মতো: নাম → নম্বর।
• multimap<K, V> — একই key-এর একাধিক জোড়া।

ভেতরে এরা একটি balanced binary search tree: প্রতিটি node-এর বাঁ দিকের সব key তার চেয়ে ছোট, ডান দিকের সব বড়। C++ standard গাছের নাম বলে না, শুধু complexity বেঁধে দেয় — খোঁজা, যোগ, মুছে ফেলা O(log n). সেই নিশ্চয়তা পূরণ করতে GCC, Clang আর Microsoft — তিনটি প্রধান লাইব্রেরিই red-black tree ব্যবহার করে, যার উচ্চতা সবসময় 2·log₂(n + 1)-এর বেশি হয় না (প্রমাণ পর্ব ২৯-এ). উচ্চতা O(log n), তাই প্রতিটি কাজ O(log n) — ইনপুট যেমনই হোক, worst case-এও।

শেষ দুই সারিই ordered container-এর আসল শক্তি — hash table এগুলো দিতে পারে না। “৫০০ টাকার সমান বা বেশি দামের সবচেয়ে সস্তা জিনিস কোনটি?”, “এই সময়ের ঠিক আগের ঘটনা কোনটি?” — এমন প্রশ্নের উত্তর lower_bound দিয়ে O(log n)-এ। এবার map দিয়ে শব্দ গোনার কাজটি ধাপে ধাপে দেখুন, আর খেয়াল রাখুন [] অপারেটর কী করে:

1map<string, int> cnt;2for (const string& w : words)3    ++cnt[w];             // missing key: insert 0, then ++4if (cnt["mango"] > 0) {}  // BUG: inserts mango = 05if (cnt.contains("mango")) {}  // C++20: no insert

৫ · Hash container — unordered_set, unordered_map আর anti-hash টেস্ট

লাইব্রেরির সাজানো তাক ভালো, কিন্তু যদি ক্রমের দরকার না থাকে? বড় অফিসের ডাকঘরের খোপগুলো ভাবুন: প্রত্যেক কর্মচারীর আইডির শেষ দুই অঙ্ক দেখে চিঠি সরাসরি সেই খোপে — খোঁজাখুঁজি নেই। এটিই hash table: একটি hash function key থেকে একটি সংখ্যা বানায়, আর সেই সংখ্যা ধরে একটি bucket (খোপ) বেছে নেওয়া হয়। C++-এর unordered_set আর unordered_map এভাবেই কাজ করে; একই bucket-এ একাধিক key পড়লে (collision) সেগুলো একটি ছোট শিকলে (chaining) রাখা হয়।

গড়ে প্রতিটি bucket-এ খুব কম key থাকে, তাই খোঁজা, যোগ আর মুছে ফেলা গড়ে O(1). ভরাট-অনুপাত বা load factor (উপাদান ÷ bucket) একটি সীমা (C++-এ ডিফল্ট 1.0) ছাড়ালে টেবিল বড় করে সব key নতুন bucket-এ বসানো হয় — rehashing, যার খরচ একবারে O(n) কিন্তু amortized O(1), ঠিক vector-এর দ্বিগুণ হওয়ার মতো। কিন্তু সব key যদি একই bucket-এ পড়ে? নিচে দেখুন:

বাস্তবে GCC bucket-সংখ্যা হিসেবে একটি নির্দিষ্ট মৌলিক সংখ্যার তালিকা ব্যবহার করে। Codeforces-এর মতো online judge-এ কনটেস্টের পরে অন্যের কোড “hack” করার সুযোগ থাকে, আর আক্রমণকারী জানেন টেবিল বড় হতে হতে কোন মৌলিক সংখ্যায় পৌঁছাবে — তিনি সেই সংখ্যার গুণিতক দিয়ে ইনপুট বানান। একে বলে anti-hash test. ফল: যে unordered_map সমাধান 0.1 সেকেন্ডে চলত, সেটি সময়সীমা পার হয়ে যায়। কনটেস্ট প্রোগ্রামারদের মধ্যে প্রচলিত সমাধানটি splitmix64 নামের একটি mixing function আর ঘড়ি থেকে নেওয়া seed:

struct SplitMixHash {                          // custom hash for integer keys
    static uint64_t mix(uint64_t x) {           // splitmix64 finalizer
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t SEED =
            chrono::steady_clock::now().time_since_epoch().count();
        return mix(x + SEED);                    // different layout every run
    }
};
unordered_map<long long, int, SplitMixHash> freq;  // use like a normal map

এই struct-টি custom hash-এর একটি উদাহরণ — এমন যেকোনো callable যা key থেকে size_t ফেরত দেয়। pair<int,int>-কে key বানাতে চাইলেও (যেমন গ্রিডের স্থানাঙ্ক) এমন একটি hash লিখতে হয়, কারণ STL-এ std::hash<pair> নেই — unordered_map<pair<int,int>, int> সরাসরি compile হয় না। অথচ map<pair<int,int>, int> কোনো ঝামেলা ছাড়াই চলে, কারণ pair-এর < আছে।

৬ · Python-এর কালেকশন — list, tuple, dict, set আর collections

Python-এ মূল চারটি স্ট্রাকচার ভাষার ভেতরেই আছে, আর বাকিগুলো স্ট্যান্ডার্ড লাইব্রেরির কয়েকটি মডিউলে। নামগুলো C++-এর থেকে আলাদা — আর একটি জায়গায় বিপজ্জনকভাবে বিভ্রান্তিকর: Python-এর list কোনো linked list নয়, এটি C++-এর vector-এর মতো একটি dynamic array.

এবার collections মডিউলের চারটি কাজের জিনিস — প্রতিটি একটি পরিচিত ঝামেলা দূর করে:

• deque — দুই প্রান্তে append/appendleft/pop/popleft O(1). BFS-এর (পর্ব ৪০) queue হিসেবে এটিই ব্যবহার করুন, list.pop(0) নয়। ভেতরে ছোট ব্লকের একটি doubly linked list, তাই প্রান্তের কাছে index দ্রুত, কিন্তু একেবারে মাঝখানে d[i] O(n) — C++-এর deque-এর মতো O(1) নয়। deque(maxlen=k) দিলে শুধু শেষ k টি উপাদান থাকে।
• Counter — dict-এরই একটি subclass, যা গোনার জন্য তৈরি: Counter("banana") → a: 3, n: 2, b: 1. না থাকা key পড়লে 0 দেয়, কিন্তু key তৈরি করে না। most_common(k) সবচেয়ে বেশি k টি দেয়; সমান গণনা হলে যেটি আগে দেখা গেছে সেটি আগে।
• defaultdict — না থাকা key পড়লেই একটি ডিফল্ট মান বানিয়ে বসিয়ে দেয় — ঠিক C++-এর map[]-এর মতো। defaultdict(list) দিয়ে গ্রাফের adjacency list বানানো খুব সহজ: g[u].append(v).
• OrderedDict — সাধারণ dict এখন ক্রম রাখে, তবু এর দুটি বাড়তি ক্ষমতা আছে: move_to_end(k) আর popitem(last=False), দুটিই O(1). LRU cache (সবচেয়ে পুরোনো ব্যবহারটি ফেলে দেওয়া) বানানোর ক্লাসিক উপায়।

heapq মডিউল একটি সাধারণ list-কে min-heap হিসেবে ব্যবহার করে: heappush(h, x) আর heappop(h) O(log n), h[0] সবচেয়ে ছোট (O(1)), আর heapify(a) একটি পুরো list-কে O(n)-এ heap বানায়। bisect মডিউল সাজানো list-এ binary search করে: bisect_left(a, x) হলো C++-এর lower_bound, bisect_right(a, x) হলো upper_bound — দুটিই O(log n). insort(a, x) সাজানো ক্রম রেখে ঢোকায়, কিন্তু জায়গা খুঁজতে O(log n) হলেও list-এ ঢোকাতে O(n).

আর সাজানো: sorted(iterable, key=..., reverse=...) নতুন list দেয়, a.sort(...) জায়গাতেই সাজায়। দুটিই Timsort অ্যালগরিদম, O(n log n), আর stable — সমান key-এর উপাদানের আগের ক্রম বদলায় না। key হলো প্রতিটি উপাদান থেকে তুলনার মাপকাঠি বানানোর একটি ফাংশন: key=len দৈর্ঘ্য ধরে, key=lambda p: (-p[1], p[0]) দ্বিতীয় মান বড় থেকে ছোট আর সমান হলে প্রথম মান ছোট থেকে বড়। key প্রতিটি উপাদানের জন্য মাত্র একবার হিসাব হয়।

৭ · তৈরি অ্যালগরিদম আর iterator — sort, lower_bound, next_permutation

STL-এর <algorithm> আর <numeric> header-এ শতাধিক তৈরি অ্যালগরিদম আছে। সবগুলো কাজ করে iterator-এর একটি জোড়া [first, last)-এর ওপর — first প্রথম উপাদানে, last শেষ উপাদানের এক ঘর পরে। এই অর্ধ-খোলা পরিসরের সুবিধা: উপাদানের সংখ্যা ঠিক last − first, আর খালি পরিসর মানে first == last. কনটেস্ট আর পরের পর্বগুলোতে সবচেয়ে বেশি লাগবে এগুলো:

C++11 থেকে standard-এ std::sort-এর জন্য worst case-এও O(n log n) তুলনা বাধ্যতামূলক। এজন্য GCC আর অন্যরা introsort ব্যবহার করে: সাধারণত quick sort চালায়, রিকার্শন বেশি গভীর হয়ে গেলে heapsort-এ চলে যায়, আর ছোট টুকরোয় insertion sort (পর্ব ২০, ২২, ২৩; লাইব্রেরির sort-এর পুরো গল্প পর্ব ২৫-এ). sort-এ নিজের তুলনা দিতে একটি comparator লাগে — দুটি উপাদান নিয়ে “প্রথমটি কি আগে বসবে?” প্রশ্নের উত্তর দেয় এমন ফাংশন। এর একটি কঠোর শর্ত আছে: সমান উপাদানের জন্য অবশ্যই false দিতে হবে। <-এর বদলে <= লিখলে আচরণ undefined — কখনো ভুল ক্রম, কখনো crash.

vector<int> p = {1, 2, 3};
do { /* visits 123 132 213 231 312 321 */ } while (next_permutation(p.begin(), p.end()));

vector<long long> bills = {120, 450, 80};
long long total = accumulate(bills.begin(), bills.end(), 0LL);   // 650 -- note 0LL, not 0

accumulate-এর তৃতীয় মানটির type-ই যোগফলের type. 0 লিখলে যোগফল int-এ হবে, আর বড় মানে নিঃশব্দে overflow — তাই 0LL. next_permutation সব বিন্যাস দিতে চাইলে শুরুতে পরিসরটি সাজানো থাকতে হবে।

lower_bound ভেতরে কীভাবে কাজ করে

lower_bound আসলে পর্ব ১৮-এর binary search-এর একটি বিশেষ রূপ: “x কোথায় আছে” নয়, বরং “x-কে ক্রম না ভেঙে সবচেয়ে বাঁয়ে কোথায় ঢোকানো যায়”। এই প্রশ্নটির সুবিধা হলো, উত্তর সবসময় আছে (x না থাকলেও), আর সদৃশ মান থাকলে প্রথমটির অবস্থান পাওয়া যায়। Pseudocode (0-based, অর্ধ-খোলা পরিসর):

Pseudocode (0-based; a[0..n-1] sorted ascending)

LOWER-BOUND(a, n, x):                // first i with a[i] >= x, or n
    lo = 0, hi = n                   // answer is always in [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) / 2     // integer division
        if a[mid] < x: lo = mid + 1  // a[0..mid] are all < x
        else:          hi = mid      // a[mid] >= x, so answer <= mid
    return lo

UPPER-BOUND: same, but test  a[mid] <= x  instead of  a[mid] < x

দুটি ভাষাতেই চালিয়ে দেখুন — এখানে চারটি ভিন্ন x নেওয়া হয়েছে: আছে, নেই কিন্তু মাঝে, সবার চেয়ে ছোট, আর সবার চেয়ে বড়। শেষ লাইনে একটি set-এ “x-এর সমান বা বড় প্রথম মান” আর “x-এর সমান বা ছোট শেষ মান” বের করা হয়েছে — কনটেস্টে খুবই প্রচলিত দুটি প্রশ্ন।

#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> a = {10, 20, 20, 20, 30, 40};          // must be sorted
    cout << "a = 10 20 20 20 30 40\n";
    for (int x : {20, 25, 5, 45}) {
        auto lo = lower_bound(a.begin(), a.end(), x) - a.begin();  // first >= x
        auto hi = upper_bound(a.begin(), a.end(), x) - a.begin();  // first >  x
        bool found = binary_search(a.begin(), a.end(), x);
        cout << "x=" << x << ": lower=" << lo << " upper=" << hi
             << " count=" << hi - lo << " found=" << (found ? "yes" : "no") << '\n';
    }
    set<int> s(a.begin(), a.end());                     // {10, 20, 30, 40}
    auto ge = s.lower_bound(25);                        // member function: O(log n)
    auto le = prev(s.upper_bound(25));                  // last element <= 25
    cout << "set: first >= 25 is " << *ge << ", last <= 25 is " << *le << '\n';
}

a = 10 20 20 20 30 40
x=20: lower=1 upper=4 count=3 found=yes
x=25: lower=4 upper=4 count=0 found=no
x=5: lower=0 upper=0 count=0 found=no
x=45: lower=6 upper=6 count=0 found=no
set: first >= 25 is 30, last <= 25 is 20

from bisect import bisect_left, bisect_right

a = [10, 20, 20, 20, 30, 40]                 # must be sorted
print("a =", *a)
for x in [20, 25, 5, 45]:
    lo = bisect_left(a, x)                   # first index with a[i] >= x
    hi = bisect_right(a, x)                  # first index with a[i] >  x
    found = lo < len(a) and a[lo] == x
    yn = "yes" if found else "no"
    print(f"x={x}: lower={lo} upper={hi} count={hi - lo} found={yn}")

s = sorted(set(a))                           # no built-in sorted set in Python
ge = s[bisect_left(s, 25)]                   # first element >= 25
le = s[bisect_right(s, 25) - 1]              # last element <= 25
print(f"set: first >= 25 is {ge}, last <= 25 is {le}")

a = 10 20 20 20 30 40
x=20: lower=1 upper=4 count=3 found=yes
x=25: lower=4 upper=4 count=0 found=no
x=5: lower=0 upper=0 count=0 found=no
x=45: lower=6 upper=6 count=0 found=no
set: first >= 25 is 30, last <= 25 is 20

৮ · বড় তুলনা টেবিল আর কোনটি বেছে নেবেন

সবকিছু এক জায়গায়। পরের পর্বগুলো পড়ার সময় এই টেবিলটি হাতের কাছে রাখুন। “গড়ে” লেখা মানে hash-নির্ভর; worst case তার পাশে বন্ধনীতে।

এবার একটি পুরো কাজ, দুই ভাষায়: একটি লেখায় কোন শব্দ কতবার এসেছে, তা গুনে বেশি থেকে কম ক্রমে ছাপানো, আর সমান গণনা হলে শব্দের বর্ণানুক্রমে। ইন্টারভিউ আর কনটেস্টে এটি একটি অতি প্রচলিত ধাঁচ — “গোনো, তারপর দুই মাপকাঠিতে সাজাও”।

#include <algorithm>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    string text = "rice fish dal rice tea fish rice egg tea dal rice";
    map<string, int> cnt;                         // ordered by word
    istringstream in(text);
    for (string w; in >> w; ) ++cnt[w];          // [] inserts 0, then ++

    cout << "alphabetical (map order):";
    for (const auto& [w, c] : cnt) cout << ' ' << w << '=' << c;
    cout << '\n';

    vector<pair<string, int>> v(cnt.begin(), cnt.end());
    sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) return a.second > b.second;   // count: high first
        return a.first < b.first;                                // then word: A to Z
    });
    cout << "by count, then word:\n";
    for (const auto& [w, c] : v) cout << c << ' ' << w << '\n';
    cout << "mango present? " << (cnt.contains("mango") ? "yes" : "no")
         << ", distinct words = " << cnt.size() << '\n';
}

alphabetical (map order): dal=2 egg=1 fish=2 rice=4 tea=2
by count, then word:
4 rice
2 dal
2 fish
2 tea
1 egg
mango present? no, distinct words = 5

from collections import Counter

text = "rice fish dal rice tea fish rice egg tea dal rice"
cnt = Counter(text.split())                  # a dict: word -> count

print("alphabetical (map order):", " ".join(f"{w}={cnt[w]}" for w in sorted(cnt)))

print("by count, then word:")
for w, c in sorted(cnt.items(), key=lambda kv: (-kv[1], kv[0])):
    print(c, w)

yn = "yes" if "mango" in cnt else "no"
print(f"mango present? {yn}, distinct words = {len(cnt)}")

alphabetical (map order): dal=2 egg=1 fish=2 rice=4 tea=2
by count, then word:
4 rice
2 dal
2 fish
2 tea
1 egg
mango present? no, distinct words = 5

কোন container বেছে নেবেন — ধাপে ধাপে

নতুন সমস্যা পেলে নিচের প্রশ্নগুলো ক্রমানুসারে নিজেকে করুন। যে প্রশ্নের উত্তর প্রথম “হ্যাঁ”, সেখানেই সাধারণত আপনার উত্তর।

C++:    vector<int> marks(n);  marks[roll] = 78;
Python: marks = [0] * n;       marks[roll] = 78
সময়:   index O(1), শেষে যোগ amortized O(1)

C++:    queue<int> q;  q.push(s);  q.front();  q.pop();
Python: q = deque([s]);  q.popleft()
সময়:   প্রতিটি কাজ O(1)

C++:    priority_queue<T, vector<T>, greater<T>> pq;  // min
Python: heapq.heappush(h, (dist, node))
সময়:   push/pop O(log n), সবচেয়ে ছোট দেখা O(1)

C++:    unordered_map<string, int> freq;  freq[w]++;
Python: freq = Counter(words)
সময়:   গড়ে O(1); কনটেস্টে custom hash ভাবুন

C++:    set<int> prices;  auto it = prices.lower_bound(500);
Python: স্ট্যান্ডার্ড লাইব্রেরিতে নেই — সাজানো list + bisect,
        বা heap / Fenwick tree দিয়ে বিকল্প
সময়:   C++-এ যোগ, মুছে ফেলা, খোঁজা — সব O(log n)

C++:    sort(a.begin(), a.end());  lower_bound(a.begin(), a.end(), x);
Python: a.sort();  bisect_left(a, x)
সময়:   একবার O(n log n), প্রতি প্রশ্ন O(log n);
        set-এর চেয়ে কম মেমরি আর cache-বান্ধব

৯ · সাধারণ ফাঁদ — যেখানে তৈরি স্ট্রাকচারও কামড় দেয়

তৈরি container ভুল করে না, কিন্তু আমরা ভুলভাবে ব্যবহার করি। নিচের ফাঁদগুলো ইন্টারভিউ, কনটেস্ট আর বাস্তব প্রজেক্টে বারবার দেখা যায়।

C++-এর ফাঁদ

• map[] নতুন key বানায়। অংশ ৪-এর ডায়াগ্রামে দেখেছেন। শুধু খোঁজার জন্য find/count/contains.
• Iterator invalidation. container বদলালে পুরোনো iterator, pointer বা reference আর বৈধ নাও থাকতে পারে। vector-এ reallocation হলে সব নষ্ট; erase হলে মুছে ফেলা ঘর আর তার পরের সব নষ্ট। map/set/list-এ শুধু মুছে ফেলা উপাদানটির iterator নষ্ট হয়, বাকিরা ঠিক থাকে। unordered_map-এ rehash হলে iterator নষ্ট হয় (reference টিকে থাকে)।
• লুপের ভেতরে মুছে ফেলা। for (auto it = m.begin(); it != m.end(); ++it) if (...) m.erase(it); — মুছে ফেলার পর ++it একটি নষ্ট iterator-এ চলে। সঠিক রূপ: it = m.erase(it); (erase পরের iterator ফেরত দেয়), নইলে ++it. C++20-এ সহজ পথ: std::erase_if(m, pred).
• set-এ সাধারণ lower_bound. lower_bound(s.begin(), s.end(), x) compile হয় আর ঠিক উত্তরও দেয়, কিন্তু set-এর iterator এক এক ঘর করে হাঁটে, তাই সময় O(n)! সবসময় member ফাংশন s.lower_bound(x) — O(log n). কনটেস্টে TLE-র একটি ক্লাসিক কারণ।
• size() unsigned. v.size() - 1 খালি vector-এ 0 − 1 হয়ে একটি বিশাল ধনাত্মক সংখ্যা হয় (unsigned wrap-around). for (int i = 0; i < (int)v.size() - 1; ++i) লিখুন, বা C++20-এর ssize(v).
• unordered_map-এ pair বা vector key. hash নেই, compile error. map নিন, বা custom hash লিখুন।

Python-এর ফাঁদ

• ঘোরার সময় dict বা set-এর আকার বদলানো। for k in d: if ...: del d[k] চালালে RuntimeError: dictionary changed size during iteration. list-এ এমন করলে error আসে না, কিন্তু উপাদান বাদ পড়ে যায় — আরও বিপজ্জনক। সমাধান: কপির ওপর ঘুরুন (for k in list(d):) বা নতুন কালেকশন বানান (d = {k: v for k, v in d.items() if keep(v)}).
• Mutable default argument. def add(x, bag=[]): — ডিফল্ট list-টি ফাংশন সংজ্ঞায়িত হওয়ার সময় একবার তৈরি হয়, প্রতিটি কলে নতুন নয়। তাই add(1) তারপর add(2) দ্বিতীয়বার [1, 2] দেয়! এটি mutable default argument ফাঁদ। সমাধান: bag=None, তারপর ভেতরে if bag is None: bag = [].
• list-এর set হয় না। {[1, 2], [3]} বা seen.add(path) (path একটি list) দিলে TypeError: unhashable type: 'list'. list বদলানো যায়, তাই তার hash স্থির থাকে না। tuple(path) বা frozenset ব্যবহার করুন।
• [[0] * m] * n. এতে n টি আলাদা সারি নয়, একই সারির n টি reference তৈরি হয় — এক ঘর বদলালে সব সারিতে বদলায়। লিখুন [[0] * m for _ in range(n)].
• লুকানো O(n). x in some_list, list.pop(0), list.insert(0, x), list.remove(x) — লুপের ভেতরে থাকলে পুরো অ্যালগরিদম O(n²) হয়ে যায়। খোঁজার জন্য set, সামনে থেকে বের করতে deque.

১০ · AI-এর যুগে কালেকশন — কোড চলে, কিন্তু complexity?

“এই সমস্যাটি Python-এ সমাধান করো” বললে AI প্রায়ই পরিষ্কার, ছোট কোড দেয় — আর ছোট উদাহরণে তা নির্ভুল চলে। কিন্তু তৈরি কালেকশনের লুকানো দাম AI প্রায়ই খেয়াল করে না: একটি x in list বা pop(0) লুপের ভেতরে পুরো সমাধানকে O(n²) বানিয়ে দেয়, অথচ ব্যাখ্যায় লেখা থাকে “O(n)”. complexity-র দাবি তাই প্রতিবার নিজে যাচাই করবেন।

কালেকশন ব্যবহারে AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) কালেকশন-নির্ভর কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি container-এর নিচে কোন স্ট্রাকচার আছে (array, tree, hash, heap) — বলতে পারি
• লুপের ভেতরের প্রতিটি অপারেশনের complexity লিখে মোট হিসাব মিলিয়েছি
• খালি container, একটি উপাদান, সব সমান মান, আর end()/সীমার বাইরের প্রশ্ন — এই edge case-গুলো চালিয়ে দেখেছি
• টাই-ভাঙার নিয়ম (সমান মানের ক্রম) প্রশ্নের সাথে মিলিয়েছি
• সবচেয়ে বড় ইনপুটে (বা সাজানো/সব-সমান/গুণিতক key-এর মতো খারাপ ইনপুটে) সময় মেপেছি
• ছোট এলোমেলো ইনপুটে একটি সরল brute force সমাধানের সাথে stress testing করে উত্তর মিলিয়েছি