map和set

正文开始前给大家推荐个网站，前些天发现了一个巨牛的 人工智能学习网站， 通俗易懂，风趣幽默，忍不住分享一下给大家。 点击跳转到网站。

关联式容器

我们前面接触的vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

什么是键值对？

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

pair

pair就是C++内置的一个键值对。


first就是Key，second就是value。

我们看那一下pair的构造函数。

它的第二个构造函数就保证了它只要first之间是可以相互赋值就就可以，因为它的构造函数又套了一个模板参数，所以如果u，v和T1，T2相等就是拷贝构造函数，如果不相等就是构造函数，所以它既是拷贝构造也是构造。

我们可以看到pair和pair 不是同一个类型，理论上是不可以相互赋值的，正是因为有了这个模板的存在，只要first和second可以相互赋值，不同类型pair就可以相互赋值。

但是我们一般不直接写pair来构造pair，我们都用make_pair.

make_pair

make_pair可以根据我们传递的类型帮我们返回一个对应的pair。

树形结构的关联式容器

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

set

1. set是按照一定次序存储元素的容器。
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

插入

我们可以看到这里的插入是一个val_type，val_type是什么呢？

我们可以看到val_type就是T。

void func()
{
	set<int> s;
	s.insert(6);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	s.insert(0);
	set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们可以看到insert的返回值是一个pair，pair的first是这个位置的迭代器，second是是否插入成功。

删除

删除可以删除一个迭代器的位置，也可以直接删除一个val_type,也可以直接删除一个迭代器区间。

void func1()
{
	set<int> s;
	s.insert(6);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	s.insert(0);

	s.erase(0);
	set<int>::iterator it = s.begin();
	s.erase(it);

	it = s.begin();

	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

查找

查找是返回这个值的迭代器。可以配合删除使用。如果找不到会返回end()的位置。

lower_bound和upper_bound

lower_bound会返回大于等于val的位置的迭代器，而upper_bound会返回大于val的位置迭代器。
这两个函数一般是配合使用的，我们可以通过这两个函数来遍历，某一段区间内的值，或者删除某一段区间的值。

void func2()
{
	set<int> s;
	for (size_t i = 0; i < 10; i++)
	{
		s.insert(i * 10);
	}
	set<int>::iterator it1, it2;
	it1 = s.lower_bound(30);
	it2 = s.upper_bound(60);
	while (it1 != it2)
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

equal_range

equal会返回该val位置的迭代器，和大于该val的迭代器。并且把他们放到一个pair中，first是val的位置的迭代器，second是大于val位置的迭代器。

void func3()
{
	set<int> s;
	for (size_t i = 0; i < 10; i++)
	{
		s.insert(i * 10);
	}
	auto m = s.equal_range(20);
	
	cout << *m.first << endl; // 20
	cout << *m.second<<endl;  // 30
}
1
2
3
4
5
6
7
8
9
10
11
12

multiset

multiset和set一样，只不过multiset允许键值相同，而set是不允许键值相同的。只不过multiset在删除是，会把那个键值的所有值都删了，并不会只删除一个。

总结：

• set是排序加去重的
• multiset时进行排序，但是不会去重。

map

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

插入

map就是一个K,V模型，里面存的是pair，所以我们要插入就是要插入一个pair。

如果插入成功会返回那个位置的迭代器，如果那个值已经存在了，就会返回那个位置的迭代器，所以insert还充当的有find的功能。后面的[]重载也是主要有insert实现的。

void func()
{
	map<string, string> mymap;
	mymap.insert(make_pair("sort", "排序"));
	mymap.insert(make_pair("left", "左边"));
	mymap.insert(make_pair("right", "右边"));

	map<string, string>::iterator it = mymap.begin();
	while (it != mymap.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后删除什么的和set的用法都是一样的，只是map重载了[]运算符，我们主要说一下这个。

我们会看到insert就是调用了insert这个函数，那么为什么可以这样呢？

因为insert如果不存在就会插入成功并且返回该位置的迭代器，如果这个值已经存在，就会插入失败并且也会返回这个位置的迭代器，所以我们不用管是不是插入成功了，都能够得到这个位置的迭代器。

比如统计次数我们就可以这样写：

void func1()
{
	map<string, int> countMap;
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };

	for (auto e : arr)
	{
		countMap[e]++;
	}

	map<string, int>::iterator it = countMap.begin();
	while (it != countMap.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

multimap

multimap也是允许键值冗余，所以它就没办法重载[]。其他的和map都一样。

总结：

• map和set通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
• map和set都是会进行排序和去重的，只不过map排序的是Key值，而multiset和multimap是不会去重的。
• map是KV模型而set是K模型。
• 它们的接口大多相似，会用一个其他的类似就好了，唯一就是map重载了[]。

那么今天的分享就到这里了，有什么不懂得可以私信博主，或者添加博主的微信，欢迎交流。