C++: Set

Tổng quan

Trong C++, set (tập hợp) là một cấu trúc dữ liệu lưu trữ các phần tử cùng kiểu dữ liệu duy nhất, nghĩa là mỗi phần tử chỉ có thể xuất hiện một lần trong tập hợp. Nó là một phần của Thư viện mẫu chuẩn (STL) và được triển khai dưới dạng vùng chứa kết hợp, cụ thể là cây nhị phân được sắp xếp.

Sử dụng set

Để sử dụng set, cần khai báo thư viện

#include <set>

Khởi tạo set với một kiểu dữ liệu nhất định

std::set<int> mySet; // tạo một set rỗng chứa các phần tử kiểu int

Thêm phần tử vào set

mySet.insert(5);
mySet.insert(10);
mySet.insert(3);
// các phần tử trong mySet đã được thêm vào và sắp xếp theo thứ tự 3, 5, 10

Duyệt các phần tử của set

Có thể sử dụng iterator để duyệt qua các phần tử của một tập hợp

for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << " "; // output: 3 5 10
}

Tìm một phần tử trong set

Hàm find() trong set container của C++ trả về một iterator trỏ đến phần tử cần tìm nếu nó được tìm thấy trong set và nó trả về iterator end() của set nếu phần tử đó không có trong set.

auto it = mySet.find(3); // tìm phần tử 3
if (it != mySet.end()) {
    std::cout << "Phan tu " << *it << " xuat hien trong set" << std::endl; 
} else {
    std::cout << "Phan tu khong ton tai" << std::endl;
}

Xóa một phần tử khỏi set

Hàm erase() trong set C++ được sử dụng để xóa các phần tử khỏi tập hợp dựa trên giá trị của chúng hoặc sử dụng trình vòng lặp.

Khi bạn sử dụng erase() với một giá trị không có trong set, sẽ không có gì xảy ra.

mySet.erase(6); // không có gì xảy ra, set vẫn giữ nguyên các giá trị 3 5 10

mySet.erase(5); // set gồm các phần tử 3 10

Set Operations

Các tập hợp trong C++ hỗ trợ nhiều thao tác tập hợp khác nhau như hợp(union), giao(intersec), hiệu(difference), v.v.

std::set<int> set1 = {1, 2, 3, 4};
std::set<int> set2 = {3, 4, 5, 6};

// Union
std::set<int> unionSet;
std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(unionSet, unionSet.begin()));

// Intersection
std::set<int> intersectionSet;
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersectionSet, intersectionSet.begin()));

// Difference
std::set<int> differenceSet;
std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(differenceSet, differenceSet.begin()));

​Tùy chỉnh toán tử so sánh

Định nghĩa chức năng so sánh riêng để tùy chỉnh  sắp xếp theo mong muốn. Ví dụ về việc sử dụng set với toán tử so sánh giảm dần với phần tử kiểu int:
 

#include <iostream>
#include <set>

struct CompareIntDescending {
    bool operator()(const int& a, const int& b) const {
        return a > b; // Reverse the comparison for descending order
    }
};

int main() {
    std::set<int, CompareIntDescending> mySet;

    mySet.insert(10);
    mySet.insert(5);
    mySet.insert(20);
    mySet.insert(15);

    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    // Output: 20 15 10 5
    return 0;
}