Bài 20.1: Bài tập thực hành Set cơ bản trong C++
Bài 20.1: Bài tập thực hành Set cơ bản trong C++
Chào mừng quay trở lại với series học C++ cùng FullhouseDev! Hôm nay, chúng ta sẽ khám phá và thực hành một cấu trúc dữ liệu cực kỳ mạnh mẽ và hữu ích trong Thư viện Chuẩn C++ (STL): Set.
Set là một bộ sưu tập các phần tử, nhưng với hai đặc điểm quan trọng làm nên sức mạnh của nó:
- Không chấp nhận phần tử trùng lặp: Mỗi phần tử trong Set là duy nhất. Nếu bạn cố gắng thêm một phần tử đã tồn tại, thao tác đó sẽ bị bỏ qua.
- Tự động sắp xếp (với
set): Các phần tử trongsetluôn được lưu trữ ở dạng đã sắp xếp theo một thứ tự nhất định (mặc định là tăng dần).
Bài viết này sẽ hướng dẫn bạn thực hành các thao tác cơ bản với set thông qua các ví dụ code C++ ngắn gọn, dễ hiểu.
Để sử dụng Set, chúng ta cần include header <set>.
#include <iostream>
#include <set>
#include <string> // Có thể lưu trữ chuỗi trong Set
Khởi tạo một Set
Bạn có thể khởi tạo một Set rỗng hoặc khởi tạo nó với các giá trị từ một phạm vi khác (như mảng, vector, list...).
#include <iostream>
#include <set>
int main() {
// Khởi tạo một Set rỗng chứa số nguyên
set<int> setSoNguyen;
cout << "Set so nguyen ban dau rong: " << boolalpha << setSoNguyen.empty() << endl; // Output: true
// Khởi tạo một Set rỗng chứa chuỗi
set<string> setChuoi;
cout << "Set chuoi ban dau co kich thuoc: " << setChuoi.size() << endl; // Output: 0
return 0;
}
Giải thích: Chúng ta khai báo các biến kiểu set. Bên trong dấu ngoặc nhọn <>, chúng ta chỉ định kiểu dữ liệu mà Set này sẽ chứa (ví dụ: int, string). empty() kiểm tra xem Set có rỗng không, còn size() trả về số lượng phần tử hiện có.
Thêm phần tử vào Set (insert)
Thao tác cốt lõi để đưa dữ liệu vào Set là sử dụng phương thức insert(). Hãy nhớ: các phần tử trùng lặp sẽ không được thêm vào.
#include <iostream>
#include <set>
int main() {
set<int> setSoNguyen;
// Them cac phan tu
setSoNguyen.insert(10);
setSoNguyen.insert(30);
setSoNguyen.insert(20);
setSoNguyen.insert(10); // Them lai phan tu 10 (se bi bo qua)
setSoNguyen.insert(40);
setSoNguyen.insert(20); // Them lai phan tu 20 (se bi bo qua)
cout << "So luong phan tu trong Set: " << setSoNguyen.size() << endl; // Output: 4 (10, 20, 30, 40)
return 0;
}
Giải thích: Chúng ta thêm các số 10, 30, 20, 10, 40, 20 vào setSoNguyen. Mặc dù chúng ta gọi insert 6 lần, nhưng vì 10 và 20 được thêm lặp lại, Set cuối cùng chỉ chứa các phần tử duy nhất là 10, 20, 30, và 40. Kích thước của Set lúc này là 4.
Duyệt (Iterate) qua các phần tử trong Set
Vì set giữ các phần tử đã sắp xếp, việc duyệt qua Set sẽ cho chúng ta các phần tử theo thứ tự đó. Cách đơn giản nhất là dùng vòng lặp dựa trên phạm vi (range-based for loop).
#include <iostream>
#include <set>
int main() {
set<int> setSoNguyen;
setSoNguyen.insert(30);
setSoNguyen.insert(10);
setSoNguyen.insert(40);
setSoNguyen.insert(20);
cout << "Cac phan tu trong Set (da sap xep):" << endl;
for (int phanTu : setSoNguyen) {
cout << phanTu << " ";
}
cout << endl; // Output: 10 20 30 40
return 0;
}
Giải thích: Vòng lặp for (int phanTu : setSoNguyen) tự động lặp qua từng phần tử trong Set theo thứ tự đã sắp xếp. Kết quả in ra cho thấy rõ điều này: 10, 20, 30, 40 dù thứ tự insert ban đầu khác.
Tìm kiếm một phần tử (find hoặc count)
Có hai cách phổ biến để kiểm tra xem một phần tử có tồn tại trong Set hay không:
find(): Trả về một iterator trỏ đến phần tử nếu tìm thấy, hoặcset.end()nếu không tìm thấy.count(): Trả về 1 nếu phần tử tồn tại, hoặc 0 nếu không tồn tại (đối vớiset, vì phần tử là duy nhất).
Sử dụng count() thường đơn giản hơn cho việc chỉ kiểm tra sự tồn tại.
#include <iostream>
#include <set>
int main() {
set<int> setSoNguyen;
setSoNguyen.insert(10);
setSoNguyen.insert(20);
setSoNguyen.insert(30);
int soCanTim1 = 20;
int soCanTim2 = 50;
// Su dung find()
auto it = setSoNguyen.find(soCanTim1);
if (it != setSoNguyen.end()) {
cout << "Tim thay " << soCanTim1 << " trong Set (su dung find)" << endl;
} else {
cout << "Khong tim thay " << soCanTim1 << " trong Set (su dung find)" << endl;
}
// Su dung count()
if (setSoNguyen.count(soCanTim2) > 0) {
cout << "Tim thay " << soCanTim2 << " trong Set (su dung count)" << endl;
} else {
cout << "Khong tim thay " << soCanTim2 << " trong Set (su dung count)" << endl; // Output: Khong tim thay 50...
}
return 0;
}
Giải thích: find(soCanTim1) trả về iterator trỏ đến 20, nên điều kiện it != setSoNguyen.end() đúng. count(soCanTim2) trả về 0 vì 50 không có trong Set, nên điều kiện > 0 sai.
Xóa phần tử khỏi Set (erase)
Bạn có thể xóa một phần tử bằng cách truyền giá trị của nó hoặc sử dụng iterator.
#include <iostream>
#include <set>
int main() {
set<int> setSoNguyen;
setSoNguyen.insert(10);
setSoNguyen.insert(20);
setSoNguyen.insert(30);
setSoNguyen.insert(40);
cout << "Set ban dau: ";
for (int phanTu : setSoNguyen) cout << phanTu << " ";
cout << endl; // Output: 10 20 30 40
// Xoa phan tu theo gia tri
setSoNguyen.erase(20); // Xoa phan tu co gia tri 20
setSoNguyen.erase(50); // Co gang xoa phan tu khong ton tai (khong gay loi)
cout << "Set sau khi xoa 20 va 50: ";
for (int phanTu : setSoNguyen) cout << phanTu << " ";
cout << endl; // Output: 10 30 40
// Xoa phan tu theo iterator (can tim iterator truoc)
auto it = setSoNguyen.find(30);
if (it != setSoNguyen.end()) {
setSoNguyen.erase(it); // Xoa phan tu ma 'it' dang tro den (la 30)
}
cout << "Set sau khi xoa 30 bang iterator: ";
for (int phanTu : setSoNguyen) cout << phanTu << " ";
cout << endl; // Output: 10 40
return 0;
}
Giải thích: erase(20) tìm và xóa phần tử có giá trị 20. erase(50) được gọi nhưng vì 50 không có trong Set, Set không thay đổi và không có lỗi xảy ra. Để xóa bằng iterator, trước tiên chúng ta dùng find() để lấy iterator trỏ đến phần tử cần xóa (ở đây là 30), sau đó gọi erase(it).
Set với kiểu dữ liệu khác
Set không chỉ giới hạn ở số nguyên, bạn có thể lưu trữ bất kỳ kiểu dữ liệu nào mà có thể so sánh được (để Set có thể sắp xếp chúng), ví dụ như chuỗi (string).
#include <iostream>
#include <set>
#include <string>
int main() {
set<string> setTen;
setTen.insert("Alice");
setTen.insert("Charlie");
setTen.insert("Bob");
setTen.insert("Alice"); // Duplicates ignored
cout << "Danh sach ten duy nhat (da sap xep theo chu cai):" << endl;
for (const string& ten : setTen) {
cout << ten << endl;
}
// Output:
// Alice
// Bob
// Charlie
return 0;
}
Giải thích: Set chứa các chuỗi được sắp xếp theo thứ tự từ điển. Tên "Alice" chỉ xuất hiện một lần.
Một ví dụ tổng hợp nhỏ
Giả sử bạn đọc một danh sách các từ từ input và muốn biết có bao nhiêu từ duy nhất và in chúng ra theo thứ tự bảng chữ cái. Set là công cụ hoàn hảo cho việc này!
#include <iostream>
#include <set>
#include <string>
#include <vector>
int main() {
set<string> setTuDuyNhat;
vector<string> danhSachTu = {"apple", "banana", "apple", "orange", "banana", "grape"};
cout << "Danh sach tu ban dau: ";
for (const auto& tu : danhSachTu) {
cout << tu << " ";
}
cout << endl;
// Them tat ca tu vao Set
for (const string& tu : danhSachTu) {
setTuDuyNhat.insert(tu);
}
cout << "------------------------" << endl;
cout << "Tong so tu duy nhat: " << setTuDuyNhat.size() << endl; // Output: 4
cout << "Cac tu duy nhat (da sap xep):" << endl;
for (const string& tu : setTuDuyNhat) {
cout << tu << endl;
}
/* Output:
apple
banana
grape
orange
*/
return 0;
}
Giải thích: Chúng ta đưa tất cả các từ từ danhSachTu vào setTuDuyNhat. Set tự động loại bỏ các từ trùng lặp và sắp xếp chúng. Sau đó, chúng ta chỉ cần lấy kích thước của Set để biết số lượng từ duy nhất và duyệt qua Set để in các từ đó theo thứ tự đã sắp xếp.
unordered_set: Khi thứ tự không quan trọng
Ngoài set (dựa trên cây nhị phân tìm kiếm cân bằng, đảm bảo thứ tự và thao tác O(log N)), STL còn cung cấp unordered_set (dựa trên bảng băm). unordered_set không đảm bảo thứ tự các phần tử, nhưng các thao tác cơ bản (insert, find, erase) có độ phức tạp trung bình là O(1) - nhanh hơn nhiều trong hầu hết các trường hợp.
Để sử dụng unordered_set, bạn cần include <unordered_set>.
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
unordered_set<string> setTuKhongSapXep;
setTuKhongSapXep.insert("apple");
setTuKhongSapXep.insert("banana");
setTuKhongSapXep.insert("orange");
setTuKhongSapXep.insert("apple"); // Duplicates ignored
cout << "Cac tu duy nhat (thu tu khong dam bao):" << endl;
for (const string& tu : setTuKhongSapXep) {
cout << tu << endl;
}
// Thu tu in ra co the khac moi lan chay, vi du:
// orange
// apple
// banana
cout << "Set co chua 'banana'? " << boolalpha << (setTuKhongSapXep.count("banana") > 0) << endl; // Output: true
setTuKhongSapXep.erase("apple");
cout << "Set co chua 'apple' sau khi xoa? " << boolalpha << (setTuKhongSapXep.count("apple") > 0) << endl; // Output: false
return 0;
}
Giải thích: Tương tự như set, unordered_set cũng chỉ chứa các phần tử duy nhất và cung cấp các thao tác insert, count, erase. Điểm khác biệt lớn nhất là thứ tự các phần tử khi duyệt qua không cố định và không theo quy luật sắp xếp nào cả. Hãy cân nhắc sử dụng unordered_set khi bạn không cần thứ tự, vì nó có thể mang lại hiệu suất tốt hơn.
Tổng kết (Ngắn gọn)
Qua các ví dụ trên, bạn đã làm quen với các thao tác thiết yếu khi làm việc với set (và cả unordered_set). Set là một công cụ cực kỳ hữu ích khi bạn cần quản lý một tập hợp các phần tử duy nhất và (với set) giữ chúng theo thứ tự. Hãy luyện tập thật nhiều với các bài tập khác để nắm vững cấu trúc dữ liệu này nhé!
Comments