---
title:
Standard Template Library (STL) (Phần 3: Associative containers và Unordered containers)
---

Standard Template Library (STL) (Phần 3: Associative containers và Unordered containers)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Giới thiệu chung
Đây là bài viết thứ 3 trong chuỗi 4 bài viết về STL (Standard Template Library) với chủ đề chính là **associative containers**. Đây là các cấu trúc dữ liệu (CTDL) *chỉ* sử dụng **con trỏ (iterator)** để truy cập các phần tử chứa trong chúng (*không* sử dụng **chỉ số (index)**). **Map**, **set**, **multiset** và ngoài ra còn có **multimap** là các CTDL dạng associative container.

Ngoài ra thì **unordered containers** cũng sẽ được giới thiệu sơ qua trong bài viết này.

# Map (ánh xạ)
## 1. Cấu trúc và cơ chế hoạt động
**Map** hoạt động dựa trên một khái niệm toán học cùng tên là **ánh xạ (mapping)** *(mọi người có thể tự tìm hiểu thêm nếu thích)*. Mỗi phần tử trong map gồm có 2 thành phần: **khoá (key)** đại diện cho *một và chỉ một* **giá trị (value)**. Nghĩa là *hai* key *có thể có cùng* giá trị nhưng *hai* giá trị thì *không thể có cùng* key.

- *(Ảnh được lấy từ Programiz)*

## 2. Các cú pháp và hàm thông dụng
- `map <char, int> mp` - khai báo map `mp` với kiểu dữ liệu của các key là char, kiểu dữ liệu của các giá trị là int và các **key** được sắp xếp **tăng dần**.
- `map <char, int, greater <char>> mp` - khai báo map `mp` với kiểu dữ liệu của các key là char, kiểu dữ liệu của các giá trị là int và các **key** được sắp xếp **giảm dần**.
*(cả hai map trên đều giống nhau trong mọi tình huống, trừ khi sử dụng các hàm `lower_bound` và `upper_bound`, ngoài ra thì lưu ý là ta **không** thể khai báo map được sắp xếp tăng hay giảm dần theo **giá trị**)*
- `mp[x]` - truy cập giá trị của key `x` trong map `mp` *(lưu ý là tốn độ phức tạp $O(logN)$)*.
- Truy cập bằng iterator:
- `(*it).first` hoặc `it->first` - truy cập vào **key** của iterator trỏ vào phần tử trong map `mp`.
- `(*it).second` hoặc `it->second` - truy cập vào **value** của iterator trỏ vào phần tử trong map `mp`.

### a. Cách duyệt qua map

*Cách duyệt map hoặc bất cứ các CTDL ở phần này hầu như giống với [các CTDL đã được trình bày ở phần 2](https://hackmd.io/@2SchoolGuideline/S1XcVF7rT). Chỉ khác nhau ở phần không thể truy cập được bằng vị trí.*

#### Sử dụng vòng lặp for-each (chỉ sử dụng cho C++11 trở lên)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    map <int, int> mp = {{2, 1}, {3, 4}, {5, 7}, {7, 9}, {11, 13}};
    for (pair<int, int> i : mp)
    {
        // logic code
        cout << i.first << " " << i.second << endl;
    }
}

#### Sử dụng iterator

#include <bits/stdc++.h>
using namespace std;

int main()
{
    map <int, int> mp = {{2, 1}, {3, 4}, {5, 7}, {7, 9}, {11, 13}};
    for (map <int, int>::iterator it = mp.begin(); it != mp.end(); it++)
    {
        // logic code
        cout << it->first << " " << it->second << endl;
    }
}

### b. Các hàm có độ phức tạp O(1)
- `mp.empty()` - trả về **true** nếu map `mp` **rỗng** (không có phần tử nào) và **false** nếu map `mp` có **ít nhất 1 phần tử**.
- `mp.size()` - trả về **kích thước** (số lượng phần tử) của map `mp`.

### c. Các hàm có độ phức tạp O(logN)
*($N$ là kích thước của map `mp`)*
- `mp.insert({a, b})` - **gán** cho key `a` giá trị `b`, tức là làm cho key `a` **đại diện** cho giá trị `b` trong map `mp` *(hoặc ta có thể sử dụng toán tử `mp[a] = b`)*.
- `mp.erase(a)` - **xoá** giá trị mà key `a` đại diện ra khỏi map `mp`.
- `mp.erase(it)` - **xoá** iterator `it` trỏ vào phần tử trong `mp`.
- `mp.lower_bound(x)`
+ Trả về **iterator** trỏ vào phần tử có **key** **nhỏ nhất** mà **$\ge$** `x` trong map `mp` (nếu map `mp` được sắp xếp **tăng dần** theo **key**).
+ Trả về **iterator** trỏ vào phần tử có **key** **lớn nhất** mà **$\le$** `x` trong map `mp` (nếu map `mp` được sắp xếp **giảm dần** theo **key**).
- `mp.upper_bound(x)`
+ Trả về **iterator** trỏ vào phần tử có **key** **nhỏ nhất** mà **$>$** `x` trong map `mp` (nếu map `mp` được sắp xếp **tăng dần** theo **key**).
+ Trả về **iterator** trỏ vào phần tử có **key** **lớn nhất** mà **$<$** `x` trong map `mp` (nếu map `mp` được sắp xếp **giảm dần** theo **key**).
- Các hàm của một CTDL dạng container *(xem trong mục **iterator** của [Standard Template Library (STL) (Phần 2: Sequential containers)](/BCb1tDCeTb-z1kUVbWsqhA))*

### d. Các hàm có độ phức tạp O(N)
*($N$ là kích thước của map `mp`)*
- `mp.clear()` - **xoá toàn bộ** phần tử của map `mp`.

## 3. Một số lưu ý khi sử dụng map
- Một key *chưa* được gán giá trị từ trước thì sẽ đại diện cho **giá trị $0$**.
- Khi không sử dụng một key nào đó nữa thì thay vì gán giá trị mà nó đại diện thành $0$ thì ta nên sử dụng hàm **xoá** giá trị tương ứng với key đó (để tiết kiệm bộ nhớ).
- Khi xoá một key **rỗng** (giá trị nó đại diện là rỗng hoặc $0$) thì **không có gì** xảy ra cả.
- **Một lỗi phổ biến trong lập trình thi đấu:** Khi sử dụng `lower_bound(mp.begin(), mp.end(), x)` hoặc `upper_bound(mp.begin(), mp.end(), x)` thì độ phức tạp đúng của nó sẽ là $O(N\log{N})$ (Lí do được đề cập trong post sau: [(Mistake 15) [Tutorial] Common Mistakes in Competitive Programming and How to Avoid Them](https://codeforces.com/blog/entry/111217)). Vậy nên C++ cung cấp cho chúng ta một phương thức được xây riêng cho map là `mp.lower_bound(x)` và `mp.upper_bound(x)` để tìm kiếm trong $O(\log{N})$.

## 4. Multimap
**Multimap** hoạt động tương tự map nhưng **mỗi key** lại có thể đại diện cho **một hoặc nhiều giá trị (value)**.

*Multimap không được ứng dụng rộng rãi trong kì thi tuyển sinh chuyên tin 10 nên mọi người có thể tự tìm hiểu thêm nếu thích ^^.*

**Lưu ý:** Khi xoá phần tử trong multimap, nếu ta ghi `mp.erase(a)` thì nó sẽ mặc định xoá tất cả các phần tử có **key** `a` trong multimap đó. Để khắc phục điều này, ta cần tìm ra key `a` rồi xoá iterator của key `a` (`mp.erase(mp.find(a))`).

## 5. Bài tập ví dụ
### Đề bài
Tìm ký tự xuất hiện nhiều nhất trong xâu.

### Input
- Dòng đầu tiên là số lượng test case $T$ $(1 \le T \le 100)$.
- Mỗi test case bao gồm $1$ dòng là xâu $S$ có cả dấu cách $(1 \le |S| \le 10^6)$.

### Output
- Gồm $T$ dòng, mỗi dòng in ra ký tự xuất hiện nhiều nhất trong xâu.

### Sample input

2
2sgtinhoc sieucapdethuong
noelnay bandaconguoiyeuchua

### Sample output

2
4

### Lời giải
Ta sử dụng map để lưu tần suất của các kí tự trong xâu, sau đó tìm phần tử xuất hiện nhiều nhất.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    cin.ignore();
    while (t--) {
        string s; getline(cin, s);
        map<char, int> mp;
        for (int i = 0; i < s.size(); i++) {
            mp[s[i]]++;
        }
        int ans = 0;
        for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
            ans = max(ans, it->second);
        }
        cout << ans << "\n";
    }

    return 0;
}

:::

# Set, multiset (tập hợp)
## 1. Cấu trúc và cơ chế hoạt động
**Set** hoạt động như một dãy số luôn luôn được sắp xếp, tức là set sẽ tự động sắp xếp lại mỗi khi ta **thêm** hay **xoá** phần tử. Tuy nhiên *mỗi giá trị* chỉ xuất hiện đúng *một lần* trong set. *Ví dụ: Ta cho giá trị $1$ vào một set hai lần thì trong set đó vẫn chỉ chứa một phần tử giá trị $1$*.

**Multiset** là phiên bản set cho phép *một giá trị* xuất hiện *nhiều lần*. *Ví dụ: Ta cho giá trị $1$ vào một multiset hai lần thì trong multiset đó sẽ chứa hai giá trị $1$*.

## 2. Các cú pháp và hàm thông dụng
- `set <int> s` - khai báo set `s` với kiểu dữ liệu của các phần tử là int và các phần tử được sắp xếp theo thứ tự **tăng dần**.
- `set <int, greater <int>> s` - khai báo set `s` với kiểu dữ liệu của các phần tử là int và các phần tử được sắp xếp theo thứ tự **giảm dần**.
- `multiset <int> ms` - khai báo multiset `ms` với kiểu dữ liệu của các phần tử là int và các phần tử được sắp xếp theo thứ tự **tăng dần**.
- `multiset <int, greater <int>> ms` - khai báo multiset `ms` với kiểu dữ liệu của các phần tử là int và các phần tử được sắp xếp theo thứ tự **giảm dần**.

*Vì các cú pháp và hàm của set và multiset giống nhau nên ở bên dưới, chúng mình sẽ chỉ đưa ra các hàm của set.*

### a. Cách duyệt qua set
#### Sử dụng vòng lặp for-each (chỉ sử dụng cho C++11 trở lên)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set <int> s = {1, 7, 7, 0, 1, 3};
    for (int i : mp)
    {
        // logic code
        cout << i << endl;
    }
}

#### Sử dụng iterator

#include <bits/stdc++.h>
using namespace std;

int main()
{
    set <int> s = {1, 7, 7, 0, 1, 3};
    for (set <int>::iterator it = mp.begin(); it != mp.end(); it++)
    {
        // logic code
        cout << *it << endl;
    }
}

### b. Các hàm có độ phức tạp O(1)
- `s.empty()` - trả về **true** nếu set `s` **rỗng** (không có phần tử nào) và **false** nếu set `s` có **ít nhất 1 phần tử**.
- `s.size()` - trả về **kích thước** (số lượng phần tử) của set `s`.

### c. Các hàm có độ phức tạp O(logN)
*($N$ là kích thước của set `s`)*
- `s.insert(x)` - **thêm** giá trị `x` vào set`s`.
- `s.erase(a)` - **xoá** phần tử có giá trị `a` ra khỏi set `s`
- `s.erase(it)` - **xoá** phần tử mà iterator `it` trỏ vào ra khỏi set `s`.
- `s.lower_bound(x)`
+ Trả về **iterator** trỏ vào phần tử có giá trị **nhỏ nhất** mà **$\ge$** `x` trong set `s` (nếu set `s` được sắp xếp tăng dần).
+ Trả về **iterator** trỏ vào phần tử có giá trị **lớn nhất** mà **$\le$** `x` trong set `s` (nếu set `s` được sắp xếp giảm dần).
- `s.upper_bound(x)`
+ Trả về **iterator** trỏ vào phần tử có giá trị **nhỏ nhất** mà **$>$** `x` trong set `s` (nếu set `s` được sắp xếp tăng dần).
+ Trả về **iterator** trỏ vào phần tử có giá trị **lớn nhất** mà **$<$** `x` trong set `s` (nếu set `s` được sắp xếp giảm dần).
- Các hàm của một CTDL dạng container *(xem trong mục **iterator** của [Standard Template Library (STL) (Phần 2: Sequential containers)](/BCb1tDCeTb-z1kUVbWsqhA))*

### d. Các hàm có độ phức tạp O(N)
*($N$ là kích thước của set `s`)*
- `s.clear()` - **xoá toàn bộ** phần tử của set `s`.

## 3. Một số lưu ý khi sử dụng set, multiset
- Khi một iterator `it` đang trỏ vào một giá trị **không tồn tại** trong set/multiset `s` mà ta sử dụng hàm `s.erase(it)` (để **xoá** giá trị mà iterator `it` trỏ vào ra khỏi set/multiset `s`) thì code sẽ bị **lỗi**. Vì vậy trước mỗi khi sử dụng hàm `erase` với set/multiset cần phải kiểm tra kĩ xem mình đang xoá thứ gì.
- Khi xoá phần tử trong multiset, nếu ta ghi `ms.erase(a)` thì nó sẽ mặc định xoá tất cả các phần tử có **giá trị** `a` trong multiset đó. Để khắc phục điều này, ta cần tìm ra **giá trị** `a` rồi xoá iterator của **giá trị** `a` (`ms.erase(ms.find(a))`).
- **Tương tự như map:** `lower_bound(s.begin(), s.end(), x)` hay `upper_bound(s.begin(), s.end(), x)` đều tốn độ phức tạp $O(N\log{N})$. Vậy nên để độ phức tạp $O(\log{N})$ ta sử dụng `s.lower_bound(x)` và `s.upper_bound(x)`.

## 4. Bài tập ví dụ
### Đề bài
Đếm số lượng phần tử khác nhau trong mảng số nguyên.

### Input
- Dòng đầu tiên là số lượng test case $T$ $(1 \le T \le 100)$.
- Mỗi test case bao gồm $2$ dòng, dòng đầu tiên là số lượng phần tử $n$ $(1 \le n \le 10^5)$, dòng thứ hai gồm $n$ phần tử trong mảng $(1 \le a_i \le 10^9)$.

### Output
- Gồm $T$ dòng, mỗi dòng in ra số lượng phần tử khác nhau trong mảng.

### Sample input

2
5
1 2 2 2 1
4
1 2 3 4

### Sample output

2
4

### Lời giải

- Sử dụng tính chất của `set` là chỉ lưu trữ các phần tử khác nhau.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        set<int> s;
        for (int i = 1; i <= n; i++) {
            int x; cin >> x;
            s.insert(x);
        }
        cout << s.size() << "\n";
    }

    return 0;
}

:::

# CTDL dạng unordered container
Trong STL, mỗi CTDL dạng **associative container** thì đều có một CTDL dạng **unordered container** tương ứng **(unordered map, unordered set,...)**.

CTDL dạng unordered container có chức năng y hệt như phiên bản gốc của chúng, nhưng hoạt động dựa trên CTDL **bảng băm (hash table)** *(đây là một CTDL nâng cao, mọi người có thể tự tìm hiểu thêm nếu thích)*. Chính vì vậy nên độ phức tạp của các thao tác (**thêm**, **xoá**, **truy cập** phần tử) sẽ là $O(1)$ hoặc $O(N)$ tuỳ vào dữ liệu phải xử lí.

*Chúng mình **không khuyến khích** việc sử dụng CTDL dạng unordered container (thay cho CTDL dạng associative container) vì chúng thiếu sự ổn định (độ phức tạp các thao tác lên đến $O(N)$ mà người dùng không lường trước được) và:*
- *Nếu một bài tập có (một trong các) lời giải sử dụng một CTDL dạng associative container thì chắc chắn sẽ có cách cài đặt CTDL dạng associative container đó để không bị TLE (time limit exceeded). Còn nếu không thì mọi người nên tìm hướng giải khác thay vì cố gắng sử dụng CTDL dạng unordered container.*
- *Trong bộ test chấm của các bài tập thường có những test đặc biệt để làm cho thao tác của CTDL dạng unordered container có độ phức tạp là $O(N)$.*

[Mọi người có thể đọc thêm về các CTDL dạng unordered container trong post này](https://codeforces.com/blog/entry/62393)

# Bài tập áp dụng
## [Bài 1](https://codeforces.com/contest/900/problem/C)
Cho một hoán vị $p$ gồm $n$ phần tử. Tìm cách xoá duy nhất một phần tử sao cho số lượng bản ghi là lớn nhất.

Ta định nghĩa $A_i$ là một bản ghi khi với mọi $j \space (1 \le j < i)$ thì $A_j < A_i$.

Một hoán vị $p$ là một dãy các số nguyên từ $1$ đến $n$ có độ dài $n$ chứa mỗi số đúng 1 lần được sắp xếp không theo thứ tự. **Ví dụ:** $(1), (4, 3, 5, 1, 2), (3, 2, 1)$ là một hoán vị, $(1, 1), (4, 3, 1), (2, 3, 4)$ không phải là một hoán vị.

### Input
- Dòng đầu chứa một số $n \space (1 \le n \le 10^5)$.
- Dòng thứ hai chứa $n$ số $a_1, a_2, ..., a_n \space (1 \le a_i \le n)$ - một hoán vị. Tất cả các số đảm bảo khác nhau.

### Output
- Chứa một số là phần tử cần bị xoá để số lượng bản ghi là nhiều nhất. Nếu có nhiều kết quả, in kết quả có giá trị nhỏ nhất.

### Sample input 1

1
1

### Sample output 1

1

### Giải thích 1
- Chỉ có một phần tử để xoá là phần tử $1$

### Sample input 2

5
5 1 2 3 4

### Sample output 2

5

### Giải thích 2
- Xoá phần tử $5$, số lượng bản ghi là $(2, 3, 4)$

## [Bài 2](https://www.spoj.com/THPTCBT/problems/MTDANCE/)
Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có $n$ học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một số nhóm học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.

Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.

### Input
- Dòng đầu chứa số nguyên dương $n (1 \le n \le 10^6)$.
- Dòng thứ hai chưa xâu độ dài $n$ gồm các kí tự từ tập $\{a, b\}$ xác định dòng xếp hàng, $a$ là nam, $b$ là nữ.

### Output
- Một dòng duy nhất là số cách lựa chọn.

### Sample input

8
abbababa

### Sample output

13

# Nguồn tham khảo
:::info
[1] https://www.geeksforgeeks.org/the-c-standard-template-library-stl/
[2] https://cplusplus.com/reference/map/map/
[3] https://cplusplus.com/reference/map/multimap/
[4] https://cplusplus.com/reference/set/set/
[5] https://cplusplus.com/reference/set/multiset/
[6] https://cplusplus.com/reference/unordered_map/unordered_map/
[7] https://cplusplus.com/reference/unordered_map/unordered_multimap/
[8] https://cplusplus.com/reference/unordered_set/unordered_set/
[9] https://cplusplus.com/reference/unordered_set/unordered_multiset/
:::