C++ STL 容器实战：set 与 multiset 深度解析

1. 序列式容器和关联式容器

在 C++ STL 中，我们常见 string、vector、list、deque 等容器，它们统称为序列式容器。这类容器的逻辑结构是线性序列，元素按存储位置顺序保存和访问，交换位置通常不影响其逻辑。

与之相对的是关联式容器，如 map/set 系列和 unordered_map/unordered_set 系列。关联式容器的逻辑结构通常是非线性的（底层多为红黑树或哈希表），元素通过关键字（Key）进行保存和访问，两个位置的值之间存在紧密的关联关系。

本文重点讲解 set 和 multiset，它们的底层实现都是红黑树（一种平衡二叉搜索树）。set 适用于 Key 搜索场景，而 map 则用于 Key-Value 搜索场景。

2. set 系列的使用

2.1 set 类的介绍

set 的模板声明如下：

template <class T,              // set::key_type/value_type
            class Compare = less<T>, // set::key_compare/value_compare
            class Alloc = allocator<T>> // set::allocator_type
class set;

这里有几个关键点需要注意：

• T：代表底层关键字的类型。
• Compare：默认要求 T 支持小于比较（less<T>）。如果不支持或需要自定义排序规则（如降序），可以自行实现仿函数传给第二个模板参数。
• Alloc：内存分配器。一般情况下无需手动指定，使用默认配置即可。
• 性能：底层基于红黑树，增删查效率为 O(logN)。迭代器遍历遵循中序遍历，因此 set 中的元素默认是有序的。

虽然库中使用 T 作为模板参数名，但在语义上它更接近于 Key。STL 容器接口设计高度相似，掌握基础后可以直接参考文档查阅具体接口。

2.2 set 的迭代器和构造

set 的迭代器属于双向迭代器，支持正向和反向遍历：

// 正向迭代器
iterator begin(); 
iterator end();

// 反向迭代器
reverse_iterator rbegin(); 
reverse_iterator rend();

主要的构造方式包括：

• 无参构造：创建空集合。
• 迭代器区间构造：从输入迭代器范围 [first, last) 构建。
• 拷贝构造：复制另一个 set 对象。
• 列表构造：使用初始化列表直接初始化。

2.3 set 的增删查

首先需要明确一个原则：set 不支持修改键值。因为它是关联式容器，直接修改数据会破坏底层的红黑树结构。

插入操作 (insert)

insert 接口有多种重载形式：

// 单个数据插入，如果已存在则插入失败，返回 pair<iterator, bool>
pair<iterator, bool> insert(const value_type& val);

// 列表插入，已在容器中的值不会重复插入
void insert(initializer_list<value_type> il);

// 迭代器区间插入，已在容器中的值不会重复插入
template<class InputIterator>
void insert(InputIterator first, InputIterator last);

注意 value_type 在这里等同于 T（即 Key）。返回值 pair<iterator, bool> 中的 bool 表示插入是否成功，这在后续 map 部分会详细展开。

示例代码：

int main() {
    // 去重 + 升序排序
    set<int> s;
    
    // 若需降序，可传入 greater<int> 仿函数
    // set<int, greater<int>> s;
    
    s.insert(5);
    s.insert(2);
    s.insert(7);
    s.insert(5); // 重复插入，失败
    
    set<int>::iterator it = s.begin();
    while(it != s.end()) {
        // *it = 1; // 错误！set 不允许修改 key
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}

运行结果会显示 2 5 7。可以看到 set 具有自动去重功能，且默认按升序排列。迭代器底层走的是中序遍历路径。

set 也支持列表插入和任意类型的元素（只要该类型支持比较运算）：

int main() {
    set<string> strset = {"sort", "insert", "add"};
    for(auto& e : strset) {
        cout << e << " ";
    }
    return 0;
}

查找与删除 (find & erase)

find 返回对应位置的迭代器，若未找到则返回 end()：

const_iterator find(const value_type& val) const;
iterator find(const value_type& val);

删除操作有三种形式：

// 通过迭代器删除，返回下一个有效迭代器
iterator erase(const_iterator position);

// 通过 Key 删除，返回删除元素的个数
size_type erase(const value_type& val);

// 通过区间删除，返回删除后的第一个迭代器
iterator erase(const_iterator first, const_iterator last);

erase(val) 返回 size_type（无符号整型）而非 bool，这是为了兼容 multiset（可能删除多个相同元素）。返回 1 表示成功删除一个，0 表示未找到。

示例代码：

int main() {
    set<int> s = {4, 2, 7, 8, 5, 9};
    
    // 删除最小值
    s.erase(s.begin());
    
    // 直接删除 x
    int x = 7;
    int num = s.erase(x);
    if(num == 0) {
        cout << x << "不存在！" << endl;
    }
    
    // 先查找再删除
    auto pos = s.find(x);
    if(pos != s.end()) {
        s.erase(pos);
    }
    
    return 0;
}

注意迭代器失效问题：

1. 删除叶子节点时，原迭代器指向的内存变为野指针。
2. 删除非叶子节点时，可能会用子节点替换当前节点，虽然指针地址未变，但所指内容已改变，视为失效。

统计个数 (count)

count 返回值在容器中的出现次数。对于 set，结果只能是 0 或 1；但对于 multiset，它可以返回实际重复的次数。

int main() {
    set<int> s = {4, 2, 7, 8, 5, 9};
    int x = 7;
    if(s.count(x)) {
        cout << x << "在！" << endl;
    } else {
        cout << x << "不存在！" << endl;
    }
    return 0;
}

相比 find，count 判断存在性更简洁，无需处理迭代器与 end() 的比较。

2.4 lower_bound 与 upper_bound

这两个接口主要用于查找特定范围的区间：

// 返回大于等于 val 位置的最小迭代器
iterator lower_bound(const value_type& val) const;

// 返回大于 val 位置的最小迭代器
iterator upper_bound(const value_type& val) const;

结合左闭右开的区间概念，可以轻松定位一段连续的数据。

示例代码：

int main() {
    std::set<int> myset;
    for(int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 ... 90
    
    // 查找 [30, 60] 区间对应的元素
    auto itlow = myset.lower_bound(30); // 指向 30
    auto itup = myset.upper_bound(60);  // 指向 70
    
    // 删除这段区间的值
    myset.erase(itlow, itup);
    
    return 0;
}

2.5 multiset 与 set 的差异

multiset 与 set 用法基本一致，核心区别在于允许重复元素。

1. 不再去重

multiset 插入时会保留所有副本，遍历时会看到重复值。

int main() {
    multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    for(auto e : s) {
        cout << e << " ";
    }
    // 输出：2 2 4 4 4 4 5 7 8 9
    return 0;
}

2. find 返回中序的第一个

当存在多个相同值时，find 会返回中序遍历遇到的第一个匹配项。这得益于红黑树的特性，查找依然是 O(logN)，而非全遍历。

int main() {
    multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    int x = 4;
    auto pos = s.find(x);
    while(pos != s.end() && *pos == x) {
        cout << *pos << " ";
        ++pos;
    }
    return 0;
}

3. erase 删除所有的 x

调用 erase(val) 时，multiset 会一次性删除所有值为 val 的元素，并返回删除的总个数。

4. count 返回实际个数

count 能准确反映某个值出现的频率。

---

set 和 multiset 是处理唯一性或重复性有序数据的高效工具。理解它们底层的红黑树机制以及迭代器失效规则，能帮助你在实际开发中避免常见的 Bug。