STARTING
CONTROL STATEMENT
FUNCTION
ARRAY & POINTER
OOP
STL
ITERATORS
OTHER FEATURES
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

[STL] Sử dụng Set trong C++

STL (Standard Template Library) cung cấp một loạt các cấu trúc dữ liệu và thuật toán tiêu chuẩn giúp làm việc với dữ liệu một cách hiệu quả. Một trong những cấu trúc dữ liệu quan trọng trong STL là set, là một container được sắp xếp không lặp lại. Trong bài viết này, mình sẽ tìm hiểu cách sử dụng set trong STL của C++ và đi kèm là các ví dụ minh họa.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Set trong C++ là gì?

Screenshot 202024 03 25 20180617 png

Set là một cấu trúc dữ liệu trong C++ được sử dụng để lưu trữ các phần tử duy nhất, tức là mỗi phần tử chỉ xuất hiện một lần trong Set. Set thường được sắp xếp theo thứ tự tăng dần mặc định, nhưng bạn cũng có thể chỉ định một hàm so sánh tùy chỉnh.

Set trong C++ được triển khai bằng cách sử dụng cấu trúc dữ liệu cây nhị phân cân bằng (balanced binary search tree), thường là cây đỏ đen (red-black tree), giúp việc thêm, xóa và tìm kiếm phần tử có độ phức tạp trung bình là O(log n), với n là số lượng phần tử trong Set.

Set trong C++ được định nghĩa trong thư viện tiêu chuẩn của C++ (STL - Standard Template Library) thông qua header <set>.

Bài viết này được đăng tại [free tuts .net]

Ứng dụng của Set trong C++:

Loại bỏ các phần tử trùng lặp

Một trong những ứng dụng chính của Set là loại bỏ các phần tử trùng lặp từ một tập hợp. Khi bạn cần lưu trữ một danh sách các phần tử mà không muốn phép tử nào lặp lại, Set là lựa chọn lý tưởng.

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30, 10, 40, 20, 50};
    // Set chỉ chứa các phần tử duy nhất
    // mySet: {10, 20, 30, 40, 50}
    return 0;
}

Thực hiện các phép toán tập hợp

Set cung cấp các phương thức để thực hiện các phép toán tập hợp như giao, hợp và hiệu giữa hai tập hợp. Điều này rất hữu ích khi bạn cần so sánh hay kết hợp các tập hợp dữ liệu.

#include <iostream>
#include <set>
#include <algorithm>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {4, 5, 6, 7, 8};
    
    // Tìm giao của hai Set
    std::set<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersection, intersection.begin()));
    
    // Tìm hợp của hai Set
    std::set<int> unionSet;
    std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(unionSet, unionSet.begin()));
    //Bài viết được đăng tại freetuts.net

    // Tìm hiệu của hai Set
    std::set<int> difference;
    std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(difference, difference.begin()));
    
    return 0;
}

Set trong C++ là một công cụ mạnh mẽ và linh hoạt trong việc xử lý dữ liệu tập hợp và thực hiện các phép toán tập hợp một cách dễ dàng.

Cấu trúc dữ liệu Set trong C++

Khai báo Set trong C++

Trong C++, để sử dụng cấu trúc dữ liệu Set, bạn cần bao gồm thư viện <set>. Cấu trúc dữ liệu Set được triển khai dưới dạng một tập hợp các phần tử duy nhất được sắp xếp theo thứ tự tăng dần mặc định. Dưới đây là cách khai báo một Set trong C++:

#include <set>

std::set<int> mySet; // Khai báo một Set chứa các số nguyên

Bạn cũng có thể chỉ định một hàm so sánh tùy chỉnh khi khai báo Set để sắp xếp các phần tử theo yêu cầu của mình.

#include <set>
// Bài viết được đăng tại freetuts.net

// Hàm so sánh tùy chỉnh để sắp xếp Set theo thứ tự giảm dần
bool customComparator(int a, int b) {
    return a > b;
}

std::set<int, decltype(customComparator)*> mySet(customComparator); // Khai báo một Set với hàm so sánh tùy chỉnh

Tính chất của Set trong C++

Các phần tử duy nhất

Các phần tử duy nhất: Set không chứa các phần tử trùng lặp. Khi bạn thêm một phần tử vào Set và phần tử đó đã tồn tại, nó sẽ không được thêm vào mà Set vẫn giữ nguyên trạng thái không thay đổi.

#include <iostream>
#include <set>
// Bài viết được đăng tại freetuts.net

int main() {
    std::set<int> mySet;
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(10); // Thêm phần tử 10 lần nữa, nhưng Set chỉ chứa một phần tử 10
    std::cout << "Size of mySet: " << mySet.size() << std::endl; // Output: Size of mySet: 2
    return 0;
}

Trong ví dụ này, mặc dù mình đã thêm phần tử 10 hai lần vào Set, nhưng kích thước của Set vẫn là 2 vì Set chỉ chứa các phần tử duy nhất.

Sắp xếp tự động

Set sắp xếp các phần tử theo thứ tự tăng dần mặc định. Điều này giúp Set trở nên rất hữu ích khi bạn cần duy trì một tập hợp các phần tử có thứ tự nhất định.

#include <iostream>
#include <set>
// Bài viết được đăng tại freetuts.net
int main() {
    std::set<int> mySet;
    mySet.insert(20);
    mySet.insert(10);
    mySet.insert(30);
    std::cout << "Contents of mySet: ";
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    // Output: Contents of mySet: 10 20 30
    return 0;
}

Trong ví dụ này, các phần tử đã được sắp xếp tự động theo thứ tự tăng dần mặc định khi duyệt qua Set.

Độ phức tạp của các thao tác: Các thao tác thêm, xóa và tìm kiếm phần tử trong Set có độ phức tạp trung bình là O(log n), với n là số lượng phần tử trong Set. Điều này là do Set được triển khai dưới dạng một cây nhị phân cân bằng, thường là cây đỏ đen.

Triển khai Set trong STL trong C++

Cấu trúc dữ liệu Set trong C++ được triển khai trong thư viện tiêu chuẩn của C++ (STL - Standard Template Library) thông qua header <set>. Trong STL, Set được triển khai dưới dạng một dạng con của cấu trúc dữ liệu dạng cân bằng (balanced tree), thường là cây đỏ đen (red-black tree). Điều này đảm bảo các thao tác thêm, xóa và tìm kiếm đều có độ phức tạp logarit với số lượng phần tử trong Set.

#include <iostream>
#include <set>
// Bài viết được đăng tại freetuts.net

int main() {
    std::set<int> mySet;
    mySet.insert(20);
    mySet.insert(10);
    mySet.insert(30);
    std::cout << "Contents of mySet: ";
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    // Output: Contents of mySet: 10 20 30
    return 0;
}

Đối với Set trong STL, các phần tử được tự động sắp xếp theo thứ tự tăng dần mặc định. Bạn cũng có thể chỉ định một hàm so sánh tùy chỉnh nếu bạn muốn sắp xếp các phần tử theo một thứ tự khác.

Các phép toán cơ bản trên Set trong C++

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

Để thêm một phần tử vào Set trong C++, bạn có thể sử dụng phương thức insert(). Set sẽ tự động loại bỏ các phần tử trùng lặp.

#include <iostream>
#include <set>
//Bài viết được đăng tại freetuts.net

int main() {
    std::set<int> mySet;
    mySet.insert(10); // Thêm phần tử 10 vào Set
    mySet.insert(20); // Thêm phần tử 20 vào Set
    mySet.insert(10); // Thêm phần tử 10 lần nữa, nhưng Set chỉ chứa một phần tử 10
    return 0;
}

Xóa phần tử khỏi Set

Để xóa một phần tử khỏi Set, bạn có thể sử dụng phương thức erase(). Bạn có thể chỉ định phần tử cụ thể hoặc một vùng được xác định bởi hai iterators.

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {10, 20, 30};
    mySet.erase(20); // Xóa phần tử 20 khỏi Set
    return 0;
}

Tìm kiếm phần tử trong Set

Để tìm kiếm một phần tử trong Set, bạn có thể sử dụng phương thức find(). Nếu phần tử được tìm thấy, phương thức này trả về iterator đến phần tử đó; nếu không, nó trả về end() của Set.

#include <iostream>
#include <set>
// Bài viết được đăng tại freetuts.net

int main() {
    std::set<int> mySet = {10, 20, 30};
    auto it = mySet.find(20);
    if (it != mySet.end()) {
        std::cout << "Phần tử 20 được tìm thấy trong Set";
    } else {
        std::cout << "Phần tử 20 không tồn tại trong Set";
    }
    return 0;
}

Screenshot 202024 03 25 20180519 png

Giao, hợp, hiệu của hai Set

Bạn có thể thực hiện các phép toán tập hợp trên hai Set bằng cách sử dụng các phương thức std::set_intersection, std::set_union, và std::set_difference từ thư viện <algorithm>.

#include <iostream>
#include <set>
#include <algorithm>
// Bài viết được đăng tại freetuts.net

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {4, 5, 6, 7, 8};
    
    std::set<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersection, intersection.begin()));
    
    std::set<int> unionSet;
    std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(unionSet, unionSet.begin()));
    
    std::set<int> difference;
    std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(difference, difference.begin()));
    return 0;
}

Kiểm tra tính chất con tập hợp

Bạn có thể kiểm tra xem một Set có phải là con tập hợp của một Set khác hay không bằng cách sử dụng phương thức includes() hoặc std::includes().

#include <iostream>
#include <set>
#include <algorithm>
// Bài viết được đăng tại freetuts.net

int main() {
    std::set<int> set1 = {1, 2, 3};
    std::set<int> set2 = {1, 2, 3, 4, 5};
    bool isSubset = std::includes(set2.begin(), set2.end(), set1.begin(), set1.end());
    if (isSubset) {
        std::cout << "Set1 là con tập hợp của Set2";
    } else {
        std::cout << "Set1 không phải là con tập hợp của Set2";
    }
    return 0;
}

Screenshot 202024 03 25 20180435 png

Ví dụ thực hành Set trong C++

Ví dụ về việc sử dụng Set để loại bỏ các phần tử trùng lặp

Trong ví dụ này, mình sẽ sử dụng Set để loại bỏ các phần tử trùng lặp từ một mảng.

#include <iostream>
#include <set>
#include <vector>
// Bài viết được đăng tại freetuts.net

int main() {
    std::vector<int> numbers = {10, 20, 30, 10, 40, 20, 50};
    std::set<int> uniqueNumbers;

    // Thêm từng phần tử từ mảng vào Set, Set sẽ tự động loại bỏ các phần tử trùng lặp
    for (int num : numbers) {
        uniqueNumbers.insert(num);
    }

    // In ra các phần tử duy nhất đã loại bỏ các phần tử trùng lặp
    std::cout << "Cac phan tu duy nhat: ";
    for (int num : uniqueNumbers) {
        std::cout << num << " ";
    }
    return 0;
}

Kết quả sẽ là:

Screenshot 202024 03 25 20180329 png

Ví dụ về phép toán tập hợp trên Set

Trong ví dụ này, mình sẽ thực hiện các phép toán giao, hợp và hiệu của hai Set.

#include <iostream>
#include <set>
#include <algorithm>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {4, 5, 6, 7, 8};
    
    // Giao của hai Set
    std::set<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersection, intersection.begin()));
    
    // Hợp của hai Set
    std::set<int> unionSet;
    std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(unionSet, unionSet.begin()));
    
    // Hiệu của hai Set
    std::set<int> difference;
    std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(difference, difference.begin()));

    // In ra kết quả của các phép toán tập hợp
    std::cout << "Giao cua hai Set: ";
    for (int num : intersection) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    //Bài viết được đăng tại freetuts.net

    std::cout << "Hop cua hai Set: ";
    for (int num : unionSet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Hieu cua hai Set: ";
    for (int num : difference) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Kết quả sẽ là:

Screenshot 202024 03 25 20180400 png

Trong hai ví dụ trên, đã minh họa cách sử dụng Set để loại bỏ các phần tử trùng lặp và thực hiện các phép toán tập hợp như giao, hợp và hiệu của hai Set.

Kết bài

Set là một cấu trúc dữ liệu mạnh mẽ trong C++, cung cấp tính chất tự động sắp xếp và loại bỏ các phần tử trùng lặp một cách hiệu quả. Bằng cách sử dụng Set, bạn có thể giải quyết một loạt các vấn đề liên quan đến việc lưu trữ dữ liệu duy nhất và sắp xếp chúng theo yêu cầu của bạn. Hi vọng bài viết này đã giúp bạn hiểu rõ hơn về Set trong C++ và cách sử dụng nó trong ứng dụng của mình.

Cùng chuyên mục:

Các hàm xử lý mảng đa chiều (array.h) trong C/C++

Các hàm xử lý mảng đa chiều (array.h) trong C/C++

Các hàm xử lý ngày tháng (datetime.h) trong C/C++

Các hàm xử lý ngày tháng (datetime.h) trong C/C++

Các hàm xử lý số thực (float.h) trong C/C++

Các hàm xử lý số thực (float.h) trong C/C++

Các hàm xử lý số nguyên lớn (bigint.h) trong C/C++

Các hàm xử lý số nguyên lớn (bigint.h) trong C/C++

Các hàm xử lý thời gian (time.h) trong C

Các hàm xử lý thời gian (time.h) trong C

Các hàm xử lý chuỗi (string.h) trong C/C++

Các hàm xử lý chuỗi (string.h) trong C/C++

Thread Pools và Parallel Algorithms trong C++

Thread Pools và Parallel Algorithms trong C++

Tạo và quản lý các Multithreading trong C++

Tạo và quản lý các Multithreading trong C++

Xử lý ngoại lệ khi làm việc với Memory Allocation trong C++

Xử lý ngoại lệ khi làm việc với Memory Allocation trong C++

Try, Catch, và Throw của Exception Handling trong C++

Try, Catch, và Throw của Exception Handling trong C++

Cách sử dụng Lambda Expressions trong C++

Cách sử dụng Lambda Expressions trong C++

Sử dụng weak_ptr trong C++

Sử dụng weak_ptr trong C++

Sử dụng shared_ptr trong C++

Sử dụng shared_ptr trong C++

Sử dụng unique_ptr trong C++

Sử dụng unique_ptr trong C++

Tổng quan về Smart Pointers trong C++

Tổng quan về Smart Pointers trong C++

Sử dụng Iterators trong STL của C++

Sử dụng Iterators trong STL của C++

[Iterator] Sử dụng Vector trong C++

[Iterator] Sử dụng Vector trong C++

[Iterator] Sử dụng trong List trong C++

[Iterator] Sử dụng trong List trong C++

[STL] Sử dụng Vector trong C++

[STL] Sử dụng Vector trong C++

Tổng quan về Iterators trong C++

Tổng quan về Iterators trong C++

Top