Trong bài viết này, hãy hiểu מה là set và unordered_set trong C++ STL và nắm rõ sự khác biệt giữa chúng.
set là gì?
Một set là một container liên kết chứa một tập hợp các đối tượng duy nhất của kiểu Key được sắp xếp. Mỗi phần tử chỉ xuất hiện một lần, nên các giá trị trùng lặp không được phép. Người dùng có thể tạo set bằng cách chèn các phần tử theo bất kỳ thứ tự nào và set sẽ trả về dữ liệu đã sắp xếp, nghĩa là set chứa định nghĩa cho việc sắp xếp dữ liệu được trừu tượng hóa khỏi người dùng.
Các lý do chính khi nên dùng set −
Khi cần dữ liệu đã sắp xếp
Khi không cần giá trị trùng lặp, chỉ cần dữ liệu duy nhất
Khi muốn sử dụng Cây tìm kiếm nhị phân thay vì Bảng băm.
Khi không có vấn đề về thời gian tìm kiếm vì nó tốn độ phức tạp log(n) khi tìm kiếm
Đầu vào −
set = {2, 1, 5, 6, 9, 3, 2} Đầu ra −
1, 2, 3, 5, 6, 9
Lưu ý − Các giá trị được chèn theo thứ tự ngẫu nhiên, nhưng chúng được sắp xếp bởi set và các giá trị trùng lặp bị loại bỏ khỏi set.
Ví dụ
#include <iostream> #include <set> using namespace std; int main(){ //tạo một mảng int arr[] = {2, 1, 5, 6, 9, 3, 2}; int size = sizeof(arr)/ sizeof(arr[0]); //khai báo một set set<int> SET; //chèn phần tử từ mảng vào set bằng insert() for(int i = 0; i<size; i++){ SET.insert(arr[i]); } set<int>::iterator it; cout<<"Values in set are: "; for(it = SET.begin(); it != SET.end(); it++){ cout <<*it<<" "; } } Đầu ra
Đầu ra cho mã trên sẽ là −
Values in set are: 1 2 3 5 6 9
unordered_set là gì?
Một unordered_set là một container liên kết chứa một tập hợp dữ liệu được chèn ngẫu nhiên, không theo thứ tự. Mỗi phần tử chỉ xuất hiện một lần, nên các giá trị trùng lặp không được phép. Người dùng có thể tạo unordered_set bằng cách chèn các phần tử theo bất kỳ thứ tự nào và unordered_set sẽ trả về dữ liệu theo bất kỳ thứ tự nào, tức là dạng không sắp xếp.
Các lý do chính khi nên dùng unordered_set −
Không cần dữ liệu đã sắp xếp, nghĩa là dữ liệu có sẵn ở dạng không theo thứ tự
Khi không cần giá trị trùng lặp, chỉ cần dữ liệu duy nhất
Khi muốn sử dụng Bảng băm thay vì Cây tìm kiếm nhị phân.
Khi cần tìm kiếm nhanh hơn vì nó tốn O(1) trung bình và O(n) trong trường hợp xấu nhất
Đầu vào −
set = {2, 1, 5, 6, 9, 3, 2} Đầu ra −
3, 9, 6, 5, 2
Ví dụ
#include <iostream> #include <unordered_set> using namespace std; int main (){ int arr[] = { 2, 1, 5, 6, 9, 3, 2 }; int size = sizeof (arr) / sizeof (arr[0]); unordered_set < int >U_SET; //chèn phần tử từ mảng vào unordered_set bằng insert() for (int i = 0; i < size; i++){ U_SET.insert (arr[i]); } unordered_set < int >::iterator it; cout << "Values in unordred set are: "; for (it = U_SET.begin (); it != U_SET.end (); it++){ cout << *it << " "; } } Đầu ra
Đầu ra cho mã trên sẽ là −
Values in unordered set are: 3 6 5 9 2 1