10.3K 778 120

Đã đăng vào thg 8 24, 2022 6:06 SA 9 phút đọc

20.1K

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 đã và đang học lập trình, đặc biệt là lập trình thi đấu, thì những cấu trúc dữ liệu như set, map hay dictionary có lẽ là rất quen thuộc. Tên gọi của chúng có thể khác nhau ở các ngôn ngữ, nhưng tác dụng thì không hề thay đổi. Ứng dụng của chúng lớn đến mức, nhiều tài liệu khi hướng dẫn về lập trình cơ bản cũng đưa những cấu trúc dữ liệu này vào giảng dạy song song với mảng hay danh sách liên kết,...

Đúng như tên gọi của nó, tập hợp (set) là một cấu trúc dữ liệu dạng giống như mảng, lưu một danh sách các phần tử. Bản chất cấu trúc này được xây dựng dựa trên cấu trúc dữ liệu cây tìm kiếm nhị phân, nhưng nó đã phổ biến đến mức người ta quên đi cách cài đặt gốc của nó. Trong bài viết này, tôi sẽ giới thiệu tới các bạn về cách sử dụng chúng, cũng như minh họa một vài bài toán để bạn đọc hiểu hơn về ứng dụng của những cấu trúc này.

II. Sử dụng `set` trong C++

1. Khai báo

Trong C++, set là một associative container của thư viện Template chuẩn C++ (STL) (những container mà kiểm soát phần tử bằng giá trị chứ không phải bằng vị trí thì gọi là associative containers). Nó sử dụng để lưu trữ các phần tử có cùng kiểu dữ liệu, tuy nhiên các phần tử đó không được lặp lại.

Những phần tử được lưu trong set gọi là khóa. Trong set sử dụng sẵn phép so sánh mặc định là less, nghĩa là phần tử đứng trước sẽ nhỏ hơn phần tử đứng sau (theo phép so sánh). Khi sử dụng set, các bạn có thể viết lại hàm so sánh theo ý muốn của mình.

Để khai báo một set, ta sử dụng những cú pháp sau:

#include <set>

using namespace std;

// Khởi tạo một set rỗng.
set <{Kiểu_phần_tử}> {Tên_set};
// Tạo một set từ mảng khác. Có thể tạo ra set từ một đoạn của mảng.
set <{Kiểu_phần_tử}> {Tên_set}({Phạm_vi_trên_mảng});

Ví dụ, dưới đây ta tạo ra một set gồm toàn số nguyên từ một mảng cho trước (vector cũng sử dụ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. Các thao tác với `set` trong C++

Duyệt `set`

Các phần tử trong set không thể truy cập trực tiếp qua vị trí, mà buộc phải sử dụng vòng lặp để duyệt. Vì set là một container thuộc STL, nên các phần tử của nó có thể duyệt qua bằng iterator theo cú pháp:

// Khai bá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} = {Địa_chỉ_đầu}; {Biến_lặp} != {Địa_chỉ_cuối}; ++{Biến_lặp})

Chẳng hạn, với một set kiểu số nguyên là $\text{integers}$ , ta duyệt qua nó như sau:

set < int > :: iterator it;
for (it = integers.begin(); it != integers.end(); ++it)
    cout << *it << endl;

Với set $\text{integers} = \{1, 2, 3, 4, 5\};$ đoạn chương trình trên sẽ có kết quả là:

Các hàm dựng sẵn

Container set đã xây dựng sẵn một số hàm để thao tác với set, cụ thể tôi trình bày ở bảng dưới đây. Để sử dụng hàm, ta dùng cú pháp: {Tên_set}.{Tên_hàm}. Coi rằng kích thước của set hiện tại là $n$ .

Tên hàm	Tác dụng	Độ phức tạp
`insert(x)`	Thêm phần tử $x$ vào tập hợp, tự động sắp xếp lại	$O\big(\log(n)\big)$
`find(x)`	Trả về `iterator` trỏ tới phần tử $x$ trong tập hợp, nếu không tìm thấy thì trả về `iterator` `end()`	$O\big(\log(n)\big)$
`clear()`	Xóa toàn bộ tập hợp	$O(n)$
`erase(id)`	Xóa một phần tử $id$ trong tập hợp, có thể xóa theo khóa hoặc xóa theo `iterator`	$O\big(\log(n)\big)$
`size()`	Trả về kích thước hiện tại của tập hợp	$O(1)$
`empty()`	Trả về `true` nếu tập hợp rỗng, ngược lại trả về `false`	$O(1)$
`lower_bound(key)`	Trả về `iterator` trỏ tới phần tử nhỏ nhất có giá trị lớn hơn hoặc bằng khóa $\text{key}$ trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về `iterator` `end()`	$O\big(\log(n)\big)$
`upper_bound(key)`	Trả về `iterator` trỏ tới phần tử nhỏ nhất có giá trị lớn hơn khóa $key$ trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về `iterator` `end()`	$O\big(\log(n)\big)$
`count(key)`	Trả về số lần xuất hiện của khóa $\text{key}$ trong tập hợp	$O\big(\log(n)\big)$

Viết hàm so sánh cho `set`

Hàm so sánh của set có thể được viết riêng theo ý các bạn theo cú pháp sau:

struct cmp
{
    bool operator() ({Kiểu_phần_tử} x, {Kiểu_phần_tử} y) 
    {
        return {Quan_hệ_x_và_y};
    }
};

set <{Kiểu_phần_tử}, cmp> {Tên_set};

Trong hàm so sánh trên, phần tử $x$ sẽ đại diện cho phần tử đứng trước trong set, $y$ đại diện cho phần tử đứng sau. Nếu như hàm đó trả về kết quả true thì phần tử $x$ sẽ được xếp đứng trước phần tử $y$ trong set, ngược lại thì hai phần tử sẽ đổi chỗ cho nhau.

Ví dụ, muốn tạo một set lưu các số nguyên nhưng theo thứ tự giảm dần, ta là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. Các cấu trúc `multiset` và `unordered_set`

Ngoài ra, trong STL C++ còn xây dựng hai associative container khác gần giống với set:

multi_set: Cấu trúc này giống hệt như set nhưng cho phép lưu trữ nhiều phần tử có cùng khóa với nhau. Các bạn có thể tìm hiểu thêm về cấu trúc này tại <i>đây.</i>
unordered_set: Cấu trúc này cũng giống như set, nhưng các phần tử khi thêm vào sẽ không được sắp xếp theo thứ tự, nên các thao tác thêm và tìm kiếm phần tử chỉ tốn thời gian $O(1)$ . Nhưng cũng chính vì thế mà cấu trúc này sẽ không có các hàm tìm kiếm như lower_bound() và upper_bound(). Các bạn tìm hiểu thêm về cấu trúc này tại <i>đây.</i>

III. Một số bài toán minh họa

1. Bài toán 1

Đề bà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, và không có hai người bạn nào nhận được cùng một loại chocolate.

Yêu cầu: Hãy cho biết Tèo có thể tặng chocolate cho tối đa bao nhiêu người bạn?

Input:

Dòng đầu tiên chứa số nguyên $n$ chỉ số lượng thanh chocolate mà Tèo đang có.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, ..., a_n$ với $a_i$ là loại của thanh chocolate thứ $i$ .

Ràng buộc:

$1 \le n \le 10^6$ .
$0 \le a_i \le 10^9; \forall i: 1 \le i \le n$ .

Output:

Số nguyên duy nhất là số lượng người bạn tối đa mà Tèo có thể phát chocolate.

Sample Input:

3
1 2 2

Sample Output:

Ý tưởng

Ý tưởng của bài toán này rất rõ ràng là đếm số lượng phần tử khác nhau trong dãy số ban đầu.

Ta có một vài cách để làm bài toán này:

Sắp xếp lại dãy số rồi duyệt lại cả dãy để xác định các phần tử phần biệt. Cách làm này hơi dài dòng và không đúng chủ đề nên tôi không đề cập.
Đếm phân phối các phần tử trong dãy số ban đầu. Cách làm này chỉ mất phức tạp $O\big(\text{max}(a_i)\big)$ - không phù hợp với ràng buộc của bài toán là $a_i \le 10^9$ .
Tạo ra một set từ dãy số ban đầu rồi đưa ra kích thước của set đó - cũng chính là số lượng phần tử phân biệt trong set. Cách làm này ngắn gọn và phù hợp nhất cho bài này.

Độ phức tạp chung của giải thuật sẽ là $O\big(n.\log(n)\big)$ .

Cà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. Bài toán 2

Đề bài

Hãy gọi một số là $k$ - tốt nếu nó chứa tất cả các chữ số không vượt quá $k \ (0, ..., k)$ . Bi có một số $k$ và một mảng $A$ chứa $n$ số. Tìm giúp Bi xem có bao nhiêu số đẹp $k$ trong $A$ (đếm từng số mỗi khi nó xuất hiện trong mảng $a$ ).

Hãy xác định có bao nhiêu số $k$ - tốt trong dãy $A?$ .

Input:

Dòng đầu tiên chứa $n$ và $k$ tương ứng với đề bài.
$n$ dòng tiếp theo, mỗi dòng chứa một số $a_i$ - phần tử thứ $i$ của mảng $A \ (1 \le i \le n)$ .

Ràng buộc:

$1 \le n \le 10^5$ .
$0 \le k \le 9$ .
$1 \le a_i \le 10^9; \forall i: 1 \le i \le n$ .

Output:

In ra số lượng số $k$ - tốt trong dãy $a$ .

Sample Input:

2 1
1
10

Sample Output:

Ý tưởng

Ứng với mỗi số $a_i,$ sử dụng đếm phân phối hoặc set để đếm các chữ số khác nhau của nó mà không vượt quá $k$ . Nếu số lượng chữ số khác nhau đó đúng bằng $k + 1$ thì số $a_i$ là số $k$ - tốt, ngược lại thì không phải.

Sử dụng set tất nhiên sẽ cài đặt ngắn gọn hơn rất nhiều, nên tôi khuyến khích các bạn sử dụng cách này.

Độ phức tạp: $O\big(n \times \log(k)\big)$ .

Cà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. Tài liệu tham khảo

I. Giới thiệu chung

II. Sử dụng set trong C++

1. Khai báo

2. Các thao tác với set trong C++

Duyệt set

Các hàm dựng sẵn

Viết hàm so sánh cho set

3. Các cấu trúc multiset và unordered_set

III. Một số bài toán minh họa

1. Bài toán 1

Đề bài

Ý tưởng

Cài đặt

2. Bài toán 2

Đề bài

Ý tưởng

Cài đặt

IV. Tài liệu tham khảo

Mục lục

II. Sử dụng `set` trong C++

2. Các thao tác với `set` trong C++

Duyệt `set`

Viết hàm so sánh cho `set`

3. Các cấu trúc `multiset` và `unordered_set`