Set - Tập hợp phần tử duy nhất

📖 Giới thiệu

Set là container lưu trữ các phần tử duy nhất theo thứ tự đã sắp xếp. Được implement bằng cây cân bằng (thường là Red-Black tree), cung cấp các operation O(log n).

Ví dụ đơn giản đầu tiên

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

int main() {
    set<int> numbers;
    
    // Thêm phần tử (tự động sắp xếp)
    numbers.insert(30);
    numbers.insert(10);
    numbers.insert(20);
    numbers.insert(10); // Trùng lặp, không thêm
    
    cout << "Set có " << numbers.size() << " phần tử: ";
    for (int x : numbers) {
        cout << x << " ";  // In ra: 10 20 30
    }
    cout << endl;
    
    // Tìm kiếm
    if (numbers.find(20) != numbers.end()) {
        cout << "Tìm thấy 20" << endl;
    }
    
    return 0;
}

🔧 Cú pháp

Khai báo Set

#include <set>

set<int> int_set;                        // Set rỗng
set<int> init_set{3, 1, 4, 1, 5};       // Khởi tạo với list
set<string> string_set;                  // Set string
multiset<int> multi_set;                 // Cho phép trùng lặp

Các phương thức chính

// Thêm/xóa
set.insert(value);           // Thêm phần tử
set.erase(value);           // Xóa theo giá trị  
set.erase(iterator);        // Xóa theo iterator
set.clear();                // Xóa tất cả

// Tìm kiếm
set.find(value);            // Trả về iterator
set.count(value);           // 0 hoặc 1 (multiset có thể > 1)
set.contains(value);        // C++20: true/false

// Thông tin
set.size();                 // Số phần tử
set.empty();                // Kiểm tra rỗng

💻 Ví dụ minh họa

Ví dụ 1: Hệ thống quản lý từ điển

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

class Dictionary {
private:
    set<string> words;
    multiset<string> word_frequency; // Để thống kê
    
public:
    Dictionary() {
        cout << "📚 Khởi tạo từ điển" << endl;
    }
    
    void add_word(const string& word) {
        string lower_word = to_lowercase(word);
        
        auto result = words.insert(lower_word);
        if (result.second) {
            cout << "✅ Đã thêm từ mới: " << word << endl;
        } else {
            cout << "ℹ️ Từ đã tồn tại: " << word << endl;
        }
        
        word_frequency.insert(lower_word); // Luôn thêm để đếm tần suất
    }
    
    bool check_word(const string& word) {
        string lower_word = to_lowercase(word);
        return words.find(lower_word) != words.end();
    }
    
    void remove_word(const string& word) {
        string lower_word = to_lowercase(word);
        
        if (words.erase(lower_word)) {
            cout << "🗑️ Đã xóa từ: " << word << endl;
        } else {
            cout << "❌ Không tìm thấy từ: " << word << endl;
        }
    }
    
    void find_words_starting_with(const string& prefix) {
        string lower_prefix = to_lowercase(prefix);
        
        cout << "🔍 Từ bắt đầu với '" << prefix << "':" << endl;
        
        auto it = words.lower_bound(lower_prefix);
        int count = 0;
        
        while (it != words.end() && it->substr(0, lower_prefix.length()) == lower_prefix) {
            cout << "  " << *it << endl;
            ++it;
            ++count;
        }
        
        if (count == 0) {
            cout << "  (Không tìm thấy)" << endl;
        } else {
            cout << "  Tổng: " << count << " từ" << endl;
        }
    }
    
    void find_words_in_range(const string& start, const string& end) {
        string lower_start = to_lowercase(start);
        string lower_end = to_lowercase(end);
        
        cout << "📖 Từ trong khoảng [" << start << ", " << end << "]:" << endl;
        
        auto begin_it = words.lower_bound(lower_start);
        auto end_it = words.upper_bound(lower_end);
        
        int count = 0;
        for (auto it = begin_it; it != end_it; ++it) {
            cout << "  " << *it << endl;
            ++count;
        }
        
        cout << "  Tổng: " << count << " từ" << endl;
    }
    
    void print_statistics() {
        cout << "\n📊 THỐNG KÊ TỪ ĐIỂN" << endl;
        cout << "Tổng số từ duy nhất: " << words.size() << endl;
        cout << "Tổng số từ đã nhập: " << word_frequency.size() << endl;
        
        if (!words.empty()) {
            cout << "Từ đầu tiên (theo alphabet): " << *words.begin() << endl;
            cout << "Từ cuối cùng (theo alphabet): " << *words.rbegin() << endl;
        }
        
        // Top 5 từ xuất hiện nhiều nhất
        map<string, int> freq_count;
        for (const auto& word : word_frequency) {
            freq_count[word]++;
        }
        
        vector<pair<int, string>> freq_pairs;
        for (const auto& p : freq_count) {
            freq_pairs.push_back({p.second, p.first});
        }
        
        sort(freq_pairs.rbegin(), freq_pairs.rend());
        
        cout << "\nTop 5 từ xuất hiện nhiều nhất:" << endl;
        for (int i = 0; i < min(5, (int)freq_pairs.size()); i++) {
            cout << "  " << freq_pairs[i].second << ": " << freq_pairs[i].first << " lần" << endl;
        }
    }
    
    void print_all_words() {
        if (words.empty()) {
            cout << "📋 Từ điển trống!" << endl;
            return;
        }
        
        cout << "\n📋 TẤT CẢ TỪ TRONG TỪ ĐIỂN (" << words.size() << " từ):" << endl;
        
        int count = 0;
        for (const auto& word : words) {
            cout << setw(15) << word;
            if (++count % 4 == 0) cout << endl;
        }
        if (count % 4 != 0) cout << endl;
    }
    
private:
    string to_lowercase(const string& str) {
        string result = str;
        transform(result.begin(), result.end(), result.begin(), ::tolower);
        return result;
    }
};

int main() {
    cout << "=== HỆ THỐNG TỪ ĐIỂN ===" << endl;
    
    Dictionary dict;
    
    // Thêm từ
    cout << "\n--- Thêm từ vào từ điển ---" << endl;
    dict.add_word("apple");
    dict.add_word("banana");
    dict.add_word("cherry");
    dict.add_word("date");
    dict.add_word("elderberry");
    dict.add_word("fig");
    dict.add_word("grape");
    dict.add_word("apple"); // Trùng lặp
    dict.add_word("apricot");
    dict.add_word("avocado");
    
    dict.print_all_words();
    
    // Tìm kiếm
    cout << "\n--- Tìm kiếm từ ---" << endl;
    vector<string> search_words = {"apple", "orange", "banana"};
    for (const string& word : search_words) {
        if (dict.check_word(word)) {
            cout << "✅ Tìm thấy: " << word << endl;
        } else {
            cout << "❌ Không tìm thấy: " << word << endl;
        }
    }
    
    // Tìm từ theo prefix
    cout << "\n--- Tìm từ theo prefix ---" << endl;
    dict.find_words_starting_with("a");
    dict.find_words_starting_with("gr");
    
    // Tìm từ trong khoảng
    cout << "\n--- Tìm từ trong khoảng ---" << endl;
    dict.find_words_in_range("b", "d");
    
    // Thống kê
    dict.print_statistics();
    
    return 0;
}

🏋️ Thực hành

Bài tập 1: Unique Number Tracker

Tạo class theo dõi số duy nhất trong stream data

Bài tập 2: Tag System

Hệ thống tag cho blog với set operations

Bài tập 3: Student Grade Tracker

Tracking điểm duy nhất, tìm median, range queries

📋 Tóm tắt

1. Set: Unique elements, tự động sắp xếp
2. Complexity: Insert/Find/Erase O(log n)
3. Multiset: Cho phép duplicate elements
4. Unordered_set: Hash-based, O(1) average

Bài tiếp theo: Map - Key-value associations.