关联式容器:是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的 键值对,在数据检索时比序列式容器效率更高。
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代 表键值,value表示与key对应的信息
根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结
构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使
用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一
个容器。
set
set是按照一定次序存储元素的容器(升序)
set在底层是用二叉搜索树(红黑树)实现的。
set也支持迭代器访问
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
set也和之前学习过的容器一样支持一些接口
不同的是,set不支持修改元素,(因为会改变原来的次序)只可以插入删除
此外因为set底层是二叉搜索树,所以他的查找效率很高
set<int> s;
s.insert(4);
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(2);
s.insert(2);
set<int>::iterator it = s.find(3);
if (it != s.end())
{
//cout << *it << endl;
s.erase(it);//删除迭代器指向的值,这个值必须存在
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
s.erase(1);//在就删除,不在就不做处理
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
如果想要删除某个区间,你不应该用find(),应该使用lower_bound upper_bound
//删除区间 [) 左闭右开
//删除1-5这个区间
auto start = s.lower_bound(1); //val>=1
auto finish = s.upper_bound(5);//val>5
s.erase(start, finish);
此外,set中的元素是去重后的,及如果插入了两个5,它只会保留第一个
multiset (不去重的set)
不去重的二叉搜索树,利用count()接口可以统计相同元素的个数,find()接口查找的是相同元素中第一个被插入的值
void text_set4()
{
multiset<int> s;//不去重的搜索二叉树
s.insert(2);
s.insert(4);
s.insert(1);
s.insert(3);
s.insert(7);
s.insert(5);
s.insert(5);
s.insert(5);
s.insert(5);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
cout << s.count(5) << endl;//5的个数
auto it = s.find(5);//找的第一个5
while (it != s.end())//从第一个5开始打印
{
cout << *it << " ";
it++;
}
cout << endl;
}
他的接口以set一样
map
map的底层也是搜索二叉树,和set的不同是,map里面存的是两个值,一个值是用来排次序的,和set中的值一样,当时另一个值是用来关联的
并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:
也就是说map里面的元素是用结构体模版pair封装起来的,第一个元素取名为first 第二个元素取名为second
所以在map中插入元素的时候不可以直接这样插入
所以他的插入应该是这样的:
void map_text1()
{
map<string, string> m;
m.insert(pair<string,string>( "sort", "排序") );
//或者
pair<string, string> kv ("string", "字符串");
m.insert(kv);
//或者
m.insert({ "return","返回" });//隐式类型转换
//或者
m.insert(make_pair("int", "整形"));
}
迭代器访问:
那么右应该如何通过迭代器指针去访问到元素呢
map<string, string>::iterator it = m.begin();
while (it != m.end())
{
cout << (*it).first << (*it).second << endl;
it++;
}
cout << endl;
map<string, string>::iterator itt = m.begin();
while (itt != m.end())
{
cout << itt->first << itt->second << endl;
itt++;
}
cout << endl;
运行结果:
因为控制序列的是first的值,map和sety一样也会只保留first值相同的一个值,所以即使second值相同,只要first的值不相同,那么就可以插入进去,反之则值插入访问的第一个值
范围扩打印
mulitmap
mulitmap和setmulitset一样他也支持key(first)的重复
map中的【】运算符重载
首先我们来用map统计水果出现的次数
void map_text3()
{
string arr[] = { "苹果","香蕉","草莓","苹果",
"香蕉","草莓" ,"苹果","香蕉","草莓" };
map<string, int> hun;
for (auto e : arr)
{
map<string, int>::iterator it = hun.find(e);
if (it != hun.end())//找到key时并没有到最后结束
{
it->second++;
}
else//到最后都没有出现,说用该水果是第一次出现直接插入
{
hun.insert(make_pair(e, 1));
}
}
for (auto& kv : hun)
{
cout << kv.first << kv.second << endl;
}
cout << endl;
}
然而我们发现map里面有一个【】运算符的重载
我们用【】就可以实现数量的统计
这是为什么呢
首先我们来看【】的底层实现
关于map的运用:
给定一个链表,每个结点包含一个额外增加的随机指针,该指针可以指向链表中的任何结点
或空结点。
要求返回这个链表的深度拷贝。链表的深拷贝
set的运用:可以达到排序和去重的目的找交集和差集
两个数组的交集