Set 是什么

set是 C++ STL 中提供的容器，set是数学上的集合——具有唯一性，即每个元素只出现一次，而 multiset 则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同。set用于判断一个集合内元素的有无。

成员方法 功能
begin() 返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end() 返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin() 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend() 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
find(val) 在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val) 返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val) 返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val) 该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。
empty() 若容器为空，则返回 true；否则 false。
size() 返回当前 set 容器中存有元素的个数。
max_size() 返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
insert() 向 set 容器中插入元素。
erase() 删除 set 容器中存储的元素。
swap() 交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。
clear() 清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。
emplace() 在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint() 在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
count(val) 在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。

头文件与声明

像这样：

  1. #include <set>
  2. set<类型> 名称;
  3. //example:
  4. set<int>s;
  5. set<vector<int> >s;     //vector中提供重载
  6. set<set<int> >s;    //平衡树嵌套，哈哈
  7. multiset<double>s;

就像其他需要排序的数据类型一样，为一个结构体的 set，需要重载小于号

struct node{
    ......;
};
set<node> s;
bool operator <(const node &ai,const node &bi)
{
    return ai.x > bi.x;
}

set.size()

统计 set 中元素个数，函数返回一个整形变量，表示 set 中元素个数，时间复杂度 2 set - 图1

用法：名称.size();
eg.
int num = s.size();

set.empty()

检查 set 是否为空，返回一个 bool 型变量，1 表示 set 为空，否则为非空，时间复杂度 2 set - 图2

用法：名称.empty();
eg.
if(s.empty())
    cout << "Myset is Empty." << endl;

set.clear()

清空 set ，无返回值

用法：名称.clear();
eg.
s.clear();

set.count(x)

返回 set 或 multiset 中值为 x 的元素个数，时间复杂度为 2 set - 图3

用法：名称.count(x)
eg.
if(!s.count(x))
    ans++;

迭代器

  1. 双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持 ++``-- 这两个算术操作

引用和操作：

set<类型>::iterator it;
eg.
set<int>::iterator it = s.begin();
it++;
it--;

若把 it++，则 it 将会指向“下一个”元素。这里的下一个是指在 key 从小到大排序的结果中，排在 it 下一名的元素。同理，若把 it-- ，则 it 会指向排在上一个的元素
++ -- 操作的复杂度均为 2 set - 图4

  1. 遍历 set 及访问其中的元素
    //set
for(set<int>::iterator it = s.begin(); it != s.end(); it++)
 cout << *it << endl;    //取出这个迭代器指向的元素
//set嵌套
for(set<set<int> >::iterator it = s.begin(); it != s.end(); it++)
{
 //首先取出set中嵌套的set
 for(set<int>::iterator rit = (*it).begin(); rit != (*it).end(); rit++)
     cout << *rit << ' ';    //遍历这个set
 cout << endl;
}

    set.begin()

    返回集合的首迭代器，即指向集合中最小元素的迭代器，时间复杂度为 2 set - 图5
    用法：名称.begin();
eg.
map<int>::iterator it = s.begin();

    set.end()

    返回集合的尾迭代器，众所周知，STL 中区间都是左闭右开的，那么 end() 函数返回的迭代器即为指向集合中最大元素的下一个位置的迭代器，因此 --s.end() 才是指向集合中最大元素的迭代器，时间复杂度为 2 set - 图6
    用法：名称.end();
eg.
maxn = *(--s.end());      //取出最大元素

    set.insert(x)

    在 set 中插入元素，返回插入地址的迭代器和是否插入成功的 bool 并成的 pair ，时间复杂度为 2 set - 图7
    PS：set 在进行插入的时候是不允许有重复的键值的，如果新插入的键值与原有的键值重复则插入无效（multiset 可以重复）
    用法：名称.insert(set类型);
eg.
s.insert(3);

    set.erase(参数)

    删除，参数可以是元素或者迭代器，返回下一个元素的迭代器，时间复杂度为 2 set - 图8 ，注意在 multiset 中 s.erase(x) 会删除所有值为 x 的元素
    用法：名称.erase(参数);
eg.
set<int>::iterator it = s.begin();
s.erase(it);
s.erase(3);

    set.find(x)

    在 set 中查找值为 x 的元素，并返回指向该元素的迭代器，若不存在，返回 set.end()，时间复杂度为 2 set - 图9
    用法：名称.find(x);
eg.
if(s.find(x) != s.end())
 cout << "Have Found!" << endl;

    set.lower_bound(x) / upper_bound(x)

    两个神奇的东西，决定把他们放在一块谈一谈
    用法与 find 类似，但查找的条件略有不同，时间复杂度 2 set - 图10
    s.lower_bound(x) 表示查找 >= x 的元素中最小的一个，并返回指向该元素的迭代器
    s.upper_bound(x) 表示查找 >x 的元素中最小的一个，并返回指向该元素的迭代器

    举个例子：

    在 2 set - 图11 中
    对于在 set 中存在的元素，比如 8
    s.lower_bound(8) 返回 8 所在位置的迭代器
    s.upper_bound(8) 返回 13 所在位置的迭代器
    对于在 set 中不存在的元素，比如 12
    两个函数返回的则都是 13 所在位置的迭代器

    特殊地，

    对于比 set 中最大的元素大的元素，比如 20
    两个函数返回的都是 s.end()

【洛谷日报#7】STL整理之set