Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng [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.
Set trong C++ là gì?
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;
}
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;
}
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à:
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à:
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.
