【C++】map和set的使用

目录

1. 内容补充

1.1. 序列式容器与关联式容器

1.2. 键值对

1.3. 树形结构的关联式容器

2. set的使用

2.1. set的介绍

2.2. set的使用

2.3. multiset的介绍

2.4. multiset的使用

3.map的使用

3.1. map的介绍

3.2. map的使用

3.3. multimap的介绍

3.4. multimap的使用

---

1. 内容补充 1.1. 序列式容器与关联式容器

我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身，其元素与元素之间并没有什么关联性。

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据查找时比序列式容器效率更高 。

1.2. 键值对

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

其在SGI版本中的定义为：

template 
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
	T1 first;
	T2 second;
	pair(): first(T1()), second(T2())
	{}
	pair(const T1& a, const T2& b): first(a), second(b)
	{}
};

1.3. 树形结构的关联式容器

根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

2. set的使用 2.1. set的介绍

set 的特点：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。

2. set中插入元素时，只需要插入value即可，不需要构造键值对。

3. set中的元素不可以重复(因此可以使用set进行去重)。

4. 使用set的迭代器遍历set中的元素，可以得到有序序列

5. set中的元素默认按照小于来比较

6. set中查找某个元素，时间复杂度为：log n

7. set中的元素不允许修改

8. set中的底层使用二叉搜索树(红黑树)来实现

2.2. set的使用

Compare：仿函数，set中元素的比较方式。

构造函数：

插入：  

insert 重载了三种插入方法，值、迭代器位置、迭代器区间，这里演示最常用的值插入。  

#include
#include
using namespace std;


void test_set()
{
	set myset;
	myset.insert(10);
	myset.insert(3);
	myset.insert(7);
	myset.insert(1);
	myset.insert(5);
	myset.insert(5); // 插入重复元素，会插入失败

	set::iterator it = myset.begin(); 
	while (it != myset.end()) // 迭代器遍历：中序
	{
		cout << *it << " ";
		++it;
	}

}

通过上面的结果，其实set的功能也就体现出来了，就是 排序+去重。后面刷题中回很常用。

删除：

erase 也重载了三种方法：

删除迭代器(必须要求迭代器有效,一般配合find使用)、

删除值(有这个值就删除，没有也不会报错，底层其实就是封装了迭代器删除的过程，返回值为删除元素个数)、

删除迭代器区间。

#include
#include
using namespace std;


void test_set()
{
	set myset;
	myset.insert(10);
	myset.insert(3);
	myset.insert(7);
	myset.insert(1);
	myset.insert(5);
	myset.insert(5);

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

	// 通过迭代器删除3
	set::iterator pos = myset.find(3);
	if (pos != myset.end())
	{
		myset.erase(pos);
	}
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	// 通过值删除10
	myset.erase(10);
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
}

2.3. multiset的介绍

multiset 的特点：

1. multiset中在底层中存储的是的键值对

2. mtltiset的插入接口中只需要插入即可

3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的

4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列

5. multiset中的元素不能修改

6. 在multiset中找某个元素，时间复杂度为: log n

7. multiset的作用：可以对元素进行排序

2.4. multiset的使用

multiset的使用与set几乎一摸一样，唯一不同就是multiset中允许插入重复值。

void test_multiset()
{
	multiset myset;
	myset.insert(1);
	myset.insert(1);
	myset.insert(5);
	myset.insert(5);
	myset.insert(5);
	myset.insert(5);
	myset.insert(3);
	myset.insert(2);

	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;

	multiset::iterator pos = myset.find(1); // 当find的val有多个值时，返回中序第一个val值所在节点的迭代器
	if (pos != myset.end())
	{
		myset.erase(pos);
	}

	int n = myset.erase(5); // 删除所有的5,并返回删除个数
	cout << n << endl;
	for (auto e : myset)
	{
		cout << e << " ";
	}
	cout << endl;
}

3.map的使用 3.1. map的介绍

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。

6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))

7. map不支持修改Key，支持修改Value。

3.2. map的使用

key: 键值对中key的类型

T： 键值对中value的类型

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

map 在使用使用上的最大区别就是多了一个模板参数V(文档中给的是T)，且使用时是将KV两个模板参数封装在了pair里面。

pair的第一个参数(first)是K，第二个参数(second)是V。

插入：

value_type：键值对，可以通过pair本身提供的构造函数初始化。  

pair键值对也可以通过make_pair函数构造，一般常用这种方法。(make_pair：其实是对pair匿名构造的封装，并且可以自动推导类型)

void test_map()
{
	map m;
	pairkv1("left", "左");
	m.insert(kv1);
	m.insert(pair("right", "右")); // 匿名对象构造
	m.insert(make_pair("one", "1"));
	m.insert(make_pair("two", "2"));
	m.insert(make_pair("three", "3"));
	for (auto& e : m)
	{
		cout << e.first << ":" << e.second << endl; // 不能直接打印pair键值对，分开打印
	}
}

删除：

可以通过某个位置的迭代器删除，也可以通过pair中first删除，也可以通过迭代器区间删除。

void test_map()
{
	map m;
	pairkv1("left", "左");
	m.insert(kv1);
	m.insert(pair("right", "右")); // 匿名对象构造
	m.insert(make_pair("one", "1"));
	m.insert(make_pair("two", "2"));
	m.insert(make_pair("three", "3"));
	map::iterator it = m.find("one");
	if (it != m.end())
	{
		m.erase(it);
	}
	m.erase("two");
	for (auto& e : m)
	{
		cout << e.first << ":" << e.second << endl; // 不能直接打印pair键值对 
	}
}

(★)operator[ ]:

map的pair不仅可以实现字典，也可以实现对Key的计数：

void test_map()
{
	map CountMap;
	string str[] = { "left","left","right","right","test","up","down","right" };
	for (auto& s : str)
	{
		auto pos = CountMap.find(s); // 在map中查找是否存在当前字符串
		if (pos == CountMap.end()) // 不存在则插入，个数为1
		{
			CountMap.insert(make_pair(s, 1));
		}
		else
		{
			pos->second++; // 存在则将个数+1即可，不需要再插入
		}
	}

	for (auto& e : CountMap)
	{
		cout << e.first << ":" << e.second << endl;
	}

}

但是，通过上面这种方式插入会对map中不存在的字符串查找两次，第一次是find查找时会查找是否存在，第二次insert插入时对字符串插入的位置查找。

所以就有了对key插入的优化：insert对key的插入时返回值是pair，不是单纯的true或者false。

如果插入成功pair的first会被设置为插入位置的迭代器，second为true；如果插入失败pair的first是已经存在key位置的迭代器，second为false。

 谷歌翻译(doge):

优化版本：  

void test_map()
{
	map CountMap;
	string str[] = { "left","left","right","right","test","up","down","right" };
	for (auto& s : str)
	{
		auto kv = CountMap.insert(make_pair(s, 1)); // 不管map中存不存在该key，直接插入
		if (kv.second == false)
		{
			kv.first->second++; // 如果插入失败，说明map中已经存在key，将value++即可
		}						// kv的first是iterator，而iterator中也是pair
	}

	for (auto& e : CountMap)
	{
		cout << e.first << ":" << e.second << endl; // 不能直接打印pair键值对 
	}

}

你以为这就是最简单的方式？其实不是，map中还提供了更简单的计数方式，原理还是上面这种方式，只是进行了封装。

operator[ ]: 支持对key位置的value直接访问

这个实现看着确实有点打脑壳，其实他这个写的有点麻烦，可以简化一下：

mapped_type& operator[] (const key_type& k) // 注意：返回value的引用，可以直接改变节点的value
{
    // return (*((this->insert(make_pair(k, mapped_type()))).first)).second;
    pair::iterator, bool> kv = insert(make_pair(k, mapped_type())); // 调用insert，make_pair内部value使用的是该类型的匿名对象
    map::iterator it = kv.first; // 取到迭代器
    return it->second; // 返回value
}

所以operator[ ]具有以下功能：

1. 插入

2. 查找

3. 修改

代码为：

void test_map()
{
	map CountMap;
	string str[] = { "left","left","right","right","test","up","down","right" };
	for (auto& s : str)
	{
		CountMap[s]++; // 将value++
	}
	// 如果string第一出现：插入+修改
    // 如果string已经存在：查找+修改
    
	for (auto& e : CountMap)
	{
		cout << e.first << ":" << e.second << endl;
	}

}

void test_map1()
{
	map dict;
	dict.insert(make_pair("up", "上"));
	dict.insert(make_pair("down", "下"));
	dict.insert(make_pair("left", "左"));
	dict.insert(make_pair("right", "右"));

	dict["left"] = "剩余"; // 修改
	dict["test"]; // 插入
	for (auto& e : dict)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

所以对于使用operator[ ] 用于单纯的查找可能是有问题的，因为如果map内不存在查找的key，会将该key插入。  

3.3. multimap的介绍

其特性与map基本一致，只是multimap中可以允许存在重复的key值

3.4. multimap的使用

multimap 不支持operator[ ]，允许插入重复key值。

如果查找的key值有多个，找到的是中序遍历的第一个key。

void test_multimap()
{
	multimap dict;

	dict.insert(make_pair("up", "上"));
	dict.insert(make_pair("down", "下"));
	dict.insert(make_pair("left", "左"));
	dict.insert(make_pair("right", "右1"));
	dict.insert(make_pair("right", "右2"));
	dict.insert(make_pair("left", "剩余"));
	dict.insert(make_pair("left", "剩余"));

	cout << dict.find("left")->second << endl;
	cout << dict.find("right")->second << endl;
    cout << dict.count("left") << endl; // count: 查找key值出现的次数
}                                       // map中也有但不常用