YouTipCpp Libs Set
# C++ Standard Library: `` Container
The `` header in the C++ Standard Template Library (STL) provides an associative container that stores unique elements following a specific order.
A `std::set` is highly efficient for searching, inserting, and removing elements. Under the hood, it is typically implemented as a **Red-Black Tree** (a self-balancing binary search tree), which guarantees logarithmic time complexity $O(\log n)$ for these operations.
---
## Key Characteristics of `std::set`
* **Unique Elements:** Duplicate values are not allowed. If you attempt to insert an existing value, the insertion is ignored.
* **Ordered Storage:** Elements are automatically sorted in ascending order by default using the `<` operator of the element type.
* **Immutable Keys:** Once an element is added to a set, its value cannot be modified directly (iterators are constant). To change an element, you must remove it and insert the new value.
* **Requirements on Element Types:**
* The element type must be **comparable** (it must support strict weak ordering, typically via the `<` operator or a custom comparator).
* The element type must be **copyable** and **assignable**.
---
## Syntax and Initialization
To use `std::set`, you must include the `` header:
```cpp
#include
```
### Declaration Syntax
```cpp
std::set containerName;
```
### Common Initialization Methods
```cpp
// 1. Empty set of integers
std::set mySet;
// 2. Initializer list (C++11 and later)
std::set mySet2 = {10, 40, 20, 30}; // Automatically sorted to: 10, 20, 30, 40
// 3. Custom sorting order (descending)
std::set> descendingSet = {10, 40, 20, 30}; // Sorted to: 40, 30, 20, 10
```
---
## Common Member Functions
| Member Function | Description | Time Complexity |
| :--- | :--- | :--- |
| `insert(val)` | Inserts an element into the set if it is not already present. | $O(\log n)$ |
| `erase(val)` | Removes the element with the specified value. | $O(\log n)$ |
| `erase(iterator)` | Removes the element at the specified iterator position. | Amortized $O(1)$ |
| `find(val)` | Returns an iterator to the element if found; otherwise, returns `end()`. | $O(\log n)$ |
| `count(val)` | Returns `1` if the element exists, and `0` otherwise (since elements are unique). | $O(\log n)$ |
| `size()` | Returns the number of elements in the set. | $O(1)$ |
| `empty()` | Returns `true` if the set is empty, `false` otherwise. | $O(1)$ |
| `clear()` | Removes all elements from the set. | $O(n)$ |
---
## Practical Code Example
The following complete example demonstrates how to declare a set, insert elements, search for values, delete elements, and iterate through the container.
```cpp
#include
#include
int main() {
// Declare a set of integers
std::set mySet;
// 1. Insert elements (note that 20 is inserted twice)
mySet.insert(10);
mySet.insert(40);
mySet.insert(20);
mySet.insert(30);
mySet.insert(20); // Duplicate element, will be ignored
// 2. Output the elements of the set
// Notice that the output is automatically sorted and contains no duplicates
std::cout << "Set contains: ";
for (int num : mySet) {
std::cout << num << " ";
}
std::cout << std::endl;
// 3. Find an element
int searchKey = 20;
if (mySet.find(searchKey) != mySet.end()) {
std::cout << searchKey << " is in the set." << std::endl;
} else {
std::cout << searchKey << " is not in the set." << std::endl;
}
// 4. Erase an element
mySet.erase(20);
std::cout << "After erasing 20, set contains: ";
for (int num : mySet) {
std::cout << num << " ";
}
std::cout << std::endl;
// 5. Check if the set is empty
if (mySet.empty()) {
std::cout << "The set is empty." << std::endl;
} else {
std::cout << "The set is not empty." << std::endl;
}
// 6. Get the size of the set
std::cout << "The set contains " << mySet.size() << " elements." << std::endl;
return 0;
}
```
### Output
```text
Set contains: 10 20 30 40
20 is in the set.
After erasing 20, set contains: 10 30 40
The set is not empty.
The set contains 3 elements.
```
---
## Advanced Considerations
### 1. Performance vs. `std::unordered_set`
* Use `std::set` when you need your elements to remain **sorted** or when you need to perform range queries (e.g., finding all elements between $A$ and $B$ using `lower_bound` and `upper_bound`).
* If sorting is not required and you only need fast lookups, insertions, and deletions, consider using `std::unordered_set` (implemented via a hash table), which offers average $O(1)$ time complexity.
### 2. Custom Comparators for User-Defined Types
If you want to store custom objects (like a `struct` or `class`) in a `std::set`, you must either overload the `<` operator or provide a custom comparator struct.
```cpp
#include
#include
#include
struct Person {
std::string name;
int age;
// Overload the < operator to sort by age
bool operator<(const Person& other) const {
return age < other.age;
}
};
int main() {
std::set people = { {"Alice", 30}, {"Bob", 25} };
// Sorted automatically by age: Bob (25) then Alice (30)
for (const auto& p : people) {
std::cout << p.name << " (" << p.age << ")\n";
}
return 0;
}
```
---
## Summary
The `` container is an essential tool in the C++ Standard Library. It is ideal for scenarios requiring unique collection management, automatic sorting, and fast logarithmic-time lookups. By understanding its underlying Red-Black Tree structure and API, you can write highly optimized and clean C++ code.