set vs unordered_set ใน C++ STL

บทความนี้อธิบาย set และ unordered_set ใน C++ STL และความแตกต่างระหว่างกัน

Set คืออะไร?

Set เป็น Associative Container ที่เก็บชุดของออบเจ็กต์ Key ที่ไม่ซ้ำและเรียงลำดับแล้ว แต่ละอิลิเมนต์เกิดขึ้นได้ครั้งเดียว ผู้ใช้สามารถเพิ่มข้อมูลในลำดับใดก็ได้ Set จะคืนข้อมูลที่เรียงลำดับแล้ว

สถานการณ์ที่ควรใช้ Set −

• ต้องการข้อมูลที่เรียงลำดับ

• ไม่ต้องการค่าซ้ำ ต้องการเฉพาะค่า unique

• ต้องการใช้ Binary Search Tree แทน Hash Table

• ยอมรับเวลาค้นหา log(n) complexity

อินพุต − set = {2, 1, 5, 6, 9, 3, 2}

เอาต์พุต − 1, 2, 3, 5, 6, 9

หมายเหตุ − ค่าเพิ่มแบบสุ่ม แต่ Set เรียงลำดับและลบค่าซ้ำให้อัตโนมัติ

ตัวอย่าง

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

int main(){ 
    int arr[] = {2, 1, 5, 6, 9, 3, 2}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
    set<int> SET; 
    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 << " "; 
}

เอาต์พุต

Values in set are: 1 2 3 5 6 9

unordered_set คืออะไร?

Unordered_set เป็น Associative Container ที่เก็บข้อมูลไม่เรียงลำดับ แต่ละอิลิเมนต์ไม่ซ้ำกัน คืนข้อมูลในลำดับสุ่ม

สถานการณ์ที่ควรใช้ Unordered_set −

• ไม่ต้องการข้อมูลเรียงลำดับ

• ไม่ต้องการค่าซ้ำ

• ต้องการใช้ Hash Table แทน Binary Search Tree

• ต้องการค้นหาเร็ว O(1) Average case, O(n) Worst case

อินพุต − set = {2, 1, 5, 6, 9, 3, 2}

เอาต์พุต − 3, 9, 6, 5, 2 (ลำดับสุ่ม)

ตัวอย่าง

#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; 
    for (int i = 0; i < size; i++) U_SET.insert(arr[i]); 
    unordered_set <int>::iterator it; 
    cout << "Values in unordered set are: "; 
    for (it = U_SET.begin(); it != U_SET.end(); it++) cout << *it << " "; 
}

เอาต์พุต

Values in unordered set are: 3 6 5 9 2 1