[0]zero-index clytie0x/zero-index

20.1 set เก็บของไม่ซ้ำ

ด่านเก็บเงินบนทางด่วนบันทึกเลขทะเบียนรถทุกคันที่ผ่าน วันหนึ่งมีรถผ่านเป็นแสนครั้ง คันเดียวกันผ่านไปกลับหลายรอบ ถ้าอยากรู้ว่ามีรถกี่คัน หรือรถทะเบียนนี้เคยผ่านแล้วหรือยัง เครื่องมือที่เรามีตอนนี้ยังไม่พอดีมือ อาเรย์นับในหน้า 5.3 ใช้ไม่ได้เมื่อค่าใหญ่ถึง 109 การเรียงข้อมูลในบทที่ 16 ใช้ได้ถ้าข้อมูลมาครบก่อนแล้วค่อยตอบ แต่ถ้ารถผ่านไปเรื่อยๆ และมีคนถามแทรกเข้ามาตลอดเวลา จะเรียงใหม่ทุกครั้งก็ไม่ทัน

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

set ตัวแรก

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

int main()
{
    set<int> plates; // (1)!
    plates.insert(4521); // (2)!
    plates.insert(1088);
    plates.insert(7310);
    plates.insert(1088);
    plates.insert(4521);
    plates.insert(2950);
    cout << "distinct: " << plates.size() << '\n';
    for (int plate : plates) { // (3)!
        cout << plate << ' ';
    }
    cout << '\n';
    return 0;
}
  1. ประกาศ set ที่เก็บ int เขียนชนิดในวงเล็บมุมเหมือน vector<int> ตอนเริ่มยังว่าง
  2. insert ใส่ค่าลงไป ถ้ามีค่านั้นอยู่แล้ว set ไม่ทำอะไรเลย
  3. วนด้วย for แบบเดียวกับ vector ได้ แต่ค่าจะออกมาเรียงจากน้อยไปมากเสมอ ไม่ใช่ตามลำดับที่ใส่
distinct: 4
1088 2950 4521 7310

ใส่ไปหกครั้ง เหลือสี่ค่า เพราะ 1088 กับ 4521 ใส่ซ้ำ size() จึงเป็นจำนวนค่าที่ไม่ซ้ำกันพอดี โจทย์ "มีกี่แบบ" หรือ "มีกี่คนที่ไม่ซ้ำ" จึงจบได้ในไม่กี่บรรทัด

set เก็บอะไรก็ได้ที่เปรียบเทียบมากน้อยได้ เช่น set<string> จะเรียงข้อความตามพจนานุกรม หรือ set<pair<int, int>> จะเรียงตาม first ก่อนแล้วค่อย second แบบเดียวกับที่ sort เรียง pair ในบทที่ 16

ถามว่ามีไหมด้วย count และ find

สหกรณ์โรงเรียนมีรายชื่อรหัสสมาชิก N คน แล้วมีคนมาถามว่ารหัสนี้เป็นสมาชิกหรือเปล่า Q ครั้ง count(x) ของ set คืนจำนวนค่า x ที่มีอยู่ ซึ่งเป็นได้แค่ 0 หรือ 1 เพราะ set ไม่เก็บค่าซ้ำ

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    set<int> members;
    for (int i = 0; i < n; i++) {
        int id;
        cin >> id;
        members.insert(id);
    }
    for (int i = 0; i < q; i++) {
        int id;
        cin >> id;
        if (members.count(id) == 1) {
            cout << id << " yes\n";
        } else {
            cout << id << " no\n";
        }
    }
    return 0;
}

5 4
640012 100345 999999999 640012 2
100345
5
999999999
640013

100345 yes
5 no
999999999 yes
640013 no

รหัสใหญ่ถึง 999999999 ก็ไม่ต้องจองอาเรย์พันล้านช่อง set ใช้หน่วยความจำตามจำนวนค่าที่ใส่จริงเท่านั้น

อีกวิธีคือ find(x) ซึ่งคืน iterator ตัวชี้ตำแหน่งแบบเดียวกับที่ lower_bound ของ vector คืนในหน้า 19.2 ถ้าไม่เจอจะคืน end() ซึ่งเป็นตำแหน่งเลยตัวสุดท้ายไปหนึ่งช่อง ไม่ใช่ค่าจริงในเซต อ่านค่าที่ iterator ชี้ด้วย * ข้างหน้า

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

int main()
{
    set<int> scores = {72, 85, 91, 60};
    auto it = scores.find(85);
    if (it != scores.end()) {
        cout << "found " << *it << '\n';
    }
    it = scores.find(100);
    if (it == scores.end()) {
        cout << "100 not found\n";
    }
    cout << "smallest " << *scores.begin() << '\n';
    cout << "largest " << *scores.rbegin() << '\n';
    return 0;
}

found 85
100 not found
smallest 60
largest 91
  • ใส่ค่าเริ่มต้นในปีกกาได้เหมือน vector ค่าซ้ำในปีกกาก็ถูกตัดทิ้งเหมือนกัน
  • auto ให้ compiler ใส่ชนิดของ iterator ให้เองตามหน้า 15.5 ชนิดจริงยาวมาก
  • begin() ชี้ค่าที่น้อยที่สุด rbegin() (reverse begin) ชี้ค่าที่มากที่สุด ทั้งสองตัวใช้ได้เฉพาะตอนที่ set ไม่ว่าง

ถ้าแค่อยากรู้ว่ามีหรือไม่มี ใช้ count อ่านง่ายกว่า ส่วน find ใช้เมื่ออยากได้ตำแหน่งไปทำอย่างอื่นต่อ เช่น ลบตัวนั้นทิ้ง

ลบด้วย erase

ห้องสมุดบันทึกว่าใครอยู่ในห้องบ้าง + id คือมีคนเข้า - id คือมีคนออก หลังทุกเหตุการณ์ บรรณารักษ์อยากรู้ว่าในห้องมีกี่คน และรหัสน้อยสุดกับมากสุดเป็นเท่าไร

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    set<int> inside;
    for (int i = 0; i < q; i++) {
        char op;
        int id;
        cin >> op >> id;
        if (op == '+') {
            inside.insert(id);
        } else {
            inside.erase(id);
        }
        if (inside.empty()) {
            cout << "empty\n";
        } else {
            cout << inside.size() << " people, ids " << *inside.begin() << " to " << *inside.rbegin() << '\n';
        }
    }
    return 0;
}

7
+ 305
+ 112
+ 480
- 112
+ 305
- 999
- 305

1 people, ids 305 to 305
2 people, ids 112 to 305
3 people, ids 112 to 480
2 people, ids 305 to 480
2 people, ids 305 to 480
2 people, ids 305 to 480
1 people, ids 480 to 480
  • erase(x) ลบค่า x ออก ถ้าไม่มี x อยู่ก็ไม่เกิดอะไรขึ้น เหตุการณ์ที่หก - 999 ลบ 999 ที่ไม่เคยเข้าห้อง จำนวนคนจึงเท่าเดิม
  • เหตุการณ์ที่ห้า + 305 ใส่ 305 ซ้ำ set ไม่เปลี่ยน
  • erase รับ iterator ได้ด้วย เช่น inside.erase(inside.begin()) ลบค่าน้อยสุดทิ้ง
  • empty() บอกว่า set ว่างหรือไม่ ต้องเช็กก่อนอ่าน *inside.begin() ทุกครั้ง

ทุกเหตุการณ์ได้ค่าน้อยสุดและมากสุดมาทันที ถ้าใช้ vector ต้องไล่หาใหม่ทุกครั้ง และการลบตรงกลาง vector ก็ต้องเลื่อนของทั้งแถว

เดินใน set ด้วย iterator

set ไม่มีช่องหมายเลข 0 1 2 แบบ vector จะไปตัวถัดไปต้องเลื่อน iterator ทีละก้าว ++it คือไปตัวถัดไป next(it) คืน iterator ของตัวถัดไปโดยไม่เปลี่ยน it และ prev(it) คืนของตัวก่อนหน้า

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

int main()
{
    set<int> heights = {158, 171, 149, 165};
    for (auto it = heights.begin(); it != heights.end(); ++it) {
        cout << *it << ' ';
    }
    cout << '\n';
    auto last = prev(heights.end());
    cout << "tallest " << *last << '\n';
    cout << "second tallest " << *prev(last) << '\n';
    cout << "second shortest " << *next(heights.begin()) << '\n';
    return 0;
}

149 158 165 171
tallest 171
second tallest 165
second shortest 158

prev(heights.end()) คือตัวสุดท้ายจริงๆ ได้ค่าเดียวกับ *heights.rbegin() วิธีนี้จะใช้บ่อยมากในหน้า 20.2 ส่วนการกระโดดไปตัวที่ k ตรงๆ ทำไม่ได้ ต้องเดินไปทีละก้าว k ครั้ง

ทำไมเร็ว และเร็วแค่ไหน

ข้างใน set ไม่ได้เก็บเป็นแถวแบบอาเรย์ แต่เก็บเป็นต้นไม้ค้นหาแบบทวิภาค (binary search tree) ทุกโหนดมีค่าที่น้อยกว่าอยู่ทางซ้าย และค่าที่มากกว่าอยู่ทางขวา การหาค่าหนึ่งตัวจึงเริ่มจากยอด แล้วเลือกเลี้ยวซ้ายหรือขวาทีละชั้น เหมือน binary search ในบทที่ 19 ที่ตัดครึ่งไปเรื่อยๆ

165 152 176 149 158 171 180 หา 171 มากกว่า 165 ไปขวา น้อยกว่า 176 ไปซ้าย เจอ

เจ็ดค่าใช้การเทียบแค่สามครั้ง set ใน C++ คอยจัดต้นไม้ให้สมดุลเองทุกครั้งที่ใส่หรือลบ ความสูงของต้นไม้จึงไม่เกินราว 2 log2 N เสมอ บทที่ 26 จะได้ดูว่าต้นไม้แบบนี้ทำให้สมดุลด้วยการหมุนอย่างไร บทนี้ใช้งานอย่างเดียว

คำสั่งเวลา
insert(x) erase(x)O(log N)
count(x) find(x)O(log N)
size() empty() begin() rbegin()O(1)
++it prev(it) next(it)เฉลี่ย O(1) ไม่เกิน O(log N)
วนทุกค่าด้วย forO(N)

log2 ของแสนประมาณ 17 และของล้านประมาณ 20 ทำคำสั่งละ O(log N) เป็นแสนครั้งจึงเป็นงานราวสองล้านก้าว สบายมากใน 1 วินาที แต่ต้องรู้ไว้ว่าแต่ละก้าวของต้นไม้ช้ากว่าการอ่านอาเรย์ช่องถัดไปหลายเท่า และแต่ละค่าในเซตกินหน่วยความจำมากกว่า int ในอาเรย์หลายเท่าเช่นกัน

ตัวอย่าง ลบตัวซ้ำ

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    set<int> seen;
    vector<int> order;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (seen.count(x) == 0) {
            seen.insert(x);
            order.push_back(x);
        }
    }
    for (int x : order) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

9
700 15 700 3000000 15 42 3000000 700 8

700 15 3000000 42 8

วิธีตรงไปตรงมาที่ไม่ใช้ set คือเก็บค่าที่เคยเห็นไว้ใน vector แล้วไล่หาทุกครั้งที่อ่านค่าใหม่ ค่าที่ N ต้องไล่ดูค่าเก่าเกือบ N ตัว รวมเป็น O(N2)

vector<int> seen;
for (int x : plates) {
    bool found = false;
    for (int y : seen) {
        if (y == x) {
            found = true;
            break;
        }
    }
    if (!found) {
        seen.push_back(x);
    }
}

อีกวิธีที่ใช้ได้ถ้าไม่สนลำดับ คือ sort แล้วนับเฉพาะตัวที่ต่างจากตัวก่อนหน้า แบบหน้า 13.1 ซึ่งเป็น O(N log N) เท่ากับ set ลองนับจำนวนค่าที่ไม่ซ้ำด้วยทั้งสามวิธี ใช้เลขทะเบียนสุ่ม 0 ถึง 109 จาก mt19937 ตัวสุ่มของ C++ ที่ให้เลขใหญ่กว่า rand() แล้วจับเวลาเฉพาะช่วงนับด้วย clock()

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

Nvector ไล่หา O(N2)set O(N log N)sort O(N log N)
1040.0220.002ไม่ถึง 0.001
1051.5030.0180.006
2 × 1054.7190.0570.010

คอมไพล์แบบ Code::Blocks ที่ไม่มี -O2 วิธี vector ช้าลงอีกมาก N = 105 ใช้ 26.9 วินาที และ N = 2 × 105 ใช้ราว 111 วินาที ส่วน set กับ sort ยังไม่ถึง 0.12 วินาทีทุกขนาด

สองเรื่องที่ตารางนี้บอก เรื่องแรก วิธี O(N2) ช้าลงราวสามถึงสี่เท่าทุกครั้งที่ N เพิ่มเป็นสองเท่า และไม่มีทางทันที่ N สองแสน เรื่องที่สอง เมื่อข้อมูลมาครบก่อนแล้วค่อยตอบ sort เร็วกว่า set อีกหลายเท่า เพราะอาเรย์เรียงกันในหน่วยความจำ ส่วนต้นไม้กระโดดไปมา set จึงคุ้มเมื่อข้อมูลเปลี่ยนไปเรื่อยๆ และต้องตอบคำถามแทรกระหว่างทาง แบบโปรแกรมห้องสมุดข้างบน ซึ่งการเรียงใหม่ทุกครั้งไม่ทัน

ลองทำให้พัง

แบบที่ 1 ใช้ set ทั้งที่ค่าซ้ำมีความหมาย

อยากได้คะแนนต่ำสุดของห้อง เลยใส่คะแนนทุกคนลง set เพราะ begin() ให้ค่าน้อยสุดมาฟรีๆ แล้วใช้ size() เป็นจำนวนนักเรียนไปด้วย

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

int main()
{
    int n;
    cin >> n;
    set<int> scores;
    int total = 0;
    for (int i = 0; i < n; i++) {
        int score;
        cin >> score;
        scores.insert(score);
        total += score;
    }
    cout << "students " << scores.size() << '\n';
    cout << "lowest " << *scores.begin() << '\n';
    cout << fixed << setprecision(2);
    cout << "average " << (double)total / scores.size() << '\n';
    return 0;
}

6
70 85 70 90 85 70

students 3
lowest 70
average 156.67

นักเรียนหกคนเหลือสามคน และค่าเฉลี่ยเกินคะแนนเต็ม เพราะ set ตัดคะแนนที่ซ้ำทิ้ง ส่วน total บวกครบทุกคน คะแนนต่ำสุดยังถูกเพราะค่าน้อยสุดไม่เปลี่ยนแม้ตัดตัวซ้ำ ซึ่งทำให้ตายใจ ก่อนใช้ set ให้ถามตัวเองเสมอว่า ถ้ามีค่าซ้ำ ต้องนับแยกกันไหม ถ้าต้องนับ ใช้ multiset ในหน้า 20.2 หรือนับจำนวนด้วยวิธีอื่น

แบบที่ 2 เรียก s[0] แบบอาเรย์

set<int> heights = {158, 171, 149, 165};
cout << heights[0] << '\n';

index.cpp:7:20: error: no match for 'operator[]' (operand types are 'std::set<int>' and 'int')
    7 |     cout << heights[0] << '\n';
      |                    ^

no match for 'operator[]' แปลว่าชนิดนี้ไม่มีวงเล็บเหลี่ยมให้ใช้ set ไม่มีช่องหมายเลข ค่าน้อยสุดใช้ *heights.begin()

แบบที่ 3 บวกเลขเข้ากับ iterator

เคยเขียน v.begin() + 1 กับ vector ได้ เลยลองกับ set

auto it = heights.begin() + 1;

plus.cpp:7:31: error: no match for 'operator+' (operand types are 'std::set<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} and 'int')
    7 |     auto it = heights.begin() + 1;
      |               ~~~~~~~~~~~~~~~ ^ ~
      |                            |    |
      |                            |    int
      |                            std::set<int>::iterator {aka std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator}

ข้อความจริงยาวเกือบ 200 บรรทัด ที่เหลือเป็นบรรทัด note ที่ compiler ไล่บอกว่าลองจับคู่กับ operator+ แบบไหนไปแล้วบ้าง ให้อ่านแค่บรรทัด error แรก iterator ของ set บวกเลขไม่ได้ เพราะไปตัวถัดไปต้องเดินตามกิ่งของต้นไม้ ไม่ได้อยู่ติดกันแบบอาเรย์ ใช้ next(heights.begin()) แทน คำว่า _Rb_tree ในข้อความคือต้นไม้แบบ red-black tree ที่ set ใช้อยู่ข้างใน

สรุป

  • set<T> เก็บค่าไม่ซ้ำ และเรียงจากน้อยไปมากเสมอ
  • insert erase count find ใช้เวลา O(log N) size กับ empty ใช้ O(1)
  • ค่าน้อยสุด *s.begin() ค่ามากสุด *s.rbegin() หรือ *prev(s.end()) เช็ก empty() ก่อนเสมอ
  • set ไม่มี s[i] และบวกเลขเข้ากับ iterator ไม่ได้ ใช้ next prev แทน
  • ข้อมูลมาครบก่อนแล้วค่อยตอบ sort เร็วกว่า ข้อมูลเปลี่ยนไปเรื่อยๆ ระหว่างตอบ ใช้ set
  • ค่าซ้ำมีความหมายเมื่อไร set จะตัดทิ้งเงียบๆ ทำให้คำตอบผิด