• C++ map和set的使用

    关联式容器
     

    vector、list、deque统称为序列式容器，因为其底层为线性序列的数据结构，存储的是元素本身
    侧重于单纯的存储数据

    关联式容器也是用来存储数据的，里面存储的是结构的键值对，在数据检索时比序列式容器效率更高
     

    键值对
     

    用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
    表键值，value表示与key对应的信息
    如英汉字典，英文单词与其中文含义是一一对应的关系，二者构成一个键值对，通过该单词就可找到与之对应的中文含义

    SGI-STL中关于键值对的定义：
     

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

    STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构

    树型结构的关联式容器主要有四种：map、set、multimap、multiset
     

    set
     

    set的介绍
     

    1 set是按照一定次序存储元素的容器
    2 在set中，value就是key，类型为T，并且每个value必须是唯一的
       set中的元素不能在容器中修改（元素被const修饰）

    3 set容器通过key访问单个元素的速度通常比unordered_set容器慢

    4 set在底层是用二叉搜索树(红黑树)实现的

    注意：
     

    1 与map/multimap不同，map/multimap中存储的是真正的键值对

       set中只放value，但在底层实际存放的是由构成的键值对

    2 set中的元素不可以重复(因此可以使用set进行去重)
    3 使用set的迭代器遍历set中的元素，可以得到有序序列

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

    下面介绍的set和map的使用仅为精简版，均为使用较多的

    set的使用：

    1 查找在不在

    2 排序+去重
     

    T: set中存放元素的类型，set中插入元素时，只需要插入value，但实际在底层存储的键值对
     Compare：set中元素默认按照小于来比较

    Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

    insert：

     返回值是pair：

    插入成功-> pair<新插入key所在节点的迭代器,true>

    插入失败-> pair<已存在的key/value所在节点的迭代器,false>

    erase：

     第一个版本的erase：（搭配find使用，需要进行判断）若不判断则给定无效的iterator会报错

                                                                                            给定正确的iterator会删除

     第二个版本的erase：无论要删除的key是否存在，均不报错，若存在就删除，不存在则无事发生

    find： 

     若是找到了，则返回此元素所在节点的迭代器，否则返回set::end()

    count:

    统计key的个数，对于set而言用处不大，因为在set里，key非0即1，可以用于判断key在不在 

    但对于multiset而言，count就有用武之地了，可以统计key的个数

    测试1：

    1. void test_set1()
    2. {
    3. 	//1 查找在不在
    4. 	//2 排序+去重
    5. 	set<int> s;
    6. 	s.insert(4);
    7. 	s.insert(3);
    8. 	s.insert(8);
    9. 	s.insert(2);
    10. 	s.insert(4);
    11. 	s.insert(5);
    12. 	pairint>::iterator,bool> ret = s.insert(2);
    13. 	cout << ret.second << endl;
    14.  
    15. 	auto ret2 = s.insert(8);
    16. 	cout << ret2.second << endl;
    17.  
    18. 	//迭代器遍历
    19. 	set<int>::iterator it = s.begin();
    20. 	while (it != s.end())
    21. 	{
    22.         //*it = 10；//不可以，set不允许key/value被修改
    23. 		cout << *it << " ";
    24. 		it++;
    25. 	}
    26. 	cout << endl;
    27.  
    28. 	//范围for
    29. 	for (auto e : s)
    30. 	{
    31. 		cout << e << " ";
    32. 	}
    33. 	cout << endl;
    34.  
    35. 	s.erase(2);//删除存在的
    36. 	for (auto e : s)
    37. 	{
    38. 		cout << e << " ";
    39. 	}
    40. 	cout << endl;
    41.  
    42. 	s.erase(11);//删除不存在的，无事发生
    43.  
    44. 	set<int>::iterator it2 = s.find(8);//删除存在的
    45. 	s.erase(it2);
    46. 	for (auto e : s)
    47. 	{
    48. 		cout << e << " ";
    49. 	}
    50. 	cout << endl;
    51.  
    52. 	//it2 = s.find(30);//删除不存在的
    53. 	//s.erase(it2); //报错，erase一个无效的迭代器程序会崩溃
    54.  
    55. 	//正确处理：
    56. 	it2 = s.find(30);
    57. 	if (it2 != s.end())
    58. 	{
    59. 		s.erase(it2);
    60. 	}
    61.  
    62. 	if (s.count(3))//可用于判断key是否存在
    63. 	{
    64. 		cout << "3存在" << endl;
    65. 	}
    66. 	else
    67. 	{
    68. 		cout << "3不存在" << endl;
    69. 	}
    70. }

    运行结果：

    lower_bound：

     

    返回>=val值位置的迭代器

     upper_bound:

    返回>val值位置的迭代器

    可能会用到：删除一段区间的值

     测试2：
    1. void test_set2()
    2. {
    3. 	set<int> myset;
    4. 	set<int>::iterator itlow, itup;
    5.  
    6. 	for (int i = 1; i < 10; i++) 
    7. 		myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
    8.  
    9. 	itlow = myset.lower_bound(30);  //返回key为30位置的迭代器           
    10. 	itup = myset.upper_bound(60);   //返回key为70位置的迭代器             
    11.  
    12. 	myset.erase(itlow, itup);//左闭右开区间[30,70)，删除[30,60]
    13. 	for (auto e : myset)
    14. 	{
    15. 		cout << e << " ";
    16. 	}
    17. 	cout << endl;
    18.  
    19. 	set<int> myset2(myset);
    20. 	set<int>::iterator itlow2, itup2;
    21.  
    22. 	for (int i = 1; i < 10; i++)
    23. 		myset2.insert(i * 10);// 10 20 30 40 50 60 70 80 90
    24.  
    25. 	itlow2 = myset2.lower_bound(25);
    26. 	itup2 = myset2.upper_bound(70);
    27. 	myset2.erase(itlow2, itup2);//左闭右开区间[30,80)，删除[30,60]
    28. 	for (auto e : myset2)
    29. 	{
    30. 		cout << e << " ";
    31. 	}
    32. 	cout << endl;
    33. }

    运行结果：

    equal_range： 

     测试3：
    1. void test_set3()
    2. {
    3. 	set<int> myset;
    4.  
    5. 	for (int i = 1; i <= 5; i++)
    6. 		myset.insert(i * 10); // myset: 10 20 30 40 50
    7.  
    8. 	//pair::iterator, set::iterator> ret = myset.equal_range(35);
    9. 	auto ret = myset.equal_range(35);
    10.  
    11. 	cout << "the lower bound points to: " << *ret.first << endl;   // >= val
    12. 	cout << "the upper bound points to: " << *ret.second << endl;  // > val
    13. }

    运行效果：

    multiset的使用：

     multiset的用法和set相似，同样也是key/value不可被修改，multiset和set的区别在于：

    multiset可以插入多个相同的key/value，即在multiset中可以存在多个某个key/value

    set只允许唯一的key/value存在，一旦某个key/value已经存在那么就不会再插入相同值的key/value

    insert：

    erase：

     

    返回删除某个值的个数 

    删除一段区间的元素 

     find：

    如果用find查找某个key/value，当此key/value存在多个，则find返回中序第一个val位置的迭代器

    count：

    multiset允许存在多个相同值，count可以统计某个值的个数

     equal_range：

    第一个iterator：第一个>=val值位置的迭代器

    第二个iterator：第一个>val值位置的迭代器

    左闭右开区间

    测试4：
    1. void test_set4()
    2. {
    3. 	multiset<int> s;
    4. 	s.insert(4);
    5. 	s.insert(3);
    6. 	s.insert(8);
    7. 	s.insert(2);
    8. 	s.insert(4);
    9. 	s.insert(5);
    10. 	s.insert(8);
    11. 	s.insert(2);
    12. 	multiset<int>::iterator it = s.begin();
    13. 	while (it != s.end())
    14. 	{
    15. 		//*it = 10;//不可以修改key/value
    16. 		cout << *it << " ";
    17. 		++it;
    18. 	}
    19. 	cout << endl;
    20.  
    21. 	// 如果有多个值，find返回中序第一个value
    22. 	it = s.find(4);
    23. 	while (it != s.end())
    24. 	{
    25. 		cout << *it << " ";
    26. 		++it;
    27. 	}
    28. 	cout << endl;
    29.  
    30. 	cout << s.count(2)<//统计某个value的个数
    31.  
    32. 	// [>=value, >value)
    33. 	auto ret = s.equal_range(2);
    34. 	s.erase(ret.first, ret.second);//删除连续的value
    35. 	for (auto e : s)
    36. 	{
    37. 		cout << e << " ";
    38. 	}
    39. 	cout << endl;
    40. }

    运行效果:

    map

    map的介绍
     

    key不可被修改，value可被修改

    1 在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容

    键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
    typedef pair value_type;
     

    2 map中的元素总是按照键值key进行比较排序的

    3 map中通过键值访问单个元素的速度通常比unordered_map容器慢

    4 map支持下标访问符，即在[]中放入key，就可以找到与key对应的value

    5 map通常被实现为平衡二叉搜索树(红黑树)


    map的使用

    key: 键值对中key的类型
    T： 键值对中value的类型

    insert:

     

    注意：map的insert插入的是一个键值对

    插入成功-> pair<新插入键值对所在节点的迭代器,true>

    插入失败-> pair<已存在的键值对所在节点的迭代器,false>

    再来熟悉一下键值对pair：

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

     pair的第二个构造函数非常强大，设计成为了模板

    如果形参的U,V和正在被初始化的pair的两个成员的类型一致，则为拷贝构造

    如果不是完全一致，则可视为构造，只要形参pair的两个成员可以赋值给正在被初始化的pair

    make_pair函数：

    make_pair会返回一个键值对，我们可以用此函数来构建理想的键值对

    operator[]：（重要)

    给定一个key， operator[]函数会返回与之对应的value的引用

    上图简化版（只是大概示意图，不是正统语法）：

     原理： operator[]函数会调用insert函数，其中的V()是value的类型的匿名对象，即使是内置类型也会有构造函数，所以若是value为int类型，那么插入的键值对，它的第二个成员的默认值就是0

    insert返回一个键值对： 

    所以operator[]有以下作用：

    给定key返回对应value的引用，若是key不存在，则用默认value与key构造键值对然后插入

    测试1：
    1. void test_map1()
    2. {
    3. 	map dict;
    4. 	dict.insert(pair("sort", "排序"));
    5. 	dict.insert(pair("insert", "插入"));
    6. 	dict.insert(pair<const char*, const char*>("left", "左边"));
    7. 	dict.insert(make_pair("right", "右边"));//推荐这个
    8. 	string s1("xxx"), s2("yyy");
    9. 	dict.insert(make_pair(s1, s2));
    10.  
    11. 	dict["erase"];  // 插入功能，原先无erase，并将对应的value初始化
    12. 	cout << dict["erase"] << endl; // 查找
    13. 	dict["erase"] = "删除"; // 修改
    14. 	cout << dict["erase"] << endl;// 查找
    15. 	dict["top"] = "顶级";  // 插入+修改
    16. 	dict["left"] = "剩余"; // 修改
    17.  
    18.  
    19. 	map::iterator it = dict.begin();//迭代器遍历
    20. 	while (it != dict.end())
    21. 	{
    22. 		cout << it->first << ":" << it->second << endl;
    23. 		//cout << (*it).first << ":" << (*it).second << endl; //也可以选择这种方式打印
    24. 		++it;
    25. 	}
    26. 	cout << endl;
    27.  
    28. 	for (auto& kv : dict)//范围for遍历+修改value（map的key不可被修改）
    29. 	{
    30. 		//kv.first += 'y';//不可以修改
    31. 		kv.second += 'y';//可以修改
    32. 		cout << kv.first << ":" << kv.second << endl;
    33. 	}
    34. }

    运行效果：

    总结：

    map中的的元素是键值对
    map中的key是唯一的，并且不能修改
    默认按照小于的方式对key进行比较
    map中的元素如果用迭代器去遍历，可以得到一个有序的序列
    map的底层为平衡搜索树(红黑树)
    支持operator[]

    multimap的介绍
     

    存储键值对，其中多个键值对之间的key是可以重复的
    multimap和map的不同之处在于：map中的key是唯一的，而multimap中key是可以重复的
    multimap中的接口可以参考map，功能都是类似的
     

  • 相关阅读:
    从协方差的角度详解线性判别分析原理+Python实现
    HarmonyOS之 组件的使用
    MySQL数据库 -- 表的增删查改
    夏日炎炎 水域守护：北斗守护安全防线——为生命撑起智能保护伞
    AI概念之人工智能、机器学习和数据挖掘之间的联系与区别
    Vue组件之间通信
    认识Tomcat
    【深入理解Kotlin协程】协程的上下文 CoroutineContext
    TechSmith Camtasia Studio 23.3.2.49471 Crack
    Mysql事务
  • 原文地址：https://blog.csdn.net/weixin_73142957/article/details/134450037