Bài 18.5: Bài tập thực hành Set trong C++

Bài 18.5: Bài tập thực hành Set trong C++
Chào mừng các bạn đã quay trở lại với series blog C++ của chúng ta! Hôm nay, chúng ta sẽ cùng nhau đi sâu vào một container cực kỳ hữu ích và mạnh mẽ trong Standard Template Library (STL) của C++: set
. Nếu bạn cần một nơi để lưu trữ các phần tử độc nhất và luôn được sắp xếp một cách tự động, thì set
chính là người bạn đồng hành tuyệt vời của bạn!
set
là gì và Tại sao nó lại đặc biệt?
Hãy tưởng tượng bạn có một bộ sưu tập các đồ vật, và bạn muốn đảm bảo rằng:
- Không có hai đồ vật nào giống hệt nhau trong bộ sưu tập.
- Các đồ vật luôn được sắp xếp gọn gàng theo một quy tắc nào đó (ví dụ: theo tên, theo kích thước...).
Đó chính xác là những gì set
làm được!
set
là một cấu trúc dữ liệu container trong C++ STL, nó lưu trữ các phần tử theo một thứ tự cụ thể (mặc định là tăng dần) và đảm bảo rằng tất cả các phần tử đều là duy nhất.
Hai đặc điểm nổi bật nhất của set
là:
- Tính Độc Nhất (Uniqueness): Bạn không thể thêm một phần tử đã tồn tại vào set. Nếu bạn cố gắng, thao tác thêm sẽ đơn giản bị bỏ qua. Điều này cực kỳ tiện lợi khi bạn muốn lọc bỏ các phần tử trùng lặp một cách tự động.
- Tính Sắp Xếp Tự Động (Automatic Sorting): Các phần tử trong set luôn được duy trì ở trạng thái đã sắp xếp. Khi bạn thêm một phần tử mới, nó sẽ tự động được đặt vào đúng vị trí của nó để duy trì thứ tự.
Nhờ hai đặc điểm này, set
rất hiệu quả cho các thao tác như tìm kiếm, chèn, và xóa phần tử. Thời gian thực hiện cho các thao tác này thường là logarithmic (phụ thuộc vào logarit của số lượng phần tử), nhanh hơn đáng kể so với các container tuần tự như vector
hay list
khi cần tìm kiếm hoặc duy trì tính độc nhất/sắp xếp.
Bắt tay vào thực hành: Các thao tác cơ bản với set
Để sử dụng set
, bạn cần include header <set>
.
#include <set>
#include <iostream> // Để in ra kết quả
#include <string> // Nếu set chứa string
#include <vector> // Nếu dùng vector để khởi tạo hoặc lấy dữ liệu
int main() {
// Khai báo một set chứa các số nguyên
set<int> mySet;
// ... các thao tác sẽ được thêm vào đây ...
return 0;
}
1. Khai báo và Khởi tạo
Bạn có thể khai báo một set rỗng hoặc khởi tạo nó với các phần tử ban đầu.
#include <set>
#include <iostream>
#include <string>
#include <vector>
int main() {
// Khai báo một set rỗng chứa số nguyên
set<int> emptySet;
cout << "Set rong duoc tao.\n";
// Khai báo và khoi tao set voi cac gia tri ban dau
set<string> names = {"Alice", "Bob", "Charlie", "Alice"};
cout << "Set ten duoc tao voi cac ten: ";
// Duyệt set để xem nội dung (chúng ta sẽ học kỹ hơn ở mục 4)
for (const string& name : names) {
cout << name << " ";
}
cout << "\n";
// Chú ý: "Alice" chỉ xuất hiện 1 lần và các tên được sắp xếp!
// Khoi tao tu mot vector
vector<double> numbers = {3.14, 1.618, 2.718, 1.618, 0.577};
set<double> uniqueNumbers(numbers.begin(), numbers.end());
cout << "Set so thuc duy nhat tu vector: ";
for (double num : uniqueNumbers) {
cout << num << " ";
}
cout << "\n";
// Chú ý: 1.618 chỉ xuất hiện 1 lần và các số được sắp xếp!
return 0;
}
- Giải thích:
set<int> emptySet;
tạo một set rỗng chỉ chứa các số nguyên.set<string> names = {"Alice", "Bob", "Charlie", "Alice"};
sử dụng initializer list để khởi tạo set. Mặc dù "Alice" xuất hiện hai lần trong list khởi tạo, chỉ có một "Alice" được thêm vào set vì tính độc nhất. Các tên sẽ được sắp xếp theo thứ tự bảng chữ cái.set<double> uniqueNumbers(numbers.begin(), numbers.end());
khởi tạo set từ một range (ở đây là từ đầu đến cuối củavector<double>
). Tương tự, các phần tử trùng lặp sẽ bị loại bỏ và các phần tử còn lại sẽ được sắp xếp.
2. Thêm phần tử (insert
)
Để thêm một phần tử vào set, chúng ta sử dụng phương thức insert()
. Phương thức này trả về một cặp: một iterator
trỏ đến phần tử được chèn (hoặc phần tử đã tồn tại nếu là trùng lặp) và một bool
cho biết việc chèn có thành công hay không (true nếu chèn mới, false nếu phần tử đã tồn tại).
#include <set>
#include <iostream>
int main() {
set<int> mySet;
// Them cac phan tu
auto result1 = mySet.insert(10); // Chen thanh cong
auto result2 = mySet.insert(5); // Chen thanh cong
auto result3 = mySet.insert(20); // Chen thanh cong
auto result4 = mySet.insert(10); // Phan tu 10 da ton tai, chen KHONG thanh cong
cout << "Ket qua chen 10 (lan 1): " << (result1.second ? "Thanh cong" : "That bai") << "\n";
cout << "Ket qua chen 5: " << (result2.second ? "Thanh cong" : "That bai") << "\n";
cout << "Ket qua chen 20: " << (result3.second ? "Thanh cong" : "That bai") << "\n";
cout << "Ket qua chen 10 (lan 2): " << (result4.second ? "Thanh cong" : "That bai") << "\n";
cout << "Set sau khi chen: ";
for (int val : mySet) {
cout << val << " ";
}
cout << "\n";
// Chú ý: Thứ tự là 5 10 20, và 10 chỉ có 1 lần!
return 0;
}
- Giải thích:
- Chúng ta gọi
mySet.insert(value);
. - Kết quả trả về là một
pair<set<int>::iterator, bool>
..first
là iterator,.second
là boolean. - Khi chèn 10 lần đầu, nó chưa có trong set, nên chèn thành công (
result1.second
làtrue
). - Khi chèn 5 và 20, chúng cũng chưa có, chèn thành công.
- Khi chèn 10 lần thứ hai, nó đã có trong set, nên chèn không thành công (
result4.second
làfalse
) và set không thay đổi. - Các phần tử trong set được tự động sắp xếp: 5, 10, 20.
- Chúng ta gọi
3. Xóa phần tử (erase
)
Bạn có thể xóa một phần tử khỏi set dựa trên giá trị của nó hoặc dựa trên iterator
trỏ đến nó.
#include <set>
#include <iostream>
int main() {
set<int> mySet = {10, 5, 20, 15, 25}; // Khoi tao set {5, 10, 15, 20, 25}
cout << "Set ban dau: ";
for (int val : mySet) {
cout << val << " ";
}
cout << "\n";
// Xoa phan tu theo gia tri
size_t num_erased = mySet.erase(15); // Xoa gia tri 15
cout << "Da xoa " << num_erased << " phan tu co gia tri 15.\n"; // Se in ra 1
num_erased = mySet.erase(100); // Xoa gia tri 100 (khong ton tai)
cout << "Da xoa " << num_erased << " phan tu co gia tri 100.\n"; // Se in ra 0
cout << "Set sau khi xoa 15 va 100: ";
for (int val : mySet) {
cout << val << " ";
}
cout << "\n"; // Set con lai {5, 10, 20, 25}
// Xoa phan tu theo iterator
// Tim iterator den phan tu 10
auto it = mySet.find(10);
if (it != mySet.end()) { // Kiem tra xem tim thay khong
mySet.erase(it); // Xoa phan tu ma iterator dang tro den (la 10)
cout << "Da xoa phan tu tai iterator tro den (gia tri 10).\n";
} else {
cout << "Khong tim thay phan tu 10 de xoa.\n";
}
cout << "Set sau khi xoa 10 bang iterator: ";
for (int val : mySet) {
cout << val << " ";
}
cout << "\n"; // Set con lai {5, 20, 25}
return 0;
}
- Giải thích:
- Phương thức
erase(value)
trả về số lượng phần tử đã bị xóa (luôn là 0 hoặc 1 đối vớiset
vì tính độc nhất). mySet.erase(15);
tìm và xóa phần tử có giá trị 15.mySet.erase(100);
cố gắng xóa 100 nhưng nó không tồn tại trong set, nên không có gì xảy ra và phương thức trả về 0.- Bạn có thể xóa bằng
iterator
. Đầu tiên dùngfind()
để lấyiterator
đến phần tử cần xóa. Nếufind()
trả vềmySet.end()
tức là không tìm thấy. Nếu tìm thấy, ta gọimySet.erase(it);
.
- Phương thức
4. Kiểm tra sự tồn tại (find
, count
)
Có hai cách phổ biến để kiểm tra xem một phần tử có trong set hay không: sử dụng find()
hoặc count()
.
#include <set>
#include <iostream>
int main() {
set<int> mySet = {10, 5, 20};
cout << "Set hien tai: ";
for (int val : mySet) {
cout << val << " ";
}
cout << "\n";
// Su dung find()
auto it_found = mySet.find(10);
if (it_found != mySet.end()) {
cout << "Su dung find(): Phan tu 10 CO trong set.\n";
} else {
cout << "Su dung find(): Phan tu 10 KHONG co trong set.\n";
}
auto it_not_found = mySet.find(100);
if (it_not_found != mySet.end()) {
cout << "Su dung find(): Phan tu 100 CO trong set.\n";
} else {
cout << "Su dung find(): Phan tu 100 KHONG co trong set.\n"; // Day se la ket qua
}
cout << "---\n";
// Su dung count()
if (mySet.count(10) > 0) { // count() tra ve 0 hoac 1
cout << "Su dung count(): Phan tu 10 CO trong set.\n"; // Day se la ket qua
} else {
cout << "Su dung count(): Phan tu 10 KHONG co trong set.\n";
}
if (mySet.count(100) > 0) {
cout << "Su dung count(): Phan tu 100 CO trong set.\n";
} else {
cout << "Su dung count(): Phan tu 100 KHONG co trong set.\n"; // Day se la ket qua
}
return 0;
}
- Giải thích:
find(value)
: Trả về mộtiterator
trỏ đến phần tử nếu nó tồn tại. Nếu không tìm thấy, nó trả vềmySet.end()
(một iterator "past-the-end"). Bạn cần so sánh kết quả vớimySet.end()
để biết phần tử có tồn tại hay không.count(value)
: Trả về số lần xuất hiện của phần tử trong set. Vì set chỉ chứa các phần tử độc nhất,count()
sẽ trả về 1 nếu phần tử tồn tại và 0 nếu không tồn tại.count()
thường đơn giản hơn khi bạn chỉ cần kiểm tra sự có mặt của phần tử mà không cần lấy iterator đến nó.
5. Duyệt qua các phần tử
Vì set tự động sắp xếp các phần tử, khi duyệt qua set, bạn sẽ nhận được các phần tử theo đúng thứ tự đã sắp xếp (mặc định là tăng dần). Bạn có thể dùng iterator
hoặc range-based for loop.
#include <set>
#include <iostream>
#include <string>
int main() {
set<string> fruits = {"banana", "apple", "orange", "grape"};
cout << "Cac loai trai cay trong set (sap xep tu dong):\n";
// Cach 1: Su dung iterator
for (auto it = fruits.begin(); it != fruits.end(); ++it) {
cout << *it << "\n";
}
cout << "---\n";
// Cach 2: Su dung range-based for loop (don gian hon)
for (const string& fruit : fruits) {
cout << fruit << "\n";
}
return 0;
}
- Giải thích:
fruits.begin()
trả về iterator trỏ đến phần tử đầu tiên (đã sắp xếp).fruits.end()
trả về iterator "past-the-end".- Range-based for loop (
for (const string& fruit : fruits)
) là cú pháp hiện đại và gọn gàng hơn, tự động lặp từbegin()
đếnend()
.const&
được dùng để tránh sao chép không cần thiết và đảm bảo chúng ta không thay đổi phần tử trong khi duyệt.
6. Kích thước và Trạng thái (size
, empty
)
Các phương thức này giúp bạn kiểm tra số lượng phần tử trong set và xem set có rỗng hay không.
#include <set>
#include <iostream>
int main() {
set<int> mySet = {10, 5, 20};
cout << "Kich thuoc hien tai cua set: " << mySet.size() << "\n"; // In ra 3
if (mySet.empty()) {
cout << "Set dang rong.\n";
} else {
cout << "Set KHONG rong.\n"; // Day se la ket qua
}
set<int> emptySet;
if (emptySet.empty()) {
cout << "Set emptySet dang rong.\n"; // Day se la ket qua
}
return 0;
}
- Giải thích:
mySet.size()
trả về số lượng phần tử hiện có trong set.mySet.empty()
trả vềtrue
nếu set không chứa phần tử nào, ngược lại trả vềfalse
.
7. Xóa tất cả phần tử (clear
)
Phương thức clear()
xóa tất cả các phần tử khỏi set, làm cho set trở nên rỗng.
#include <set>
#include <iostream>
int main() {
set<int> mySet = {10, 5, 20, 15, 25};
cout << "Kich thuoc set ban dau: " << mySet.size() << "\n"; // In ra 5
mySet.clear(); // Xoa tat ca phan tu
cout << "Kich thuoc set sau khi clear(): " << mySet.size() << "\n"; // In ra 0
if (mySet.empty()) {
cout << "Set da duoc lam rong.\n"; // Day se la ket qua
}
return 0;
}
- Giải thích:
- Gọi
mySet.clear();
để xóa hết các phần tử. - Sau khi clear,
size()
sẽ là 0 vàempty()
sẽ trả vềtrue
.
- Gọi
Một ví dụ thực tế hơn: Tìm các số duy nhất trong một danh sách
Hãy sử dụng những kiến thức vừa học để giải quyết một bài toán nhỏ: Cho một danh sách các số, tìm và in ra các số duy nhất theo thứ tự tăng dần.
#include <set>
#include <vector>
#include <iostream>
#include <algorithm> // Chi dung cho sort (truoc khi dua vao set) neu muon so sanh
int main() {
vector<int> numbers = {1, 5, 2, 8, 2, 5, 10, 1, 3, 8};
cout << "Danh sach so ban dau: ";
for (int num : numbers) {
cout << num << " ";
}
cout << "\n";
// Su dung set de loc cac so duy nhat va sap xep chung
set<int> uniqueSortedNumbers;
// Them tung so tu vector vao set
for (int num : numbers) {
uniqueSortedNumbers.insert(num);
}
cout << "Cac so duy nhat (va da sap xep) trong danh sach:\n";
// Duyet qua set
for (int num : uniqueSortedNumbers) {
cout << num << " ";
}
cout << "\n";
// Mot cach khac ngan gon hon de khoi tao set tu vector
set<int> uniqueSortedNumbersFromVector(numbers.begin(), numbers.end());
cout << "Cach khoi tao ngan gon tu vector: ";
for (int num : uniqueSortedNumbersFromVector) {
cout << num << " ";
}
cout << "\n";
return 0;
}
- Giải thích:
- Chúng ta có một
vector
chứa các số, có cả số lặp lại và không theo thứ tự. - Chúng ta tạo một
set<int> uniqueSortedNumbers;
. - Khi lặp qua
vector
vàinsert
từng số vàoset
,set
sẽ tự động xử lý việc:- Chỉ thêm các số chưa có vào set (loại bỏ trùng lặp).
- Đặt các số vào đúng vị trí để duy trì thứ tự sắp xếp.
- Kết quả là khi chúng ta duyệt qua
set
, chúng ta nhận được các số duy nhất từvector
ban đầu và chúng đã được sắp xếp theo thứ tự tăng dần! Tuyệt vời phải không nào? - Cách thứ hai thể hiện việc khởi tạo set trực tiếp từ một range (ở đây là vector), đây là cú pháp rất tiện lợi cho những trường hợp như thế này.
- Chúng ta có một
Comments