บทนำ
ใน C++ ทั้ง std::set และ std::unordered_set เป็นโครงสร้างข้อมูลแบบ Associative Container ที่ใช้เก็บข้อมูลเพื่อให้เข้าถึงและแทรกข้อมูลได้อย่างมีประสิทธิภาพ แต่มันมีลักษณะการทำงานและประสิทธิภาพที่แตกต่างกันอย่างมาก
ตารางเปรียบเทียบหลัก
| ลำดับ | หัวข้อ | std::set | std::unordered_set |
|---|---|---|---|
| 1 | นิยาม | เป็น Associative Container ที่เก็บข้อมูลแบบ Key-Value โดยแต่ละค่าต้องไม่ซ้ำกัน (Unique) และจัดเก็บในลำดับที่เรียงลำดับแล้ว | เป็นส่วนหนึ่งของ STL เช่นกัน แต่เก็บข้อมูลแบบ Key-Value ที่ ไม่ได้เรียงลำดับ ใช้ Hash Table ในการจัดเก็บ |
| 2 | การเรียงลำดับ (Sorting) | ข้อมูลถูกเก็บในลำดับน้อยไปมาก (Ascending Order) ตลอดเวลา | ข้อมูล ไม่ได้เรียงลำดับ ลำดับขึ้นอยู่กับ Hash Function และ Bucket |
| 3 | ค่าซ้ำ (Duplicate Values) | ไม่รองรับค่าซ้ำ หากพยายามแทรกค่าซ้ำจะถูกละทิ้ง | ไม่รองรับค่าซ้ำเช่นกัน ค่าซ้ำจะถูกละทิ้ง |
| 4 | การนำไปใช้ (Implementation) | ใช้ Binary Search Tree (BST) โดยทั่วไปคือ Red-Black Tree | ใช้ Hash Table พร้อมการจัดการ Collision (เช่น Chaining) |
| 5 | Complexity (เฉลี่ย) | O(log n) สำหรับ insert, find, erase | O(1) สำหรับ insert, find, erase (เฉลี่ย) แแต่วอร์สเคส O(n) |
| 6 | Iterator Invalidation | Iterator คงอยู่ได้ ยกเว้น element ที่ถูกลบ | Iterator อาจถูกทำลายเมื่อ Rehashing เกิดขึ้น |
ตัวอย่างโค้ด: std::set
#include <iostream>
#include <set>
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 i = 0; i < 15; i++) {
my_set.insert(data[i]);
}
for (auto it = my_set.begin(); it != my_set.end(); ++it) {
cout << "Item: " << *it << endl;
}
return 0;
}
ผลลัพธ์ (เรียงลำดับอัตโนมัติ)
Item: 11
Item: 22
Item: 23
Item: 33
Item: 41
Item: 44
Item: 55
Item: 66
Item: 77
Item: 88
Item: 99
ตัวอย่างโค้ด: std::unordered_set
#include <iostream>
#include <unordered_set>
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 i = 0; i < 15; i++) {
my_set.insert(data[i]);
}
for (auto it = my_set.begin(); it != my_set.end(); ++it) {
cout << "Item: " << *it << endl;
}
return 0;
}
ผลลัพธ์ (ไม่ได้เรียงลำดับ)
Item: 11
Item: 55
Item: 22
Item: 66
Item: 33
Item: 44
Item: 77
Item: 88
Item: 99
Item: 23
Item: 41
เมื่อไหร่ควรใช้ตัวไหน?
- ใช้ std::set เมื่อ: ต้องการข้อมูลเรียงลำดับ, ต้องการ lower_bound/upper_bound, หรือต้องการความเสถียรของ Iterator
- ใช้ std::unordered_set เมื่อ: ต้องการความเร็วสูงสุดสำหรับ lookup/insert/delete โดยเฉลี่ย O(1) และไม่สนใจลำดับข้อมูล
