wdgmultiset
set 的构造函数
cppreference
set 有一堆构造函数。C++ 98 有如下：
1
2
3
4
5
6
7
| set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
set (const set& x);
|
- default：
set<int> s; 构造一个空的 set<int>；
- range:
set<int> s(v.begin(), v.end()) 对 v 进行遍历，并构造一个相同的 set<int>；
- copy：从一个
set 拷贝构造为另一个。
值得一提的是第三个 range，它能将 vector list 等数据结构转化为 set。更有意思的是，vector 等模板类也有类似的构造函数，因此二者可以互相转换：
1
2
3
4
5
6
7
8
9
10
11
| #include<bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v1{ 1, 4, 2, 3 };
set<int> s1(v1.begin(), v1.end());
vector<int> v2(s1.begin(), s1.end());
return 0;
}
|
反向遍历 set
1
2
3
4
5
6
7
8
9
10
| set<int> s = {1, 3, 5};
for(set<int>::iterator iter = s.begin(); iter != s.end(); iter++)
cout << *s << " ";
cout << endl;
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)（文档）set 使用任意插入，因此需要使用 std::inserter(s, s.begin())（文档
以下函数需要引入 #include<algorithm>。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
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()));
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(intersection_v));
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(diff_v));
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）。
++和--支持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 来判断两边是否有重叠。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#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();
}
}
|
最后更新时间：
