set ב-C++: איברים ייחודיים וממוינים עם std::set

שק של ערכים ייחודיים וממוינים

ראיתם איך unordered_map שומר זוגות מפתח-ערך עם חיפוש מהיר מבוסס גיבוב. std::set הוא בן הדוד הפשוט יותר: הוא שומר רק ערכים, בלי נתונים משויכים, ואוכף שני כללים אוטומטית. כל איבר הוא ייחודי (כפילויות נזרקות בשקט), והאיברים תמיד נשמרים בסדר ממוין.

זה הופך את set לבחירה הטבעית לשאלות כמו "האם כבר ראיתי את זה?" או "תן לי את הפריטים השונים בסדר ממוין". מכניסים בלי לדאוג לכפילויות, ועוברים על האיברים בלי למיין קודם.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // כפילות: מתעלמים ממנה

    for (int x : s) cout << x << " ";   // 10 30 40 (ממוין, בלי חזרות)
}

שימו לב שהכנסנו את 10 פעמיים ולא לפי הסדר, ובכל זאת הפלט ממוין ו-10 מופיע פעם אחת. ה-set עשה בשבילכם את הניהול.

הכנסה והסרה

insert מוסיף ערך אם הוא עוד לא שם. הוא מחזיר pair שה-.second שלו הוא bool שאומר אם ההכנסה באמת קרתה, וזה שימושי כשרוצים לדעת אם ערך היה חדש:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

כדי להסיר ערך, קוראים ל-erase עם הערך עצמו: הוא מחזיר את מספר האיברים שהוסרו (0 או 1 ב-set). מחיקה של משהו שלא קיים לא מזיקה ואינה שגיאה:

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // מסיר את 3
    s.erase(99);         // לא עושה כלום, מחזיר 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

בדיקת שייכות

כל הטעם ב-set הוא בדיקות מהירות של "האם זה נמצא כאן?". הדרך הברורה ביותר היא count, שמחזיר 1 או 0:

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

מאז C++20 יש אפשרות קריאה עוד יותר, contains, שמחזירה bool ישירות:

if (primes.contains(7)) { /* ... */ }   // C++20

טעות נפוצה היא לנסות להשתמש ב-operator[] כמו ב-map. ל-set אין operator[]: אין ערך להביא, יש רק נוכחות לבדוק. השתמשו ב-count או ב-contains, לא ב-s[7].

אם צריך את המיקום בפועל (כדי למחוק אותו, או כדי להסתכל על השכנים), השתמשו ב-find, שמחזיר איטרטור או end():

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

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // מחיקה לפי איטרטור: בלי חיפוש שני
    }
    cout << "size now " << s.size() << "\n";
}

מעבר מסודר ושאילתות טווח

מכיוון ש-set ממוין, מעבר עליו תמיד מחזיר את האיברים מהקטן לגדול, ומקבלים בחינם את הטריקים של מכולה מסודרת. lower_bound(x) נותן את האיבר הראשון שאינו קטן מ-x, ו-upper_bound(x) את האיבר הראשון שגדול ממש מ-x: יחד הם מאפשרים לסרוק טווח מספרי בלי לבדוק כל איבר:

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // מדפיסים את כל מה שבטווח [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

כלל עדין אבל חשוב: איברי set אינם ניתנים לשינוי. האיטרטור נותן לכם הפניית const, ולכן אי אפשר לשנות איבר במקומו: זה עלול לשבור את סדר המיון שהמכולה מסתמכת עליו. כדי "לשנות" ערך, מחקו את הישן והכניסו את החדש.

כברירת מחדל הסדר עולה (std::less). לסדר יורד, ספקו פונקציית השוואה אחרת כארגומנט התבנית השני:

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set מול multiset מול unordered_set

std::set הוא אחד משלושה קרובי משפחה, וחשוב לבחור את הנכון:

set<int>            // ערכים ייחודיים, ממוין, O(log n)
multiset<int>       // מאפשר כפילויות, ממוין, O(log n)
unordered_set<int>  // ערכים ייחודיים, בלי סדר, O(1) בממוצע

השתמשו ב-unordered_set כשצריך רק בדיקות שייכות והסדר לא משנה: החיפושים מבוססי הגיבוב שלו מהירים יותר בממוצע מה-O(log n) מבוסס העץ של set. בחרו ב-set כשצריך איברים בסדר ממוין, שאילתות טווח עם lower_bound/upper_bound, או התנהגות יציבה של איטרטורים. השתמשו ב-multiset רק כשלכפילויות יש משמעות (למשל היסטוגרמה של ערכים חוזרים): ב-multiset, count(x) יכול להחזיר יותר מ-1, ו-erase(x) מסיר את כל העותקים, אלא אם מוחקים לפי איטרטור בודד.

שימוש קלאסי אחד ב-set: הסרת כפילויות ומיון של vector בצעד אחד.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

בניית ה-set מהאיטרטורים של ה-vector זורקת כל כפילות וממיינת את השאר: בלי לולאה ידנית, ובלי הריקוד של מיון מפורש ועוד std::unique.

הבא בתור: pair ו-tuple

ראיתם עכשיו את .first ו-.second מופיעים ב-pair ש-insert מחזיר, ו-structured bindings יחד עם מילת המפתח auto (auto [it, inserted]) מפרקים אותו בצורה נקייה. הטיפוסים הקלים האלה, ש"אורזים כמה ערכים יחד", נמצאים בכל מקום ב-STL. בהמשך נסתכל ישירות על pair ו-tuple: איך בונים אותם, איך מפרקים אותם, ואיך מחזירים כמה ערכים מפונקציה בלי להגדיר struct שלם.