Cả set và multiset đều là container liên kết sắp xếp, nhưng khác nhau ở việc cho phép trùng lặp.
| Tiêu chí | set | multiset |
|---|---|---|
| Định nghĩa | Lưu key duy nhất, tự động sắp xếp. | Lưu key có thể trùng lặp, tự động sắp xếp. |
| Sắp xếp | Tăng dần. | Tăng dần. |
| Trùng lặp | Không cho phép. | Cho phép (lưu multiplicity). |
| Cài đặt | Red-Black Tree. | Red-Black Tree. |
| Thao tác | insert/find/erase: O(log n). | insert/find/erase: O(log n). count(x) trả về số lần xuất hiện. |
| Sửa giá trị | Không thể sửa trực tiếp (phải xóa rồi insert mới). | Tương tự. |
Ví dụ Set
#include <bits/stdc++.h>
using namespace std;
int main() {
int data[15] = {11,55,22,66,33,22,11,44,77,88,66,99,66,23,41};
set<int> my_set;
for (int x : data) my_set.insert(x);
for (int x : my_set) cout << "Item: " << x << endl;
// Output: 11, 22, 23, 33, 41, 44, 55, 66, 77, 88, 99
return 0;
}Ví dụ Multiset
#include <bits/stdc++.h>
using namespace std;
int main() {
int data[15] = {11,55,22,66,33,22,11,44,77,88,66,99,66,23,41};
multiset<int> my_set;
for (int x : data) my_set.insert(x);
for (int x : my_set) cout << "Item: " << x << endl;
// Output: 11, 11, 22, 22, 23, 33, 41, 44, 55, 66, 66, 66, 77, 88, 99
return 0;
}Khi nào dùng Multiset?
- Cần lưu tần suất xuất hiện của các phần tử.
- Cần lấy tất cả phần tử bằng một giá trị (equal_range).
- Cần thao tác upper_bound/lower_bound trên dữ liệu có trùng lặp.