• 大话STL第五期——set/multiset（含pair对组）

    书接上期，这一期我们聊聊关联式容器set和multiset，关联式容器与前面我们学习的顺序容器还是有很大的区别

    文章目录

    什么的是set？

    set的特点

    注意：set与multiset唯一的区别是

    set容器的API 

    注意：

    set构造和赋值

    set大小和交换

    set插入和删除

    set查找和统计

    set自定义规则排序(利用仿函数)内置类型

    对于自定义类型的排序

    有关Pair对组

    Pair的创建

    用类模板实现Pair

    什么的是set？

    set为单集合容器，底层数据结构为红黑树

    • BST：二叉搜索树，二叉排序树：保证中序遍历排列升序有序。所以在插入结点时，需要调整结点。
    • 红黑树：是一种特殊的BST树，把结点划分为红节点和黑节点，进行调整。

    set的特点

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

    举个例子，如下有 2 组键值对数据：

    {<'a', 1>, <'b', 2>, <'c', 3>}
    {<'a', 'a'>, <'b', 'b'>, <'c', 'c'>}

    显然，第一组数据中各键值对的键和值不相等，而第二组中各键值对的键和值对应相等。对于 set 容器来说，只能存储第 2 组键值对，而无法存储第一组键值对。

    基于 set 容器的这种特性，当使用 set 容器存储键值对时，只需要为其提供各键值对中的 value 值（也就是 key 的值）即可。仍以存储上面第 2 组键值对为例，只需要为 set 容器提供 set{'a','b','c'} ，该容器即可成功将它们存储起来。而对于第一组数可以利用map/multimap进行存储，map{{'a',1},{'b',2},{'c',3}},这个我们下一期再讲。

    注意：set与multiset唯一的区别是

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

    例如一组数据{1,3,2,5,5,}存入set后，set里面存的是{1,2,3,5}//自动排序，且不存重复元素

    而对于multiset则存入{1,2,3,5,5}//自动排序，可以存入相同元素

    set容器的API 

    首先要清楚set 容器类模板中未提供 at() 成员函数，也未对 [] 运算符进行重载。因此，要想访问 set 容器中存储的元素，只能借助 set 容器的迭代器。

    STL 标准库为 set 容器配置的迭代器类型为双向迭代器。这意味着，假设 p 为此类型的迭代器，则其只能进行 ++p、p++、--p、p--、*p 操作，并且 2 个双向迭代器之间做比较，也只能使用 == 或者 != 运算符。

    注意：

    • set的元素不能在容器中直接修改，因为：元素用const修饰，修改过后不能自己调整红黑树，导致序列乱序。所以正确的做法是修改一个元素可以先删除再插入。

    set构造和赋值

    1. set st;//默认构造
    2. set(const set &st);//拷贝构造
    3. set& operator=(const set& st);//重载等号赋值
    1. template<typename T>
    2. void Show(set& st)
    3. {
    4. 	for (auto it = st.begin(); it != st.end(); ++it)
    5. 	{
    6. 		cout <<(*it)<<" ";
    7. 	}
    8. 	cout << endl;
    9. }
    10.  
    11. int main()
    12. {
    13. 	set<int>st;
    14. 	//插入数据只有insert方式
    15. 	st.insert(1);
    16. 	st.insert(2);
    17. 	st.insert(3);
    18. 	st.insert(4);
    19. 	Show(st);
    20.  
    21. 	cout << "-----------------" << endl;
    22. 	set<int>st1;//set特点，所有元素插入时自动被排序
    23. 	st1.insert(5);
    24. 	st1.insert(10);
    25. 	st1.insert(3);
    26. 	st1.insert(1);
    27. 	Show(st1);
    28.  
    29. 	cout << "-----------------" << endl;
    30. 	set<int>st2;//set容器不允许插入重复值
    31. 	st2.insert(10);
    32. 	st2.insert(3);
    33. 	st2.insert(3);
    34. 	Show(st2);
    35.  
    36. 	cout << "-----------------" << endl;
    37. 	set<int>st3(st2);//拷贝构造
    38. 	Show(st3);
    39.  
    40. 	cout << "-----------------" << endl;
    41. 	set<int>st4;//等号赋值
    42. 	st4 = st3;
    43. 	Show(st4);
    44. 	return 0;
    45.  
    46. }
    1. template<typename T>
    2. void Show(multiset& st)
    3. {
    4. 	for (auto it = st.begin(); it != st.end(); ++it)
    5. 	{
    6. 		cout <<(*it)<<" ";
    7. 	}
    8. 	cout << endl;
    9. }
    10.  
    11. int main()
    12. {
    13.     //允许插入重复值
    14. 	multiset<int>st{1,5,3,3,3,4,2};//用初始化列表初始化
    15. 	
    16. 	Show(st);
    17. 	return 0;	
    18. }

    set大小和交换

    1. size();//返回容器中元素的数目
    2. empty();//判断容器是否为空
    3. swap(st);//交换两个集合容器
    1. template<typename T>
    2. void Show(set& st)
    3. {
    4. 	for (auto it = st.begin(); it != st.end(); ++it)
    5. 	{
    6. 		cout <<(*it)<<" ";
    7. 	}
    8. 	cout << endl;
    9. }
    10.  
    11. int main()
    12. {
    13. 	set<int>st{1,5,3,4,2};//用初始化列表初始化
    14. 	if (st.empty())
    15. 	{
    16. 		cout << "为空" << endl;
    17. 	}
    18. 	else
    19. 		cout << "不空" << endl;
    20. 	Show(st);
    21. 	cout << st.size()<
    22.  
    23. 	set<int>st1{8,1,5,2};
    24. 	st.swap(st1);
    25. 	cout << "交换后st：";
    26. 	Show(st);
    27. 	cout << "交换后st1：";
    28. 	Show(st1);
    29. 	return 0;
    30.  
    31. }

    set插入和删除

    1. insert(elem);//在容器中插入元素
    2. clear();//清除所有元素
    3. erase(pos);//删除pos迭代器所指的元素，返回下一元素的迭代器
    4. erase(beg,end);//删除区间[beg,end]的所有元素，返回下一元素迭代器
    5. erase(elem);//删除容器中elem值元素 类似list中remove函数
    1. template<typename T>
    2. void Show(set& st)
    3. {
    4. 	for (auto it = st.begin(); it != st.end(); ++it)
    5. 	{
    6. 		cout <<(*it)<<" ";
    7. 	}
    8. 	cout << endl;
    9. }
    10.  
    11. int main()
    12. {
    13. 	set<int>st{1,5,3,4,2};//用初始化列表初始化
    14. 	st.insert(15);
    15. 	Show(st);
    16. 	st.erase(st.begin(), ++st.begin() );//因为不能随机访问，同样没有重载+或-
    17. 	Show(st);
    18.  
    19. 	st.erase(3);//删除3
    20. 	Show(st);
    21.  
    22. 	return 0;
    23. 	
    24. }

    set查找和统计

    1. find(key);//查找key是否存在，若存在返回该键的迭代器，不存在返回set.end()位置
    2. count(key);//统计key的元素个数；对于set只有0或1 因为set不允许插入重复数据
    1. int main()
    2. {
    3. 	set<int>st{1,5,3,4,2};//用初始化列表初始化
    4. 	
    5. 	
    6. 	set<int>::iterator ot = st.find(5);
    7. 	if (ot != st.end())
    8. 	{
    9. 		cout << "找到元素:" << (*ot) << endl;
    10. 	}
    11. 	else
    12. 		cout << "没找到元素:" << (*ot) << endl;
    13.  
    14. 	//统计1的个数
    15. 	cout << st.count(1) << endl;
    16. 	return 0;
    17. 	
    18. }

    这是标准库里迭代器部分的内容，简单点说，就是用find这个函数，去找str这个序列中的i元素，如果序列中所找的这个元素不存在，就会返回end()。

    那么按着这个思路去理解这两行命令就很容易了！

    如果str.find(i)返回的不是str.end(),就说明在str序列中找到i元素：
     

    str.find(i) != str.end() //说明找到了

    同理，如果str.find(i)返回的是str.end(),就说明在str序列中没找到i元素： 

    str.find(i) == str.end() //说明没到

    set自定义规则排序(利用仿函数)内置类型

    因此set容器的特性，在容器创建是内部元素自动会排序，那么如果我们想要利用set保存我们自己想要的排序顺序该如何操作呢？

    1. //set容器默认排序为从小到大,掌握如何改变排序规则
    2. //利用仿函数,可以改变排序规则
    3. #include
    4. #include
    5. using namespace std;
    6. //仿函数:用类调用函数
    7. //仿函数设计:
    8. class MyCompare {
    9. public:
    10. 	//下一行末尾加上const
    11. 	/*bool operator()(int v1, int v2){
    12. 		return v1 > v2;
    13. 	}*/
    14. 	bool operator()(int v1, int v2)const {
    15. 		return v1 > v2;
    16. 	}
    17. };
    18. void test01() {
    19. 	set<int>s1;
    20. 	s1.insert(10);
    21. 	s1.insert(40);
    22. 	s1.insert(30);
    23. 	s1.insert(50);
    24. 	s1.insert(20);
    25. 	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
    26. 		cout << *it << " ";
    27. 	}
    28. 	cout << endl;
    29.  
    30. 	//指定排序规则为从大到小
    31. 	//重新指定第一步,更改第二个默认值
    32. 	//注意:这里第二个默认值需求为类型,不可以是函数(函数名),故使用仿函数
    33.    //set > s2; // 从大到小排序，也可以这样创建，使用内置的仿函数
    34.  
    35. 	set<int,MyCompare>s2;
    36. 	s2.insert(10);
    37. 	s2.insert(40);
    38. 	s2.insert(30);
    39. 	s2.insert(50);
    40. 	s2.insert(20);
    41. 	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
    42. 		cout << *it << " ";
    43. 	}
    44. 	cout << endl;
    45. }
    46. int main() {
    47. 	test01();
    48. }

    对于自定义类型的排序

    1. class Person {
    2. public:
    3. 	Person(string name, int age) {
    4. 		this->m_Name = name;
    5. 		this->m_Age = age;
    6. 	}
    7.  
    8. 	string m_Name;
    9. 	int m_Age;
    10. };
    11.  
    12. class comparePerson {
    13. public:
    14. 	bool operator()(const Person& p1, const Person& p2)const {
    15. 		//按照年龄 降序
    16. 		return p1.m_Age > p2.m_Age;
    17. 	}
    18. };
    19.  
    20. void test01() {
    21. 	//自定义数据类型 都会指定排序规则
    22.  
    23. 	sets;
    24.  
    25. 	Person p1("刘备", 28);
    26. 	Person p2("关羽", 26);
    27. 	Person p3("张飞", 24);
    28. 	Person p4("马超", 22);
    29. 	Person p5("赵云", 21);
    30. 	s.insert(p1);
    31. 	s.insert(p2);
    32. 	s.insert(p3);
    33. 	s.insert(p4);
    34. 	s.insert(p5);
    35.  
    36. 	for (set::iterator it = s.begin(); it != s.end(); it++) {
    37. 		cout << "姓名：" << it->m_Name << " " << "年龄:" << it->m_Age << endl;
    38. 	}
    39. }
    40.  
    41. int main() {
    42.  
    43.  
    44. 	test01();
    45.  
    46. 	return 0;
    47. }

    有关Pair对组

    pair只含有两个元素，可以看作是只有两个元素的结构体。对于成对出现的数据，利用对组可以返回两个数据
    应用：

    • 代替二元结构体
    • 作为map键值对进行插入（下一期会讲map）

    在创建pair对象时，必须提供两个类型名，两个对应的类型名的类型不必相同，可以在定义时进行成员初始化。

    Pair的创建

    1. 创建方式
    2. pair p(value1,value2);
    3. pair p=make_pair(value1,value2);
    4.  
    5. 头文件
    6. #include
    7.  
    8. //1.初始化定义
    9. pairint> p("wangyaqi",1);//带初始值的
    10. pairint> p;//不带初始值的
    11.  
    12. //2.赋值
    13. p = {"wang",18};
    14. 	
    15. int main()
    16. {
    17. 	//数据类型         数据
    18. 	pairint>p("公孙离", 17);
    19. 	cout << "姓名:" << p.first << " 年岁:" << p.second << endl;
    20.  
    21.     //和结构体类似，first代表第一个元素，second代表第二个元素
    22.  
    23. 	pairint>p1=make_pair("钟馗", 47);
    24. 	cout << "姓名:" << p1.first << " 年岁:" << p1.second << endl;
    25. 	return 0;	
    26. }

    头文件中除了提供创建 pair 对象的方法之外，还为 pair 对象重载了 <、<=、>、>=、==、!= 这 6 的运算符，其运算规则是：对于进行比较的 2 个 pair 对象，先比较 pair.first 元素的大小，如果相等则继续比较 pair.second 元素的大小。

    注意，对于进行比较的 2 个 pair 对象，其对应的键和值的类型比较相同，否则将没有可比性，同时编译器提示没有相匹配的运算符，即找不到合适的重载运算符。

    最后需要指出的是，pair类模板还提供有一个 swap() 成员函数，能够互换 2 个 pair 对象的键值对，其操作成功的前提是这 2 个 pair 对象的键和值的类型要相同。例如：

    1. #include 
    2. #include       // pair
    3. #include        // string
    4. using namespace std;
    5. int main() {
    6.     pair int> pair1("pair", 10);                   
    7.     pair int> pair2("pair2", 20);
    8.     //交换 pair1 和 pair2 的键值对
    9.     pair1.swap(pair2);
    10.     cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    11.     cout << "pair2: " << pair2.first << " " << pair2.second << endl;
    12.     return 0;
    13. }

     执行结果：

    1. pair1: pair2 20
    2. pair2: pair 10

    用类模板实现Pair

    1. // 类模板
    2. template <class T1, class T2>
    3. class Pair
    4. {
    5. public:
    6.     Pair(T1 k, T2 v):m_key(k),m_value(v) {};
    7.     bool operator < (const Pair & p) const;
    8. private:
    9.     T1 m_key;
    10.     T2 m_value;
    11. };
    12.  
    13. // 类模板里成员函数的写法
    14. template <class T1, class T2>
    15. bool Pair::operator < (const Pair &p) const
    16. {
    17.     return m_value < p.m_value;
    18. }
    19. int main()
    20. {
    21.     Pairint> Astudent("Jay",20); 
    22.     Pairint> Bstudent("Tom",21);
    23.  
    24.     cout << (Astudent < Bstudent) << endl;
    25.  
    26.     return 0;
    27. }
    28. //结果为1   20<21

    这一期就到此结束了，感谢观看，订阅此专栏。

  • 相关阅读:
    Web Based Quiz System SQL注入漏洞复现（CVE-2022-32991）
    核心解读 - 2022版智慧城市数字孪生标准化白皮书
    PHP会话技术session我不允许还有人不会！
    Java使用mybatis框架调用MySQL存储过程
    【router-view】切换组件 深刻理解用法 vue的设计思想
    Python3 如何实现 websocket 服务？
    Linux 下以其他用户运行程序
    【虚拟化生态平台】树莓派安装虚拟化平台操作流程
    图像分割算法
    商业合作保密协议书(公对公)【设计】
  • 原文地址：https://blog.csdn.net/weixin_51609435/article/details/126375682