好久没有水文了，这次梳理一下 set 的用法。

set 的翻译就是集合，但是与数学上集合不同的是 set 是一个内部自动有序且不含重复元素的容器。因为这个特点，set 在某些场景下能很方便的解决一些问题。

使用 set 之前，需要先引入 set 头文件。另外，set 的底层好像是用红黑树来实现的？

初始化

set 的初始化与 vector 和其他 STL 容器类似（可以看下 set 提供的构造函数）：

set<int> s1;
set<double> s2;
set<char> s3;
set<int> s4[100]  // s4 大小为 100，内部每一个元素都是一个 set

访问

set 只能通过迭代器（iterator）访问：

1
2
3

set<int>::iterator it;
set<double>::iterator it;
set<char>::iterator it;

set 的迭代器只能通过自增（减）运算符来改变：

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> st;
    st.insert(1);
    st.insert(2);
    st.insert(3);
    st.insert(4);
    st.insert(5);
    for(set<int>::iterator it = st.begin(); it != st.end(); it++) {
        cout << *it << ' ';
    }
    return 0;
}
/*
out:
1 2 3 4 5 
*/

常用函数

insert

向集合内插入元素，前面说过了，集合会自动排序和去重。

1	st.insert(x);

find

集合内查找元素，返回 set 中对应值为 value 的迭代器，时间复杂度为 O(logN)。

1	st.find(value);

count

查询集合内是否存在值为 value 的元素，如果存在返回 1，反之，返回 0。

1	st.count(value);

erase

erase 函数用于删除集合内的元素，两种用法。

删除单个元素

按照这个元素的迭代器进行删除：

1	st.erase(it);

删除单个值为 value 的元素：

1	st.erase(value);

删除一个区间的元素

需要提供区间首尾的迭代器：

1 2	st.erase(it1, it2); st.erase(it1, st.end());

size

size 函数用来返回集合内元素个数。

1	st.size();

clear

clear 函数用来清空 set 内的所有元素。

1	st.clear();

lower_bound

lower_bound 函数是 set 内集成的一个二分查找函数，功能与std::lower_bound函数的功能是类似的。
对 set 而言，使用其内部的 lower_bound 函数的效率会更高，用起来也更方便，只用提供一个 value 即可，但前提是要确保 value 的类型与 set 容器内元素类型一致。
另外，lower_bound 函数的返回值是 set 的迭代器。

set<int> st;
st.insert(1);
st.insert(2);
st.insert(3);
st.lower_bound(2);

upper_bound

与上述 lower_bound 函数的用法一致，与std::upper_bound功能类似。

扩展

有时候可能不需要 set 容器的去重功能，可以使用 multiset；有时候不需要排序功能，就可以使用 unordered_set，此时由于没有排序操作了，运行速度会快很多。unordered_set 在某些场合下，还可以当作哈希表来用。

bachzart's Blog

C++_set 容器的常见用法

初始化

访问