• 进阶C++__STL__set/ multiset和map/ multimap使用方法

    目录

    一、关联式容器

    二、键值对

    三、树形结构的关联式容器

    set/ multiset 容器

    set基本概念

    set构造和赋值

    set大小和交换

    set插入和删除

    set查找和统计

    set和multiset区别

    set / multiset总结

    pair对组创建

    set容器排序

    内置类型指定排序规则

    自定义数据类型指定排序规则

    map/ multimap容器

    map基本概念

    map构造和赋值

    map大小和交换

    map插入和删除

    map查找和统计

    map容器排序

    map / multimap总结

    OJ练习

    set的算法常用方式

     两个数组的交集

    set的算法常用方式

    字符串中的第一个唯一字符

    只出现一次的数字 II

    一、关联式容器

    在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、

    forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

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

    二、键值对

    用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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. 	T1 first;
    7. 	T2 second;
    8. 	pair() : first(T1()), second(T2())
    9. 	{}
    10. 	pair(const T1& a, const T2& b) : first(a), second(b)
    11. 	{}
    12. };

    三、树形结构的关联式容器

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

    set/ multiset 容器

    set文档介绍链接：set - C++ Reference

    set基本概念

    简介：

    • 所有元素都会在插入时自动被排序

    本质：

    • set/multiset属于关联式容器，底层结构是用二叉树实现。

    set和multiset区别

    • set不允许容器中有重复的元素
    • multiset允许容器中有重复的元素

    set构造和赋值

    功能描述：创建set容器以及赋值

    构造：

    • set st; //默认构造函数：
    • set(const set &st); //拷贝构造函数

    赋值：

    • set& operator=(const set &st); //重载等号操作符
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printSet(set<int> & s)
    7. {
    8. 	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    9. 	{
    10. 		cout << *it << " ";
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. //构造和赋值
    16. void test01()
    17. {
    18. 	set<int> s1;
    19.  
    20. 	s1.insert(10);
    21. 	s1.insert(30);
    22. 	s1.insert(20);
    23. 	s1.insert(40);
    24. 	printSet(s1);
    25.  
    26. 	//拷贝构造
    27. 	set<int>s2(s1);
    28. 	printSet(s2);
    29.  
    30. 	//赋值
    31. 	set<int>s3;
    32. 	s3 = s2;
    33. 	printSet(s3);
    34. }
    35.  
    36. int main() {
    37.  
    38. 	test01();
    39.  
    40. 	system("pause");
    41.  
    42. 	return 0;
    43. }

    输出：

    10 20 30 40
    10 20 30 40
    10 20 30 40

    总结：

    • set容器插入数据时用insert
    • set容器插入数据的数据会自动排序

    set大小和交换

    功能描述：

    • 统计set容器大小以及交换set容器

    函数原型：

    • size(); //返回容器中元素的数目
    • empty(); //判断容器是否为空
    • swap(st); //交换两个集合容器

    示例：

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printSet(set<int> & s)
    7. {
    8. 	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    9. 	{
    10. 		cout << *it << " ";
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. //大小
    16. void test01()
    17. {
    18.  
    19. 	set<int> s1;
    20. 	
    21. 	s1.insert(10);
    22. 	s1.insert(30);
    23. 	s1.insert(20);
    24. 	s1.insert(40);
    25.  
    26. 	if (s1.empty())
    27. 	{
    28. 		cout << "s1为空" << endl;
    29. 	}
    30. 	else
    31. 	{
    32. 		cout << "s1不为空" << endl;
    33. 		cout << "s1的大小为： " << s1.size() << endl;
    34. 	}
    35.  
    36. }
    37.  
    38. //交换
    39. void test02()
    40. {
    41. 	set<int> s1;
    42.  
    43. 	s1.insert(10);
    44. 	s1.insert(30);
    45. 	s1.insert(20);
    46. 	s1.insert(40);
    47.  
    48. 	set<int> s2;
    49.  
    50. 	s2.insert(100);
    51. 	s2.insert(300);
    52. 	s2.insert(200);
    53. 	s2.insert(400);
    54.  
    55. 	cout << "交换前" << endl;
    56. 	printSet(s1);
    57. 	printSet(s2);
    58. 	cout << endl;
    59.  
    60. 	cout << "交换后" << endl;
    61. 	s1.swap(s2);
    62. 	printSet(s1);
    63. 	printSet(s2);
    64. }
    65.  
    66. int main() {
    67.  
    68. 	test01();
    69.  
    70. 	test02();
    71.  
    72. 	return 0;
    73. }

    输出：

    s1不为空
    s1的大小为： 4
    交换前
    10 20 30 40
    100 200 300 400

    交换后
    100 200 300 400
    10 20 30 40

    set插入和删除

    功能描述：

    • set容器进行插入数据和删除数据

    函数原型：

    • insert(elem); //在容器中插入元素。
    • clear(); //清除所有元素
    • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
    • erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    • erase(elem); //删除容器中值为elem的元素。
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printSet(set<int> & s)
    7. {
    8. 	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    9. 	{
    10. 		cout << *it << " ";
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. //插入和删除
    16. void test01()
    17. {
    18. 	set<int> s1;
    19. 	//插入
    20. 	s1.insert(10);
    21. 	s1.insert(30);
    22. 	s1.insert(20);
    23. 	s1.insert(40);
    24. 	printSet(s1);
    25.  
    26. 	//删除
    27. 	s1.erase(s1.begin());
    28. 	printSet(s1);
    29.  
    30. 	s1.erase(30);
    31. 	printSet(s1);
    32.  
    33. 	//清空
    34. 	//s1.erase(s1.begin(), s1.end());
    35. 	s1.clear();
    36. 	printSet(s1);
    37. }
    38.  
    39. int main() {
    40.  
    41. 	test01();
    42.  
    43. 	system("pause");
    44.  
    45. 	return 0;
    46. }

    10 20 30 40
    20 30 40
    20 40
     

    set查找和统计

    功能描述：

    • 对set容器进行查找数据以及统计数据

    函数原型：

    • find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
    • count(key); //统计key的元素个数
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. //查找和统计
    7. void test01()
    8. {
    9. 	set<int> s1;
    10. 	//插入
    11. 	s1.insert(10);
    12. 	s1.insert(30);
    13. 	s1.insert(20);
    14. 	s1.insert(40);
    15. 	
    16. 	//查找
    17. 	set<int>::iterator pos = s1.find(30);
    18.  
    19. 	if (pos != s1.end())
    20. 	{
    21. 		cout << "找到了元素 ： " << *pos << endl;
    22. 	}
    23. 	else
    24. 	{
    25. 		cout << "未找到元素" << endl;
    26. 	}
    27.  
    28. 	//统计
    29. 	int num = s1.count(30);
    30. 	cout << "num = " << num << endl;
    31. }
    32.  
    33. int main() {
    34.  
    35. 	test01();
    36.  
    37. 	system("pause");
    38.  
    39. 	return 0;
    40. }

    找到了元素 ： 30
    num = 1

    set和multiset区别

    学习目标：

    • 掌握set和multiset的区别

    区别：

    • set不可以插入重复数据，而multiset可以
    • set插入数据的同时会返回插入结果，表示插入是否成功
    • multiset不会检测数据，因此可以插入重复数据
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. //set和multiset区别
    7. void test01()
    8. {
    9. 	set<int> s;
    10. 	pairint>::iterator, bool>  ret = s.insert(10);
    11. 	if (ret.second) {
    12. 		cout << "第一次插入成功!" << endl;
    13. 	}
    14. 	else {
    15. 		cout << "第一次插入失败!" << endl;
    16. 	}
    17.  
    18. 	ret = s.insert(10);
    19. 	if (ret.second) {
    20. 		cout << "第二次插入成功!" << endl;
    21. 	}
    22. 	else {
    23. 		cout << "第二次插入失败!" << endl;
    24. 	}
    25.     
    26. 	//multiset
    27. 	multiset<int> ms;
    28. 	ms.insert(10);
    29. 	ms.insert(10);
    30.  
    31. 	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
    32. 		cout << *it << " ";
    33. 	}
    34. 	cout << endl;
    35. }
    36.  
    37. int main() {
    38.  
    39. 	test01();
    40.  
    41. 	system("pause");
    42.  
    43. 	return 0;
    44. }

    输出：

    第一次插入成功!
    第二次插入失败!
    10 10

    总结：

    • 如果不允许插入重复数据可以利用set
    • 如果需要插入重复数据利用multiset

    set / multiset总结

    1. set是按照一定次序存储元素的容器

    2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。

    set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

    3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

    4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对

    子集进行直接迭代。

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

    注意：

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

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

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

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

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

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

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

    7. set中的元素不允许修改(为什么?)

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

    pair对组创建

    功能描述：

    • 成对出现的数据，利用对组可以返回两个数据

    两种创建方式：

    • pair p ( value1, value2 );
    • pair p = make_pair( value1, value2 );
    1. #include
    2. #include 
    3. using namespace std;
    4. //对组创建
    5. void test01()
    6. {
    7. 	pairint> p(string("Tom"), 20);
    8. 	cout << "姓名： " <<  p.first << " 年龄： " << p.second << endl;
    9.  
    10. 	pairint> p2 = make_pair("Jerry", 10);
    11. 	cout << "姓名： " << p2.first << " 年龄： " << p2.second << endl;
    12. }
    13.  
    14. int main() {
    15.  
    16. 	test01();
    17.  
    18. 	system("pause");
    19.  
    20. 	return 0;
    21. }

    输出：

    姓名： Tom 年龄： 20
    姓名： Jerry 年龄： 10

    set容器排序

    内置类型指定排序规则

    改变排序顺序核心 

    1. class MyCompare 
    2. {
    3. public:
    4. 	bool operator()(int v1, int v2) {
    5. 		return v1 > v2;
    6. 	}
    7. };
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. class MyCompare 
    7. {
    8. public:
    9. 	bool operator()(int v1, int v2) {
    10. 		return v1 > v2;
    11. 	}
    12. };
    13. void test01() 
    14. {    
    15. 	set<int> s1;
    16. 	s1.insert(10);
    17. 	s1.insert(40);
    18. 	s1.insert(20);
    19. 	s1.insert(30);
    20. 	s1.insert(50);
    21.  
    22. 	//默认从小到大
    23. 	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
    24. 		cout << *it << " ";
    25. 	}
    26. 	cout << endl;
    27.  
    28. 	//指定排序规则
    29. 	set<int,MyCompare> s2;
    30. 	s2.insert(10);
    31. 	s2.insert(40);
    32. 	s2.insert(20);
    33. 	s2.insert(30);
    34. 	s2.insert(50);
    35.  
    36. 	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
    37. 		cout << *it << " ";
    38. 	}
    39. 	cout << endl;
    40. }
    41.  
    42. int main() {
    43.  
    44. 	test01();
    45.  
    46. 	system("pause");
    47.  
    48. 	return 0;
    49. }

    输出：

    10 20 30 40 50
    50 40 30 20 10

    利用仿函数可以指定set容器的排序规则

    自定义数据类型指定排序规则

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. class Person
    7. {
    8. public:
    9. 	Person(string name, int age)
    10. 	{
    11. 		this->m_Name = name;
    12. 		this->m_Age = age;
    13. 	}
    14.  
    15. 	string m_Name;
    16. 	int m_Age;
    17.  
    18. };
    19. class comparePerson
    20. {
    21. public:
    22. 	bool operator()(const Person& p1, const Person &p2)
    23. 	{
    24. 		//按照年龄进行排序  降序
    25. 		return p1.m_Age > p2.m_Age;
    26. 	}
    27. };
    28.  
    29. void test01()
    30. {
    31. 	set s;
    32.  
    33. 	Person p1("刘备", 23);
    34. 	Person p2("关羽", 27);
    35. 	Person p3("张飞", 25);
    36. 	Person p4("赵云", 21);
    37.  
    38. 	s.insert(p1);
    39. 	s.insert(p2);
    40. 	s.insert(p3);
    41. 	s.insert(p4);
    42.  
    43. 	for (set::iterator it = s.begin(); it != s.end(); it++)
    44. 	{
    45. 		cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age << endl;
    46. 	}
    47. }
    48. int main() {
    49.  
    50. 	test01();
    51.  
    52. 	system("pause");
    53.  
    54. 	return 0;
    55. }

    输出：

    姓名： 关羽 年龄： 27
    姓名： 张飞 年龄： 25
    姓名： 刘备 年龄： 23
    姓名： 赵云 年龄： 21

    对于自定义数据类型，set必须指定排序规则才可以插入数据

    map/ multimap容器

    map的文档简介链接：map - C++ Reference

    map基本概念

    简介：

    • map中所有元素都是pair
    • pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
    • 所有元素都会根据元素的键值自动排序

    本质：

    • map/multimap属于关联式容器，底层结构是用二叉树实现。

    优点：

    • 可以根据key值快速找到value值

    map和multimap区别：

    • map不允许容器中有重复key值元素
    • multimap允许容器中有重复key值元素

    map构造和赋值

    功能描述：

    • 对map容器进行构造和赋值操作

    函数原型：

    构造：

    • map mp; //map默认构造函数:
    • map(const map &mp); //拷贝构造函数

    赋值：

    • map& operator=(const map &mp); //重载等号操作符

    示例：

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printMap(map<int,int>&m)
    7. {
    8. 	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    9. 	{
    10. 		cout << "key = " << it->first << " value = " << it->second << endl;
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. void test01()
    16. {
    17. 	map<int,int>m; //默认构造
    18. 	m.insert(pair<int, int>(1, 10));
    19. 	m.insert(pair<int, int>(2, 20));
    20. 	m.insert(pair<int, int>(3, 30));
    21. 	printMap(m);
    22.  
    23. 	map<int, int>m2(m); //拷贝构造
    24. 	printMap(m2);
    25.  
    26. 	map<int, int>m3;
    27. 	m3 = m2; //赋值
    28. 	printMap(m3);
    29. }
    30.  
    31. int main() {
    32.  
    33. 	test01();
    34.  
    35. 	system("pause");
    36.  
    37. 	return 0;
    38. }
    39.

    key = 1 value = 10
    key = 2 value = 20
    key = 3 value = 30

    key = 1 value = 10
    key = 2 value = 20
    key = 3 value = 30

    key = 1 value = 10
    key = 2 value = 20
    key = 3 value = 30
     

    map中所有元素都是成对出现，插入数据时候要使用对组

    map大小和交换

    功能描述：

    • 统计map容器大小以及交换map容器

    函数原型：

    • size(); //返回容器中元素的数目
    • empty(); //判断容器是否为空
    • swap(st); //交换两个集合容器
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printMap(map<int,int>&m)
    7. {
    8. 	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    9. 	{
    10. 		cout << "key = " << it->first << " value = " << it->second << endl;
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. void test01()
    16. {
    17. 	map<int, int>m;
    18. 	m.insert(pair<int, int>(1, 10));
    19. 	m.insert(pair<int, int>(2, 20));
    20. 	m.insert(pair<int, int>(3, 30));
    21.  
    22. 	if (m.empty())
    23. 	{
    24. 		cout << "m为空" << endl;
    25. 	}
    26. 	else
    27. 	{
    28. 		cout << "m不为空" << endl;
    29. 		cout << "m的大小为： " << m.size() << endl;
    30. 	}
    31. }
    32.  
    33.  
    34. //交换
    35. void test02()
    36. {
    37. 	map<int, int>m;
    38. 	m.insert(pair<int, int>(1, 10));
    39. 	m.insert(pair<int, int>(2, 20));
    40. 	m.insert(pair<int, int>(3, 30));
    41.  
    42. 	map<int, int>m2;
    43. 	m2.insert(pair<int, int>(4, 100));
    44. 	m2.insert(pair<int, int>(5, 200));
    45. 	m2.insert(pair<int, int>(6, 300));
    46.  
    47. 	cout << "交换前" << endl;
    48. 	printMap(m);
    49. 	printMap(m2);
    50.  
    51. 	cout << "交换后" << endl;
    52. 	m.swap(m2);
    53. 	printMap(m);
    54. 	printMap(m2);
    55. }
    56.  
    57. int main() {
    58.  
    59. 	test01();
    60.  
    61. 	test02();
    62.  
    63. 	system("pause");
    64.  
    65. 	return 0;
    66. }
    67.

    m不为空
    m的大小为： 3
    交换前
    key = 1 value = 10
    key = 2 value = 20
    key = 3 value = 30

    key = 4 value = 100
    key = 5 value = 200
    key = 6 value = 300

    交换后
    key = 4 value = 100
    key = 5 value = 200
    key = 6 value = 300

    key = 1 value = 10
    key = 2 value = 20
    key = 3 value = 30

    map插入和删除

    功能描述：

    • map容器进行插入数据和删除数据

    函数原型：

    • insert(elem); //在容器中插入元素。
    • clear(); //清除所有元素
    • erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
    • erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    • erase(key); //删除容器中值为key的元素。
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printMap(map<int,int>&m)
    7. {
    8. 	for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
    9. 	{
    10. 		cout << "key = " << it->first << " value = " << it->second << endl;
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. void test01()
    16. {
    17. 	//插入
    18. 	map<int, int> m;
    19. 	//第一种插入方式
    20. 	m.insert(pair<int, int>(1, 10));
    21. 	//第二种插入方式
    22. 	m.insert(make_pair(2, 20));
    23. 	//第三种插入方式
    24. 	m.insert(map<int, int>::value_type(3, 30));
    25. 	//第四种插入方式
    26. 	m[4] = 40; 
    27. 	printMap(m);
    28.  
    29. 	//删除
    30. 	m.erase(m.begin());
    31. 	printMap(m);
    32.  
    33. 	m.erase(3);
    34. 	printMap(m);
    35.  
    36. 	//清空
    37. 	m.erase(m.begin(),m.end());
    38. 	m.clear();
    39. 	printMap(m);
    40. }
    41.  
    42. int main() {
    43.  
    44. 	test01();
    45.  
    46. 	system("pause");
    47.  
    48. 	return 0;
    49. }
    50.

    key = 1 value = 10
    key = 2 value = 20
    key = 3 value = 30
    key = 4 value = 40

    key = 2 value = 20
    key = 3 value = 30
    key = 4 value = 40

    key = 2 value = 20
    key = 4 value = 40

    map查找和统计

    功能描述：

    • 对map容器进行查找数据以及统计数据

    函数原型：

    • find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
    • count(key); //统计key的元素个数
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. //查找和统计
    7. void test01()
    8. {
    9. 	map<int, int>m; 
    10. 	m.insert(pair<int, int>(1, 10));
    11. 	m.insert(pair<int, int>(2, 20));
    12. 	m.insert(pair<int, int>(3, 30));
    13.  
    14. 	//查找
    15. 	map<int, int>::iterator pos = m.find(2);
    16.  
    17. 	if (pos != m.end())
    18. 	{
    19. 		cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;
    20. 	}
    21. 	else
    22. 	{
    23. 		cout << "未找到元素" << endl;
    24. 	}
    25.  
    26. 	//统计
    27. 	int num = m.count(3);
    28. 	cout << "num = " << num << endl;
    29. }
    30.  
    31. int main() {
    32.  
    33. 	test01();
    34.  
    35. 	system("pause");
    36.  
    37. 	return 0;
    38. }

    找到了元素 key = 2 value = 20
    num = 1

    map容器排序

    • 利用仿函数可以指定map容器的排序规则
    • 对于自定义数据类型，map必须要指定排序规则,同set容器
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. class MyCompare {
    7. public:
    8. 	bool operator()(int v1, int v2) {
    9. 		return v1 > v2;
    10. 	}
    11. };
    12.  
    13. void test01() 
    14. {
    15. 	//默认从小到大排序
    16. 	//利用仿函数实现从大到小排序
    17. 	map<int, int, MyCompare> m;
    18.  
    19. 	m.insert(make_pair(1, 10));
    20. 	m.insert(make_pair(2, 20));
    21. 	m.insert(make_pair(3, 30));
    22. 	m.insert(make_pair(4, 40));
    23. 	m.insert(make_pair(5, 50));
    24.  
    25. 	for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++) {
    26. 		cout << "key:" << it->first << " value:" << it->second << endl;
    27. 	}
    28. }
    29. int main() {
    30.  
    31. 	test01();
    32.  
    33. 	system("pause");
    34.  
    35. 	return 0;
    36. }

    key:5 value:50
    key:4 value:40
    key:3 value:30
    key:2 value:20
    key:1 value:10

    map / multimap总结

    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通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

    注意：multimap与map最大区别就是不支持operator[]传值（key的唯一性）

    OJ练习

    set的算法常用方式

     两个数组的交集

     利用set去重并排序

    1. class Solution {
    2. public:
    3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.         set<int> s1;
    5.         for(auto e:nums1) s1.insert(e);
    6.  
    7.         set<int> s2;
    8.         for(auto e:nums2) s2.insert(e);
    9.  
    10.         vector<int> v;
    11.  
    12.         for(auto e1:s1)
    13.         {
    14.             if(s2.count(e1)) v.push_back(e1);
    15.         }
    16.         return v;
    17.     }
    18. };

    set的算法常用方式

    字符串中的第一个唯一字符

    经典哈希表存储频数方法

    1. class Solution {
    2. public:
    3.     int firstUniqChar(string s) {
    4.         map<int,int> m;
    5.         for(auto ch:s) m[ch]++;
    6.  
    7.         for(int i=0;isize();i++)
    8.         {
    9.             if(m[s[i]]==1) return i;
    10.         }
    11.         return -1;
    12.     }
    13. };

    只出现一次的数字 II

     对于map的范围for：

    1. map<int,string> mp;
    2. for(auto [key值,value值] : mp)
    1. class Solution {
    2. public:
    3.     int singleNumber(vector<int>& nums) {
    4.         map<int,int> m;
    5.         for(int n:nums)
    6.         {
    7.             m[n]++;
    8.         }
    9.         int ret;
    10.         for(auto [n,ac]:m)
    11.         {
    12.             if(ac==1) 
    13.             {
    14.                 ret=n;
    15.                 break;
    16.             }
    17.         }
    18.         return ret;
    19.     }
    20.  
    21. };

    面试题 01.04. 回文排列

    1. class Solution {
    2. public:
    3.     bool canPermutePalindrome(string s) {
    4.         unordered_map<char, int> tempMP;
    5.         for (char c:s) {
    6.             tempMP[c]++;
    7.         }
    8.         int time = 0; //记录奇数次字母的个数
    9.         for (auto [first, second] : tempMP) {
    10.             if (second % 2) 
    11.             {
    12.                 if(++time > 1) return false;//若超过1个则不可能对称形成回文
    13.             }
    14.         }
    15.         return true;
    16.     }
    17. };
    18.

    692. 前K个高频单词 - 力扣（LeetCode）

    单词识别_牛客题霸_牛客网 (nowcoder.com)

  • 相关阅读:
    低代码+BPM+KM于一体的软件开发平台
    深入学习Semantic Kernel：创建和配置prompts functions
    ARMday02（汇编语法、汇编指令）
    强化学习基本概念
    如何签署exe或Windows应用程序？
    浏览器调试模式获取链接信息（获取京东cookie为例）
    Jacoco+git生成差异代码覆盖率测试报告
    ELK高级搜索（四）
    Java - NPE(NullPointerException)；Optional
    航天常用术语-双想、九新、六个百分百确认、三图、三类关键特性、可靠性1+6+2、质量问题归零、技术状态更改“五条”原则、四随
  • 原文地址：https://blog.csdn.net/weixin_73961973/article/details/134047469