map: প্রতিটা key-এর সাথে একটা value, আর key-গুলো থাকে সাজানো

Kenji-র café-তে প্রতিবার আসার জন্য একটা করে loyalty stamp মেলে। কেউ এলেই counter-কে জানতে হয়, এই customer-এর এখন কয়টা stamp। দোকান বন্ধের সময় Kenji চায় প্রতিটা customer আর তার stamp, বর্ণমালার ক্রমে। (name, stamps) pair-এর একটা vector হলে প্রতিটা প্রশ্নে পুরো তালিকা ঘাঁটতে হয়, Module 2-এর find দিয়ে। এই lesson Kenji-কে এমন একটা container দেবে, যেটা customer আসতে আসতেই দুটো কাজ সেরে ফেলে।

Key আর ওর value

Map হলো pair-এর একটা container, Module 1-এর pair-এর মতো। প্রতিটা pair-এর প্রথম অংশ ওর key, যেটা ধরে তুমি খোঁজো: এখানে customer-এর নাম। দ্বিতীয় অংশ ওর value, key-এর সাথে যা থাকে: এখানে stamp-এর সংখ্যা। Map প্রতিটা key বড়জোর একবার রাখে, আর pair-গুলো সাজিয়ে রাখে key ধরে।

Array-ও "কয়টা stamp?" প্রশ্নের উত্তর দিতে পারে, তবে শুধু সংখ্যা দিয়ে: stamps[3], কখনো stamps["maria"] না। Map-এর key হতে পারে একটা নাম, একটা শব্দ, বা < দিয়ে তুলনা করা যায় এমন যেকোনো type। এই যে সাতবার আসার পরে Kenji-র stamp, দুইভাবে আঁকা।

দুইটা ছবিতেই একই ছয়টা pair। Table-টা হলো map-এর উপর দিয়ে হাঁটলে যা ফেরত আসে। Tree-টা হলো map ওদের আসলে কীভাবে রাখে, আর পরের অংশ সেটা খুলে দেখাবে। তাই stamps["bob"] হলো Bob-এর value, 2, আর key-এর ক্রমে Bob-এর pair বসে Amara আর David-এর মাঝখানে।

ভেতরে: Module 8-এর tree, প্রতিটা node-এ একটা pair

Module 8 set রেখেছিল একটা balanced binary search tree-তে, যেখানে খোঁজা নিচে নামে এক level করে। Map-ও সেই একই tree। তফাত শুধু node-এ কী থাকে: key আর ওর value একসাথে, একটা pair হিসেবে। Tree সাজানো শুধু key ধরে, আর value থাকে ওর সাথে সাথে।

C++ standard কোনো tree-র নাম বলে না। ও শুধু কথা দেয়, একটা key খোঁজা, যোগ করা বা erase করায় লাগবে O(log n) ধাপ, যেখানে n হলো key-এর সংখ্যা। GCC-র library, libstdc++, রাখে একটা red-black tree, set-এর বেলায় যেমন রাখে। এই module-এর ছবিগুলোতে রংগুলো বাদ দেওয়া। তাই নামগুলো সাজানো থাকে, কারণ tree-ই ওদের সাজিয়ে রাখে, শেষে কেউ sort করে বলে না।

Stamp-গুলো আসতে দেখো

এই যে Kenji-র প্রথম সকাল, প্রতিবার আসার জন্য একটা call: maria, bob, zara, kenji, আবার bob, amara আর david। তারপর counter find দিয়ে zara আর carol-কে খোঁজে, আর শেষে carol-কে পড়ে [] দিয়ে। প্রতিটা ছবি GCC 12-এর library-র বানানো আসল আকার, Compiler Explorer-এ একটা run থেকে print করা। Value-গুলো আছে note-এ, আর widget-এর নিচের table-এ।

Bob দ্বিতীয়বার আসায় পথটা ওর node পর্যন্ত নামল, আর বাড়ল শুধু ওর গোনাটা। find("carol") david-এর নিচে গিয়ে tree থেকে পড়ে গেল, কিছুই বদলাল না। শেষ ধাপটাই এই lesson-এর ফাঁদ: [] দিয়ে একবার পড়তেই carol যোগ হয়ে গেল 0টা stamp নিয়ে, আর জায়গা করতে tree ঘুরে গেল। তাই map বাড়ে শুধু নতুন key রাখলে, আর [] একটা key রেখে দেয়, তুমি শুধু পড়তে চাইলেও।

প্রথম দিনেই যে syntax লাগবে

#include <map>

map<K, V> m;                      an empty map from K keys to V values
map<K, V> m{{k1, v1}, {k2, v2}};  a map made from a list of pairs
m[k] = v;                         store v under k, or overwrite k's value
m[k]++;                           add 1 to k's value; a missing k starts at 0
m.count(k)                        1 if k is there, 0 if not; adds nothing
m.find(k)                         an iterator to k's pair, or m.end()
it->first   it->second            the key and the value of that pair
m.erase(k);                       remove k and its value, if k is there
m.size()                          how many keys
for (const auto& [k, v] : m)      every pair, in key order

multimap<K, V> mm;                the same, but a key may repeat; no []

তাই রোজকার map-এর code প্রতিবার একটা key-এর নাম বলে, আর pair কোথায় থাকবে, সেটা map নিজেই ঠিক করে।

m[k] value রাখে, আর না থাকা key শুরু হয় শূন্য থেকে

m[k] = v k-এর নিচে v রাখে। k নতুন হলে map আগে ওকে যোগ করে value type-এর শূন্য দিয়ে, C++-এ যেটা লেখা হয় V()। এই শূন্য একটা int-এর জন্য 0, আর একটা string-এর জন্য খালি string। তারপর = ওই শূন্যের উপর লিখে দেয়। m[k]++ আর m[k] += 2-ও একইভাবে কাজ করে, তাই গোনার আগে কিছুই সাজিয়ে নিতে হয় না।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps;
    stamps["maria"] = 3;
    stamps["bob"]++;
    stamps["bob"]++;
    stamps["maria"] += 2;
    cout << "maria " << stamps["maria"] << ", bob " << stamps["bob"] << '\n';

    map<string, string> note;
    note["kenji"] += "tea";
    note["kenji"] += ", no sugar";
    cout << "kenji: " << note["kenji"] << '\n';
    cout << stamps.size() << " customers, " << note.size() << " note\n";
    return 0;
}

maria 5, bob 2
kenji: tea, no sugar
2 customers, 1 note

Bob-এর প্রথম ++ কোনো bob পায়নি, তাই map ওকে 0 দিয়ে যোগ করে 1-এ তুলল। Kenji-র note শুরু হয়েছিল একটা খালি string হিসেবে, আর += শব্দগুলো ওতে জুড়ে দিল। দুইজন customer, একটা note: যতবারই ছোঁয়া হোক, প্রতিটা key যোগ হয়েছে একবারই। তাই m[k]++ নিজেই গোনার পুরো program, কোনো check বা শুরুর মান ছাড়াই।

count আর find: কিছু যোগ না করে দেখা

m.count(k) বলে k key-ওয়ালা কয়টা pair আছে, আর map-এ সেটা 1 বা 0। m.find(k) ফেরত দেয় k-এর pair-এর দিকে একটা iterator, আর k না থাকলে m.end()। ওই iterator দিয়ে it->first হলো key, আর it->second হলো value। এদের কোনোটাই কখনো key যোগ করে না।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps{{"bob", 2}, {"maria", 5}, {"zara", 1}};
    cout << stamps.count("zara") << ' ' << stamps.count("kenji") << '\n';

    auto it = stamps.find("maria");
    if (it != stamps.end()) {
        cout << it->first << " has " << it->second << " stamps\n";
    }
    if (stamps.find("kenji") == stamps.end()) {
        cout << "kenji is not a customer yet\n";
    }
    cout << "still " << stamps.size() << " customers\n";
    return 0;
}

1 0
maria has 5 stamps
kenji is not a customer yet
still 3 customers

দুইবার kenji-কে নিয়ে জিজ্ঞেস করার পরেও map-এ customer 3 জনই। it->second পড়ার আগে find-এর উত্তর end()-এর সাথে মিলিয়ে নাও; end() পড়লে একবার চালাতে কী print হয়েছিল, দেখাবে lesson 02। তাই সোজা হ্যাঁ বা না-এর জন্য count নাও, আর value-টাও লাগলে find।

ফাঁদ: m[k] পড়লেই k যোগ হয়ে যায়

m[k] পড়া আর লেখার তফাত বোঝে না। k না থাকলে ও আগে k-কে শূন্য value দিয়ে যোগ করে, একটা cout-এর ভিতরে হলেও। তাই যে map তুমি শুধু পড়ছ, সেটাও বেড়ে যেতে পারে।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps{{"bob", 2}, {"maria", 5}};
    cout << "size before: " << stamps.size() << '\n';
    cout << "carol has " << stamps["carol"] << " stamps\n";
    cout << "size after:  " << stamps.size() << '\n';
    cout << "count(\"carol\") is now " << stamps.count("carol") << '\n';
    return 0;
}

size before: 2
carol has 0 stamps
size after:  3
count("carol") is now 1

একবার পড়তেই print হলো বিশ্বাস করার মতো একটা 0, আর carol চিরদিনের জন্য যোগ হয়ে গেল। Size 2 থেকে 3 হলো, আর count এখন ওকে খুঁজে পায়। Kenji-র দিনশেষের তালিকায় থাকত এমন একজন customer, যে কখনো আসেইনি। তাই শুধু জিজ্ঞেস করতে চাইলে জিজ্ঞেস করো count বা find দিয়ে।

Key-এর ক্রমে হাঁটা

একটা range-for map-এর উপর দিয়ে হাঁটে সবচেয়ে ছোট key থেকে সবচেয়ে বড় key পর্যন্ত, একবারে একটা pair। প্রতিটা pair-এর দুইটা অংশ: p.first, মানে key, আর p.second, মানে value। Module 1-এর structured binding দুই অংশেরই একসাথে নাম দেয়, তাই [name, count] পড়তে .first আর .second-এর চেয়ে সহজ।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps;
    stamps["zara"] = 1;
    stamps["amara"] = 4;
    stamps["kenji"] = 2;

    for (const auto& p : stamps) {
        cout << p.first << ": " << p.second << '\n';
    }

    cout << "again:";
    for (const auto& [name, count] : stamps) {
        cout << ' ' << name << '=' << count;
    }
    cout << '\n';
    return 0;
}

amara: 4
kenji: 2
zara: 1
again: amara=4 kenji=2 zara=1

Key-গুলো ঢুকেছিল zara, amara, kenji ক্রমে, আর দুই loop-এই বেরোল বর্ণমালার ক্রমে। const auto& প্রতিটা pair যেখানে আছে সেখানেই পড়ে, copy না করে। তাই map-এর উপর দিয়ে প্রতিটা হাঁটাই key-এর ক্রমে হাঁটা।

Key ধরে erase

m.erase(k) k-কে ওর value-সহ সরিয়ে দেয়, আর ফেরত দেয় কয়টা pair সরাল। Map-এ সেটা 1 বা 0। নেই এমন key erase করলে কিছুই হয় না, কোনো error-ও না।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps{{"bob", 2}, {"maria", 5}, {"zara", 1}};
    cout << "erase(\"bob\") removed " << stamps.erase("bob") << '\n';
    cout << "erase(\"carol\") removed " << stamps.erase("carol") << '\n';
    for (const auto& [name, count] : stamps) {
        cout << name << ' ' << count << '\n';
    }
    return 0;
}

erase("bob") removed 1
erase("carol") removed 0
maria 5
zara 1

Bob-এর pair চলে গেছে, হাঁটার সময় ওকে আর পাওয়া যায় না। আর carol-এর বেলায় 0 বলছে, ও কখনো ছিলই না। তাই নেই এমন key erase করা নিরাপদ, আর ওর উত্তরই বলে দেয় কিছু গেল কি না।

প্রতিটা key একবারই

Map কখনো একই key-এর দুইটা pair রাখে না। দ্বিতীয় m[k] = v প্রথম pair-টা খুঁজে পায় আর ওর value-র উপর লিখে দেয়। তাই সবচেয়ে নতুন লেখাটাই টিকে থাকে।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, string> phone;
    phone["maria"] = "555-0101";
    phone["bob"] = "555-0102";
    phone["maria"] = "555-0188";
    cout << phone.size() << " names\n";
    for (const auto& [name, number] : phone) {
        cout << name << ": " << number << '\n';
    }
    return 0;
}

2 names
bob: 555-0102
maria: 555-0188

Maria-র পুরোনো নম্বর আর নেই, আর map-এ নাম এখনো দুইটাই। তাই map মানায় সেই কাজে, যেখানে প্রতিটা key-এর একটাই চলতি value, যেমন বদলে যাওয়া একটা ফোন নম্বর।

multimap: যে map বারবার আসা key-ও রাখে

কখনো কখনো একটা key-এর কয়েকটা value লাগে: Bob-এর একটা বাসার নম্বর আছে, একটা অফিসের নম্বরও আছে। Multimap প্রতিটা pair রাখে, বারবার আসা key-সহ, তবু key ধরে সাজিয়ে। একই header-এ থাকে, আর insert, count, find আর erase-ও একই। ওর count(k) বলে k key-ওয়ালা কয়টা pair আছে।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    multimap<string, string> phones;
    phones.insert({"bob", "555-0102"});
    phones.insert({"maria", "555-0101"});
    phones.insert({"bob", "555-0177"});
    for (const auto& [name, number] : phones) {
        cout << name << ": " << number << '\n';
    }
    cout << "bob has " << phones.count("bob") << " numbers, " << phones.size() << " in all\n";
    return 0;
}

bob: 555-0102
bob: 555-0177
maria: 555-0101
bob has 2 numbers, 3 in all

Bob-এর দুইটা নম্বরই রইল, পাশাপাশি, যে ক্রমে এসেছিল সেই ক্রমে। Multimap-এ কোনো [] নেই, কারণ phones["bob"] বুঝতেই পারত না, Bob-এর কোন নম্বরের কথা বলছ।

multimap<string, string> phones;
phones["bob"] = "555-0102";

Runner-এর flag-এ GCC 12 থেমে যায় error: no match for 'operator[]' (operand types are 'std::multimap<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> >' and 'const char [4]') দিয়ে। Lesson 02 দেখাবে equal_range, যেটা একটা key-এর প্রতিটা value তোমার হাতে দেয়। তাই একটা key-এর কয়েকটা value লাগলে multimap নাও, আর একটা হলেই চললে map।

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> price;
    price["mango"] = 120;
    price["banana"] = 60;
    price["apple"] = 180;
    price["guava"] = 80;

    cout << price.size() << " fruits on the board:\n";
    for (const auto& [fruit, taka] : price) {
        cout << fruit << ' ' << taka << '\n';
    }
    return 0;
}

4 fruits on the board:
apple 180
banana 60
guava 80
mango 120

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps;
    for (string name : {"maria", "bob", "zara", "kenji", "bob", "amara", "david"}) {
        stamps[name]++;
    }

    auto it = stamps.find("bob");
    if (it != stamps.end()) {
        cout << "bob has " << it->second << " stamps\n";
    }

    cout << "closing list:\n";
    for (const auto& [name, count] : stamps) {
        cout << "  " << name << ' ' << count << '\n';
    }
    return 0;
}

bob has 2 stamps
closing list:
  amara 1
  bob 2
  david 1
  kenji 1
  maria 1
  zara 1

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> calling_code{
        {"bangladesh", 880}, {"brazil", 55}, {"japan", 81},
        {"kenya", 254}, {"peru", 51}, {"spain", 34}};

    for (string country : {"japan", "chile", "kenya"}) {
        auto it = calling_code.find(country);
        if (it != calling_code.end()) {
            cout << country << ": +" << it->second << '\n';
        } else {
            cout << country << ": not found\n";
        }
    }
    cout << calling_code.size() << " countries in the book\n";
    return 0;
}

japan: +81
chile: not found
kenya: +254
6 countries in the book

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

int main() {
    vector<pair<string, string>> cards{
        {"bob", "555-0102"}, {"zara", "555-0144"}, {"bob", "555-0177"}, {"amara", "555-0110"}};

    map<string, string> latest;
    multimap<string, string> every;
    for (const auto& [name, number] : cards) {
        latest[name] = number;
        every.insert({name, number});
    }

    cout << "map keeps " << latest.size() << ":\n";
    for (const auto& [name, number] : latest) {
        cout << "  " << name << ' ' << number << '\n';
    }
    cout << "multimap keeps " << every.size() << ":\n";
    for (const auto& [name, number] : every) {
        cout << "  " << name << ' ' << number << '\n';
    }
    return 0;
}

map keeps 3:
  amara 555-0110
  bob 555-0177
  zara 555-0144
multimap keeps 4:
  amara 555-0110
  bob 555-0102
  bob 555-0177
  zara 555-0144

map<string, int> stamps{{"bob", 2}, {"maria", 5}};
if (stamps["zara"] == 0) {
    cout << "zara has no stamps yet\n";
}
for (const auto& [name, count] : stamps) {
    cout << name << ' ' << count << '\n';
}

#include <iostream>
#include <string>
using namespace std;

int main() {
    map<string, int> stamps;
    stamps["maria"]++;
    cout << stamps.size() << '\n';
    return 0;
}

map<int, int> guests{{12, 4}, {15, 2}};
auto it = guests.find(12);
it->first = 13;

map<string, int> course;
course["soup"] = 1;
course["rice"] = 2;
course["sweet"] = 3;
for (const auto& [dish, number] : course) {
    cout << dish << '\n';
}

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<char, int> letters;
    string word = "banana";
    for (char c : word) {
        letters[c]++;
    }
    for (const auto& [c, n] : letters) {
        cout << c << ' ' << n << '\n';
    }
    return 0;
}

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    map<string, int> price;   // item name -> its price in taka
    for (int i = 0; i < n; i++) {
        string item;
        int taka = 0;
        cin >> item >> taka;
        // Remember that item costs taka.
    }

    int m = 0;
    cin >> m;
    long long total = 0;   // the day's total can pass 2147483647
    for (int i = 0; i < m; i++) {
        string item;
        int qty = 0;
        cin >> item >> qty;
        // Print the cost of this order, and add it to total.
    }

    // Print the day's total.

    return 0;
}

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<string, int> first;   // name -> score in the first round
    for (int i = 0; i < n; i++) {
        string name;
        int score;
        cin >> name >> score;
        first[name] = score;
    }
    int m;
    cin >> m;
    map<string, int> second;   // name -> score in the second round
    for (int i = 0; i < m; i++) {
        string name;
        int score;
        cin >> name >> score;
        second[name] = score;
    }

    // Walk first in key order. For every name that second also holds,
    // print the name and both scores. Print none if nobody sat both.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    map<string, int> stamps;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        stamps[name]++;
    }

    // Walk stamps once. Keep the most stamps seen so far, and the names
    // that have that many. Then print the most stamps on one line, and
    // those names on the next, separated by single spaces.

    return 0;
}

এরপর lesson 02 map আর multimap-এর প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ।