6. set 集合

集合（set） 是 C++ 标准模板库（STL）中用于存储唯一元素的容器。其底层通常使用红黑树实现。

集合 内部用红黑树实现，其查找、插入、删除的时间复杂度都是 O(logⁿ)。

集合的特点是自动去重。适用于需要判断元素是否存在、去重和集合运算。

set 模板的定义方法如下:

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

说明:

set 创建的集合可以使用统一初始化列表 {...} 进行初始化。如：

std::set<int> s = {11, 22, 33, 44};

统一初始化列表的语法格式

{对象1, 对象2, 对象3, ...}

常用的成员函数

成员函数
说明
set
构造函数。
~set
析构函数。
operator=
赋值。
容量相关成员函数
empty
判断是否为空
size
返回数据元素个数
max_size
返回可能存储的最大数据元素个数。
修改相关成员函数
clear
清空数据。
insert
插入数据
emplace(C++11)
使用构造对象替换
erase
删除数据
swap
交换两个容器内容
查找相关成员函数
count
返回指定键匹配成功的数量。
find
查找指定的键。
迭代器相关成员函数
begin 或 cbegin(C++11)
返回容器数据开始位置的迭代器
end或cend(C++11)
返回容器数据结束位置的迭代器（最后一个元素的后面）
rbegin或crbegin(C++11)
返回反向迭代器的起始位置（最后一个元素）
rend或 crend(C++11)
返回反向迭代器的结束位置（第一个元素的前一位置）

以上函数只给出了函数名，以上函数大多数都有重载，具体请查看官方文档.

参考文档

https://en.cppreference.com/cpp/container/set

非成员函数

操作
说明
operator==
比较两个容器是否相同。
std::swap
交换两个同类型的容器内容。

示例

// filename: myset.cpp
#include <iostream>
#include <set>

int main(int argc, char * argv[]) {

    std::set<int> s{1, 5, 3, 3, 3, 1};  // 集合自动去重
    // 打印集合信息：(C++98 的用法)
    for (std::set<int>::const_iterator it = s.cbegin(); it != s.cend(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;

    s.insert(7);  // 加入数据
    // 打印集合信息：(C++11 的用法)
    for (auto it = s.cbegin(); it != s.cend(); it++)
        std::cout << *it << " ";
    std::cout << std::endl;

    s.erase(1);  // 删除数据
    for (int key : s)
        std::cout << key << " ";
    std::cout << std::endl;

    // 判断 5 是否在集合中:
    if (s.count(5))
        std::cout << "5 在集合中" << std::endl;
    else
        std::cout << "5 不在集合中" << std::endl;

    return 0;
}

编译和运行结果如下

weimz@mzstudio:~$ g++ -o myset myset.cpp
weimz@mzstudio:~$ ./myset
1 3 5 
1 3 5 7 
3 5 7 
5 在集合中