template-এর ধারণা: একটা function, সব type-এর জন্য

গত term-এ Amara-র তিনবার দুইটা সংখ্যার বড়টা লেগেছিল: নম্বরের জন্য, দামের জন্য, আর দূরত্বের জন্য। তাই ও লিখেছিল max_int, max_double আর max_ll, একই body-র তিনটা function। C++-এ ও লেখে std::max, আর body একবারও লিখতে হয় না। এর পেছনের কৌশলটার নাম template, আর এই track-এর প্রতিটা container আর algorithm আসলে একেকটা template।

C-তে তিনটা max function, C++-এ একটা

C-র পথটা এরকম। Body-গুলো হুবহু এক; তফাত শুধু type-এ, আর C-র প্রতিটার জন্য আলাদা নাম লাগে।

#include <stdio.h>

int max_int(int a, int b)
{
    return a > b ? a : b;
}

double max_double(double a, double b)
{
    return a > b ? a : b;
}

long long max_ll(long long a, long long b)
{
    return a > b ? a : b;
}

int main(void)
{
    printf("%d\n", max_int(3, 7));
    printf("%.2f\n", max_double(2.5, 1.25));
    printf("%lld\n", max_ll(4000000000LL, 3000000000LL));
    return 0;
}

7
2.50
4000000000

আর এই হলো C++, সবগুলোর জন্য একটাই নাম, string সহ।

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::cout << std::max(3, 7) << '\n';
    std::cout << std::max(2.5, 1.25) << '\n';
    std::cout << std::max(4000000000LL, 3000000000LL) << '\n';
    std::cout << std::max(std::string("pear"), std::string("apple")) << '\n';
    return 0;
}

7
2.5
4000000000
pear

std::max থাকে <algorithm> header-এ। দুইটা string পেলে এটা ফেরত দেয় সেটা, যেটা অভিধানে পরে আসে, তাই "pear" জিতে যায় "apple"-এর বিপক্ষে। মানে একটাই নাম, std::max, তিনটা C function-এর কাজ করে, সাথে চতুর্থ একটা, যেটা C-তে ছিলই না।

Template মানে type-এর জায়গা ফাঁকা রাখা একটা রেসিপি

Template হলো একবার লেখা code, যেখানে type-এর জায়গাটা ফাঁকা রাখা। Standard library max লিখেছে এভাবে: "কোনো এক type T-এর দুইটা মান < দিয়ে তুলনা করো, বড়টা ফেরত দাও"। দুইটা int দিয়ে call করলে T-এর জায়গায় বসে int।

Function template-এর বেলায় compiler সাধারণত argument দেখে T বের করে নেয়, ওপরে যেমন হলো। Container-এর বেলায় type-টা তুমি নিজেই বলে দাও, angle bracket-এর ভিতরে। <...> পড়ো "দিয়ে ভরা" হিসেবে।

std::vector<int>                  a vector, filled in with int
std::vector<std::string>          a vector, filled in with string
std::map<std::string, int>        a map, filled in with string keys and int values
std::pair<std::string, int>       a pair, filled in with a string and an int
std::max(3, 7)                    max, with T worked out as int

তাই lesson 04-এ দেখা std::vector<long long> হলো একটা রেসিপি, "vector", একটা type দিয়ে ভরা, long long।

Template নিয়ে compiler কী করে

Template নিজে এমন code না যেটা machine চালাতে পারে। এটা একটা ছাঁচ: কোনো program প্রথমবার যখন একটা type চায়, compiler ফাঁকা জায়গা ভরে ছাঁচ থেকে একটা কপি তুলে নেয়। ভরা কপিটার নাম instantiation। int, double আর std::string-এ max চাও, compiler তিনটা সাধারণ function লিখে ফেলবে।

এটা কথার কথা না। Compiler Explorer-এ GCC 12 দিয়ে, optimisation বন্ধ রেখে (-O0), এমন একটা program compile করো যেটা ওই তিন type-এ std::max call করে। Assembly listing-এ তিনটা আলাদা function-এর নাম দেখবে: std::max<int>(int const&, int const&), std::max<double>(double const&, double const&), আর std::string-এর জন্য একটা। Playground-এর -O2-এ ওরা উধাও হয়ে যায়: প্রতিটা এত ছোট যে GCC 12 এদের body সরাসরি main-এর ভিতরে বসিয়ে দেয়।

Class template-ও একই নিয়মে চলে। std::vector<int> আর std::vector<std::string> হলো একই রেসিপি থেকে compiler-এর লেখা দুইটা আলাদা type। এরা মেশে না: একটাকে অন্যটায় assign করলে GCC 12 দেয় error: no match for 'operator=' (operand types are 'std::vector<int>' and 'std::vector<std::__cxx11::basic_string<char> >')। অদ্ভুত দেখতে std::__cxx11::basic_string<char> হলো GCC-র library-তে std::string-এর আসল নাম, আর অনেক বার্তায় এর সাথে দেখা হবে।

Scope নিয়ে একটা সৎ কথা। এই track template পড়ে আর ব্যবহার করে: প্রতিটা container, প্রতিটা algorithm। template শব্দ আর নিজের একটা T দিয়ে নিজের template লেখা C++ track-এর কাজ। তাই এই track-এ instantiation লেখে compiler, আর তোমার কাজ type বসানো আর তার বার্তা পড়া।

যেকোনো type-এ std::max, std::min আর std::swap

তিনটা ছোট template প্রায় প্রতিটা program-এ হাজির হয়। std::max আর std::min দুইটা মানের বড় আর ছোটটা ফেরত দেয়। std::swap দুইটা variable-এর মান বদলাবদলি করে, reference দিয়ে, ঠিক lesson 03-এর Maria-র swapRef-এর মতো।

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    int a = 4;
    int b = 9;
    std::cout << "max " << std::max(a, b) << ", min " << std::min(a, b) << '\n';
    std::cout << "max of three " << std::max({a, b, 2}) << '\n';

    std::swap(a, b);
    std::cout << "after swap: a = " << a << ", b = " << b << '\n';

    std::string first = "Kenji";
    std::string second = "Amara";
    std::swap(first, second);
    std::cout << first << ' ' << second << '\n';
    return 0;
}

max 9, min 4
max of three 9
after swap: a = 9, b = 4
Amara Kenji

তিনটারই একটা করে নিয়ম আছে। std::max আর std::min-এর লাগে একই type-এর দুইটা মান, যেগুলো < দিয়ে তুলনা করা যায়। দুইটার বেশি হলে braces-এ রাখো: std::max({a, b, 2}) পুরো একটা list নেয়। std::swap-এর লাগে একই type-এর দুইটা variable, কখনো খালি একটা সংখ্যা না, কারণ এটা reference দিয়ে লেখে।

মানে একটা template call int, double, std::string, আর < আছে এমন যেকোনো type-এ চলে, আর যে version লাগবে সেটা compiler লিখে দেয়।

Template error পড়া: আসল লাইনটা একটাই

Template call-এর ভিতরে একটা ভুল হলে GCC 12 একটা error-এর জন্য কয়েক ডজন লাইন print করতে পারে। এগুলো কয়েক ডজন সমস্যা না। Compiler সে function-এর যত version চেষ্টা করেছে, আর প্রতিটা কেন খাটল না, সেটার তালিকা দিচ্ছে। কী ভুল, সেটা বলে এক বা দুইটা লাইন, বাকিটা খোঁজাখুঁজির হিসাব।

সেগুলো খুঁজে পাওয়ার নিয়মের তিনটা ধাপ।

1. তোমার file-এর নাম আছে আর error: লেখা আছে, এমন প্রথম লাইনটা খোঁজো। Compiler-এর নিজের folder-এর file (যে path-এর শেষে bits/stl_algobase.h বা এরকম কিছু) হলো library, তুমি না।
2. প্রথম error: যদি library-র কোনো file-এ থাকে, তার ঠিক ওপরে required from here খোঁজো। এই কথাটা যে লাইনে আছে, সেটা তোমার file আর তোমার লাইনের নাম বলে।
3. যে note: সহজ কথায় একটা কারণ বলে, সেটা পড়ো: "deduced conflicting types", "no known conversion", "no match for 'operator<'"। যে note শুধু candidate-এর তালিকা দেয়, সেগুলো বাদ দাও।

নিচে তিনটা আসল error, প্রতিটাই Playground-এর command line, -O2 -std=c++17-এ GCC 12-এর। Compiler Explorer তোমার file-এর নাম দেয় <source>; compiler-এর নিজের file-গুলোর লম্বা path এখানে কেটে শেষ অংশটুকু রাখা হয়েছে।

Gallery 1: যেখানে একটা type লাগে, সেখানে দুইটা। Kenji একটা চলতি যোগফল রাখে long long-এ, আর চায় সেটা কখনো শূন্যের নিচে না নামুক।

long long total = 0;
long long best = std::max(total, 0);

GCC 12 print করে 30-এর বেশি লাইন। পড়ার মতো দুইটা:

<source>:7:30: error: no matching function for call to 'max(long long int&, int)'
<source>:7:30: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')

প্রথমটা call-টার নাম আর পাওয়া দুইটা type বলে। Note বলে কেন: _Tp হলো ফাঁকা জায়গাটার জন্য library-র দেওয়া নাম, আর সেটা একসাথে long long আর int হতে পারে না। সমাধান হলো দুইটাকে একই type বানানো: std::max(total, 0LL), যেখানে LL শূন্যটাকে long long বানায়।

Gallery 2: যে type-এর কোনো < নেই। Maria parcel-গুলো রাখে একটা C struct-এ, আর ভারী parcel-টা চায়।

struct Parcel {
    int weight;
    int price;
};

Parcel a = {3, 120};
Parcel b = {5, 80};
Parcel heavier = std::max(a, b);

GCC 12 print করে 40-এর বেশি লাইন, আর প্রথম error:-টাই library-র ভিতরে। ধাপ 2 তোমার লাইন খুঁজে দেয়:

.../bits/stl_algobase.h: In instantiation of 'constexpr const _Tp& std::max(const _Tp&, const _Tp&) [with _Tp = Parcel]':
<source>:13:30:   required from here
.../bits/stl_algobase.h:259:15: error: no match for 'operator<' (operand types are 'const Parcel' and 'const Parcel')

[with _Tp = Parcel] বলে কোন instantiation ভেঙেছে। required from here দেখিয়ে দেয় লাইন 13, তোমার call। Error বলে কারণ: std::max তুলনা করে < দিয়ে, আর parcel-এর জন্য "ছোট" মানে কী, কেউ বলে দেয়নি। ওজনে ভারী? নাকি দামে সস্তা? Compiler আন্দাজ করতে পারে না। যে field বোঝাতে চাও, সেটা তুলনা করো, std::max(a.weight, b.weight); algorithm-কে নিজের নিয়ম কীভাবে দিতে হয়, সেটা দেখাবে Module 12।

Gallery 3: container-এ ভুল type ঢোকানো। Bob নম্বরের একটা list-এ একটা নাম ঢুকিয়ে দেয়।

std::vector<int> marks = {70, 85};
std::string name = "Zara";
marks.push_back(name);

GCC 12 print করে 20-এর মতো লাইন। পড়ার মতো দুইটা:

<source>:9:20: error: no matching function for call to 'std::vector<int>::push_back(std::string&)'
.../bits/stl_vector.h:1276:35: note:   no known conversion for argument 1 from 'std::string' {aka 'std::__cxx11::basic_string<char>'} to 'const std::vector<int>::value_type&' {aka 'const int&'}

push_back শেষে একটা element যোগ করে (Module 2)। Note বলে, এটা চেয়েছিল একটা const int&, কারণ এই vector int দিয়ে ভরা, আর পেয়েছে একটা std::string। {aka ...} অংশগুলো library-র নামকে সাধারণ নামে অনুবাদ করে দেয়। সমাধান নির্ভর করে Bob আসলে কী চেয়েছিল তার ওপর: নামের জন্য আলাদা একটা vector, নাকি নাম আর নম্বরের একটা pair (lesson 06)।

মানে 50 লাইনের template error হলো একটা ভুল আর লম্বা একটা খোঁজাখুঁজি। তোমার file-এর প্রথম error:, বা library-র error-এর ওপরের required from here, সাথে কারণ বলা একটা note, ব্যস, এটুকু পড়লেই চলে।

#include <algorithm>
#include <iostream>

int main()
{
    int a = 0;
    int b = 0;
    std::cin >> a >> b;

    std::cout << "higher " << std::max(a, b) << ", lower " << std::min(a, b) << '\n';
    return 0;
}

higher 85, lower 72

#include <algorithm>
#include <iostream>

int main()
{
    int readings[3] = {25, -55, 70};

    for (int& t : readings) {
        t = std::min(std::max(t, -40), 60);
    }
    std::cout << readings[0] << ' ' << readings[1] << ' ' << readings[2] << '\n';
    return 0;
}

25 -40 60

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    int n = 0;
    std::cin >> n;

    std::string title;
    int price = 0;
    std::cin >> title >> price;

    std::string firstTitle = title;
    std::string lastTitle = title;
    int cheapest = price;
    int dearest = price;

    for (int i = 1; i < n; i++) {
        std::cin >> title >> price;
        firstTitle = std::min(firstTitle, title);
        lastTitle = std::max(lastTitle, title);
        cheapest = std::min(cheapest, price);
        dearest = std::max(dearest, price);
    }
    std::cout << "prices " << cheapest << " to " << dearest << '\n';
    std::cout << "titles " << firstTitle << " to " << lastTitle << '\n';
    return 0;
}

prices 120 to 450
titles Dracula to Ulysses

std::cout << std::max(a, b, c) << '\n';

std::vector v;

long long smallest = 5000000000LL;
smallest = std::min(smallest, 1000000000);

std::swap(a, 5);

#include <algorithm>
#include <iostream>

int main()
{
    double best = 4.5;
    best = std::max(best, 3.0);
    std::cout << best << '\n';
    return 0;
}

#include <algorithm>
#include <iostream>

int main()
{
    double a = 0;
    double b = 0;
    double c = 0;
    std::cin >> a >> b >> c;

    // Use std::min and std::max to find the fastest and the slowest lap.

    return 0;
}

#include <iostream>
#include <string>
#include <utility>

int main()
{
    std::string first;
    std::string second;
    std::cin >> first >> second;

    // The long way: swap first and second with a third string, then print.

    // The short way: swap them back with std::swap, then print again.

    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 0;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        std::string type;
        int k = 0;
        std::cin >> type >> k;

        // type is "int", "double" or "string". Read the k values into
        // variables of that type, keep the largest with std::max,
        // and print it on its own line.
    }
    return 0;
}

এরপর lesson 06 একটা template একসাথে দুইটা type দিয়ে ভরবে: std::pair, আর তার বড় ভাই std::tuple।