STL中map和set的工作原理

STL中的`map`和`set`都是关联容器，它们以不同的方式存储和管理数据。

**Set (无序集合)**:
1. **原理**: `set`存储唯一且有序的元素，基于比较运算符实现。每个元素都有一个唯一的键，通过键值查找元素非常高效。
2. **使用**:
- 它们通常用于删除重复项并保持数据有序。
- `set`的迭代器有`begin()`和`end()`，以及`rbegin()`和`rend()`，后者表示从后向前遍历，移动方向相反。
- 示例:

     set<int> s = {1, 3, 2};
     for(auto it = s.begin(); it != s.end(); ++it)
       std::cout << *it << " "; // 输出：1 2 3

**Map (关联映射)**:
1. **原理**: `map`也存储唯一元素，但关联每个键有一个值。它内部维护了一个红黑树，使得查找、插入和删除操作具有近似O(log n)的时间复杂度。
2. **使用**:
- 通过键可以直接访问对应的值，如`map[key]`。
- 它的迭代器包括`begin()`和`end()`，同样有`rbegin()`和`rend()`。
- 示例:

     map<string, int> m = {"apple", 1, "banana", 2};
     for(auto it = m.begin(); it != m.end(); ++it)
       std::cout << it->first << ": " << it->second << "\n";

要了解更多关于`map`和`set`的操作，可以查阅它们的构造函数、容量控制（如`empty()`、`size()`）、修改操作（如`insert()`、`erase()`）、搜索（`find()`）和计数（`count()`）等内容[^1]。