Trong C++, cả set và unordered_set đều là container liên kết lưu trữ giá trị duy nhất. Dưới đây là sự khác biệt chính:
| Tiêu chí | set | unordered_set |
|---|---|---|
| Định nghĩa | Container liên kết lưu cặp key-value, key duy nhất, tự động sắp xếp. | Container liên kết dùng hash table, key duy nhất, không sắp xếp. |
| Sắp xếp | Dữ liệu được lưu theo thứ tự tăng dần (mặc định). | Dữ liệu không theo thứ tự nào. |
| Trùng lặp | Không cho phép giá trị trùng. | Không cho phép giá trị trùng (tự loại bỏ). |
| Cài đặt | Cây nhị phân tìm kiếm cân bằng (Red-Black Tree). | Bảng băm (Hash Table). |
| Độ phức tạp | insert/find/erase: O(log n). | insert/find/erase: O(1) trung bình, O(n) xấu nhất. |
| Duyệt | Duyệt theo thứ tự tăng dần. | Duyệt theo thứ tự ngẫu nhiên (phụ thuộc hash). |
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;
return 0;
}
// Output: 11, 22, 23, 33, 41, 44, 55, 66, 77, 88, 99 (sorted)Ví dụ UnorderedSet
#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};
unordered_set<int> my_set;
for (int x : data) my_set.insert(x);
for (int x : my_set) cout << "Item: " << x << endl;
return 0;
}
// Output: thứ tự ngẫu nhiên, ví dụ: 11, 55, 22, 66, 33, 44, 77, 88, 99, 23, 41Khi nào dùng cái nào?
- Dùng set khi cần dữ liệu có thứ tự hoặc thao tác lower_bound/upper_bound.
- Dùng unordered_set khi chỉ cần kiểm tra tồn tại/insert/xóa nhanh O(1), không quan tâm thứ tự.