STL algorithm — লুপ না লিখে তৈরি সমাধান

১ · লুপ নয়, উদ্দেশ্য লিখুন — “no raw loops” ভাবনা

ধরুন একটি কোচিং সেন্টারের মডেল টেস্টের ফল আপনার হাতে, একটি std::vector<int> marks-এ। এখন চারটি প্রশ্ন: কতজন পাস করেছে (৩৩ বা তার বেশি)? সর্বোচ্চ নম্বর কত? গড় কত? আর মেধাতালিকা কেমন? এ পর্যন্ত যা শিখেছেন, তা দিয়ে প্রথম প্রশ্নের উত্তর সম্ভবত এভাবে লিখবেন:

int pass = 0;
for (std::size_t i = 0; i < marks.size(); ++i) {
    if (marks[i] >= 33) ++pass;
}

কোডটি ঠিক আছে। কিন্তু একজন পাঠককে এটি বুঝতে মাথার ভেতরে লুপটি চালিয়ে দেখতে হয়: একটি counter শূন্য থেকে শুরু, একটি index, শর্ত < না <=, প্রতিবার কী বাড়ছে। চার লাইনের প্রতিটিতে ভুলের একটি করে সুযোগ — counter-এর শুরুর মান, সীমার শর্ত (off-by-one), ভুল ভ্যারিয়েবল বাড়ানো। এবার একই কাজ standard library-র একটি algorithm দিয়ে:

auto pass = std::count_if(marks.begin(), marks.end(),
                          [](int m) { return m >= 33; });

নামটিই বলে দিচ্ছে কী হচ্ছে: “শর্ত পূরণ করে এমন কয়টি আছে, গোনো।” [](int m) { return m >= 33; } অংশটি একটি lambda — নামহীন ছোট একটি ফাংশন, যা ঠিক সেই জায়গাতেই লেখা হয়, যেখানে দরকার। এখানে এটি শুধু বলে “এই নম্বরটি কি পাস?” lambda-র পুরো ব্যাকরণ পর্ব ৩৪-এ আসবে; এই পর্বে আমরা কেবল এমন ছোট, এক লাইনের lambda ব্যবহার করব।

এই ভাবনাকে বিখ্যাত করেন Adobe-এর প্রকৌশলী Sean Parent, ২০১৩ সালের GoingNative সম্মেলনের “C++ Seasoning” বক্তৃতায়। তাঁর প্রথম পরামর্শ ছিল তিন শব্দের: no raw loops. raw loop মানে এমন হাতে লেখা for/while, যার কাজ আসলে একটি পরিচিত algorithm, কিন্তু কোডে তার নাম কোথাও লেখা নেই। কথাটা “লুপ নিষিদ্ধ” নয়। কথাটা হলো: লুপ লিখতে বসলে আগে জিজ্ঞেস করুন, এই কাজের কোনো নাম আছে কি? থাকলে সেই নামটিই ডাকুন। না থাকলে লুপটিকে একটি ভালো নামের নিজের ফাংশনে ভরে দিন — তাহলে বাকি কোডে আবার নামটিই ডাকা হবে।

২ · algorithm-এর ভাষা — range, predicate আর ফেরত আসা iterator

প্রায় সব algorithm থাকে দুটি header-এ: <algorithm> (খোঁজা, বদলানো, সাজানো — শতাধিক ফাংশন) আর <numeric> (যোগফল, ক্রমযোগ, ক্রমিক সংখ্যা)। সবার কথা বলার ধরন একই, তাই একবার ধরনটা বুঝলে নতুন algorithm শেখা মানে শুধু নতুন একটি নাম শেখা।

১. কাজ করে একটি range-এ, container-এ নয়

পর্ব ৩২-এ দেখেছেন, একটি iterator হলো container-এর ভেতরে একটি জায়গা দেখানোর উপায়। algorithm নেয় দুটি iterator — first আর last — আর কাজ করে half-open range [first, last)-এ: first-এর উপাদান থেকে শুরু, last-এর ঠিক আগে শেষ। last নিজে range-এর বাইরে। এই ধরনের কারণে খালি range লেখা সহজ (first == last), আর উপাদানের সংখ্যা সরাসরি last - first.

যেহেতু algorithm শুধু iterator দেখে, একই std::find কাজ করে std::vector-এ, std::array-এ, std::deque-এ, std::list-এ, এমনকি সাধারণ C array-তেও। কিন্তু এর একটি বড় পরিণতি আছে: algorithm container-কে দেখতেই পায় না, তাই container-এর আকার বদলাতে পারে না। সে উপাদান পড়তে, লিখতে, জায়গা বদলাতে পারে; কিন্তু একটি উপাদানও মুছে vector ছোট করতে পারে না। ৪ নম্বর অংশে remove-এর রহস্য এই কথা থেকেই আসবে।

২. ফল আসে iterator হয়ে — না পেলে last

খোঁজার algorithm সাধারণত পাওয়া উপাদানের iterator ফেরত দেয়। কিছু না পেলে ফেরত দেয় last — অর্থাৎ “range-এর শেষে পৌঁছে গেছি, পাইনি।” তাই ফল ব্যবহারের আগে সবসময় যাচাই:

auto it = std::find(marks.begin(), marks.end(), 100);
if (it != marks.end()) {
    std::println("100 found at index {}", it - marks.begin());
}   // না মিলিয়ে *it পড়লে: end() dereference — undefined behavior

৩. শর্ত দেওয়া হয় predicate আর comparator দিয়ে

অনেক algorithm-এর নামের শেষে _if — find_if, count_if, remove_if. এরা একটি predicate নেয়: এমন একটি ফাংশন, যা একটি উপাদান নিয়ে true বা false বলে — “এটি কি পাস?”, “এটি কি খালি?” সাজানো আর খোঁজার algorithm নেয় একটি comparator: দুটি উপাদান নিয়ে উত্তর দেয় “a কি b-এর আগে বসবে?” দুটিই হতে পারে সাধারণ ফাংশন, lambda, বা function object (পর্ব ২৩-এর operator()-ওয়ালা object). দেওয়া না হলে ডিফল্ট হলো == (খোঁজায়) আর < (সাজানোয়)।

একটি সতর্কতা: কিছু container-এর নিজের member function আছে, যা একই কাজ আরও ভালোভাবে করে। std::set বা std::map-এ খুঁজতে s.find(x) লিখুন — এটি O(log n), অথচ std::find এক এক করে সব দেখে, O(n). আর std::list সাজাতে lst.sort(), কারণ std::sort-এর random-access iterator লাগে, যা list দিতে পারে না (পর্ব ৩০ ও ৩১)। নিয়ম: container-এর নিজের সংস্করণ থাকলে সেটিই আগে।

৩ · খোঁজা, গোনা, যাচাই — যারা ডেটা বদলায় না

প্রথম পরিবারটি শুধু পড়ে, কিছু লেখে না। তাই এদের const ডেটাতেও চালানো যায়, আর এরা সবচেয়ে নিরাপদ। প্রতিটির একটি ছোট উদাহরণ দেখুন (সবখানে m হলো নম্বরের একটি vector):

auto fail = std::find_if(m.begin(), m.end(), [](int x) { return x < 33; });
auto n100 = std::count(m.begin(), m.end(), 100);
bool allPass = std::all_of(m.begin(), m.end(), [](int x) { return x >= 33; });
bool anyZero = std::any_of(m.begin(), m.end(), [](int x) { return x == 0; });

// দুটি উত্তরপত্র মেলানো: key = সঠিক উত্তর, ans = শিক্ষার্থীর উত্তর
auto [k, a] = std::mismatch(key.begin(), key.end(), ans.begin(), ans.end());
if (k != key.end()) std::println("first wrong answer: Q{}", k - key.begin() + 1);

শেষ উদাহরণে std::mismatch দুটি range পাশাপাশি হাঁটে, আর প্রথম যে জায়গায় উপাদান মেলে না, সেখানকার দুটি iterator একসাথে ফেরত দেয় — structured binding (পর্ব ১২) দিয়ে সেগুলো k আর a-তে খুলে নেওয়া হয়েছে। চার-iterator রূপটি (C++14 থেকে) দুই range-এর শেষ-বিন্দুই নেয়, তাই দ্বিতীয় তালিকা ছোট হলেও সীমার বাইরে পড়ে না। পুরোনো তিন-iterator রূপে দ্বিতীয় range অন্তত প্রথমটির সমান লম্বা হতে হয় — সেটি আপনার দায়িত্ব।

C++23-এ std::ranges::contains(m, 100) এসেছে, যা সরাসরি bool দেয় — “আছে কি না” প্রশ্নে find(...) != end() লেখার চেয়ে আরও পরিষ্কার। ranges-এর কথা ৮ নম্বর অংশে আর পর্ব ৩৫-এ।

৪ · বদলানো — copy, transform, fill, আর remove কেন মোছে না

দ্বিতীয় পরিবার উপাদান লেখে বা জায়গা বদলায়। এদের বেশিরভাগ একটি গন্তব্য iterator নেয় — “ফল কোথায় লিখব?” — আর সেখানে যথেষ্ট জায়গা থাকা আপনার দায়িত্ব।

std::vector<int> out(m.size());                 // আগে থেকেই m-এর সমান জায়গা
std::copy(m.begin(), m.end(), out.begin());     // সব কপি

std::vector<int> passed;                        // খালি — জায়গা নেই
std::copy_if(m.begin(), m.end(), std::back_inserter(passed),
             [](int x) { return x >= 33; });    // back_inserter: প্রতিবার push_back

std::transform(m.begin(), m.end(), m.begin(),   // নিজের জায়গাতেই বদল
               [](int x) { return x + 5; });    // গ্রেস মার্কস: সবাইকে +৫
std::fill(out.begin(), out.end(), 0);           // সব ঘরে 0
std::replace_if(m.begin(), m.end(),             // ১০০-এর বেশি হলে ১০০
                [](int x) { return x > 100; }, 100);

std::transform প্রতিটি উপাদানে একটি ফাংশন চালিয়ে ফল লেখে — হয় নতুন জায়গায়, নয়তো (উপরের মতো) নিজের জায়গাতেই। এর দুই-range রূপও আছে, যা দুটি তালিকা থেকে জোড়ায় জোড়ায় নেয় — ৭ নম্বর অংশে কেনাকাটার কার্টে দাম × পরিমাণ হিসাবে এটি দেখবেন।

remove কেন মোছে না — আর erase কেন লাগে

ধরুন নম্বরের তালিকায় যারা পরীক্ষায় বসেনি, তাদের জন্য 0 লেখা আছে, আর আপনি সেগুলো বাদ দিতে চান। নামের কারণে স্বাভাবিকভাবে লিখবেন std::remove(m.begin(), m.end(), 0). কিন্তু ২ নম্বর অংশের কথা মনে করুন: algorithm container দেখতে পায় না, শুধু iterator. তাই সে vector ছোট করতে পারে না। remove / remove_if আসলে যা করে: রাখার মতো উপাদানগুলো ক্রম ঠিক রেখে সামনের দিকে সরিয়ে আনে, তারপর “নতুন শেষ”-এর একটি iterator ফেরত দেয়। এর পরের ঘরগুলোতে কী থাকবে, standard তা বলে না। ধাপে ধাপে দেখুন:

1std::vector<int> m{72, 0, 85, 0, 40};2auto it = std::remove(m.begin(), m.end(), 0);3m.erase(it, m.end());

এই দুই ধাপের জোড়াকে বলে erase-remove idiom, আর বহু বছর ধরে C++-এ এটি এক লাইনে লেখা হতো: m.erase(std::remove(m.begin(), m.end(), 0), m.end());. পুরো কাজটা এক পাসে, O(n). লুপের ভেতরে একটি একটি করে erase করলে প্রতিবার পেছনের সব উপাদান সরাতে হয় — সবচেয়ে খারাপ ক্ষেত্রে O(n²), সাথে iterator invalidation-এর ঝুঁকি।

C++20 থেকে কাজটি আরও সহজ: std::erase(m, 0); আর std::erase_if(m, pred); — পর্ব ১৩-এ দেখা std::erase_if. ভেতরে এরা ঠিক এই idiom-ই চালায়, আর মুছে ফেলা উপাদানের সংখ্যাও ফেরত দেয়। নতুন কোডে এটিই লিখুন; কিন্তু idiom-টি চিনে রাখুন, কারণ পুরোনো কোড আর AI-এর কোডে এটি সব জায়গায় পাবেন — অনেক সময় ভুলভাবে, erase ছাড়া।

unique — শুধু পাশাপাশি duplicate

std::unique-ও remove-এর মতো কাজ করে: পরপর বসা একই মানের উপাদানের মধ্যে প্রথমটি রেখে বাকিগুলো সামনে থেকে সরিয়ে দেয়, আর নতুন শেষ ফেরত দেয়। “পরপর” শব্দটি জরুরি — 3 1 3-এ দুটি 3 পাশাপাশি নয়, তাই কোনোটাই বাদ যাবে না। পুরো তালিকা থেকে duplicate সরাতে তাই প্রচলিত তিন ধাপ: আগে sort, তারপর unique, তারপর erase:

std::sort(rolls.begin(), rolls.end());                          // 3 1 3 2  -> 1 2 3 3
rolls.erase(std::unique(rolls.begin(), rolls.end()), rolls.end()); // -> 1 2 3

৫ · সাজানো — sort, stable_sort, partial_sort আর comparator-এর নিয়ম

std::sort সবচেয়ে বেশি ব্যবহৃত algorithm. ডিফল্টভাবে < দিয়ে ছোট থেকে বড় সাজায়। বড় থেকে ছোট চাইলে একটি comparator দিন:

std::sort(m.begin(), m.end());                         // 28 40 72 ... (ছোট থেকে বড়)
std::sort(m.begin(), m.end(), std::greater<>{});       // 85 85 72 ... (বড় থেকে ছোট)
std::sort(s.begin(), s.end(),                          // struct হলে: কোন ফিল্ড দেখে?
          [](const Student& a, const Student& b) { return a.marks > b.marks; });

comparator-এর একটিই নিয়ম — strict weak ordering

comparator যেকোনো bool-ফেরত ফাংশন হতে পারে না। standard চায় এটি একটি strict weak ordering হোক। শুনতে ভারী, কিন্তু ব্যবহারিক অর্থ সহজ — comparator comp(a, b) যেন “a কঠোরভাবে b-এর আগে” প্রশ্নের উত্তর দেয়:

• নিজের আগে কেউ নয়: comp(a, a) সবসময় false.
• দুজন দুজনের আগে নয়: comp(a, b) সত্য হলে comp(b, a) মিথ্যা।
• ক্রম ছড়ায়: a আগে b, আর b আগে c হলে, a আগে c.
• “সমান”-ও ছড়ায়: কেউ কারও আগে নয় এমন জোড়াকে সমান (equivalent) ধরা হয়; a ≡ b আর b ≡ c হলে a ≡ c.

< আর > এই নিয়ম মানে। <= আর >= মানে না, কারণ a <= a সত্য — প্রথম নিয়মই ভেঙে যায়। দেখতে নিরীহ এই ভুলের ফল undefined behavior: বাস্তবে কিছু বাস্তবায়নে std::sort range-এর সীমা পেরিয়ে মেমরি পড়তে শুরু করে, আর বড় ইনপুটে প্রোগ্রাম crash করে — ছোট পরীক্ষায় হয়তো ঠিকঠাক চলবে, তাই ধরা পড়ে দেরিতে। একই কারণে double-এর তালিকায় NaN থাকলে সাধারণ <-ও নিয়ম ভাঙে (NaN কারও সাথে তুলনায় সত্য দেয় না, ফলে “সমান” আর ছড়ায় না)। এ নিয়ে ভাবনার প্রশ্ন ০৪-এ বিস্তারিত।

stable_sort — সমানদের পুরোনো ক্রম রাখা

মেধাতালিকা বানানোর সময় নিয়ম অনেক সময় এমন: “নম্বর অনুযায়ী সাজাও; নম্বর সমান হলে রোল নম্বরের ক্রম যেমন ছিল, তেমন থাকবে।” তালিকাটি যদি আগে থেকেই রোল অনুযায়ী সাজানো থাকে, তাহলে দরকার এমন sort, যা সমান উপাদানগুলোর আপেক্ষিক ক্রম বদলায় না। একে বলে stable sort. std::sort এর নিশ্চয়তা দেয় না; std::stable_sort দেয়। পার্থক্যটি ধাপে ধাপে দেখুন:

roll 1  Rafi    72
roll 2  Mita    85
roll 3  Sabbir  40
roll 4  Nusrat  85
roll 5  Tanvir  28
roll 6  Joya    72

comparator:  a.marks > b.marks   (বড় নম্বর আগে)

Nusrat  85   (roll 4)   ┐ সমান নম্বর — ক্রম
Mita    85   (roll 2)   ┘ উল্টে যেতে পারে
Joya    72   (roll 6)   ┐ এখানেও
Rafi    72   (roll 1)   ┘
Sabbir  40
Tanvir  28
নম্বরের ক্রম ঠিক; সমানদের ক্রম standard বলে না

Mita    85   (roll 2)   ┐ রোল 2 আগে, 4 পরে —
Nusrat  85   (roll 4)   ┘ ইনপুটে যেমন ছিল
Rafi    72   (roll 1)   ┐ রোল 1 আগে, 6 পরে
Joya    72   (roll 6)   ┘
Sabbir  40
Tanvir  28

পথ ১: ইনপুট রোল অনুযায়ী আছে  =>  stable_sort(by marks)

পথ ২: যেকোনো ইনপুট  =>  sort, tie ভাঙা comparator দিয়ে
  if (a.marks != b.marks) return a.marks > b.marks;
  return a.roll < b.roll;

কৌশল: আগে গৌণ চাবি দিয়ে সাজান, তারপর মুখ্য চাবি দিয়ে stable_sort

এবার পুরো ফলাফল-শিটটি একটি প্রোগ্রামে: কতজন পাস (count_if), গড় (accumulate), আর মেধাতালিকা (stable_sort) — একটিও হাতে লেখা হিসাবের লুপ নেই:

#include <algorithm>
#include <numeric>
#include <print>
#include <string>
#include <vector>

struct Student { int roll; std::string name; int marks; };

int main() {
    std::vector<Student> v{{1, "Rafi", 72}, {2, "Mita", 85}, {3, "Sabbir", 40},
                           {4, "Nusrat", 85}, {5, "Tanvir", 28}, {6, "Joya", 72}};
    auto pass = std::count_if(v.begin(), v.end(),
                              [](const Student& s) { return s.marks >= 33; });
    double sum = std::accumulate(v.begin(), v.end(), 0.0,
                     [](double acc, const Student& s) { return acc + s.marks; });
    std::stable_sort(v.begin(), v.end(),
                     [](const Student& a, const Student& b) { return a.marks > b.marks; });
    std::println("pass {} of {}, average {:.2f}", pass, v.size(), sum / v.size());
    for (const auto& s : v) std::println("{:<7} roll {}  {}", s.name, s.roll, s.marks);
}

পুরোটা সাজানোর দরকার নেই — partial_sort আর nth_element

ধরুন এক লাখ পরীক্ষার্থীর মধ্যে শুধু সেরা তিনজনকে পুরস্কার দেবেন। পুরো তালিকা সাজানো অপচয়। std::partial_sort শুধু প্রথম k টি ঘর সাজানো অবস্থায় ভরে, বাকিগুলো যেকোনো ক্রমে ফেলে রাখে — খরচ মোটামুটি n log k, যেখানে পুরো sort-এ n log n. আর শুধু “মাঝের মান” (median) বা “১০০তম স্থান কত নম্বরে” জানতে চাইলে std::nth_element: n-তম ঘরে ঠিক সেই উপাদান বসায়, যা পুরো sort করলে সেখানে বসত, আর তার বাঁয়ে সব ছোট-বা-সমান, ডানে সব বড়-বা-সমান রাখে — গড়ে মাত্র O(n).

std::partial_sort(v.begin(), v.begin() + 3, v.end(),    // সেরা ৩ জন, সাজানো
                  [](const Student& a, const Student& b) { return a.marks > b.marks; });

auto mid = m.begin() + m.size() / 2;
std::nth_element(m.begin(), mid, m.end());               // *mid = median (বিজোড় n হলে)
bool ok = std::is_sorted(m.begin(), m.end());            // সাজানো আছে কি?

৬ · সাজানো ডেটায় খোঁজা, set-এর হিসাব আর min/max

সাজানো তালিকায় এক এক করে খোঁজার দরকার নেই — অভিধানে শব্দ খোঁজার মতো মাঝখানে খুলে দেখুন, শব্দটি আগে না পরে, তারপর অর্ধেক বাদ। প্রতি ধাপে খোঁজার জায়গা অর্ধেক হয়, তাই দশ লাখ উপাদানেও মোটামুটি ২০টি তুলনাই যথেষ্ট। এটি binary search, আর STL-এ এর একটি পুরো পরিবার আছে:

std::lower_bound সবচেয়ে কাজের — এটি ধাপে ধাপে কীভাবে অর্ধেক অর্ধেক করে খোঁজে, দেখুন। প্রশ্ন: সাজানো তালিকায় 55 নেই, তাহলে কোথায় বসত?

1std::vector<int> v{10, 20, 30, 40, 50, 60, 70, 80};2auto it = std::lower_bound(v.begin(), v.end(), 55);3// it - v.begin() == 5,  *it == 60

সাজানো তালিকায় সমান মানের সব উপাদান পাশাপাশি থাকে, তাই std::equal_range এক ডাকে তাদের শুরু আর শেষ দুটোই দেয়: auto [lo, hi] = std::equal_range(m.begin(), m.end(), 85); — তারপর hi - lo হলো কতজন 85 পেয়েছে।

set-এর হিসাব — সাজানো দুই তালিকায়

দুটি সাজানো রোল-তালিকা — ক্রিকেট দলের আর বিতর্ক ক্লাবের। কারা দুটোতেই আছে? set operation-এর algorithm দুই তালিকা একসাথে একবার হেঁটে উত্তর দেয়, খরচ O(n + m):

std::vector<int> cricket{2, 5, 7, 9}, debate{1, 5, 9, 12}, both;
std::set_intersection(cricket.begin(), cricket.end(), debate.begin(), debate.end(),
                      std::back_inserter(both));   // both = 5 9
// আরও: set_union (যেকোনোটিতে), set_difference (প্রথমটিতে আছে, দ্বিতীয়টিতে নেই),
//       includes (দ্বিতীয়টির সব কি প্রথমটিতে আছে?)

সবচেয়ে ছোট, সবচেয়ে বড়, আর সীমার ভেতরে রাখা

auto top = std::max_element(m.begin(), m.end());   // iterator! খালি হলে end()
auto [lo, hi] = std::minmax_element(m.begin(), m.end());  // এক পাসে দুটোই
int bigger = std::max(a, b);                        // দুটি মানের মধ্যে
auto [mn, mx] = std::minmax({a, b, c});             // initializer_list: মান ফেরত
int pct = std::clamp(raw, 0, 100);                  // C++17: 0-এর নিচে 0, 100-এর ওপরে 100

লক্ষ করুন, min_element / max_element মান নয়, iterator ফেরত দেয় — যাতে আপনি জানতে পারেন কোথায় আছে (কোন শিক্ষার্থী সর্বোচ্চ)। খালি range-এ এরা end() দেয়, আর তখন *top লেখা undefined behavior. std::clamp একটি মানকে সীমার ভেতরে টেনে আনে; শর্ত হলো নিচের সীমা ওপরেরটির চেয়ে বড় হবে না। আর একটি সূক্ষ্ম ফাঁদ: দুই-argument-এর std::minmax(a, b) মান নয়, reference-এর জোড়া ফেরত দেয় — temporary দিয়ে ডাকলে (std::minmax(f(), g())) সেই reference ঝুলে যায় (পর্ব ১৮)। initializer_list রূপ std::minmax({...}) মান কপি করে দেয়, তাই নিরাপদ।

৭ · হিসাবের algorithm — <numeric>, accumulate-এর ফাঁদ আর shuffle

std::accumulate একটি শুরুর মান নিয়ে range-এর সব উপাদান বাঁ থেকে ডানে একে একে তার সাথে জুড়ে দেয়। ডিফল্টভাবে “জোড়া” মানে +; চতুর্থ argument দিলে অন্য যেকোনো নিয়ম। একটি অনলাইন দোকানের কার্ট ধরুন — প্রতিটি পণ্যের দাম আর পরিমাণ দুটি আলাদা তালিকায়। transform দিয়ে প্রতিটি লাইনের দাম, remove + erase দিয়ে শূন্য লাইন বাদ, আর accumulate দিয়ে মোট:

#include <algorithm>
#include <numeric>
#include <print>
#include <vector>

int main() {
    std::vector<int> price{120, 45, 300, 80};            // taka per item
    std::vector<int> qty{2, 0, 1, 3};
    std::vector<int> line(price.size());
    std::transform(price.begin(), price.end(), qty.begin(), line.begin(),
                   [](int p, int q) { return p * q; });  // 240 0 300 240
    auto it = std::remove(line.begin(), line.end(), 0);
    std::println("after remove: size {}", line.size());
    line.erase(it, line.end());
    std::println("after erase:  size {}", line.size());
    std::println("total = {} taka", std::accumulate(line.begin(), line.end(), 0));

    std::vector<double> kg{0.5, 1.25, 2.0};
    std::println("weight: int init {} vs double init {}",
                 std::accumulate(kg.begin(), kg.end(), 0),
                 std::accumulate(kg.begin(), kg.end(), 0.0));
}

কেন 3? — শুরুর মানই ফলের টাইপ

accumulate-এর ভেতরের যোগফল-ভ্যারিয়েবলের টাইপ ঠিক হয় শুরুর মান দেখে, উপাদান দেখে নয়। 0 একটি int, তাই প্রতিটি ধাপে int + double-এর ফল আবার একটি int-এ রাখা হয় — দশমিক অংশ কেটে বাদ। ধাপে ধাপে দেখুন:

1std::vector<double> kg{0.5, 1.25, 2.0};2auto a = std::accumulate(kg.begin(), kg.end(), 0);    // T = int3auto b = std::accumulate(kg.begin(), kg.end(), 0.0);  // T = double

একই কারণে অনেক বড় int যোগ করতে 0 দিলে যোগফল int-এর সীমা পেরিয়ে overflow হতে পারে; তখন 0LL দিন, যাতে যোগফল long long-এ থাকে।

accumulate-এর আত্মীয়রা

std::vector<int> runs{6, 4, 9, 12, 3};          // প্রতি ওভারে রান
std::vector<int> score(runs.size());
std::partial_sum(runs.begin(), runs.end(), score.begin());  // 6 10 19 31 34

std::vector<int> roll(5);
std::iota(roll.begin(), roll.end(), 1);          // 1 2 3 4 5 — ক্রমিক নম্বর

int total = std::reduce(runs.begin(), runs.end(), 0);   // C++17: ক্রম না মেনেও যোগ করতে পারে

std::partial_sum চলতি যোগফল বানায় — প্রতি ওভারের রান থেকে প্রতি ওভার শেষের মোট স্কোর, বা প্রতিদিনের লেনদেন থেকে প্রতিদিন শেষের ব্যালান্স। std::iota একটি range-কে শুরুর মান থেকে একে একে বাড়িয়ে ভরে — রোল নম্বর বা index-এর তালিকা বানাতে কাজে লাগে (পর্ব ৮-এর std::views::iota-র মতো, কিন্তু এটি সত্যিই ঘরগুলোতে লেখে)। std::reduce (C++17) দেখতে accumulate-এর মতো, কিন্তু standard তাকে উপাদানগুলো যেকোনো ক্রমে, যেকোনো দলে ভাগ করে জোড়ার অনুমতি দেয়। তাই একে সমান্তরালে চালানো যায়, কিন্তু অপারেশনটি associative আর commutative হতে হয় (যেমন পূর্ণসংখ্যার যোগ)। double-এর যোগে ক্রম বদলালে শেষ দশমিক ঘরে ফল একটু বদলাতে পারে — বাঁ থেকে ডানে নিশ্চিত ক্রম চাইলে accumulate.

shuffle — এলোমেলো, কিন্তু নিয়ন্ত্রিত

পরীক্ষার হলে আসন এলোমেলো করতে, বা কুইজের প্রশ্নের ক্রম বদলাতে std::shuffle. এটি একটি random-number engine নেয়, যেমন std::mt19937:

#include <random>
std::mt19937 rng(2026);                          // নির্দিষ্ট seed: প্রতিবার একই ক্রম
std::shuffle(seats.begin(), seats.end(), rng);

seed নির্দিষ্ট রাখলে প্রতিবার প্রোগ্রাম চালালে একই “এলোমেলো” ক্রম আসে — টেস্ট লেখা আর বাগ আবার ঘটিয়ে দেখার জন্য এটা অমূল্য। আসল ব্যবহারে seed নিন std::random_device থেকে (পর্ব ৪১)। একটি সূক্ষ্ম কথা: mt19937-এর সংখ্যার ধারা standard নির্দিষ্ট করে দেয়, কিন্তু shuffle সেই সংখ্যাগুলো কীভাবে ব্যবহার করবে তা নির্দিষ্ট নয় — তাই একই seed-এ GCC আর MSVC ভিন্ন ক্রম দিতে পারে। আর পুরোনো std::random_shuffle C++14-এ deprecated হয়ে C++17-এ বাদ পড়েছে; পুরোনো কোড বা AI-এর উত্তরে দেখলে বদলে দিন।

৮ · খরচের নিশ্চয়তা, parallel policy আর ranges-এর ঝলক

হাতে লেখা লুপ কত দ্রুত, তা জানতে কোড পড়ে হিসাব করতে হয়। STL algorithm-এর ক্ষেত্রে উত্তর standard-এই লেখা আছে — প্রতিটি algorithm-এর পাশে লেখা থাকে সর্বোচ্চ কতবার তুলনা বা অপারেশন হবে। এটি একটি চুক্তি: যে লাইব্রেরি এর বেশি নেয়, সে standard মানে না (Big-O-র কথা পর্ব ৮-এ)।

একটি সূক্ষ্মতা: lower_bound std::list-এও চলে, আর তুলনা তখনো O(log n) টিই হয় — কিন্তু list-এ মাঝখানে লাফ দেওয়া যায় না, iterator এক এক ঘর হাঁটে, তাই মোট সময় O(n). complexity বুঝতে iterator-এর ধরনও (পর্ব ৩২) দেখতে হয়।

parallel execution policy — এক শব্দে সমান্তরাল

C++17 থেকে অনেক algorithm-এর প্রথম argument হিসেবে একটি execution policy দেওয়া যায় (<execution> header):

#include <execution>
std::sort(std::execution::par, v.begin(), v.end());   // একাধিক thread-এ সাজানোর অনুমতি
auto s = std::reduce(std::execution::par, v.begin(), v.end(), 0LL);

seq মানে সাধারণ ক্রমিক, par মানে একাধিক thread, par_unseq মানে thread-এর সাথে vector instruction-ও (আর C++20-এ এসেছে শুধু unseq). policy একটি অনুমতি, আদেশ নয় — লাইব্রেরি চাইলে ক্রমিকভাবেই চালাতে পারে। GCC-তে আসল সমান্তরাল চালাতে সাধারণত Intel-এর TBB লাইব্রেরি যুক্ত করতে হয় (-ltbb). আর দায়িত্ব আপনার: আপনার lambda যেন একই ডেটায় একসাথে লিখে data race না বাঁধায় (পর্ব ৪৫)। ছোট vector-এ thread চালুর খরচই বেশি পড়ে; মেপে দেখেই ব্যবহার করুন (পর্ব ৪৯)।

ranges সংস্করণ — begin/end আর লিখতে হয় না

C++20-এ প্রায় সব algorithm-এর একটি std::ranges:: সংস্করণ এসেছে, যা পুরো container সরাসরি নেয়:

std::ranges::sort(m);                                         // begin/end ছাড়াই
auto pass = std::ranges::count_if(m, [](int x) { return x >= 33; });
std::ranges::sort(students, std::greater{}, &Student::marks); // projection: কোন ফিল্ড দেখে

std::ranges::sort-এর শেষ উদাহরণে তৃতীয় argument একটি projection: “তুলনার আগে প্রতিটি Student থেকে marks বের করে নাও।” আর lambda লিখতে হয় না। ranges সংস্করণ concepts দিয়ে ভুল টাইপ compile-এর সময়েই ধরে, আর begin একটির আর end আরেকটির — এমন ভুলের সুযোগই রাখে না। views আর pipeline (|) নিয়ে পুরো আলোচনা পর্ব ৩৫-এ।

৯ · AI-এর যুগে — লুপ আর algorithm-এর ভুল ধরা

AI টুলকে “নম্বরের তালিকা থেকে পাসের সংখ্যা বের করো” বললে প্রায়ই একটি হাতে লেখা index-লুপ আসে — কারণ অনলাইনের বিপুল শিক্ষামূলক কোড এভাবেই লেখা। উল্টো দিকে, algorithm ব্যবহার করলেও AI প্রায়ই পূর্বশর্তগুলো ভুলে যায়, কারণ সেগুলো কোডে দেখা যায় না — ডকুমেন্টেশনে লেখা থাকে। ভুলগুলো প্রায় সবই compile হয়, আর ছোট পরীক্ষায় ঠিকঠাক চলে। সাধারণ ভুলগুলো:

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

• প্রতিটি হাতে লেখা লুপের জন্য জিজ্ঞেস করেছি — এর কোনো নাম আছে কি (count_if, find_if, any_of, transform…)?
• remove/remove_if/unique-এর পরে erase আছে, অথবা std::erase_if ব্যবহার হয়েছে
• প্রতিটি accumulate/reduce-এর শুরুর মানের টাইপ ফলের টাইপের সাথে মেলে (0.0, 0LL)
• প্রতিটি comparator “কঠোরভাবে ছোট” — <=/>= নেই; সমানে ক্রম জরুরি হলে stable_sort বা tie-ভাঙা comparator
• binary_search/lower_bound-এর আগে range সাজানো, আর একই comparator-এ
• ফেরত পাওয়া iterator end()-এর সাথে মিলিয়ে তবেই dereference; খালি তালিকা দিয়ে নিজে চালিয়ে দেখেছি