Why would anyone use set instead of unordered_set?

Several key factors should be considered when choosing between set and unordered_set:

1. Element Ordering

• set: set is implemented using a red-black tree, which automatically sorts elements. This makes it an excellent choice for scenarios requiring ordered data.
• unordered_set: unordered_set is implemented using a hash table and does not guarantee element order. If order is not important, using unordered_set offers faster access speeds.

2. Performance

• Lookup, Insertion, and Deletion Operations:
  • set: These operations typically have logarithmic time complexity (O(log n)) due to its tree-based structure.
  • unordered_set: These operations have average constant time complexity (O(1)), but may degrade to linear time complexity (O(n)) in the worst case, especially with high hash collisions.

Application Example:

• Imagine handling a personnel list that must be displayed in alphabetical order by surname; using set is highly suitable because it automatically sorts elements during insertion. Conversely, for frequent existence checks (e.g., quickly searching for a user in a large dataset), unordered_set's hash table structure provides faster lookup speeds.

3. Feature Characteristics

• Iterator Stability:
  • set: Iterators are stable; adding or deleting elements does not invalidate iterators pointing to other elements.
  • unordered_set: During rehashing (e.g., resizing), iterators may become invalid.

This characteristic makes set more suitable when maintaining element order while traversing, adding, or deleting elements from the dataset.

Summary: The choice between set and unordered_set primarily depends on your specific requirements, whether element ordering is needed, and performance expectations. Use set for ordered data scenarios, and unordered_set when prioritizing performance with no order requirement. This selection helps efficiently implement your target functionality and optimize overall performance.