set 的构造函数

cppreference (opens new window)

set 有一堆构造函数。C++ 98 有如下：

set (const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type()); //empty (1)
template <class InputIterator>
set (InputIterator first, InputIterator last,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type()); //range (2)
set (const set& x); //copy (3)

• default：set<int> s; 构造一个空的 set<int>；
• range: set<int> s(v.begin(), v.end()) 对 v 进行遍历，并构造一个相同的 set<int>；
• copy：从一个 set 拷贝构造为另一个。

值得一提的是第三个 range，它能将 vector list 等数据结构转化为 set。更有意思的是，vector 等模板类也有类似的构造函数，因此二者可以互相转换：

#include<bits/stdc++.h>

using namespace std;

int main()
{
    vector<int> v1{ 1, 4, 2, 3 };
    set<int> s1(v1.begin(), v1.end());    // s1 = {1, 2, 3, 4}
    vector<int> v2(s1.begin(), s1.end()); // v2 = {1, 2, 3, 4}
    return 0;
}

反向遍历 set

set<int> s = {1, 3, 5};

// 正向遍历，输出 1 3 5
for(set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
    cout << *s << " ";
cout << endl;

// 反向遍历，输出 5 3 1
for(set<int>::iterator iter = s.rbegin(); iter != s.rend(); iter++)
    cout << *s;

集合运算

集合运算包括：交集、并集、差集、对称差集（二者相互作差集，然后对两个差集作并集）、超集。

集合运算实际上不是 std::set 独享的，它可以用于任何有序的（由两个 iterator 表示的）range 上。其迭代是基于 iterator 的，所以就可以用于 vector、list、set、map 等容器之上了。

供读入的 InputIterator 可以使用 vector 和 set 的 s.begin() 和 s.end()，但是在供输出的 OutputIterator 上，vector 和 set 有些差异，在于二者添加元素方式的差异。

• vector 使用尾插，因此需要使用 std::back_inserter(v)（文档 (opens new window)）
• set 使用任意插入，因此需要使用 std::inserter(s, s.begin())（文档 (opens new window)

以下函数需要引入 #include<algorithm>。

set<int> s1{1, 3, 5, 7, 9};
vector<int> s2{2, 3, 5, 7};
vector<int> s3{2, 3};
vector<int> union_v, intersection_v, diff_v, symdiff_v;
set<int> union_s;

// 将 s1 和 s2 的并集保存到 s 的最后，返回 {1, 2, 3, 5, 7, 9}
// https://zh.cppreference.com/w/cpp/algorithm/set_union
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(union_v));
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(union_s, union_s.begin()));

// 将 s1 和 s2 的交集保存到 s 的最后，返回 {3, 5, 7}
// https://zh.cppreference.com/w/cpp/algorithm/set_intersection
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(intersection_v));

// 将 s1 和 s2 的差集保存到 s 的最后，返回 {1, 9}
// https://zh.cppreference.com/w/cpp/algorithm/set_difference
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(diff_v));

// 将 s1 和 s2 的对称差集保存到 s 的最后，返回 {1, 2, 9}
// https://zh.cppreference.com/w/cpp/algorithm/set_symmetric_difference
set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(symdiff_v));

注意如果不是用在 map 或 set 等自带排序的结构上，需要提前排好序。

multiset

支持操作	C++代码
插入	insert(value);
删除	erase(value); erase(iter);
查询	set::iterator iter = find(value);
二分搜索	lower_bound(value); upper_bound(value);
开头（最小）	begin()
结尾（最大）	--end()

• set.insert() 的返回值是一个 Pair，first 是（新加入或原本就存在的）该元素的 iterator，second 是 插入成功与否的 bool 值。而 multiset 只返回 iterator。
• C++ 11 起，保证 multiset.insert() 插入的数在相同的数的最后（reference (opens new window)）。
• ++和--支持list和set multiset，简直无敌。
• set的*iter不会随数据插入、删除而改变（想想指针你大概就懂了）。
• 如何遍历 const multiset 呢？set::const_iterator iter。

unordered_set

unordered_set 的实现不是二叉平衡树，而是 hash。对于自定义类型，可能需要定义 hash_value() 函数并且重载operator==。

使用的时候，没有排序，所以不能二分；遍历的效率也会很低（猜测是要遍历整个 hash 表）。用的话，一般用于查询某个数是否被存过，并且数据范围过大需要丽离散化。

set.find()妙用

𝒔𝒆𝒕的𝒇𝒊𝒏𝒅函数可以直接找到和一个元素在逻辑上相等的另外一个元素 find、upper_bound、lower_bound函数的相等用的并不是a==b，而是!(a<b)&&!(b<a)，只需要重定义<

find()没有找到就返回set.end();

下面是一道潇神出的题，很好的利用这个性质，用 set 来判断两边是否有重叠。

//Lutece 2145 人在地上走，锅从天上来
//https://acm.uestc.edu.cn/contest/12/problem/C
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 100001;
struct edge {
    int l;
    int r;
};

bool operator <(edge a, edge b)
{
    return a.r < b.l;
}
set<edge> s;
set<edge>::iterator iter;
int merge(edge & temp)
{
    if ((iter = s.find(temp)) != s.end())
    {
      temp.l = min(temp.l, iter->l);
      temp.r = max(temp.r, iter->r);
      s.erase(iter);
      merge(temp);
      return 1;
    }
    else
    {
      s.insert(temp);
      return 0;
    }
}
int main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
      edge temp;
      cin >> temp.l >> temp.r;
      merge(temp);
      cout << (i?" ":"") << s.size();
    }
}