20.3 map จับคู่คีย์กับค่า

อาเรย์คือการจับคู่หมายเลขช่องกับค่า count[5] เก็บว่าเลข 5 เจอกี่ครั้ง แต่หมายเลขช่องต้องเป็นจำนวนเต็มเล็กๆ ที่เริ่มจาก 0 ถ้าอยากนับว่าเบอร์โทร 812345678 โทรเข้ามากี่ครั้ง ต้องมีอาเรย์เกือบพันล้านช่อง กิน 4 GB ซึ่งประกาศไม่ได้ ถ้าอยากนับว่าคำว่า the เจอกี่ครั้ง ใช้ข้อความเป็นหมายเลขช่องไม่ได้เลย

map คืออาเรย์ที่หมายเลขช่องเป็นอะไรก็ได้ที่เรียงลำดับได้ เราเรียกหมายเลขช่องว่า คีย์ (key) และสิ่งที่เก็บว่า ค่า (value) ข้างในเป็นต้นไม้แบบเดียวกับ set ที่เรียงตามคีย์ แต่ละคีย์มีค่าติดมาด้วยหนึ่งค่า ทุกคำสั่งจึงเป็น O(log N) และวนแล้วได้คีย์เรียงจากน้อยไปมาก

นับความถี่เมื่อค่ากว้างเกินอาเรย์นับ

ศูนย์รับแจ้งเหตุอยากรู้ว่าแต่ละเบอร์โทรเข้ามากี่ครั้ง เบอร์เป็นตัวเลขถึง 10⁹

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    map<int, int> count; // (1)!
    for (int i = 0; i < n; i++) {
        int phone;
        cin >> phone;
        count[phone]++; // (2)!
    }
    for (auto entry : count) { // (3)!
        cout << entry.first << " called " << entry.second << " times\n";
    }
    return 0;
}

map<ชนิดคีย์, ชนิดค่า> ตัวนี้มีคีย์เป็นเบอร์โทร ค่าเป็นจำนวนครั้ง ตอนเริ่มยังไม่มีคีย์ไหนเลย
เขียนเหมือนอาเรย์นับในหน้า 5.3 ทุกตัวอักษร ถ้าเบอร์นี้ยังไม่มีใน map วงเล็บเหลี่ยมจะสร้างคีย์ใหม่ให้พร้อมค่าเริ่มต้น 0 ก่อน แล้ว ++ จึงได้ 1
วนแล้วได้ทีละคู่ เป็น pair ที่ first คือคีย์ และ second คือค่า เรียงตามคีย์จากน้อยไปมาก

8
812345678 21000777 812345678 990000001 21000777 812345678 5 990000001

5 called 1 times
21000777 called 2 times
812345678 called 3 times
990000001 called 2 times

map มีแค่สี่คีย์ตามจำนวนเบอร์ที่ไม่ซ้ำ ไม่ว่าเบอร์จะใหญ่แค่ไหน หน่วยความจำจึงขึ้นกับจำนวนค่าที่ไม่ซ้ำ ไม่ใช่ขนาดของค่า ใช้ map เมื่อ

ค่าที่นับกว้างเกินกว่าจะประกาศอาเรย์ได้ เช่น ถึง 10⁹ หรือ 10¹⁸
ค่าติดลบปนกับค่าบวกในช่วงกว้าง ซึ่งการบวกค่าคงที่แบบหน้า 5.3 ช่วยไม่ได้
คีย์ไม่ใช่ตัวเลข เช่น ข้อความ หรือ pair ของพิกัด

map<string, int>

เก็บคะแนนสอบตามชื่อเล่น ใช้ชื่อเป็นคีย์

#include <bits/stdc++.h>
using namespace std;

int main()
{
    map<string, int> score;
    score["nok"] = 78;
    score["ploy"] = 91;
    score["arm"] = 66;
    score["nok"] = 82;
    cout << "size " << score.size() << '\n';
    cout << "nok " << score["nok"] << '\n';
    if (score.count("beam") == 0) {
        cout << "beam not found\n";
    }
    auto it = score.find("ploy");
    if (it != score.end()) {
        cout << it->first << ' ' << it->second << '\n';
    }
    score.erase("arm");
    for (auto entry : score) {
        cout << entry.first << ' ' << entry.second << '\n';
    }
    return 0;
}

size 3
nok 82
beam not found
ploy 91
nok 82
ploy 91

บรรทัดที่ 10 ใส่ nok ซ้ำ ไม่ได้เพิ่มคีย์ใหม่ แต่เขียนทับค่าเดิม size จึงเป็น 3 คีย์ใน map ไม่ซ้ำกันเหมือน set
count(key) กับ find(key) ใช้เหมือน set ทุกอย่าง ถามด้วยคีย์ ไม่ใช่ด้วยค่า
iterator ของ map ชี้ไปที่ pair it->first เขียนย่อมาจาก (*it).first ลูกศรนี้เป็นเครื่องหมายเดียวกับที่ใช้กับ pointer ของ struct ในหน้า 11.4
erase(key) ลบทั้งคีย์และค่าออก
ถ้ามีคนชื่อซ้ำกันได้ ชื่อเป็นคีย์ไม่ได้ เพราะคะแนนของคนหลังจะเขียนทับคนแรก ให้ใช้คีย์ที่ไม่ซ้ำแน่นอน เช่น รหัสนักเรียน

map มี lower_bound upper_bound begin rbegin แบบเดียวกับ set ด้วย ทุกตัวทำงานกับคีย์ เช่น score.begin()->first คือชื่อที่มาก่อนสุดตามพจนานุกรม

ตัวอย่าง นับคำที่พบบ่อยที่สุด

อ่านข้อความจนหมดข้อมูล แล้วบอกว่ามีคำต่างกันกี่คำ และคำไหนพบบ่อยที่สุด ถ้าเสมอกันให้ตอบคำที่มาก่อนตามพจนานุกรม การอ่านจนหมดใช้ while (cin >> word) ตามหน้า 15.2 ในหน้าต่างดำจบข้อมูลด้วย Ctrl+Z ที่ต้นบรรทัดใหม่แล้วกด Enter แบบหน้า 4.3

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<string, int> count;
    string word;
    while (cin >> word) {
        count[word]++;
    }
    string best_word;
    int best_count = 0;
    for (auto entry : count) {
        if (entry.second > best_count) { // (1)!
            best_word = entry.first;
            best_count = entry.second;
        }
    }
    cout << count.size() << " different words\n";
    cout << best_word << ' ' << best_count << '\n';
    return 0;
}

ใช้ > ไม่ใช่ >= map วนตามพจนานุกรมอยู่แล้ว คำที่เจอก่อนจึงมาก่อนตามพจนานุกรม ถ้าคำหลังมีจำนวนแค่เท่ากัน จะไม่แย่งที่ ได้กติกาเรื่องเสมอมาฟรีๆ

the cat and the dog and the bird
saw a cat and a dog

7 different words
and 3

and กับ the เจอสามครั้งเท่ากัน and มาก่อนตามพจนานุกรมจึงชนะ ถ้าโจทย์อยากได้คำยอดนิยมหลายอันดับ ให้ย้ายทุกคู่ไปใส่ vector แล้ว sort ตามจำนวนครั้ง ซึ่งเป็นแบบฝึกหัดข้อ 4

วงเล็บเหลี่ยมสร้างคีย์ให้เอง

ตัวอย่างนับคำทำงานได้เพราะ count[word] สร้างคีย์ใหม่ที่มีค่า 0 ให้ทันทีเมื่อยังไม่มีคีย์นั้น ข้อดีนี้กลายเป็นกับดักตอนที่แค่อยากอ่านค่า เพราะการอ่านด้วยวงเล็บเหลี่ยมก็สร้างคีย์ด้วยเหมือนกัน โปรแกรมนี้นับตัวเลข แล้วตอบคำถามว่าค่าที่ถามมีอยู่ในข้อมูลหรือไม่

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    map<int, int> count;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        count[x]++;
    }
    cout << "keys before: " << count.size() << '\n';
    int found = 0;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        if (count[x] > 0) {
            found++;
        }
    }
    cout << "found " << found << '\n';
    cout << "keys after: " << count.size() << '\n';
    return 0;
}

5 6
10 20 10 30 20
10 40 50 20 60 70

keys before: 3
found 2
keys after: 7

คำตอบ found 2 ถูก แต่ map โตจาก 3 คีย์เป็น 7 คีย์ เพราะคำถาม 40 50 60 70 ถูกสร้างเป็นคีย์ที่มีค่า 0 ทิ้งไว้ ผลเสียมีสามอย่าง

ถ้าหลังจากนั้นพิมพ์ count.size() เป็นจำนวนค่าที่ไม่ซ้ำ หรือวนพิมพ์ทุกคีย์ จะได้คำตอบผิด เพราะมีคีย์ที่ไม่เคยอยู่ในข้อมูลปนมา
คำถามเป็นแสนข้อที่ส่วนใหญ่ไม่มีในข้อมูล ทำให้ map โตเป็นแสนคีย์ กินหน่วยความจำและเวลาเพิ่มโดยไม่จำเป็น
ถ้าคีย์เป็น string แต่ละคีย์ที่สร้างเกินมาก็เก็บข้อความทั้งคำไว้ด้วย

อยากแค่ถามว่ามีไหม ใช้ count.count(x) อยากได้ค่าด้วย ใช้ find แล้วเช็ก end() สองคำสั่งนี้ไม่สร้างคีย์ใหม่ ส่วนวงเล็บเหลี่ยมเก็บไว้ใช้ตอนตั้งใจจะเขียนค่า

if (count.count(x) == 1) {
    found++;
}

นับช่วงที่ผลรวมเท่ากับ k ด้วย map

หน้า 19.5 นับช่วงวันที่กำไรรวมเท่ากับ k ได้สองทาง ทางที่ 1 จดว่าค่าแต่ละค่าเคยเป็น prefix มาแล้วกี่ครั้งด้วยอาเรย์นับ ซึ่งใช้ได้เฉพาะเมื่อค่าอยู่ในช่วงแคบ ทางที่ 2 ใช้ได้กับค่ากว้าง แต่ต้องเรียง pair แล้วค้นสองครั้ง พอมี map แล้ว ทางที่ 1 ก็ใช้กับค่าขนาดไหนก็ได้ แค่เปลี่ยนอาเรย์นับเป็น map ไม่ต้องเลื่อนค่าติดลบด้วย limit และไม่ต้องเช็กว่า want หลุดขอบอาเรย์

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    map<long long, int> seen; // (1)!
    long long prefix = 0;
    seen[prefix]++; // (2)!
    long long count = 0;
    for (int i = 1; i <= n; i++) {
        int profit;
        cin >> profit;
        prefix += profit;
        auto it = seen.find(prefix - k); // (3)!
        if (it != seen.end()) {
            count += it->second;
        }
        seen[prefix]++;
    }
    cout << count << '\n';
    return 0;
}

คีย์คือค่าของ prefix ค่าคือจำนวนครั้งที่ prefix เป็นค่านั้น ค่าติดลบหรือใหญ่ถึง 2 × 10¹⁴ ก็เป็นคีย์ได้เลย
จด prefix[0] = 0 ไว้ก่อนเริ่มเหมือนเดิม ช่วงที่เริ่มวันที่ 1 ต้องใช้ค่านี้
ถามด้วย find ไม่ใช่ seen[prefix - k] เพราะวงเล็บเหลี่ยมจะสร้างคีย์ใหม่ทุกครั้งที่ไม่เจอ ตามหัวข้อก่อน ทำให้ map โตขึ้นเกือบเท่าตัวโดยไม่ได้อะไร

8 5
3 2 -1 1 5 -5 5 0

แต่ละวันใช้ find หนึ่งครั้งกับวงเล็บเหลี่ยมหนึ่งครั้ง อย่างละ O(log N) รวมเป็น O(N log N) เท่ากับทางที่ 2 แต่สั้นกว่าและไม่ต้องคิดเรื่องรอยต่อของกลุ่ม

ลองกับ N = 200000 วัน กำไรสุ่มตั้งแต่ -10⁹ ถึง 10⁹ วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 แรม 32 GB ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks รันทีละโปรแกรม 6 ครั้ง ทิ้งครั้งแรก แล้วใช้ค่ากลางของ 5 ครั้งที่เหลือ นับรวมเวลาเปิดโปรแกรม แบบ -O2 โปรแกรมนี้ใช้ 0.10 วินาที ทางที่ 2 ของหน้า 19.5 ใช้ 0.06 วินาที แบบ Code::Blocks ใช้ 0.20 กับ 0.16 วินาที map ช้ากว่าการเรียงอยู่บ้าง เพราะทุกคีย์ใหม่ต้องจองหน่วยความจำและหาที่ในต้นไม้ แต่ทั้งคู่เร็วพอสำหรับ N หลายแสน ส่วนวิธีลองทุกคู่ O(N²) ใช้ 2 วินาทีตั้งแต่ N = 100000 ตามตารางของหน้า 19.5

เร็วแค่ไหน

คำสั่งของ map	เวลา
`m[key]` อ่าน เขียน หรือสร้างคีย์	O(log N)
`count(key)` `find(key)` `erase(key)`	O(log N)
`lower_bound(key)` `upper_bound(key)`	O(log N)
`size()` `empty()`	O(1)
วนทุกคู่	O(N)

N ในตารางคือจำนวนคีย์ ถ้าคีย์เป็นข้อความ การเทียบแต่ละครั้งต้องเทียบทีละตัวอักษร คำยาว L ตัวจึงใช้ราว O(L log N)

เทียบกับวิธีตรงไปตรงมาที่ไม่มี map คือเก็บคู่ (คำ, จำนวน) ใน vector แล้วไล่หาคำเดิมทุกครั้งที่อ่านคำใหม่ และวิธีเรียงคำทั้งหมดด้วย sort แล้วนับคำที่ติดกัน ใช้คำสุ่มยาว 5 ถึง 8 ตัวอักษร N คำ จากคำที่ต่างกัน N/4 คำ

vector<pair<string, int>> table;
for (const string &word : words) {
    bool found = false;
    for (auto &entry : table) {
        if (entry.first == word) {
            entry.second++;
            found = true;
            break;
        }
    }
    if (!found) {
        table.push_back({word, 1});
    }
}

วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 แรม 32 GB ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks แบบ -O2 ตัวเลขเป็นวินาที แต่ละช่องคือค่ากลางของการรันสามครั้ง ระหว่างวัดเครื่องมีงานอื่นรันอยู่ด้วย ตัวเลขของแต่ละรอบจึงแกว่งได้ราวหนึ่งในห้า

N	vector ไล่หา	map	sort
10⁴	0.009	0.001	0.001
10⁵	1.802	0.015	0.018
2 × 10⁵	19.5	0.084	0.087

คอมไพล์แบบ Code::Blocks วิธี vector ใช้ 21.7 วินาทีที่ N = 10⁵ และ 51.9 วินาทีที่ N = 2 × 10⁵ ส่วน map กับ sort ไม่ถึง 0.12 วินาที

vector ไล่หาเป็น O(N × จำนวนคำที่ต่างกัน) จึงพังเมื่อคำมีเป็นหมื่น map กับ sort เป็น O(N log N) ทั้งคู่ ถ้าได้ข้อมูลครบแล้วค่อยนับครั้งเดียว sort ก็ใช้ได้ดี แต่ map ยังได้เปรียบเมื่อต้องตอบระหว่างทาง เช่น หลังอ่านแต่ละคำต้องบอกว่าคำนี้เจอมาแล้วกี่ครั้ง

ลองทำให้พัง

แบบที่ 1 แก้ค่าผ่านตัวแปรที่เป็นสำเนา

ครูให้คะแนนพิเศษทุกคน 5 คะแนน เลยวน map แล้วบวกเข้าไป

#include <bits/stdc++.h>
using namespace std;

int main()
{
    map<string, int> score = {{"arm", 66}, {"nok", 82}, {"ploy", 91}};
    for (auto entry : score) {
        entry.second += 5;
    }
    for (auto entry : score) {
        cout << entry.first << ' ' << entry.second << '\n';
    }
    return 0;
}

arm 66
nok 82
ploy 91

ไม่มีใครได้คะแนนเพิ่ม auto entry คือสร้าง pair ใหม่ที่ก๊อปค่ามาจาก map แล้วแก้ที่ตัวก๊อป ของจริงใน map ไม่เปลี่ยน เป็นเรื่องเดียวกับการส่งค่าแบบสำเนาในหน้า 8.2 แก้ด้วย reference จากหน้า 15.5 เติม & เป็น for (auto &entry : score) จะได้ 71 87 96 ส่วน entry.first แก้ไม่ได้แม้ใช้ & เพราะถ้าเปลี่ยนคีย์ ลำดับในต้นไม้จะผิด อยากเปลี่ยนคีย์ต้องลบคีย์เก่าแล้วใส่คีย์ใหม่

แบบที่ 2 พิมพ์ค่าของคีย์ที่ไม่มี

ในโปรแกรม scores เพิ่มบรรทัด cout << score["beam"] << '\n'; ก่อนวนพิมพ์ จะได้ 0 ไม่มี error และตอนวนพิมพ์ท้ายโปรแกรมจะมี beam 0 โผล่มาเป็นบรรทัดแรก ทั้งที่ไม่มีใครชื่อ beam สอบเลย เป็นกับดักเดียวกับหัวข้อก่อน คือวงเล็บเหลี่ยมสร้างคีย์ทุกครั้งที่หาไม่เจอ

สรุป

map<K, V> จับคู่คีย์กับค่า คีย์ไม่ซ้ำและเรียงจากน้อยไปมาก ทุกคำสั่งหลักเป็น O(log N)
นับความถี่ของค่าที่กว้างเกินอาเรย์ ใช้ m[x]++ ได้เลย
วนได้ทีละ pair คีย์อยู่ใน first ค่าอยู่ใน second จะแก้ค่าระหว่างวนต้องใช้ auto &
m[key] สร้างคีย์ใหม่ที่ค่าเป็น 0 ถ้ายังไม่มี แม้แค่อ่าน ถามว่ามีไหมให้ใช้ count หรือ find
เสมอกันแล้วต้องเลือกคีย์ที่น้อยกว่า ใช้ > ตอนวนหาค่ามากสุด เพราะ map วนจากคีย์น้อยไปมากอยู่แล้ว