Bài 18.1: Khái niệm và sử dụng Set trong C++
Bài 18.1: Khái niệm và sử dụng Set trong C++
Chào mừng các bạn quay trở lại với series blog của FullhouseDev về C++! Trong bài viết thứ 18 này, chúng ta sẽ cùng khám phá một cấu trúc dữ liệu cực kỳ hữu ích và mạnh mẽ trong Thư viện Chuẩn (STL) của C++: set. Nếu bạn đã từng làm việc với các tập hợp (set) trong toán học, thì khái niệm này sẽ rất quen thuộc.
Set là một container liên kết (associative container) đặc biệt, nổi bật với hai đặc tính cốt lõi:
- Chứa các phần tử duy nhất: Bạn không thể thêm hai phần tử có giá trị giống hệt nhau vào một set.
- Các phần tử luôn được sắp xếp: Set tự động duy trì các phần tử theo một thứ tự nhất định (mặc định là thứ tự tăng dần đối với số và theo thứ tự từ điển đối với chuỗi).
Nhờ hai đặc tính này, set trở thành lựa chọn tuyệt vời khi bạn cần quản lý một bộ sưu tập dữ liệu mà bạn muốn đảm bảo không có sự trùng lặp và cần truy xuất hoặc duyệt qua các phần tử theo thứ tự.
Về mặt kỹ thuật, set thường được triển khai dựa trên cấu trúc cây tìm kiếm nhị phân cân bằng (Balanced Binary Search Tree), chẳng hạn như Red-Black Tree. Điều này mang lại hiệu suất logarit (O(log n)) cho hầu hết các thao tác quan trọng như thêm, xóa và tìm kiếm phần tử.
Làm quen với set
Để sử dụng set, bạn cần include header <set>.
#include <set>
Khai báo một set rất đơn giản. Bạn cần chỉ định kiểu dữ liệu của các phần tử mà set sẽ chứa:
set<int> myIntSet; // Một set chứa các số nguyên
set<string> myStringSet; // Một set chứa các chuỗi
Các Thao tác Cơ bản với set
Chúng ta sẽ đi qua các thao tác phổ biến nhất khi làm việc với set cùng với các ví dụ minh họa.
1. Thêm phần tử (insert)
Thao tác insert() dùng để thêm một phần tử mới vào set. Nếu phần tử đó đã tồn tại, thao tác sẽ bị bỏ qua và set không thay đổi.
#include <iostream>
#include <set>
#include <string>
int main() {
set<string> uniqueWords;
// Thêm các từ vào set
uniqueWords.insert("apple");
uniqueWords.insert("banana");
uniqueWords.insert("cherry");
uniqueWords.insert("apple"); // Thêm lại 'apple', sẽ bị bỏ qua
uniqueWords.insert("date");
cout << "Cac tu trong set (duoc sap xep):" << endl;
// Duyệt qua set - các phần tử sẽ được in ra theo thứ tự từ điển
for (const string& word : uniqueWords) {
cout << "- " << word << endl;
}
// Output:
// - apple
// - banana
// - cherry
// - date
return 0;
}
Giải thích: Trong ví dụ này, chúng ta tạo một set chứa chuỗi. Khi chúng ta insert("apple") lần thứ hai, set đã có "apple" nên thao tác này không có hiệu lực. Khi duyệt qua set, các từ được in ra theo thứ tự từ điển tự động.
2. Kiểm tra sự tồn tại của phần tử (count và find)
Có hai cách chính để kiểm tra xem một phần tử có tồn tại trong set hay không:
count(value): Trả về1nếuvaluetồn tại trong set, và0nếu không.find(value): Trả về một iterator trỏ đến phần tử nếu nó tồn tại. Nếu không tìm thấy, nó trả vềset.end().findthường hiệu quả hơncountnếu bạn có ý định làm gì đó với phần tử sau khi tìm thấy (ví dụ: xóa nó).
#include <iostream>
#include <set>
int main() {
set<int> numbers = {10, 20, 30, 40, 50};
// Kiem tra su ton tai bang count
if (numbers.count(30)) {
cout << "So 30 ton tai trong set." << endl; // Sẽ in ra dòng này
} else {
cout << "So 30 khong ton tai trong set." << endl;
}
if (numbers.count(99)) {
cout << "So 99 ton tai trong set." << endl;
} else {
cout << "So 99 khong ton tai trong set." << endl; // Sẽ in ra dòng này
}
cout << "------------------" << endl;
// Kiem tra su ton tai bang find
auto it_40 = numbers.find(40);
if (it_40 != numbers.end()) {
cout << "Tim thay so 40 tai vi tri iterator." << endl; // Sẽ in ra dòng này
} else {
cout << "Khong tim thay so 40." << endl;
}
auto it_5 = numbers.find(5);
if (it_5 != numbers.end()) {
cout << "Tim thay so 5 tai vi tri iterator." << endl;
} else {
cout << "Khong tim thay so 5." << endl; // Sẽ in ra dòng này
}
return 0;
}
Giải thích: Ví dụ này minh họa cả hai cách kiểm tra sự tồn tại. count(30) trả về 1, count(99) trả về 0. find(40) trả về một iterator hợp lệ, trong khi find(5) trả về numbers.end(), cho biết 5 không có trong set.
3. Xóa phần tử (erase)
Bạn có thể xóa phần tử khỏi set bằng cách sử dụng erase(). Có nhiều phiên bản của erase():
erase(value): Xóa phần tử có giá trịvalue. Trả về số lượng phần tử đã xóa (luôn là 1 nếu tìm thấy và xóa, hoặc 0 nếu không tìm thấy).erase(iterator): Xóa phần tử tại vị trí được chỉ định bởi iterator.
#include <iostream>
#include <set>
int main() {
set<double> prices = {1.1, 2.2, 3.3, 4.4, 5.5};
cout << "Set ban dau: ";
for (double p : prices) cout << p << " ";
cout << endl; // Output: 1.1 2.2 3.3 4.4 5.5
// Xoa phan tu co gia tri 3.3
size_t removed_count = prices.erase(3.3);
cout << "Da xoa " << removed_count << " phan tu co gia tri 3.3." << endl; // Output: Da xoa 1 phan tu co gia tri 3.3.
// Xoa phan tu khong ton tai
removed_count = prices.erase(99.9);
cout << "Da xoa " << removed_count << " phan tu co gia tri 99.9." << endl; // Output: Da xoa 0 phan tu co gia tri 99.9.
// Xoa phan tu bang iterator (tim phan tu 2.2 truoc)
auto it_2_2 = prices.find(2.2);
if (it_2_2 != prices.end()) {
prices.erase(it_2_2);
cout << "Da xoa phan tu tai vi tri cua 2.2." << endl; // Sẽ in ra
}
cout << "Set sau khi xoa: ";
for (double p : prices) cout << p << " ";
cout << endl; // Output: 1.1 4.4 5.5
return 0;
}
Giải thích: Chúng ta lần lượt xóa phần tử bằng giá trị (3.3) và bằng iterator (tìm 2.2 rồi dùng iterator đó để xóa). Set tự động cập nhật và duy trì trạng thái sắp xếp.
4. Duyệt (Iterate) qua Set
Duyệt qua các phần tử trong set là cách để truy cập từng phần tử một. Vì set luôn được sắp xếp, việc duyệt sẽ cho bạn các phần tử theo thứ tự tăng dần (hoặc thứ tự tùy chỉnh nếu bạn cung cấp hàm so sánh khác). Cách thông thường là dùng range-based for loop hoặc iterator.
#include <iostream>
#include <set>
#include <string>
int main() {
set<string> colors = {"red", "green", "blue", "yellow"};
cout << "Cac mau trong set (duoc sap xep tu dien):" << endl;
// Cach 1: Range-based for loop (de doc nhat)
for (const string& color : colors) {
cout << "- " << color << endl;
}
// Output:
// - blue
// - green
// - red
// - yellow
cout << "------------------" << endl;
// Cach 2: Su dung iterator (co ban va linh hoat hon)
cout << "Duyet set bang iterator:" << endl;
for (auto it = colors.begin(); it != colors.end(); ++it) {
cout << "* " << *it << endl;
}
// Output tuong tu:
// * blue
// * green
// * red
// * yellow
return 0;
}
Giải thích: Cả hai cách đều cho phép duyệt qua các phần tử. Range-based for loop đơn giản hơn cho việc duyệt toàn bộ, trong khi iterator linh hoạt hơn nếu bạn cần thao tác đặc biệt (ví dụ: xóa khi đang duyệt, nhưng cần cẩn thận với việc iterator bị mất hiệu lực).
5. Kích thước (size) và Xóa toàn bộ (clear)
Bạn có thể lấy số lượng phần tử hiện có trong set bằng size() và xóa tất cả các phần tử bằng clear().
#include <iostream>
#include <set>
int main() {
set<int> data = {10, 20, 30, 40};
cout << "Kich thuoc ban dau cua set: " << data.size() << endl; // Output: 4
data.insert(50);
cout << "Kich thuoc sau khi them 50: " << data.size() << endl; // Output: 5
data.insert(20); // 20 da ton tai
cout << "Kich thuoc sau khi them lai 20: " << data.size() << endl; // Output: 5 (khong thay doi)
data.erase(10);
cout << "Kich thuoc sau khi xoa 10: " << data.size() << endl; // Output: 4
data.clear(); // Xoa het
cout << "Kich thuoc sau khi clear: " << data.size() << endl; // Output: 0
return 0;
}
Giải thích: size() trả về số lượng phần tử duy nhất. clear() đặt set về trạng thái rỗng, làm cho size() trở thành 0.
Khi nào nên sử dụng set?
set là một lựa chọn tuyệt vời khi bạn cần:
- Lưu trữ một tập hợp các phần tử mà không muốn có sự trùng lặp.
- Truy cập các phần tử theo một thứ tự nhất định (mặc định là tăng dần/từ điển).
- Thực hiện các thao tác thêm, xóa, tìm kiếm với hiệu suất logarit O(log n), rất hiệu quả cho các tập dữ liệu lớn.
Ví dụ:
- Theo dõi danh sách các ID người dùng duy nhất đang hoạt động.
- Tìm các từ duy nhất trong một văn bản và hiển thị chúng theo thứ tự bảng chữ cái.
- Kiểm tra nhanh xem một phần tử có nằm trong một tập hợp lớn các giá trị không trùng lặp hay không.
Comments