So sánh set, multiset, unordered_set, unordered_multiset C++

Bốn container liên hợp trong STL C++ với đặc điểm khác nhau về thứ tự, trùng lặp và cấu trúc dữ liệu bên dưới.

Bảng so sánh

Ví dụ minh họa

#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

int main() {
    int a[] = {11, 55, 22, 66, 33, 22, 11, 44, 77, 88, 66, 99, 66, 23, 41};
    
    set<int> s(a, a+15);
    multiset<int> ms(a, a+15);
    unordered_set<int> us(a, a+15);
    unordered_multiset<int> ums(a, a+15);
    
    cout << "set (unique, sorted):      "; for(int x: s)  cout << x << ' '; cout << '\n';
    cout << "multiset (dup, sorted):    "; for(int x: ms) cout << x << ' '; cout << '\n';
    cout << "unordered_set (unique):    "; for(int x: us) cout << x << ' '; cout << '\n';
    cout << "unordered_multiset (dup):  "; for(int x: ums) cout << x << ' '; cout << '\n';
    return 0;
}

Đầu ra

set (unique, sorted):       11 22 23 33 41 44 55 66 77 88 99
multiset (dup, sorted):     11 11 22 22 23 33 41 44 55 66 66 66 77 88 99
unordered_set (unique):     99 11 44 22 77 33 88 55 66 41 23  (thứ tự bất định)
unordered_multiset (dup):   99 11 11 44 22 22 77 33 88 55 66 66 66 41 23

Khi nào dùng cái nào?

• set: Cần duy nhất, cần thứ tự, thao tác log n.
• multiset: Cho trùng lặp, cần thứ tự.
• unordered_set: Cần O(1) trung bình, không cần thứ tự.
• unordered_multiset: Cho trùng lặp, cần O(1).