C++ map&set的使用讲解

关联式容器和序列式容器

序列式容器的底层存储结构是线性的，例如：vector，list，string，容器存储的是数据本身。而关联式容器的底层结构不再是线性的，存储的数据为这样的键值对，在检索数据时效率比关联式容器高。

键值对

键值对是用来表示一种对应关系的结构，中的key表示键值，value表示与key对应的信息。

SGI-STL中对键值对的定义

template <class T1, class T2>
struct pair
{
	T1 first;
	T2 second;
	
	pair(): first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b): first(a), second(b)
	{}
};
1
2
3
4
5
6
7
8
9
10
11

键值对存储的两个对象类型可以不同，key对应first成员，value对应second成员。

树形结构的关联式容器

关联式容器有两种结构，树形结构和哈希结构，map，set，multimap，multiset的结构是关联式容器，关联式容器的底层结构是红黑树，存储的是一个有序序列。

set的使用

T：set存储的value值的类型
Compare：弱排序的方式，默认小于
Alloc：空间配置器，默认使用STL提供的

通过阅读文档，总结set的几个特点

1.set存储的value值不能重复，所以可以用set进行去重
2.set存储的value值不能修改，因为value被const修饰，修改value值可能会破坏树结构（但可以删除或插入节点）
3.set中的value以弱排序的顺序进行存储，set默认弱排序是小于
4.与map/multimap不同，set只存储value而不是的键值对，但set的底层是由这样的键值对实现，所以插入数据不用构造键值对
5.用set的迭代器遍历容器，得到的是有序数列
6.set查找某个元素的时间复杂度为O(logN)

set的其他使用看文档就行，与其他容器的接口类似，学习成本很低，需要补充的是：set很少使用find，find返回节点的迭代器，但set不能用来修改节点，所以使用find是用来查看这个数据在不在树中。set有个更好用的接口：count，count返回该数据在树中的个数，set的count只会返回0和1，使用起来比find简洁

if (s.find(3) != s.end()) // find不存在的数据，返回end迭代器
if (s.count(3)) // 相比较就简洁多了
1
2

还有这两个接口的使用



lower_bound()，比如set有1~9，9个数，lower_bound查找3，函数返回3的迭代器。但upper_bound返回4迭代器，不返回3，lower_bound是一个大于等于的意思，upper_bound是大于的意思

这两个接口常配合erase使用，erase可以删除一个左闭右开的区间，比如删除[3，6]区间的所有数，lower_bound找3，返回指向3的迭代器，upper_bound找6，返回指向7的迭代器，由于erase删除的区间是左闭右开的，7不会被删除，只会删除到7的前一个数。

这样的方式常用于不知道树中具体的数。

（补充一个找交集和差集的思路：先用set去重，分别用两个迭代器指向两个set的第一个数，比较两数，小的那个数属于集合的差集，然后将小数的迭代器++，大数不动，两数相等就是交集，然后两个迭代器++。这个思路也常用于数据同步。）

map的使用

前面说过map存储的是键值对，所以map插入数据时需要构造一个键值对。

map<int, string> m;
m.insert(make_pair(1, "hello"));
m.insert(pair<int, string>(6, "world));
1
2
3

两种构造方式，make_pair是调用函数


下面的方式是构造pair的匿名对象，调用函数的优势在于不用传模板参数，编译器自动推导。推荐用函数调用

另外map存储的pair不能直接调用cout输出，流输出没有重载pair对象，输出时要指定输出pair的first或者second对象。

统计字符串出现的次数

void test15()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> count;
	for (auto& str : arr)
	{
		auto it = count.find(str); // 在map中查找字符串
		if (it != count.end()) // map中有这个键值对
		{
			it->second++;
		}
		else
		{
			count.insert(make_pair(str, 1));
		}
	}

	for (auto e : count)
	{
		// 不能直接输出e
		cout << e.first << ':' << e.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

算法还能进行优化，map的insert不是返回void，而是返回pair对象

pair对象的first是迭代器，如果map中没有key对应的数据，迭代器指向这个数据在map应该在的位置，有这个数据，迭代器指向这个数据所在的位置

pair的second是一个bool值，如果数据已经存在，bool为false，数据不存在，bool为true

void test15()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> count;
	for (auto& str : arr)
	{
		// pair::iterator, bool> ret = count.insert(make_pair(str, 0);
		auto ret = count.insert(make_pair(str, 1));
		if (ret.second == false) // 有这个key值数据了
		{
			ret.first->second++;
		}
	}

	for (auto e : count)
	{
		// 不能直接输出e
		cout << e.first << ':' << e.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最后的优化：利用map重载的操作符[]

void test15()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> count;
	for (auto& str : arr)
	{
		count[str]++;
	}

	for (auto e : count)
	{
		// 不能直接输出e
		cout << e.first << ':' << e.second << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(*((this->insert(make_pair(k, mapped_type()))).first)).second

auto ret = insert(make_pair(k, mapped_type());
ret.first->second;
1
2
3
4

mapped_type其实是value类型的重定义，mapped_type()是调用该类型的默认构造函数。第一行代码的意思是根据key值构造一个键值对，key对应的value是默认的，然后将键值对插入。第二行是根据insert返回的pair的first得到迭代器，最后返回这个迭代器的second也就是valud（并且是引用），所以可以通过引用可以修改这个value值。

count[str]++的意思是，构造一个键值对，以str为key值，value是默认值，然后插入该键值对，刚开始map中没有这个节点，插入的是类似<"苹果”, 0>这样的键值对，然后[]返回的是value的引用，++将0改成1，苹果出现一次。

总结[]的用途，以上面的count为例子

count["梨子"] = 4; // 插入+修改 
count["苹果"] = 4; // 查找+修改
count["桃子"]; // 插入
cout << count["苹果"] << endl; // 查找
1
2
3
4