পরের প্রশ্নটা কোন container সামলাবে?

Library খোলার আগে Alice-এর তিন কাজ। ফেরত আসা বই আগে আসা আগে যাবে। তাকের হিসাবে নাম সাজিয়ে মোট দেখাতে হবে। মেরামতের কাজে সবচেয়ে জরুরিটা আগে নিতে হবে। সবখানেই record রাখছে, কিন্তু পরের প্রশ্নটা এক না।

আগের সেই চার প্রশ্ন

কাগজে শুধু container-এর নাম লিখে শুরু করলে আসল কাজ চাপা পড়ে যায়। Container মানে মান রাখার জায়গা, সাথে কিছু operation-এর খরচের প্রতিশ্রুতি। আর pattern মানে সেই operation-গুলো মেলানোর একটা নিয়ম। এই module-এ আগের শেখা জিনিসগুলো একসাথে লাগাবে।

Module 2-এর প্রথম প্রশ্ন ছিল, তোমার data কি একটা ক্রম, নাকি key ধরে খুঁজবে? দ্বিতীয়টা, position দিয়ে পড়বে, নাকি মান খুঁজতে হবে? তৃতীয়টা, কোথায় ঢুকবে আর কোথা থেকে বেরোবে? চতুর্থটা, মোট কয়টা element আর একেকটা কত বড়?

উত্তরগুলো লিখে রাখো। একটার উত্তর অন্যটার চেয়ে বেশি জরুরি হতে পারে। সাজানো vector-এ মাঝখানে বারবার ঢোকাতে গেলে অনেক মান সরাতে হবে। List-এ insert সস্তা হলেও কোথায় insert করবে, তার iterator আগে হাতে থাকতে হবে। সেটা খুঁজতেও হাঁটা লাগে।

আরেকটা শব্দ কাজে লাগবে, invariant। মানে প্রতিটা বদলের পর যে কথাটা সত্যি রাখবে। Queue-এ আসার ক্রম ঠিক থাকে। সাজানো vector-এ ছোট থেকে বড় ক্রম ঠিক থাকে। Container বাছার সময় এই সত্যিটা আর পরের operation, দুটোই বলতে পারা চাই।

ক্রম, key, নাকি বের হওয়ার বাঁধা নিয়ম

Position-এর মানে থাকলে সেটা sequence-এর কাজ। শেষে যোগ করবে, index দিয়ে পড়বে, পুরোটা হাঁটবে, তখন আগে vector দেখো। মাপ যদি type-এর অংশ হয়, array দেখো। Character-এর ক্রম রাখলে string। তবে byte-এর index আর মানুষের চোখে একটা অক্ষরের position সব ভাষায় এক হয় না।

দুই মাথায় কাজ আর indexing চাইলে deque আছে। পেছনে লোক আসে, সামনে থেকে চলে যায়, এই ধরনের সারিতে ও কাজে দেয়। জানা iterator-এর কাছে বদল বা পুরো linked অংশ সরালে list কাজে দেয়। List-এর মাঝের index সরাসরি পড়া যায় না। ওই জায়গায় যেতে হাঁটতেই হবে।

অন্য container-এর কিছু operation ঢেকে অল্প কয়টা দেখায় adaptor। Stack নতুনটাকে আগে দেয়। Queue পুরোনোটাকে। Priority_queue comparison-এর নিয়মে বড় বা ছোটটাকে দেয়। অল্প interface-ও সুবিধা, কারণ তোমার কাজের নিয়মটা type দেখেই বোঝা যায়।

পরের দরকার যদি যেকোনো একটা key খোঁজা হয়, priority_queue নিও না। ওর top পড়া সস্তা, ভেতরে ইচ্ছামতো খোঁজা ওর কাজ না। গল্পে বইয়ের স্তূপ আছে বলেই stack হবে না। আসল কথা, বের করার সময় কোনটাকে আগে লাগছে।

সাজানো key, সমান মান আর সাথে রাখা value

Set আলাদা key ছোট থেকে বড় রাখে। Multiset একই key বারবার রাখতে পারে। Map-এ আলাদা key-এর সাথে value থাকে। Multimap-এ একই key-এর একাধিক entry চলে। চারটাতেই সাজানো খোঁজা যায়, তাই পরের বড় key চাওয়ার মানে আছে।

Unordered নামেরগুলো hashing করে। Unordered_set আর unordered_multiset শুধু key রাখে। Unordered_map আর unordered_multimap সাথে value রাখে। সাধারণভাবে খোঁজার গড় খরচ constant। সবচেয়ে খারাপ ক্ষেত্রে linear হতে পারে। আর এদের হাঁটার ক্রম সাজানো report না।

একই মান বারবার এলে কী করবে, সেটা statement দেখে বুঝতে হবে। একই দামের দুই ticket আলাদা ticket। একই বই দুইবার scan হলে হয়তো একটা আলাদা বই-ই বোঝাচ্ছে। দরকারি duplicate হারালে উত্তর বদলে যাবে। শুধু দেখতে ঠিকঠাক সংখ্যা print হলেই তাই নিশ্চিন্ত হবে না।

সব input আগে পেয়ে গেলে সাজানো vector-টাও আবার ভাবো। একবার sort করলে পরে binary search আর indexing পাও। প্রশ্নের মাঝে মান ঢুকলে বা মুছলে set বা map ভালো হতে পারে। আর সাজানো থাকলেই rank query সস্তা হয়ে যায় না। তার জন্য কীভাবে হাঁটতে হচ্ছে, সেটা দেখতে হবে।

মাপ আর মানের গঠনও দেখো

Bitset বাঁধা সংখ্যক হ্যাঁ-না রাখে। অল্প কয়টা flag integer mask-এও রাখা যায়। Vector<bool>-এর মাপ input থেকে আসতে পারে, তবে ওর reference সাধারণ bool reference-এর মতো না। Sparse label-এর সাথে record রাখতে চাইলে এই কোনোটাই map-এর বদলি না।

Pair আর tuple কয়েকটা field এক মানে জোড়ে। বাইরের container-এর কাজ তারা করে না। Pair রাখা priority_queue আগে ছোট distance, তারপর ছোট node নিতে পারে। Pair রাখা vector-এ road রাখা যায়। ভেতরের field আর বাইরের রাখার নিয়ম, দুইটা আলাদা সিদ্ধান্ত।

বড় record বারবার সরালে খরচ বাড়ে। তখন আলাদা জায়গায় record রেখে ছোট index সরানো যায়। Record-এর পরিচয় টিকিয়ে রাখতে হলে সেই জায়গা স্থির থাকতে হবে। পরে storage বদলালে index বা pointer-এর মানে নষ্ট হচ্ছে কি না, সেটাও তোমার দেখার কাজ।

শুধু payload গুনে memory শেষ করো না। Linked node-এর সাথে link লাগে। Vector বাড়তি capacity রাখতে পারে। Adjacency list-এ অনেক ভেতরের vector থাকে। তাই সীমা দেখে মোট খরচ ধরবে। মাপ না দেখে শুধু container-এর নাম শুনে ধীর বলে বাদ দেবে না।

তিনটা কাজ ধরে পথ মিলাও

ফেরত বইয়ের জন্য Alice-এর উত্তর, একটা ক্রম, পুরোনো আগে, পেছনে আসে, সামনে যায়। Queue-এ নিয়মটা সরাসরি বলা যায়। কর্মীদের দুই মাথাই দেখতে হলে deque লাগতে পারে। বই কতটা আসবে সেটা চলার সময় বদলায়, তাই array দিয়ে শুরু করার কারণ নেই।

Maria তাকের নাম ধরে count বদলাবে, শেষে নাম সাজিয়ে দেখাবে। Map<string,int> এই প্রশ্নগুলো সামলায়। Report খুব কম হলে unordered_map নিয়ে শেষে key সাজানোও যায়। তবে সেই sort-এর খরচ মোট হিসাবের মধ্যে ধরতে হবে। বাদ দিলে তুলনাটাই ভুল হবে।

David মেরামতের প্রতিশ্রুত শেষ সময়ের মধ্যে ছোটটা আগে চায়। শুধু পরের কাজ দরকার হলে min-priority_queue চলে। কাজ বাতিল করাও লাগলে আরেকটা শর্ত এলো। তখন id ধরে বর্তমান খবর রাখবে, পুরোনো heap entry উপরে এলে বাদ দেবে। Module 7-এ সেই lazy deletion দেখেছ।

এই বাছাই ভবিষ্যতের সব প্রশ্নের উত্তর না। নতুন operation এলে সিদ্ধান্ত পাল্টাতে পারে। Sliding window-এ বড় মানের সাথে মেয়াদও দেখতে হয়। Dijkstra-তে heap-এর পাশাপাশি বর্তমান distance লাগে। পরের lesson-গুলোতে এই সত্যিগুলো জুড়বে, শুরুর চার প্রশ্ন একই থাকবে।

queue<int> returns;             // Oldest first.
map<string, int> shelfCount;     // Key lookup and sorted reporting.
priority_queue<int> urgency;     // Largest currently waiting value.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> returns;
    for (int id : {8, 3, 8}) returns.push(id);
    while (!returns.empty()) {
        cout << returns.front() << '\n'; returns.pop();
    }
}

8
3
8

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
    map<string,int> count;
    for (string shelf : {"Z", "A", "Z"}) ++count[shelf];
    for (const auto& [shelf, n] : count) cout << shelf << ' ' << n << '\n';
}

A 1
Z 2

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> jobs;
    for (int x : {4, 9, 4}) jobs.push(x);
    while (!jobs.empty()) { cout << jobs.top() << '\n'; jobs.pop(); }
}

9
4
4

তোমার দরকারি operation-এর শাখা ধরো। শেষ সারিতে মাপ আর payload আবার দেখতে বলছে, কারণ ওগুলো বাদ দেওয়ার প্রশ্ন না।

Deque-এ রাখা আছে index। Window পুরো না হলে max দেখাচ্ছে না। মেয়াদ শেষ হওয়ার আগেই কিছু index কেন বাদ যায়, সেটা lesson 02-এ দেখবে।

#include <list>
#include <iostream>
int main() { std::list<int> a{7,8}; std::cout << a[1]; }

#include <queue>
int main() { std::queue<int> q; q.push(3); int x=q.pop(); return x; }

3
2 1 2
2 2 1

0 0 1

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n), b(n);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;
    // Compare all three complete departure orders.
}

5
4 4 1 4 4

#include <iostream>
#include <vector>
using namespace std;
int main() { int n; cin>>n; vector<int> a(n); for(int& x:a) cin>>x;
    // Count adjacent equal pairs without reordering the sequence.
}

2

6
4 1 4 2 2 4

#include <iostream>
#include <vector>
using namespace std;
int main() { int n; cin>>n; vector<int> a(n); for(int& x:a) cin>>x;
    // Report how many different labels repeat at least twice.
}

2

পরের lesson-এ window সরাব, ভেতরটা নতুন করে খুঁজতে হবে না।