C++ set 教程：用 std::set 存储唯一且有序的元素

一袋唯一且有序的值

你已经见过 unordered_map 如何用基于哈希的快速查找来存储键值对。std::set 是它更简单的近亲：它只存储值，没有关联的数据，并且自动遵守两条规则。每个元素都是唯一的（重复的值会被悄悄丢弃），元素也始终保持有序。

这让 set 成了回答“这个我以前见过吗？”或“按顺序给我所有不重复的项”这类问题的自然选择。插入时不必担心重复，遍历前也不必先排序。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplicate - ignored

    for (int x : s) cout << x << " ";   // 10 30 40 (sorted, no repeat)
}

注意，我们把 10 插入了两次，而且顺序是乱的，可输出却是有序的，10 也只出现一次。这些记账工作 set 都替你做了。

插入和删除

insert 会在值不存在时添加它。它返回一个 pair，其中 .second 是一个 bool，告诉你插入是否真的发生了。想知道一个值是不是新的时，这很方便：

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

要删除一个值，就用这个值本身调用 erase，它返回被删除的元素个数（对 set 来说是 0 或 1）。删除一个不存在的值不会出问题，也不算错误：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // removes 3
    s.erase(99);         // does nothing, returns 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

检查元素是否存在

set 的全部意义就在于快速回答“它在不在里面？”。最清楚的写法是 count，它返回 1 或 0：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

从 C++20 开始还有一个更易读的选择 contains，它直接返回 bool：

if (primes.contains(7)) { /* ... */ }   // C++20

一个常见错误是像用 map 那样去用 operator[]。set 没有 operator[]：没有值可以取，只有存在与否可以检查。请用 count 或 contains，而不是 s[7]。

如果你需要元素的实际位置（比如要删除它，或者查看它的相邻元素），就用 find，它返回一个迭代器或 end()：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // erase by iterator - no second lookup
    }
    cout << "size now " << s.size() << "\n";
}

有序遍历和范围查询

由于 set 是有序的，遍历时元素总是从小到大出现，你也就免费得到了有序容器的种种技巧。lower_bound(x) 给出第一个不小于 x 的元素，upper_bound(x) 给出第一个严格大于 x 的元素，两者合用，就能扫描一个数值范围，而不必检查每个元素：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // print everything in [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

有一条不起眼但很重要的规则：set 的元素是不可修改的。迭代器给你的是一个 const 引用，所以你不能原地修改元素，否则可能破坏容器所依赖的排序顺序。要“修改”一个值，就删除旧值，再插入新值。

默认的排序是升序（std::less）。想要降序，就把另一个比较器作为第二个模板参数传进去：

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set、multiset 与 unordered_set

std::set 有三个近亲，选对很重要：

set<int>            // unique values, sorted, O(log n)
multiset<int>       // allows duplicates, sorted, O(log n)
unordered_set<int>  // unique values, NO order, average O(1)

只需要判断元素是否存在、又不在乎顺序时，选 unordered_set：它基于哈希的查找平均比 set 基于树的 O(log n) 更快。需要元素保持有序、要用 lower_bound/upper_bound 做范围查询，或者需要稳定的迭代器行为时，选 set。只有当重复值有意义时（比如统计重复值的直方图）才用 multiset：在 multiset 中，count(x) 可能返回大于 1 的数，而 erase(x) 会删除所有副本，除非你通过单个迭代器来删除。

set 的一个经典用法：一步完成 vector 的去重和排序。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

用 vector 的迭代器构造 set，会丢掉所有重复值并把剩下的排好序：不用手写循环，也不用先排序再调用 std::unique 来回折腾。

下一节：pair 和 tuple

你已经看到 insert 返回的 pair 上出现了 .first 和 .second，而结构化绑定配合 auto 关键字（auto [it, inserted]）能把它干净地拆开。这些“把几个值打包在一起”的轻量类型在 STL 中随处可见。下一节我们会直接学习 pair 和 tuple：如何构造它们、拆开它们，以及如何不定义整个结构体就从函数返回多个值。