Bài 15: Thư viện STL C++ (phần 2) - Tập hợp (Set) và một số ứng dụng
I. Giới thiệu chung
Với những ai đã và đang học lập trình, đặc biệt là lập trình thi đấu, thì những cấu trúc dữ liệu như set
, map
hay dictionary
có lẽ là rất quen thuộc. Tên gọi của chúng có thể khác nhau ở các ngôn ngữ, nhưng tác dụng thì không hề thay đổi. Ứng dụng của chúng lớn đến mức, nhiều tài liệu khi hướng dẫn về lập trình cơ bản cũng đưa những cấu trúc dữ liệu này vào giảng dạy song song với mảng hay danh sách liên kết,...
Đúng như tên gọi của nó, tập hợp (set) là một cấu trúc dữ liệu dạng giống như mảng, lưu một danh sách các phần tử. Bản chất cấu trúc này được xây dựng dựa trên cấu trúc dữ liệu cây tìm kiếm nhị phân, nhưng nó đã phổ biến đến mức người ta quên đi cách cài đặt gốc của nó. Trong bài viết này, tôi sẽ giới thiệu tới các bạn về cách sử dụng chúng, cũng như minh họa một vài bài toán để bạn đọc hiểu hơn về ứng dụng của những cấu trúc này.
II. Sử dụng set
trong C++
1. Khai báo
Trong C++, set
là một associative container của thư viện Template chuẩn C++ (STL) (những container mà kiểm soát phần tử bằng giá trị chứ không phải bằng vị trí thì gọi là associative containers). Nó sử dụng để lưu trữ các phần tử có cùng kiểu dữ liệu, tuy nhiên các phần tử đó không được lặp lại.
Những phần tử được lưu trong set
gọi là khóa. Trong set
sử dụng sẵn phép so sánh mặc định là less
, nghĩa là phần tử đứng trước sẽ nhỏ hơn phần tử đứng sau (theo phép so sánh). Khi sử dụng set
, các bạn có thể viết lại hàm so sánh theo ý muốn của mình.
Để khai báo một set
, ta sử dụng những cú pháp sau:
#include <set>
using namespace std;
// Khởi tạo một set rỗng.
set <{Kiểu_phần_tử}> {Tên_set};
// Tạo một set từ mảng khác. Có thể tạo ra set từ một đoạn của mảng.
set <{Kiểu_phần_tử}> {Tên_set}({Phạm_vi_trên_mảng});
Ví dụ, dưới đây ta tạo ra một set
gồm toàn số nguyên từ một mảng cho trước (vector
cũng sử dụng tương tự):
#include <iostream>
#include <set>
using namespace std;
signed main()
{
int a[] = {1, 5, 2, 4, 3};
set < int > integers(a, a + 5); // integers = {1, 2, 3, 4, 5}.
return 0;
}
2. Các thao tác với set
trong C++
Duyệt set
Các phần tử trong set
không thể truy cập trực tiếp qua vị trí, mà buộc phải sử dụng vòng lặp để duyệt. Vì set
là một container thuộc STL, nên các phần tử của nó có thể duyệt qua bằng iterator
theo cú pháp:
// Khai báo biến lặp.
set < {Kiểu_phần_tử} > :: iterator {Tên_biến_lặp};
// Duyệt set.
for ({Biến_lặp} = {Địa_chỉ_đầu}; {Biến_lặp} != {Địa_chỉ_cuối}; ++{Biến_lặp})
Chẳng hạn, với một set
kiểu số nguyên là , ta duyệt qua nó như sau:
set < int > :: iterator it;
for (it = integers.begin(); it != integers.end(); ++it)
cout << *it << endl;
Với set
đoạn chương trình trên sẽ có kết quả là:
1
2
3
4
5
Các hàm dựng sẵn
Container set
đã xây dựng sẵn một số hàm để thao tác với set
, cụ thể tôi trình bày ở bảng dưới đây. Để sử dụng hàm, ta dùng cú pháp: {Tên_set}.{Tên_hàm}
. Coi rằng kích thước của set
hiện tại là .
Tên hàm | Tác dụng | Độ phức tạp |
---|---|---|
insert(x) |
Thêm phần tử vào tập hợp, tự động sắp xếp lại | |
find(x) |
Trả về iterator trỏ tới phần tử trong tập hợp, nếu không tìm thấy thì trả về iterator end() |
|
clear() |
Xóa toàn bộ tập hợp | |
erase(id) |
Xóa một phần tử trong tập hợp, có thể xóa theo khóa hoặc xóa theo iterator |
|
size() |
Trả về kích thước hiện tại của tập hợp | |
empty() |
Trả về true nếu tập hợp rỗng, ngược lại trả về false |
|
lower_bound(key) |
Trả về iterator trỏ tới phần tử nhỏ nhất có giá trị lớn hơn hoặc bằng khóa trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() |
|
upper_bound(key) |
Trả về iterator trỏ tới phần tử nhỏ nhất có giá trị lớn hơn khóa trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() |
|
count(key) |
Trả về số lần xuất hiện của khóa trong tập hợp |
Viết hàm so sánh cho set
Hàm so sánh của set
có thể được viết riêng theo ý các bạn theo cú pháp sau:
struct cmp
{
bool operator() ({Kiểu_phần_tử} x, {Kiểu_phần_tử} y)
{
return {Quan_hệ_x_và_y};
}
};
set <{Kiểu_phần_tử}, cmp> {Tên_set};
Trong hàm so sánh trên, phần tử sẽ đại diện cho phần tử đứng trước trong set
, đại diện cho phần tử đứng sau. Nếu như hàm đó trả về kết quả true
thì phần tử sẽ được xếp đứng trước phần tử trong set
, ngược lại thì hai phần tử sẽ đổi chỗ cho nhau.
Ví dụ, muốn tạo một set
lưu các số nguyên nhưng theo thứ tự giảm dần, ta làm như sau:
#include <iostream>
#include <set>
using namespace std;
struct cmp
{
bool operator() (int x, int y)
{
return x > y;
}
};
signed main()
{
int arr[] = {1, 5, 2, 4, 3};
set < int, cmp > integers(arr, arr + 5); // integers = {5, 4, 3, 2, 1}.
return 0;
}
3. Các cấu trúc multiset
và unordered_set
Ngoài ra, trong STL C++ còn xây dựng hai associative container khác gần giống với set
:
multi_set
: Cấu trúc này giống hệt nhưset
nhưng cho phép lưu trữ nhiều phần tử có cùng khóa với nhau. Các bạn có thể tìm hiểu thêm về cấu trúc này tại <i>đây.</i>unordered_set
: Cấu trúc này cũng giống nhưset
, nhưng các phần tử khi thêm vào sẽ không được sắp xếp theo thứ tự, nên các thao tác thêm và tìm kiếm phần tử chỉ tốn thời gian . Nhưng cũng chính vì thế mà cấu trúc này sẽ không có các hàm tìm kiếm nhưlower_bound()
vàupper_bound()
. Các bạn tìm hiểu thêm về cấu trúc này tại <i>đây.</i>
III. Một số bài toán minh họa
1. Bài toán 1
Đề bài
Tèo chuẩn bị tổ chức một bữa tiệc và anh ấy có nhiều thanh chocolate, trong đó có một số thanh chocolate cùng loại. Anh ấy muốn tặng chocolate cho bạn bè của mình một cách hoàn hảo, tức là mỗi người bạn của Tèo chỉ nhận được một thanh chocolate, và không có hai người bạn nào nhận được cùng một loại chocolate.
Yêu cầu: Hãy cho biết Tèo có thể tặng chocolate cho tối đa bao nhiêu người bạn?
Input:
- Dòng đầu tiên chứa số nguyên chỉ số lượng thanh chocolate mà Tèo đang có.
- Dòng thứ hai chứa số nguyên với là loại của thanh chocolate thứ .
Ràng buộc:
- .
- .
Output:
- Số nguyên duy nhất là số lượng người bạn tối đa mà Tèo có thể phát chocolate.
Sample Input:
3
1 2 2
Sample Output:
2
Ý tưởng
Ý tưởng của bài toán này rất rõ ràng là đếm số lượng phần tử khác nhau trong dãy số ban đầu.
Ta có một vài cách để làm bài toán này:
- Sắp xếp lại dãy số rồi duyệt lại cả dãy để xác định các phần tử phần biệt. Cách làm này hơi dài dòng và không đúng chủ đề nên tôi không đề cập.
- Đếm phân phối các phần tử trong dãy số ban đầu. Cách làm này chỉ mất phức tạp - không phù hợp với ràng buộc của bài toán là .
- Tạo ra một
set
từ dãy số ban đầu rồi đưa ra kích thước củaset
đó - cũng chính là số lượng phần tử phân biệt trongset
. Cách làm này ngắn gọn và phù hợp nhất cho bài này.
Độ phức tạp chung của giải thuật sẽ là .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
main()
{
int n;
cin >> n;
vector < int > a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
set < int > unique_elements(a.begin(), a.end());
cout << unique_elements.size();
}
2. Bài toán 2
Đề bài
Hãy gọi một số là - tốt nếu nó chứa tất cả các chữ số không vượt quá . Bi có một số và một mảng chứa số. Tìm giúp Bi xem có bao nhiêu số đẹp trong (đếm từng số mỗi khi nó xuất hiện trong mảng ).
Hãy xác định có bao nhiêu số - tốt trong dãy .
Input:
- Dòng đầu tiên chứa và tương ứng với đề bài.
- dòng tiếp theo, mỗi dòng chứa một số - phần tử thứ của mảng .
Ràng buộc:
- .
- .
- .
Output:
- In ra số lượng số - tốt trong dãy .
Sample Input:
2 1
1
10
Sample Output:
1
Ý tưởng
Ứng với mỗi số sử dụng đếm phân phối hoặc set
để đếm các chữ số khác nhau của nó mà không vượt quá . Nếu số lượng chữ số khác nhau đó đúng bằng thì số là số - tốt, ngược lại thì không phải.
Sử dụng set
tất nhiên sẽ cài đặt ngắn gọn hơn rất nhiều, nên tôi khuyến khích các bạn sử dụng cách này.
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
void enter(int& n, int& k, vector < string >& a)
{
cin >> n >> k;
a.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
void solution(int n, int k, vector < string >& a)
{
int res = 0;
for (int i = 1; i <= n; ++i)
{
set < char > digits;
for (char d: a[i])
{
if (d - '0' > k)
continue;
digits.insert(d);
}
res += (digits.size() == k + 1);
}
cout << res;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
vector < string > a;
enter(n, k, a);
solution(n, k, a);
return 0;
}
IV. Tài liệu tham khảo
- https://codelearn.io/Discussion/Topic/136961
- https://www.codegrepper.com/code-examples/cpp/c%2B%2B+custom+compare+in+set
- https://www.cplusplus.com/reference/set/multiset/
- https://www.cplusplus.com/reference/set/set/
©️ Tác giả: Vũ Quế Lâm từ Viblo
All Rights Reserved