04-数据结构/05-set与unordered set

set 采用红黑树实现（有序），unordered_set 采用哈希表实现（无序）。

set

集合中的元素唯一且有序。

set<int> s;                // 存 int 的集合（默认升序）
set<int, greater<int>> s;  // 降序排列
set<string> ss[30];        // 30 个集合

操作	说明
`s.insert(x)`	插入元素（已存在则插入失败）
`s.erase(x)`	删除元素
`s.find(x)`	查找元素，不存在返回 `s.end()`
`s.count(x)`	判断元素是否存在（返回 [math]\displaystyle{ 0 }[/math] 或 [math]\displaystyle{ 1 }[/math]）
`s.clear()`	清空
`s.size()`	返回元素数量
`s.empty()`	判断是否为空

// 迭代器
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    cout << *it << "\n";

// 范围 for
for (auto now : s)
    cout << now << "\n";

set 支持二分查找（红黑树特性）：

auto it = s.lower_bound(x); // 第一个 >= x 的元素
auto it = s.upper_bound(x); // 第一个 > x 的元素

- 基于哈希表，插入/查找/删除平均 [math]\displaystyle{ O(1) }[/math] - 元素无序 - 用法与 set 基本相同

unordered_set<int> s;
s.insert(5);
if (s.find(5) != s.end())
    cout << "找到了";

允许重复元素的集合：

multiset<int> ms;
ms.insert(1);
ms.insert(1); // 允许重复
ms.erase(ms.find(1)); // 只删除一个 1（如果 erase(1) 会删除所有）

- 需要有序且不重复：用 set - 需要有序且可重复：用 multiset - 只需要查重不关心顺序：用 unordered_set