C++STL详解之set与multiset的使用、区间查询和算法应用小结

一、序列式容器和关联式容器

1.1 序列式容器按位置组织元素

序列式容器里，常见的有这么几个：

std::vector
std::list
std::deque
std::array
std::forward_list

数据是按照它们在容器中的位置来组织的。

举个例子：

std::vector values{10, 20, 30};

关注的是：

values[0] 是 10
values[1] 是 20
values[2] 是 30

交换两个元素后，容器本身依然是合法的：

std::swap(values[0], values[2]);

结果只是顺序变了：

30 20 10

1.2 关联式容器按关键字组织元素

有序关联式容器里，常见的有这些：

std::set
std::multiset
std::map
std::multimap

数据是根据关键字和比较规则来组织的。

拿 set 来说：

std::set values{8, 3, 10, 1, 6};

内部需要维持类似二叉搜索树的有序关系：

左边关键字更小
右边关键字更大

不能随意把两个结点中的关键字交换，否则会破坏搜索结构。

1.3 set 和 map 的定位

一句话区分就是：

set：只保存 key
map：保存 key 和 value

举几个例子：

set：
车牌号是否存在
账号是否在黑名单中
一个数字是否出现过
map：
英文单词 -> 中文解释
学生学号 -> 学生成绩
商品编号 -> 库存数量

二、set 是什么？

2.1 set 的基本声明

要使用 set，先得包含头文件：

#include 

最常见的定义方式：

std::set numbers;

它的简化模板形式可以理解为：

template<
    class Key,
    class Compare = std::less,
    class Allocator = std::allocator
>
class set;

三个模板参数分别表示：

Key       ：关键字类型
Compare   ：关键字比较规则
Allocator ：内存分配器

一般只需要提供第一个参数：

std::set numbers;
std::set words;

2.2 set 的核心特点

set 有下面几个重要特点：

1. 每个关键字最多保存一份
2. 元素按照比较器规定的顺序排列
3. 不支持下标访问
4. 不能通过迭代器修改关键字
5. 查找、插入和删除通常为 O(log N)
6. 支持按照关键字进行范围查询

2.3 set 不一定是“从小到大”

默认比较器是：

std::less

所以通常表现为升序。

但如果使用：

std::greater

就会变为降序：

std::set> numbers;

更准确的说法是：

set 会按照比较器定义的顺序保存和遍历元素。

三、set 的构造方式

3.1 默认构造

std::set numbers;

此时得到一个空集合。

3.2 初始化列表构造

std::set numbers{5, 2, 8, 2, 7, 5};

集合中的内容为：

2 5 7 8

重复元素不会重复保存。

3.3 迭代器区间构造

#include 
#include 
std::vector values{5, 2, 8, 2, 7};
std::set numbers(values.begin(), values.end());

这种写法可以同时完成：

复制数据
去除重复元素
按照比较规则排序

3.4 拷贝构造

std::set first{1, 3, 5};
std::set second(first);

也可以写成：

std::set second = first;

四、set 的遍历方式

4.1 正向迭代器遍历

#include 
#include 
int main()
{
    std::set numbers{5, 2, 8, 1, 5};
    for (auto it = numbers.begin();
         it != numbers.end();
         ++it)
    {
        std::cout << *it << ' ';
    }
    return 0;
}

输出：

1 2 5 8

set 的迭代器属于双向迭代器，支持：

++it;
--it;

但不支持：

it + 3;
it - 2;

4.2 范围 for 遍历

for (int value : numbers)
{
    std::cout << value << ' ';
}

范围 for 是日常使用中最简单的遍历方式。

4.3 反向遍历

for (auto it = numbers.rbegin();
     it != numbers.rend();
     ++it)
{
    std::cout << *it << ' ';
}

如果默认使用升序 set，反向遍历会得到降序结果：

8 5 2 1

4.4 为什么不能修改 set 中的元素？

下面的代码无法通过编译：

auto it = numbers.begin();
*it = 100;

因为元素本身就是关键字。

假设原来的结构中：

3 位于 5 的左边

如果直接把 3 修改成 10：

10 仍然位于 5 的左边

搜索树中的大小关系就被破坏了。

因此，set 不允许通过迭代器修改元素。

需要修改关键字时，应当：

先删除旧值
再插入新值

例如：

auto it = numbers.find(3);
if (it != numbers.end())
{
    numbers.erase(it);
    numbers.insert(10);
}

五、insert：向 set 中插入元素

5.1 插入单个元素

std::set numbers;
numbers.insert(5);
numbers.insert(2);
numbers.insert(8);

结果：

2 5 8

5.2 重复插入会怎样？

numbers.insert(5);
numbers.insert(5);

set 中仍然只保存一个 5。

因为 set 要求关键字唯一。

5.3 insert 的返回值

插入单个元素时，返回类型是：

std::pair

示例：

auto result = numbers.insert(5);

其中：

result.first  ：指向关键字 5 的迭代器
result.second ：是否真正插入成功

完整示例：

#include 
#include 
int main()
{
    std::set numbers;
    auto result1 = numbers.insert(5);
    auto result2 = numbers.insert(5);
    std::cout << std::boolalpha;
    std::cout << "第一次插入："
              << result1.second << 'n';
    std::cout << "第二次插入："
              << result2.second << 'n';
    std::cout << "关键字："
              << *result2.first << 'n';
    return 0;
}

输出：

第一次插入：true
第二次插入：false
关键字：5

即使插入失败：

result2.first

仍然指向集合中已经存在的 5。

5.4 使用结构化绑定接收返回值

C++17 可以写成：

auto [it, inserted] = numbers.insert(5);
if (inserted)
{
    std::cout << "插入成功n";
}
else
{
    std::cout << "元素已经存在n";
}

5.5 插入一组数据

numbers.insert({3, 6, 8, 3});

已经存在的关键字会被忽略。

也可以插入一段迭代器区间：

std::vector values{10, 20, 10, 30};
numbers.insert(values.begin(), values.end());

六、find、count 和 contains

6.1 find 查找关键字

auto it = numbers.find(5);

找到时，返回指向元素的迭代器。

没有找到时，返回：

numbers.end()

标准写法：

auto it = numbers.find(5);
if (it != numbers.end())
{
    std::cout << "找到了：" << *it << 'n';
}
else
{
    std::cout << "没有找到n";
}

6.2 不要优先使用通用 find

算法库也提供了：

std::find(numbers.begin(), numbers.end(), 5);

但通用算法不知道 set 内部的有序结构，只能从头逐个比较，复杂度为：

O(N)

而成员函数：

numbers.find(5);

可以利用关联式容器的搜索结构，复杂度通常为：

O(log N)

因此，在 set 中查找关键字时，应优先使用成员函数 find()。

6.3 count 判断元素是否存在

对于 set：

numbers.count(5);

返回值只有两种：

0：不存在
1：存在

因此可以写成：

if (numbers.count(5) != 0)
{
    std::cout << "5 存在n";
}

6.4 contains

C++20 增加了：

numbers.contains(5);

它直接返回布尔值：

if (numbers.contains(5))
{
    std::cout << "5 存在n";
}

Linux 下使用 C++20 编译：

g++ -std=c++20 main.cpp -o main
./main

6.5 find、count 和 contains 如何选择？

只想判断是否存在：

numbers.contains(key); // C++20
numbers.count(key);    // C++11 也可用

还需要拿到对应迭代器：

auto it = numbers.find(key);

七、erase：删除 set 中的元素

7.1 根据关键字删除

std::size_t count = numbers.erase(5);

对于 set：

返回 1：成功删除
返回 0：关键字不存在

示例：

if (numbers.erase(5) == 0)
{
    std::cout << "5 不存在n";
}

7.2 根据迭代器删除

auto it = numbers.find(5);
if (it != numbers.end())
{
    numbers.erase(it);
}

7.3 删除最小值

默认升序 set 中：

numbers.begin()

指向最小值。

所以：

if (!numbers.empty())
{
    numbers.erase(numbers.begin());
}

可以删除最小元素。

最大值可以通过：

std::prev(numbers.end())

找到：

if (!numbers.empty())
{
    numbers.erase(std::prev(numbers.end()));
}

7.4 遍历过程中删除

假设要删除所有偶数：

auto it = numbers.begin();
while (it != numbers.end())
{
    if (*it % 2 == 0)
    {
        it = numbers.erase(it);
    }
    else
    {
        ++it;
    }
}

erase(it) 会返回被删除元素的下一个迭代器。

不要写成：

numbers.erase(it);
++it;

因为删除后，原来的 it 已经失效。

7.5 迭代器失效规则

对于 set 这类结点式关联容器：

插入元素通常不会让已有迭代器失效
删除元素只会让指向被删除元素的迭代器失效
其他元素的迭代器通常仍然有效

这和可能整体扩容的 vector 不同。

八、lower_bound、upper_bound 和 equal_range

8.1 lower_bound

默认升序情况下：

numbers.lower_bound(value);

返回第一个：

大于等于 value

的元素。

例如：

std::set numbers{10, 20, 30, 40, 50};
auto it = numbers.lower_bound(25);

it 指向：

30

8.2 upper_bound

numbers.upper_bound(value);

返回第一个：

严格大于 value

的元素。

例如：

auto it = numbers.upper_bound(30);

it 指向：

40

8.3 删除闭区间 [30, 60]

std::set numbers{
    10, 20, 30, 40, 50, 60, 70, 80
};
auto first = numbers.lower_bound(30);
auto last = numbers.upper_bound(60);
numbers.erase(first, last);

因为迭代器区间采用左闭右开：

[first, last)

所以删除的是：

30 40 50 60

8.4 equal_range

auto range = numbers.equal_range(30);

相当于同时获得：

range.first  == numbers.lower_bound(30);
range.second == numbers.upper_bound(30);

C++17 可以写成：

auto [first, last] = numbers.equal_range(30);

8.5 不要把“大小”理解死

lower_bound 和 upper_bound 实际上依据的是比较器，而不一定是数学意义上的小于和大于。

默认 std::less 下，可以理解为：

lower_bound：第一个 >= key
upper_bound：第一个 > key

如果使用自定义比较器，就应按照该比较器定义的顺序理解。

九、自定义排序规则

9.1 降序 set

#include 
#include 
std::set> numbers{
    3, 1, 5, 2
};

遍历结果：

5 3 2 1

9.2 自定义类型作为 key

假设需要按照学生学号排序：

#include 
#include 
#include 
struct Student
{
    int id;
    std::string name;
};
struct StudentCompare
{
    bool operator()(const Student& left,
                    const Student& right) const
    {
        return left.id < right.id;
    }
};
int main()
{
    std::set students;
    students.insert({1003, "张三"});
    students.insert({1001, "李四"});
    students.insert({1002, "王五"});
    for (const auto& student : students)
    {
        std::cout << student.id << ' '
                  << student.name << 'n';
    }
    return 0;
}

9.3 相同学号能否插入？

比较器只比较：

left.id < right.id

因此，如果两个学生学号相同，即使姓名不同，set 仍会把它们视为等价关键字。

例如：

students.insert({1001, "李四"});
students.insert({1001, "赵六"});

第二次插入会失败。

9.4 比较器必须满足严格弱序

比较器通常应该表达“严格排在前面”，例如：

return left.id < right.id;

不要写成：

return left.id <= right.id;

比较器至少应保证：

compare(x, x) 必须为 false

否则容器的排序关系会失去一致性，程序行为可能不符合预期。

十、set 和 multiset 的区别

10.1 multiset 允许重复元素

std::multiset numbers{
    4, 2, 7, 2, 4, 8, 4
};

遍历结果：

2 2 4 4 4 7 8

multiset 保持有序，但不会去重。

10.2 insert 返回值不同

set::insert：

std::pair

因为要告诉调用者是否插入成功。

multiset::insert：

iterator

因为重复关键字也能正常插入，不需要返回“是否成功”。

10.3 count 返回实际数量

std::cout << numbers.count(4);

对于上面的 multiset，结果是：

3

而 set::count() 只能返回 0 或 1。

10.4 erase(key) 会删除所有等价元素

numbers.erase(4);

会删除所有的 4。

如果只想删除一个 4：

auto it = numbers.find(4);
if (it != numbers.end())
{
    numbers.erase(it);
}

10.5 获取所有相同关键字

推荐使用：

auto [first, last] = numbers.equal_range(4);
for (auto it = first; it != last; ++it)
{
    std::cout << *it << ' ';
}

10.6 set 和 multiset 对比

十一、应用一：去重并排序

11.1 基本实现

#include 
#include 
#include 
int main()
{
    std::vector values{
        5, 2, 8, 5, 3, 2, 7
    };
    std::set uniqueValues(
        values.begin(),
        values.end()
    );
    for (int value : uniqueValues)
    {
        std::cout << value << ' ';
    }
    return 0;
}

输出：

2 3 5 7 8

11.2 这种方法适合什么情况？

适合：

希望同时得到有序结果
数据规模不算特别大
后续还要进行有序查询

如果只需要快速判重而不关心顺序，unordered_set 通常更合适。

十二、应用二：两个数组的交集

给定：

nums1 = [1, 2, 2, 3, 5]
nums2 = [2, 2, 4, 5]

要求返回不重复的交集：

[2, 5]

12.1 利用 set 去重

#include 
#include 
std::vector intersection(
    const std::vector& nums1,
    const std::vector& nums2)
{
    std::set first(nums1.begin(), nums1.end());
    std::set second(nums2.begin(), nums2.end());
    std::vector result;
    auto it1 = first.begin();
    auto it2 = second.begin();
    while (it1 != first.end() &&
           it2 != second.end())
    {
        if (*it1 < *it2)
        {
            ++it1;
        }
        else if (*it2 < *it1)
        {
            ++it2;
        }
        else
        {
            result.push_back(*it1);
            ++it1;
            ++it2;
        }
    }
    return result;
}

因为两个 set 都是有序的，所以可以使用双指针思想：

较小的一方前进
相等时加入答案

12.2 也可以使用标准算法

#include 
#include 
std::set_intersection(
    first.begin(),
    first.end(),
    second.begin(),
    second.end(),
    std::back_inserter(result)
);

十三、应用三：检测链表是否访问过某个结点

判断链表是否存在环，可以把访问过的结点地址放入 set：

struct ListNode
{
    int val;
    ListNode* next;
};
ListNode* detectCycle(ListNode* head)
{
    std::set visited;
    ListNode* current = head;
    while (current != nullptr)
    {
        auto [it, inserted] = visited.insert(current);
        if (!inserted)
        {
            return current;
        }
        current = current->next;
    }
    return nullptr;
}

当一个结点地址第二次插入失败时，说明程序再次访问到了同一个结点。

不过该方法需要额外空间：

O(N)

如果题目要求常数额外空间，应使用快慢指针。

十四、set 与 unordered_set 怎么选？

14.1 set

主要特点：

元素有序
支持 lower_bound 和 upper_bound
单次查找、插入和删除通常为 O(log N)
性能比较稳定

适合：

需要有序遍历
需要查找某个范围
需要找大于等于某值的第一个元素

14.2 unordered_set

主要特点：

元素无序
基于哈希规则查找
平均查找、插入和删除接近 O(1)
最坏情况可能退化
不支持 lower_bound 和 upper_bound

适合：

只关心是否存在
不需要有序结果
希望获得平均意义上的快速查找

14.3 简单选择原则

需要顺序或范围查询：set
只需要快速判重：unordered_set
允许重复且需要有序：multiset
允许重复但不要求有序：unordered_multiset