查看“︁04-数据结构/05-set与unordered set”︁的源代码


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

== set ==

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

=== 定义 ===

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

=== 常用操作 ===

{| class="wikitable"
! 操作 !! 说明
|-
| <code>s.insert(x)</code>
| 插入元素（已存在则插入失败）
|-
| <code>s.erase(x)</code>
| 删除元素
|-
| <code>s.find(x)</code>
| 查找元素，不存在返回 <code>s.end()</code>
|-
| <code>s.count(x)</code>
| 判断元素是否存在（返回 <math>0</math> 或 <math>1</math>）
|-
| <code>s.clear()</code>
| 清空
|-
| <code>s.size()</code>
| 返回元素数量
|-
| <code>s.empty()</code>
| 判断是否为空
|}

=== 枚举 ===

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

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

=== 二分查找 ===

<code>set</code> 支持二分查找（红黑树特性）：

<syntaxhighlight lang="cpp">
auto it = s.lower_bound(x); // 第一个 >= x 的元素
auto it = s.upper_bound(x); // 第一个 > x 的元素
</syntaxhighlight>

== unordered_set ==

- 基于哈希表，插入/查找/删除平均 <math>O(1)</math>
- 元素'''无序'''
- 用法与 <code>set</code> 基本相同

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

== multiset ==

允许重复元素的集合：

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

== 选择建议 ==

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


[[Category:数据结构]]
[[Category:三三文档]]