[C++随想录] map和set的使用

set — — key模拟
map — — key_value模型

set

初始化

void set_test1()
{
	set<int>s;
	s.insert(10);
	s.insert(12);
	s.insert(13);
	s.insert(9);
	s.insert(10);
	s.insert(5);

	cout << "s-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	set<int>s1(s.begin(), s.end());

	cout << "s1-> ";
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

int main()
{

	set_test1();

	return 0;
}
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

运行结果:

s-> 5 9 10 12 13
s1-> 5 9 10 12 13
1
2

1. set默认 去重 + 排序
2. 支持 遍历, 但不支持 随机访问, 即[], 迭代器是 双向迭代器👇👇👇
   

find

void set_test2()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);

	auto it = s.find(10);
	if(it != s.end())
		cout << *it << endl;
	auto tem = s.find(5);
	if(tem != s.end())
		cout << *tem << endl;
}

int main()
{

	set_test2();

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

运行结果:

5
1

• 算法库里面的 find — — 暴力搜索, O(N)
  set自带的 find — — 利用二叉搜索树的特性 O(logN)

void set_test2()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);

	// set自带的find函数
	auto it = s.find(5);
	if(it != s.end())
		cout << *it << endl;

	// 算法库里面的 find函数
	auto tem = find(s.begin(), s.end(), 5);
	if(tem != s.end())
		cout << *tem << endl;
}

int main()
{

	set_test2();

	return 0;
}
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

运行结果:

5
5
1
2

erase

1. 先找后删
   🗨️思考: 下面的代码正确不?

void set_test1()
{
	set<int>s;
	s.insert(10);
	s.insert(12);
	s.insert(13);
	s.insert(9);
	s.insert(10);
	s.insert(5);
	
	auto it = s.begin();
	s.erase(it);
	s.erase(it + 3);
}

int main()
{
	set_test1();
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 上面的代码是错误的:
  1. set没有重载 +
  2. 即使重载了 +, 我们也要 判断 我们要删除的地址是否在s中

我们应该这样写👇👇👇

void set_test1()
{
	set<int>s;
	s.insert(10);
	s.insert(12);
	s.insert(13);
	s.insert(9);
	s.insert(10);
	s.insert(5);

	cout << "s-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	auto it = s.find(10);
	// 判断 s 中是否有此元素
	if (it != s.end())
	{
		s.erase(it);
	}

	cout << "删除后-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test1();

	return 0;
}
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

运行结果:

s-> 5 9 10 12 13
删除后-> 5 9 12 13
1
2

2. 传值直接删

void set_test1()
{
	set<int>s;
	s.insert(10);
	s.insert(12);
	s.insert(13);
	s.insert(9);
	s.insert(10);
	s.insert(5);

	cout << "s-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 传值直接删除
	s.erase(10);

	cout << "删除后-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test1();

	return 0;
}
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

运行结果:

s-> 5 9 10 12 13
删除后-> 5 9 12 13
1
2

🗨️传值直接删除, 不用判断元素在不在set对象中?

• 不用!
  如果在对象中, 就删除; 如果不在对象中, 啥事不干👇👇👇

void set_test1()
{
	set<int>s;
	s.insert(10);
	s.insert(12);
	s.insert(13);
	s.insert(9);
	s.insert(10);
	s.insert(5);

	cout << "s-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 传值直接删除
	s.erase(15);

	cout << "删除后-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test1();

	return 0;
}
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

运行结果:

s-> 5 9 10 12 13
删除后-> 5 9 10 12 13
1
2

3. 删除一段区间

void set_test1()
{
	set<int>s;
	s.insert(10);
	s.insert(12);
	s.insert(13);
	s.insert(9);
	s.insert(10);
	s.insert(5);

	cout << "s-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 删除 [5, 10)区间内的值
	auto i = s.find(5);
	auto j = s.find(10);
	s.erase(i, j);

	cout << "删除后-> ";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test1();

	return 0;
}
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

运行结果:

s-> 5 9 10 12 13
删除后-> 10 12 13
1
2

• 这个我感觉很 鸡肋:
  1. set不支持 +
  2. 找到了还要判断是否存在

从而导致, 用这个方法删除一段区间有点麻烦.
不过, 后面有两个函数: lower_bound 和 upper_bound, 可以配合使用找寻 一段区间, 可以配合这个方法使用~~

count

在 set中, 判断一个元素存不存在:

1. find
2. count

count函数返回 该元素的个数, 由于set 去重 ⇒ 所以, 返回 1 或 0
count函数 在 multiset 里面可以体现出 统计元素个数的功能

1. 判段元素在不在

void set_test3()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);

	// count 和 find 来判断元素是否存在
	int tem = s.count(5);
	if (tem > 0)
	{
		cout << "5元素存在" << endl;
	}
	else
	{
		cout << "5元素不存在" << endl;
	}

	auto it = s.find(11);
	if (it != s.end())
	{
		cout << "11元素存在" << endl;
	}
	else
	{
		cout << "11元素不存在" << endl;
	}
}

int main()
{

	set_test3();

	return 0;
}
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

运行结果:

5元素存在
11元素不存在
1
2

2. 统计元素个数

void set_test3()
{
	multiset<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);
	s.insert(15);
	s.insert(15);
	
	int n = s.count(15);
	cout << "15的个数: " << n << endl;

}

int main()
{

	set_test3();

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果:

15的个数: 3
1

• multiset 和 set
  1. set中的 key是唯一的, 而multiset中的 key 允许是多个的
  2. set 和 multiset 都是包含在 的头文件中的

lower_bound && upper_bound

void set_test3()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);
	s.insert(10);
	s.insert(11);
	
	// lower_bound && upper_bound
	auto itlow = s.lower_bound(5);
	cout << *itlow << endl;

	auto itup = s.upper_bound(15);
	cout << *itup << endl;

}

int main()
{

	set_test3();

	return 0;
}
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

运行结果:

5
18
1
2

itlow 和 itup构成的区间是 [itlow, itup) ⇒ 这样我们就可以 删除特定区间的内容👇👇👇

void set_test3()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);
	s.insert(10);
	s.insert(11);

	cout << "s ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// 删除 5~15 这段区间的内容
	auto itlow = s.lower_bound(5);
	auto itup = s.upper_bound(15);

	s.erase(itlow, itup);
	cout << "删除 5~15 ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test3();

	return 0;
}
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

运行结果:

s ->1 5 10 11 12 15 18
删除 5~15 ->1 18
1
2

equal_ range

• pair :
  在C++中，std::pair是一个模板类，用于保存两个元素的有序对。std::pair的成员变量 first和second分别表示有序对中的第一个和第二个元素。你可以使用 点号（.）操作符来访问这些成员

如果对象里面 存在val, 那么正常返回; 如果对象里面 不存在val, 那么就 返回一个不存在的区间

void set_test3()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(1);
	s.insert(10);
	s.insert(11);

	cout << "s ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	cout << "equal_range(5) val存在的情况" << endl;
	auto eit1 = s.equal_range(5);
	cout << "first element-> " << *eit1.first << endl;
	cout << "second element-> " << *eit1.second << endl;

	cout << "equal_range(6) val不存在的情况" << endl;
	auto eit2 = s.equal_range(6);
	cout << "first element-> " << *eit2.first << endl;
	cout << "second element-> " << *eit2.second << endl;

}

int main()
{

	set_test3();

	return 0;
}
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

运行结果:

equal_range(5) val存在的情况
first element-> 5
second element-> 10
equal_range(6) val不存在的情况
first element-> 10
second element-> 10
1
2
3
4
5
6

假设: set中, 值等于value的下标为i;
其实, set 使用 equal_range 最多只能返回 [i, i+1)
multiset 使用 equal_range 可以返回 [i, i+1, i+2, ... ... j)

set

void set_test3()
{
	set<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(1);
	s.insert(10);
	s.insert(11);

	cout << "s ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// set 删除所有等于5的值
	auto eit = s.equal_range(5);
	s.erase(eit.first, eit.second);
	cout << "set删除所有等于5的值 ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test3();

	return 0;
}
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

运行结果:

s ->1 5 10 11 12 15 18
set删除所有等于5的值 ->1 10 11 12 15 18
1
2

multiset

void set_test3()
{
	multiset<int> s;
	s.insert(15);
	s.insert(18);
	s.insert(12);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(5);
	s.insert(1);
	s.insert(10);
	s.insert(11);

	cout << "s ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
	
	// set 删除所有等于5的值
	auto eit = s.equal_range(5);
	s.erase(eit.first, eit.second);
	cout << "multiset删除所有等于5的值 ->";
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{

	set_test3();

	return 0;
}

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

运行结果:

s ->1 5 5 5 5 10 11 12 15 18
multiset删除所有等于5的值 ->1 10 11 12 15 18
1
2

map

insert

void map_test1()
{
	map<string, string> m1;

	// C++98
	// 1. 传一个pair对象
	pair<string, string> kv1("insert", "插入");
	m1.insert(kv1);

	// 2. 传一个pair的匿名对象
	m1.insert(pair < string, string>("sort", "排序"));

	// 3. make_pair
	m1.insert(make_pair("love", "爱情"));

	// C++11
	// 4. 多参数的构造函数支持隐式类型转换, 用{}
	m1.insert({ "insert", "xxx" });

	for (auto e : m1)
	{
		cout << e.first  << "-> " << e.second << endl;
	}
	cout << endl;

	// 区间初始化
	map<string, string> m2(m1.begin(), m1.end());
	map<string, string>::iterator it = m2.begin();
	while (it != m2.end())
	{
		// cout << (*it).first << "-> "(*it).second << endl;
		cout << it->first << "-> " << it->second << endl;
		++it;
	}
	cout << endl;

}

int main()
{
	map_test1();

	return 0;
}
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

运行结果:

insert-> 插入
love-> 爱情
sort-> 排序

insert-> 插入
love-> 爱情
sort-> 排序
1
2
3
4
5
6
7

1. map的 insert, 传的是一个 pair结构, 返回的也是一个 pair结构.
   

2. map的 insert, 是根据 key来进行判断的: 如果 key形同, value不同, 就 不会覆盖

3. map的 insert, 几种传参方式:

   1. C++98
      1. 传一个pair对象
      2. 传一个pair的匿名对象
      3. 用 make_pair来创建一个pair对象
   2. C++11
      4. 支持多参数的隐式类型转换, 用 {}

4. map的迭代器也是 双向迭代器, 而不是随机迭代器. map虽然重载了[ ], 但跟我们平常的不大一样, 下面会讲的
   

[ ]运算符

一般的[ ] 是返回 存储对象的, 比如: vector 就返回 int, list 就返回 string;
但是 map中的 [ ], 不是返回 pair结构, 而是返回 pair结构中的 第二个元素的.

我们细看一下 [ ] 的不同:

[ ]的本质是 调用 insert, 通过 key 来返回 value:

1. 当key不存在时, 会插入该键的新元素, 并返回value的引用
2. 当key存在时, 会返回value的引用

⇒ [ ]有两大功能 插入 + 修改

[ ] 的本质是调用 insert, 但是有所不同

1. insert中, key相同, value不同的键值对是 不会覆盖的
2. [ ]中, 会返回value的引用, 所以能对value就行修改 ⇒ key相同, value不同的键值对是可以 覆盖的

void map_test1()
{
	map<string, string> m1;

	// C++98
	// 1. 传一个pair对象
	pair<string, string> kv1("insert", "插入");
	m1.insert(kv1);

	// 2. 传一个pair的匿名对象
	m1.insert(pair < string, string>("sort", "排序"));

	// 3. make_pair
	m1.insert(make_pair("love", "爱情"));

	// C++11
	// 4. 多参数的构造函数支持隐式类型转换, 用{}
	m1.insert({ "insert", "xxx" });

	for (auto e : m1)
	{
		cout << e.first  << "-> " << e.second << endl;
	}
	cout << endl;

	// 插入
	m1["muyu"];
	cout << "[]: 插入(muyu)" << endl;
	for (auto e : m1)
	{
		cout << e.first << "-> " << e.second << endl;
	}
	cout << endl;

	// 修改(覆盖)
	m1["insert"] = "xxx";
	cout << "[]: 修改(insert)" << endl;
	for (auto e : m1)
	{
		cout << e.first << "-> " << e.second << endl;
	}
	cout << endl;

	// 插入 + 修改
	m1["mutong"] = "沐潼";
	cout << "[]: 插入 + 修改()" << endl;
	for (auto e : m1)
	{
		cout << e.first << "-> " << e.second << endl;
	}
	cout << endl;
}

int main()
{

	map_test1();

	return 0;
}
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
48
49
50
51
52
53
54
55
56
57
58
59
60

运行结果:

insert-> 插入
love-> 爱情
sort-> 排序

[]: 插入(muyu)
insert-> 插入
love-> 爱情
muyu->
sort-> 排序

[]: 修改(insert)
insert-> xxx
love-> 爱情
muyu->
sort-> 排序

[]: 插入 + 修改(<mutong, 沐潼>)
insert-> xxx
love-> 爱情
mutong-> 沐潼
muyu->
sort-> 排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在这里, 我们可以 简化之前写的统计次数👇👇👇

int main()
{
	map<string, int> count;
	string arr[] = {"苹果", "桃子", "土豆", "苹果", "栗子", "桃子"};
	for (auto e : arr)
	{
		// 直接改变 e 所对应的value值
		count[e]++;
	}

	for (auto e : count)
	{
		cout << e.first << "-> " << e.second << endl;
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果:

栗子-> 3
苹果-> 1
苹果-> 2
土豆-> 4
1
2
3
4

map的其他迭代器诸如 find, erase, count, lower_bound, upper_bound, equal_range ; 用法都和 set的用法都差不多的, 在这里, 我们就不过多介绍了!

multiset && multimap

multiset 和 multimap都允许 key冗余

void multi_test()
{
	multiset<int> ms;
	ms.insert(1);
	ms.insert(1);
	ms.insert(5);
	ms.insert(2);
	cout << "multiset " << endl;
	for (auto e : ms)
	{
		cout << e << " ";
	}
	cout << endl << endl;

	multimap<string, int> mm;
	mm.insert({ "苹果", 1 });
	mm.insert({ "苹果", 2 });
	mm.insert({ "栗子", 3 });
	mm.insert({ "土豆", 4 });
	cout << "multimap " << endl;
	for (auto e : mm)
	{
		cout << e.first << "-> " << e.second << endl;
	}
	cout << endl;

}

int main()
{
	multi_test();

	return 0;
}
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

运行结果:

multiset
1 1 2 5

multimap
栗子-> 3
苹果-> 1
苹果-> 2
土豆-> 4
1
2
3
4
5
6
7
8

multiset 和 multimap 的其它接口的用法 都是和 set 和 map 都是大致一样的

---

望门投止思张俭，忍死须臾待杜根；
我自横刀向天笑，去留肝胆两昆仑。
— — 谭嗣同《狱中题壁》