set trong C++: phần tử duy nhất, có thứ tự với std::set

Một túi giá trị duy nhất, đã sắp xếp

Bạn đã thấy unordered_map lưu các cặp khóa và giá trị với khả năng tra cứu nhanh dựa trên băm. std::set là người anh em đơn giản hơn: nó chỉ lưu giá trị, không kèm dữ liệu nào, và tự động áp dụng hai quy tắc. Mọi phần tử đều duy nhất (phần tử trùng bị bỏ qua mà không báo gì), và các phần tử luôn được giữ theo thứ tự đã sắp xếp.

Điều đó khiến set là lựa chọn tự nhiên cho những câu hỏi như "mình đã gặp cái này chưa?" hay "cho mình các phần tử khác nhau theo thứ tự". Bạn thêm vào mà không lo trùng lặp, và duyệt mà không cần sắp xếp trước.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplicate - ignored

    for (int x : s) cout << x << " ";   // 10 30 40 (sorted, no repeat)
}

Để ý rằng ta đã thêm 10 hai lần và không theo thứ tự, vậy mà kết quả vẫn được sắp xếp và 10 chỉ xuất hiện một lần. set đã lo phần sổ sách đó cho bạn.

Thêm và xóa

insert thêm một giá trị nếu nó chưa có. Hàm này trả về một pair có .second là một bool cho biết việc thêm có thật sự xảy ra hay không, rất tiện khi bạn muốn biết giá trị đó có mới hay không:

#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";
    }
}

Để xóa một giá trị, gọi erase với chính giá trị đó: hàm trả về số phần tử đã bị xóa (0 hoặc 1 với set). Xóa một thứ không có trong set là vô hại, không phải lỗi:

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

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

    s.erase(3);          // removes 3
    s.erase(99);         // does nothing, returns 0

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

Kiểm tra phần tử có tồn tại không

Mục đích chính của set là kiểm tra nhanh "cái này có ở trong không?". Cách rõ ràng nhất là count, trả về 1 hoặc 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";
}

Từ C++20 có một lựa chọn còn dễ đọc hơn là contains, trả về trực tiếp một bool:

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

Một lỗi thường gặp là dùng operator[] như với map. set không có operator[]: không có giá trị nào để lấy ra, chỉ có sự tồn tại để kiểm tra. Hãy dùng count hoặc contains, đừng dùng s[7].

Nếu bạn cần vị trí thật sự (để xóa nó, hoặc để xem các phần tử lân cận), hãy dùng find, hàm trả về một iterator hoặc 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);   // erase by iterator - no second lookup
    }
    cout << "size now " << s.size() << "\n";
}

Duyệt theo thứ tự và truy vấn theo khoảng

Vì set đã được sắp xếp, duyệt qua nó luôn cho các phần tử từ nhỏ đến lớn, và bạn được dùng miễn phí các mẹo của container có thứ tự. lower_bound(x) cho phần tử đầu tiên không nhỏ hơn x, còn upper_bound(x) cho phần tử đầu tiên lớn hơn hẳn x; kết hợp lại, chúng cho phép bạn quét một khoảng số mà không phải kiểm tra từng phần tử:

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

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

    // print everything in [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
}

Một quy tắc khó thấy nhưng quan trọng: phần tử của set là bất biến. Iterator trả về cho bạn một tham chiếu const, nên bạn không thể sửa trực tiếp một phần tử, vì làm vậy có thể phá vỡ thứ tự sắp xếp mà container dựa vào. Để "đổi" một giá trị, hãy xóa giá trị cũ rồi thêm giá trị mới.

Mặc định thứ tự là tăng dần (std::less). Để có thứ tự giảm dần, hãy truyền một hàm so sánh khác làm đối số template thứ hai:

#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 và unordered_set

std::set là một trong ba người anh em gần gũi, và chọn đúng loại rất quan trọng:

set<int>            // unique values, sorted, O(log n)
multiset<int>       // allows duplicates, sorted, O(log n)
unordered_set<int>  // unique values, NO order, average O(1)

Dùng unordered_set khi bạn chỉ cần kiểm tra tồn tại và không quan tâm thứ tự: tra cứu dựa trên băm của nó trung bình nhanh hơn O(log n) dựa trên cây của set. Chọn set khi bạn cần phần tử theo thứ tự, truy vấn theo khoảng với lower_bound/upper_bound, hoặc iterator ổn định. Chỉ dùng multiset khi phần tử trùng có ý nghĩa (ví dụ, đếm tần suất các giá trị lặp lại): trong multiset, count(x) có thể trả về lớn hơn 1, và erase(x) xóa tất cả các bản trùng trừ khi bạn xóa bằng một iterator duy nhất.

Một cách dùng set kinh điển: loại bỏ trùng lặp và sắp xếp một vector chỉ trong một bước.

#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
}

Tạo set từ các iterator của vector sẽ bỏ mọi phần tử trùng và sắp xếp phần còn lại: không cần vòng lặp thủ công, không cần sắp xếp rồi gọi thêm std::unique.

Tiếp theo: pair và tuple

Bạn đã thấy .first và .second xuất hiện trên pair mà insert trả về, và structured binding đi cùng từ khóa auto (auto [it, inserted]) tách nó ra gọn gàng. Những kiểu nhẹ "gom vài giá trị lại với nhau" này có mặt khắp nơi trong STL. Tiếp theo, chúng ta sẽ tìm hiểu trực tiếp pair và tuple: cách tạo, cách tách và cách trả về nhiều giá trị từ một hàm mà không cần định nghĩa cả một struct.