书接上期，这一期我们聊聊关联式容器set和multiset，关联式容器与前面我们学习的顺序容器还是有很大的区别
文章目录
什么的是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<string>{'a','b','c'} ，该容器即可成功将它们存储起来。而对于第一组数可以利用map/multimap进行存储，map<string,int>{{'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构造和赋值
set<T> st;//默认构造
set(const set &st);//拷贝构造
set& operator=(const set& st);//重载等号赋值
template<typename T>
void Show(set<T>& st)
{
for (auto it = st.begin(); it != st.end(); ++it)
{
cout <<(*it)<<" ";
}
cout << endl;
}
int main()
{
set<int>st;
//插入数据只有insert方式
st.insert(1);
st.insert(2);
st.insert(3);
st.insert(4);
Show(st);
cout << "-----------------" << endl;
set<int>st1;//set特点，所有元素插入时自动被排序
st1.insert(5);
st1.insert(10);
st1.insert(3);
st1.insert(1);
Show(st1);
cout << "-----------------" << endl;
set<int>st2;//set容器不允许插入重复值
st2.insert(10);
st2.insert(3);
st2.insert(3);
Show(st2);
cout << "-----------------" << endl;
set<int>st3(st2);//拷贝构造
Show(st3);
cout << "-----------------" << endl;
set<int>st4;//等号赋值
st4 = st3;
Show(st4);
return 0;
}
template<typename T>
void Show(multiset<T>& st)
{
for (auto it = st.begin(); it != st.end(); ++it)
{
cout <<(*it)<<" ";
}
cout << endl;
}
int main()
{
//允许插入重复值
multiset<int>st{1,5,3,3,3,4,2};//用初始化列表初始化
Show(st);
return 0;
}
set大小和交换
size();//返回容器中元素的数目
empty();//判断容器是否为空
swap(st);//交换两个集合容器template<typename T>
void Show(set<T>& st)
{
for (auto it = st.begin(); it != st.end(); ++it)
{
cout <<(*it)<<" ";
}
cout << endl;
}
int main()
{
set<int>st{1,5,3,4,2};//用初始化列表初始化
if (st.empty())
{
cout << "为空" << endl;
}
else
cout << "不空" << endl;
Show(st);
cout << st.size()<<endl;
set<int>st1{8,1,5,2};
st.swap(st1);
cout << "交换后st：";
Show(st);
cout << "交换后st1：";
Show(st1);
return 0;
}set插入和删除
insert(elem);//在容器中插入元素
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一元素的迭代器
erase(beg,end);//删除区间[beg,end]的所有元素，返回下一元素迭代器
erase(elem);//删除容器中elem值元素 类似list中remove函数
template<typename T>
void Show(set<T>& st)
{
for (auto it = st.begin(); it != st.end(); ++it)
{
cout <<(*it)<<" ";
}
cout << endl;
}
int main()
{
set<int>st{1,5,3,4,2};//用初始化列表初始化
st.insert(15);
Show(st);
st.erase(st.begin(), ++st.begin() );//因为不能随机访问，同样没有重载+或-
Show(st);
st.erase(3);//删除3
Show(st);
return 0;
}set查找和统计
find(key);//查找key是否存在，若存在返回该键的迭代器，不存在返回set.end()位置
count(key);//统计key的元素个数；对于set只有0或1 因为set不允许插入重复数据int main()
{
set<int>st{1,5,3,4,2};//用初始化列表初始化
set<int>::iterator ot = st.find(5);
if (ot != st.end())
{
cout << "找到元素:" << (*ot) << endl;
}
else
cout << "没找到元素:" << (*ot) << endl;
//统计1的个数
cout << st.count(1) << endl;
return 0;
}这是标准库里迭代器部分的内容，简单点说，就是用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保存我们自己想要的排序顺序该如何操作呢？
//set容器默认排序为从小到大,掌握如何改变排序规则
//利用仿函数,可以改变排序规则
#include<iostream>
#include<set>
using namespace std;
//仿函数:用类调用函数
//仿函数设计:
class MyCompare {
public:
//下一行末尾加上const
/*bool operator()(int v1, int v2){
return v1 > v2;
}*/
bool operator()(int v1, int v2)const {
return v1 > v2;
}
};
void test01() {
set<int>s1;
s1.insert(10);
s1.insert(40);
s1.insert(30);
s1.insert(50);
s1.insert(20);
for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
cout << *it << " ";
}
cout << endl;
//指定排序规则为从大到小
//重新指定第一步,更改第二个默认值
//注意:这里第二个默认值需求为类型,不可以是函数(函数名),故使用仿函数
//set<int, greater<int> > s2; // 从大到小排序，也可以这样创建，使用内置的仿函数
set<int,MyCompare>s2;
s2.insert(10);
s2.insert(40);
s2.insert(30);
s2.insert(50);
s2.insert(20);
for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
int main() {
test01();
}对于自定义类型的排序
class Person {
public:
Person(string name, int age) {
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
class comparePerson {
public:
bool operator()(const Person& p1, const Person& p2)const {
//按照年龄 降序
return p1.m_Age > p2.m_Age;
}
};
void test01() {
//自定义数据类型 都会指定排序规则
set<Person, comparePerson>s;
Person p1("刘备", 28);
Person p2("关羽", 26);
Person p3("张飞", 24);
Person p4("马超", 22);
Person p5("赵云", 21);
s.insert(p1);
s.insert(p2);
s.insert(p3);
s.insert(p4);
s.insert(p5);
for (set<Person, comparePerson>::iterator it = s.begin(); it != s.end(); it++) {
cout << "姓名：" << it->m_Name << " " << "年龄:" << it->m_Age << endl;
}
}
int main() {
test01();
return 0;
}有关Pair对组
pair只含有两个元素，可以看作是只有两个元素的结构体。对于成对出现的数据，利用对组可以返回两个数据
应用：
- 代替二元结构体
- 作为map键值对进行插入（下一期会讲map）
在创建pair对象时，必须提供两个类型名，两个对应的类型名的类型不必相同，可以在定义时进行成员初始化。
Pair的创建
创建方式
pair<type,type> p(value1,value2);
pair<type,type> p=make_pair(value1,value2);
头文件
#include<utility>
//1.初始化定义
pair<string,int> p("wangyaqi",1);//带初始值的
pair<string,int> p;//不带初始值的
//2.赋值
p = {"wang",18};
int main()
{
//数据类型 数据
pair<string, int>p("公孙离", 17);
cout << "姓名:" << p.first << " 年岁:" << p.second << endl;
//和结构体类似，first代表第一个元素，second代表第二个元素
pair<string, int>p1=make_pair("钟馗", 47);
cout << "姓名:" << p1.first << " 年岁:" << p1.second << endl;
return 0;
} <utility>头文件中除了提供创建 pair 对象的方法之外，还为 pair 对象重载了 <、<=、>、>=、==、!= 这 6 的运算符，其运算规则是：对于进行比较的 2 个 pair 对象，先比较 pair.first 元素的大小，如果相等则继续比较 pair.second 元素的大小。
注意，对于进行比较的 2 个 pair 对象，其对应的键和值的类型比较相同，否则将没有可比性，同时编译器提示没有相匹配的运算符，即找不到合适的重载运算符。
最后需要指出的是，pair类模板还提供有一个 swap() 成员函数，能够互换 2 个 pair 对象的键值对，其操作成功的前提是这 2 个 pair 对象的键和值的类型要相同。例如：
#include <iostream>
#include <utility> // pair
#include <string> // string
using namespace std;
int main() {
pair <string, int> pair1("pair", 10);
pair <string, int> pair2("pair2", 20);
//交换 pair1 和 pair2 的键值对
pair1.swap(pair2);
cout << "pair1: " << pair1.first << " " << pair1.second << endl;
cout << "pair2: " << pair2.first << " " << pair2.second << endl;
return 0;
}执行结果：
pair1: pair2 20
pair2: pair 10用类模板实现Pair
// 类模板
template <class T1, class T2>
class Pair
{
public:
Pair(T1 k, T2 v):m_key(k),m_value(v) {};
bool operator < (const Pair<T1,T2> & p) const;
private:
T1 m_key;
T2 m_value;
};
// 类模板里成员函数的写法
template <class T1, class T2>
bool Pair<T1,T2>::operator < (const Pair<T1,T2> &p) const
{
return m_value < p.m_value;
}
int main()
{
Pair<string,int> Astudent("Jay",20);
Pair<string,int> Bstudent("Tom",21);
cout << (Astudent < Bstudent) << endl;
return 0;
}
//结果为1 20<21这一期就到此结束了，感谢观看，订阅此专栏。
