• set和map的使用

    文章目录

    1. set的使用

    set是Key模型的二叉搜索树，它不仅能排序还能去重，底层实际上是用红黑树实现的。

    注意:set的普通迭代器和const迭代器都不支持对Key的修改。

    因为源码用的都是const_iterator。

    1.1 插入

    void test_set1()
{
	set s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);


	// 排序 + 去重 
	set::iterator it = s.begin();
	while (it != s.end())
	{
		//*it = 10;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : s)
	{
		cout << e << " ";
	}
	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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    image-20220730181742140

    1.2 查找

    erase得配合find使用。find如果没找到会返回end。set.find是按照二叉搜索树的性质来查找，时间复杂度是O(1)。而算法库里的find是暴力查找，时间复杂度是O(n)。

    void test_set2()
{
	set s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);

	set::iterator pos = s.find(20);  // O(logN)
	if (pos != s.end())
	{
		cout << "set.find找到了" << endl;
	}

	pos = find(s.begin(), s.end(), 2); // O(N)
	if (pos != s.end())
	{
		cout << "find找到了" << endl;
	}
}

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

    image-20220730183037852

    1.3 删除

    eras是从集合容器中移除单个元素或一组元素[first,last)。

    如果没有找到pos就删除会出问题。所以删除时要加条件判断。而如果是直接用一个值去删除比如s.erase(3)，编译器会自己去调用find，如果在就删除(返回删除的个数)，不在就不会做任何事情(删除失败返回0)。

    void test_set3()
{
	set s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);

	cout << s.erase(3) << endl;
	cout << s.erase(30) << endl;

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

	set::iterator pos = s.find(3);
	if (pos != s.end())
		s.erase(pos);

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

	/*int x;
	while (cin >> x)
	{
		set::iterator pos = s.find(x);
		if (pos != s.end())
		{
			s.erase(pos);
			cout << "删除" << x << "成功" << endl;
		}
		else
		{
			cout << x << "不在set中" << endl;
		}

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;
	}*/

    // count在容器中搜索与val相等的元素，并返回匹配的数量。 
    // count是为了支持multiset版本的set
    // 对于普通set而言，因为集合容器中的所有元素都是唯一的，所以函数只能返回1(如果找到了元素)或0(否则)。
	if (s.count(5))
	{
		cout << "5在" << endl;
	}

	if (s.find(5) != s.end())
	{
		cout << "5在" << endl;
	}
}

    • 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
    • 61
    • 62
    • 63
    • 64
    • 65

    image-20220730184336678

    1.4 lower_bound

    void test_set4()
{
	set s;
	s.insert(4);
	s.insert(5);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(7);
	s.insert(9);

	// 返回>= val得位置迭代器  3返回3位置  6 返回7位置
	/*set::iterator lowIt = s.lower_bound(3); 存在
	lowIt = s.lower_bound(6); 不存在*/
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 要求删除>=x的所有值
	int x;
	cin >> x;
	set::iterator lowIt = s.lower_bound(x);
	s.erase(lowIt, s.end());

	for (auto e : s)
	{
		cout << e << " ";
	}
	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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    image-20220730185234632

    1.5 upper_bound

    因为erase从集合容器中移除单个元素或一组元素([first,last)])。

    void test_set5()
{
	set s;
	s.insert(4);
	s.insert(5);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(7);
	s.insert(9);

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

	// 返回>x位置的迭代器  -》 都是返回 7位置的迭代器
	//set::iterator upIt = s.upper_bound(5);  // 存在
	//upIt = s.upper_bound(6); // 不存在

	// 删除x <=  <= y的区间 删除 [x,y]
    // 因为erase的区间是[first,last)
    int x, y;
	cin >> x >> y;
	auto leftIt = s.lower_bound(x);  // [
	auto rightIt = s.upper_bound(y); // )
    // 输入3 7区间为[3,9)包含[3,7]
	s.erase(leftIt, rightIt);
	for (auto e : s)
	{
		cout << e << " ";
	}
	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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    image-20220730191122507

    1.6 multiset

    multiset用法和set一样，唯一不同是允许键值冗余。排序不去重。

    这里count的作用就体现出来了。

    void test_set6()
{
	multiset s;
	s.insert(4);
	s.insert(5);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(3);
	s.insert(3);
	s.insert(3);
	s.insert(3);

	// 排序 
	set::iterator it = s.begin();
	while (it != s.end())
	{
		//*it = 10;
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

	cout << s.count(1) << endl;
	cout << s.erase(1) << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	// 多个x的话，find返回中序第一个x
	auto pos = s.find(3);
	while (pos != s.end())
	{
		cout << *pos << " ";
		++pos;
	}
	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
    • 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

    image-20220730194725519

    2. 两个数组的交集

    349. 两个数组的交集

    image-20220730200352456

    image-20220730200326185

    3. map的使用

    map是KV模型的二叉搜索树。

    3.1 插入及其遍历

    插入的是一个键值对，返回的也是一个键值对，iterator就是指向value_type的指针。

    image-20220730201939998

    void test_map1()
{
	map dict;

	// pair构造函数
	dict.insert(pair("sort", "排序"));
	pair kv("insert", "插入");
	dict.insert(kv);

	// make_pair函数模板自动推导类型
	dict.insert(make_pair("left","左边"));

	// C++11 再讲
	//dict.insert({ "right", "右边" });

	// 遍历
	//map::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//cout << *it << " "; // it->operator*()
		//cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

	for (const auto& kv : dict)
	{
		cout << kv.first << ":" << kv.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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    image-20220730202818540

    3.2 统计水果出现次数

    void test_map2()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

	/*map countMap;
	for (auto& str : arr)
	{
		map::iterator it = countMap.find(str);
		if (it != countMap.end())
		{
			it->second++;
		}
		else
		{
			countMap.insert(make_pair(str, 1));
		}
	}*/

	//map countMap;
	//for (auto& str : arr)
	//{
	//	//pair::iterator, bool> ret = countMap.insert(make_pair(str, 1));
	//	auto ret = countMap.insert(make_pair(str, 1));
	//	if (ret.second == false)
	//	{
	//		ret.first->second++;
	//	}
	//}

	map countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}

	for (const auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.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
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    insert单元素版本(1)返回一个元素对pair，pair::first被设置为一个迭代器，指向新插入的元素或映射中具有相同键值的元素。 如果插入了新元素，则pair::second设置为true;如果已经存在等价的键，则设置为false。

    image-20220730204112634

    3.3 operator[]

    image-20220730205801212

    image-20220730210502869

    multimap不支持operator[]，因为一个key对应多个value。

    3. 前k个高频单词

    692. 前K个高频单词

    image-20220801091018560

    class Solution {
public:
    typedef map::iterator CountIter;
    struct IterCompare
    {
        bool operator()(CountIter it1, CountIter it2)
        {
            return it1->second > it2->second;
        }
    };
    
    vector topKFrequent(vector& words, int k) {
        //按key排好序且统计对应的出现次数
		map countMap;
        for(auto& str : words)
        {
            countMap[str]++;
        }
        
        //将map数据节点的迭代器放入vector
        vector v;
        CountIter it = countMap.begin();
        while(it != countMap.end())
        {
            v.push_back(it);
            ++it;
        }
        //因为stable_sort只支持随机迭代器且是稳定的排序
        //按出现次数排序，如果次数相同按照字典序排序
        stable_sort(v.begin(), v.end(), IterCompare());
        
        //录入排序好的结果--单词
        vector ret;
        for(size_t i = 0; i < k; ++i)
        {
            ret.push_back(v[i]->first);
        }
        
        return ret;
    }
};

    • 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

    第二种方法：

    class Solution {
public:    
    vector topKFrequent(vector& words, int k) {
        //按key排好序且统计对应的出现次数
		map countMap;
        for(auto& str : words)
        {
            countMap[str]++;
        }
        
        //再用multimap按出现次数排序,排降序
        //multimap遇到相等的值会插入到右边
        multimap> sortMap;
        for(auto& kv : countMap)
        {
            sortMap.insert(make_pair(kv.second, kv.first));
        }
        
        //录入排序好的结果--单词
        vector ret;
        auto it = sortMap.begin();
        for(size_t i = 0; i < k; ++i)
        {
            ret.push_back(it->second);
            ++it;
        }
        
        return ret;
    }
};


    //再用multimap按出现次数排序,排降序
        //multimap遇到相等的值会插入到右边
        multimap> sortMap;
        for(auto& kv : countMap)
        {
            sortMap.insert(make_pair(kv.second, kv.first));
        }
        
        //录入排序好的结果--单词
        vector ret;
        auto it = sortMap.begin();
        for(size_t i = 0; i < k; ++i)
        {
            ret.push_back(it->second);
            ++it;
        }
        
        return ret;
    }
};

    • 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
  • 相关阅读:
    Android ANR 日志分析定位
    Python selenium模块的常用方法【更新中】
    记录一次 vue2 前端项目整合过程
    解决 sh 和 bash 在执行脚本时的差异：双括号问题
    Linux UWB Stack实现——MCPS调度接口（数据结构）
    2022年IC行业还缺人吗?
    Cheat Engine 修改器获取内存数据心路历程， THREADSTACK0 C# .NET VB 获取基址 CE修改器
    前端项目--尚医通学习分享
    用闪电侠的例子解释一下进程和线程
    牛客多校11 - Jellyfish and its dream（差分，思维）
  • 原文地址：https://blog.csdn.net/iwkxi/article/details/126403120