【map与set】—— 我与C++的不解之缘（二十二）

前言

在前面的学习中，已经接触过了string、vector、list、stack、queue等容器，现在了解set与map容器的使用

本篇只来了解set和map的使用；（其底层为红黑树，在后面再详细学习）

序列式容器与关联式容器

​ 在之前学习到的string、vector、list、deque等容器，这些容器统称为序列式容器，因为其逻辑结构为线性序列的数据结构，两个存储的数据之间没有必要的联系；（比如交换一下，仍然是序列式容器；在访问时都通过数据的存储位置来顺序存储和访问）

而关联式容器虽然也是来存储数据的，但与序列式容器不同的是，关联式容器的逻辑结构是非线性的；两个位置存储的值之间有着必要的联系，如果交换一个，其存储结构就被破坏了。

关联式容器主要有set/map系列、unordered_map/unordered_set系列。

set是key搜索场景的结构、而map是key/value搜索场景的结构。

set的使用

set是一个key搜索场景的结构；set是不支持数据冗余的（主要讲解set），multiset支持数据冗余。

1.set的构造函数

对于set的构造函数，有三个（分别是默认构造、迭代器区间构造和拷贝构造）

void test_set1()
{
	//默认构造
	set<int> st1;
	//迭代器区间构造
	int arr[] = { 11,7,5,9,15,17,19,11 };
	set<int> st2(arr, arr + sizeof(arr) / sizeof(arr[0]));
	//拷贝构造
	set<int> st3 = st2;
}

2.set的遍历

对于set的遍历，就是使用迭代器来遍历（这里set的迭代器遍历是中序遍历，因为中序遍历搜索二叉树的有序的）。

支持迭代器就支持范围for

void test_set2()
{
	int arr[] = { 11,7,5,9,15,17,19,11 };
	set<int> st(arr, arr + sizeof(arr) / sizeof(arr[0]));
	//迭代器遍历
	set<int>::iterator it = st.begin();
	while (it != st.end())
	{
		cout << *it << ' ';
		++it;
	}
	cout << endl;
	//范围for
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
}

输出结果

5 7 9 11 15 17 19
5 7 9 11 15 17 19

3.set的增删查

这里首先声明，set当中是不支持数据修改的，修改可能会破坏其存储结构

插入insert

可以看到，在set在不支持push和pop这些插入删除了，而是insert插入。

insert支持三种（这里主要就看第一和第三种）

• 插入单个数据，如果数据存在就插入失败（返回值是pair类型，如果插入成功返回该位置的迭代器和true；插入失败就返回false
• 插入一段迭代器区间，（已经存在的值不会进行插入）。

查找find

查找val值，如果存在就返回该位置迭代器，如果不存在就返回end();

删除erase

这里删除也是支持三种：

• 删除一个迭代器位置的值
• 删除值val
• 删除一段区间

void test_set3()
{
	set<int> st;
	//插入一个值
	st.insert(9);
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
	//插入一段迭代器区间
	vector<int> v = { 1,3,5,7,9,11,13,15,17,19 };
	st.insert(v.begin(), v.end());
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
	//查找
	auto f = st.find(11);
	if (f != st.end())
	{
		//该值存在，删除这个位置
		st.erase(f);
	}
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;

	//删除一段区间的值
	set<int>::iterator beg = st.begin();
	set<int>::iterator en = beg;
	++en;
	++en;
	st.erase(beg, en);//这里就删除中序前两个位置
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
}

输出结果

9
1 3 5 7 9 11 13 15 17 19
1 3 5 7 9 13 15 17 19
5 7 9 13 15 17 19

4.set其他操作

其他操作主要就是，size返回元素个数、count返回元素出现的次数、empty判断是否为空等操作

count统计个数

count返回元素出现的个数，在set无非就是0或者1；在multiset中返回其出现的次数。

这里还可以利用count来判断数据是否存在（返回1就是存在，0就是不存在）。

set中还存在新的接口

• lower_bound：返回大于等于key的位置的迭代器。
• upper_bound：返回小于key位置的迭代器。

void test_set4()
{
	int arr[] = { 11,7,5,9,15,17,19,11 };
	set<int> st(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "数据个数 : " << st.size() << endl;
	if (st.empty())
	{
		cout << "为空" << endl;
	}
	cout << "3 出现的次数 : " << st.count(3) << endl;
	cout << "11 出现的次数 : " << st.count(11) << endl;

	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
	auto bg = st.lower_bound(7);
	auto ed = st.upper_bound(15);
	cout << *bg << ' ' << *ed << endl;
	st.erase(bg, ed);
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
}

输出结果

数据个数 : 7
3 出现的次数 : 0
11 出现的次数 : 1
5 7 9 11 15 17 19
7 17
5 17 19

5.set和multiset的区别

set和multiset的主要区别就是，set不支持数据冗余，而multiset支持数据冗余

而insert、find、erase和count都略有差别

void test_set5()
{
	//multiset支持数据结冗余
	multiset<int> st = { 11,7,15,9,15,17,19,11,11 };
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
	//multiset可以插入条件存在的元素
	st.insert(7);
	//find，如果存在多个查找的是中序的第一个
	auto i = st.find(11);
	//把所以的11都输出
	while (i != st.end() && *i == 11)
	{
		cout << *i << ' ';
		++i;
	}
	cout << endl;
	//count会返回其出现的次数
	cout << "11 的个数 : " << st.count(11) << endl;

	//multiset 的erase会删除所有的val值
	st.erase(11);
	for (auto e : st)
	{
		cout << e << ' ';
	}
	cout << endl;
}

输出结果

7 9 11 11 11 15 15 17 19
11 11 11
11 的个数 : 3
7 7 9 15 15 17 19

6.set使用场景

这里分享两个题，使用set来解决慧方便很多

349. 两个数组的交集 - 力扣（LeetCode）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> st1(nums1.begin(),nums1.end());
        set<int> st2(nums2.begin(),nums2.end());
        vector<int> ret;
        auto it1 = st1.begin();
        auto it2 = st2.begin();
        while(it1 !=st1.end() && it2!= st2.end())
        {
            if(*it1 < *it2)
            {
                ++it1;
            }
            else if(*it1 > *it2)
            {
                ++it2;
            }
            else
            {
                ret.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return ret;
    }
};

142. 环形链表 II - 力扣（LeetCode）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* cur = head;
        set<ListNode*> st;
        while(cur)
        {
            auto ret = st.insert(cur);
            if(ret.second == false)
                return cur;
            cur = cur->next;
        }
        return nullptr;
    }
};

还依稀记得之前使用C语言写了多少行代码，这里就简单了不少。

map的使用

在了解map之前呢，我们先来看pair；pair是什么呢？

我们知道map是一个key/value结构，但key和value是直接存储到map对象当中的吗？

不是，key/value 封装成了一个pair<key,value>对象，然后map中包含了pair对象，从而到达key/value结构。

这里我们可以验证一下：通过断点，监视窗口查看map对象中数据

void test_map0()
{
	map<string, int> mp;
	mp.insert({ "one", 1 });
	mp.insert({ "two", 2 });
	mp.insert({ "three", 3 });
	mp.insert({ "four", 4 });
	mp.insert({ "five", 5 });
	mp.insert({ "six", 6 });


}

这里我们可以看到，map对象中存储的key/value数据被封装起来，并且对应first和second。

说这么多，那pair到底是个啥？

简单来说，pair将key/value两个不同（或者相同）类型的数据耦合到了一起；我们可以通过访问pair的公共成员first和second来访问key和value。

此外，pair还实现了多种运算符重载：

map就是以pair<key, value>来存储数据的。

1.map的构造函数

map的构造函数与set一样，有三种

• 默认构造函数
• 迭代器区间构造
• 拷贝构造

void test_map1()
{
	//默认构造
	map<string, int> mp1;
	//迭代器区间构造
	vector<pair<string, int>> v = { {"one",1},{"two",2},{"three",3},{"four",4},{"five",5} };
	map<string, int> mp2(v.begin(), v.end());
	//拷贝构造
	map<string, int> mp3 = mp2;
}

2.map的遍历

map遍历也与set相似，都是按照二叉树的中序遍历。

void test_map2()
{
	//vector<pair<string, int>> v = { {"one",1},{"two",2},{"three",3},{"four",4},{"five",5} };
	vector<pair<int, string>> v = { {1,"one"},{2,"two"},{3,"three"},{4,"four"},{5,"five"} };
	map<int, string> mp(v.begin(), v.end());

	map<int, string>::iterator it = mp.begin();
	while (it != mp.end())
	{
		cout << (*it).first << " : " << (*it).second << endl;
		++it;
	}
	cout << endl;
	for (auto e : mp)
	{
		cout << e.first << " : " << e.second << endl;
	}
	cout << endl;
}

这里要注意：

在pair中，first对应的是key，所有我们要将key的数据类型放到前面，数据也是。

3.map的增删查

map支持增删查，其value支持修改，但是key不支持。

插入insert

与set类似，insert可以插入值，或者迭代器区间。

查找find

查找一个值**（这里是根据key值查找）**，如果存在返回去位置的迭代器，如果不存在返回end()。

删除erase

与set类似，根据值删除、根据迭代器删除、删除一段区间。

void test_map3()
{
	//插入一个数据
	map<int, string> mp;
	mp.insert({ 6, "six" });
	for (auto e : mp)
	{
		cout << e.first << " : " << e.second << endl;
	}
	cout << endl;
	//插入一段迭代器区间
	vector<pair<int, string>> v = { {1,"one"},{2,"two"},{3,"three"},{4,"four"},{5,"five"} };
	mp.insert(v.begin(), v.end());
	for (auto e : mp)
	{
		cout << e.first << " : " << e.second << endl;
	}
	cout << endl;

	//查找
	auto fd = mp.find(3);
	cout << (*fd).first << " : " << (*fd).second << endl;

	mp.erase(fd);//删除一个迭代器位置的值
	size_t sz = mp.erase(7);//要删除的值不存在就返回0
	cout << sz << endl;

}

4.map的其他操作

主要还是：size返回元素个数、count返回元素出现的次数、empty判断是否为空等操作

count统计个数

注意：map中是根据key来查找的。

count返回元素出现的个数，在map无非就是0或者1；在multimap中返回其出现的次数。

这里还可以利用count来判断数据是否存在（返回1就是存在，0就是不存在）。

map中也存在lower_bound和upper_bound接口

void test_map4()
{
	vector<pair<int, string>> v = { {1,"one"},{2,"two"},{3,"three"},{4,"four"},{5,"five"}, {6,"six"} };
	map<int, string> mp(v.begin(), v.end());
	cout << "数据个数：" << mp.size() << endl;
	if (mp.empty())
		cout << "为空" << endl;
	cout << "3 的个数 : " << mp.count(3) << endl;

	for (auto e : mp)
	{
		cout << e.first << " : " << e.second << endl;
	}
	auto bg = mp.lower_bound(3);
	auto ed = mp.upper_bound(5);
	cout << (*bg).first << ' ' << (*ed).first << endl;
	mp.erase(bg, ed);
	for (auto e : mp)
	{
		cout << e.first << " : " << e.second << endl;
	}
}

5.operator[]

对于这个[]运算符重载，set是不支持的；map支持，并且使用起来也非常方便

• 数据不存在：如果使用[]访问的数据不存在，就会直接插入并且返回新插入位置的value的引用。
• 数据存在：如果[]访问数据存在，就返回该数据位置value的引用。

这样我们也可以使用[]来插入数据，并且还可以修改数据的value值。

void test_map5()
{
	vector<pair<int, string>> v = { {1,"one"},{2,"two"},{3,"three"},{4,"four"},{5,"five"} };
	map<int, string> mp(v.begin(), v.end());
	
	mp[6];//不存在就插入
	mp[3] += "hello";
	for (auto e : mp)
	{
		cout << e.first << " : " << e.second << endl;
	}
}

6.map和multimap的区别

map和multimap的主要区别就是，map不支持数据冗余，而multimap支持数据冗余

而insert、find、erase和count都略有差别

还有就是multimap不支持[]。

7.map使用场景

这里还是一样，看在题目当中map的使用

138. 随机链表的复制 - 力扣（LeetCode）

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* cur = head;
        map<Node*,Node*> mp;
        Node* copyhead = nullptr;
        Node* copytail = copyhead;
        while(cur!=nullptr)
        {
            if(copyhead==nullptr)
            {
                copytail = copyhead = new Node(cur->val);
            }
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            mp.insert({cur,copytail});
            cur = cur->next;
        }
        
        cur = head;
        Node* tail = copyhead;
        while(cur)
        {
            if(cur->random ==nullptr)
            {
                tail->random = nullptr;
            }
            else
            {
                tail->random = mp[cur->random];
            }
            cur = cur->next;
            tail = tail->next;
        }
        return copyhead;
    }
};

到这里map和set的了解就结束了，继续加油！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws