std::set và std::unordered_set

std::set và std::unordered_set lưu trữ một tập hợp các giá trị không trùng lặp - mỗi giá trị chỉ xuất hiện đúng một lần, giống khái niệm tập hợp trong toán học.

std::set: có thứ tự, không trùng lặp

#include <set>
#include <iostream>

int main() {
    std::set<int> numbers = {5, 2, 8, 2, 1, 5};

    for (int n : numbers) {
        std::cout << n << " ";
    }
    // 1 2 5 8
    // (Các giá trị trùng lặp tự động bị loại bỏ, và luôn được sắp xếp tăng dần)

    return 0;
}

Thêm và xóa phần tử

#include <set>
#include <iostream>

int main() {
    std::set<int> numbers;

    numbers.insert(10);
    numbers.insert(5);
    numbers.insert(10); // Không có tác dụng gì - 10 đã có trong set

    std::cout << numbers.size() << std::endl; // 2

    numbers.erase(5);
    std::cout << numbers.size() << std::endl; // 1

    return 0;
}

Kiểm tra một giá trị có trong set không

#include <set>
#include <iostream>

int main() {
    std::set<int> numbers = {1, 2, 3};

    if (numbers.find(2) != numbers.end()) {
        std::cout << "2 co trong set" << std::endl;
    }

    if (numbers.count(5) == 0) {
        std::cout << "5 khong co trong set" << std::endl;
    }

    return 0;
}

std::unordered_set: nhanh hơn, không có thứ tự

Tương tự mối quan hệ giữa map và unordered_map, unordered_set dùng bảng băm để tra cứu nhanh hơn nhưng không đảm bảo thứ tự:

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<std::string> visited;

    visited.insert("Hanoi");
    visited.insert("Saigon");
    visited.insert("Hanoi"); // Không thêm trùng

    std::cout << visited.size() << std::endl; // 2

    return 0;
}

Ứng dụng thực tế: loại bỏ phần tử trùng lặp

Một ứng dụng rất phổ biến của set là loại bỏ các giá trị trùng lặp khỏi một danh sách:

#include <vector>
#include <set>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 3, 2, 3, 1, 4, 2};
    std::set<int> unique_numbers(numbers.begin(), numbers.end());

    for (int n : unique_numbers) {
        std::cout << n << " ";
    }
    // 1 2 3 4

    return 0;
}

Khi nào dùng set, khi nào dùng unordered_set?

Giống nguyên tắc của map/unordered_map: dùng set khi cần các phần tử được sắp xếp tự động, dùng unordered_set khi chỉ cần kiểm tra sự tồn tại nhanh mà không quan tâm thứ tự.

Tổng kết

• set/unordered_set lưu trữ các giá trị duy nhất, tự động loại bỏ trùng lặp
• set có thứ tự (sắp xếp tăng dần theo mặc định); unordered_set nhanh hơn nhưng không có thứ tự
• Dùng .find()/.count() để kiểm tra một giá trị có tồn tại trong set hay không
• Ứng dụng phổ biến: loại bỏ phần tử trùng lặp, kiểm tra sự tồn tại nhanh chóng