欧美做视频网站,网站建设swot,wordpress添加栏目,wordpress没有安装主题选项卡目录#xff1a; 什么是关联式容器#xff1f;键值对树形结构的关联式容器 set的概念multiset的使用pair和make_pair map的概念用“[]”实现统计水果的次数 multimap的使用 什么是关联式容器#xff1f;
在初阶阶段#xff0c;我们已经接触过STL中的部分容器#xff0c;比… 目录 什么是关联式容器键值对树形结构的关联式容器 set的概念multiset的使用pair和make_pair map的概念用“[]”实现统计水果的次数 multimap的使用 什么是关联式容器
在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那关联式容器又是什么呢其实关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。
键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。
树形结构的关联式容器
根据应用场景的不同STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。
set的概念
定义 set是关联容器也就是按照一定次序存储元素的容器 T: set中存放元素的类型实际在底层存储value, value的键值对。 Compareset中元素默认按照小于来比较 Allocset中元素空间的管理方式使用STL提供的空间配置器管理
我们可以通过cplusplus网站查到set的一些成员函数 网站点击进入 代码实现一个set:
#includeiostream
#includeset
using namespace std;void test_set1()
{setint s;s.insert(3);s.insert(1);s.insert(4);s.insert(7);s.insert(2);s.insert(1);//排序去重auto it s.begin();//关联式容器的迭代器 it//setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;//auto pos s.find(3);auto pos find(s.begin(), s.end(), 3);//算法里的find也能查找,因为find写的是一个模板,底层是迭代器实现的但是效率不高if (pos ! s.end()){s.erase(pos);//找到pos删除}//s.erase(1) endl;//给值删除cout s.erase(1) endl;//对于基于值的版本该函数返回擦除的元素数量 cout s.erase(3) endl;//对于基于值的版本该函数返回擦除的元素数量 for (auto e : s){cout e ;} cout endl;
}
int main()
{test_set1();return 0;
}输出结果 第一行结果通过运行我们看到第一行的输出结果是按照升序排序并且数据不重复我们插入insert的是两个1输出一个1说明set底层按照二叉搜索树走中序进行了排序并且还去重。 第二行结果为了方便我们也可以用范围for来输出结果因为范围for的底层也是迭代器实现的。 erase删除元素的时候函数会返回擦除的元素数量0表示找到pos位置的元素并删除了1表示pos没有去找还在元素是直接删除的。
总结
与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素可以得到有序序列set中的元素默认按照小于来比较set中查找某个元素时间复杂度为:(O)logN,也就是说查找一千个元素找10次、一百万个元素找20次、10亿个元素才找30次左右set中的元素不允许修改(为什么?)set中的底层使用二叉搜索树(红黑树)来实现的并且左右两边比较均衡因为二叉搜索树有退化成单支的情况所以准确来说底层是平衡二叉搜索树来实现的
multiset的使用
定义: multiset是按照特定顺序存储元素的容器其中元素是可以重复的。 代码实现
void test_set2()
{multisetint s;//multiset允许冗余排序s.insert(3);s.insert(3);s.insert(3);s.insert(1);s.insert(4);s.insert(3);s.insert(7);s.insert(3);s.insert(2);s.insert(1);auto it s.begin();//关联式容器的迭代器 it
//setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;auto pos s.find(3);//multiset从第一个3开始查找while (pos ! s.end()){cout *pos ;pos;}cout endl;
} 从上面的运行结果我们不难看出multiset支持键值冗余可以排序我们用find查找的时候只需要找到第一个3往后面走(pos)就能找到所有的3。
总结
multiset中再底层中存储的是value, value的键值对mtltiset的插入接口中只需要插入即可与set的区别是multiset中的元素可以重复set是中value是唯一的使用迭代器对multiset中的元素进行遍历可以得到有序的序列multiset中的元素不能修改在multiset中找某个元素时间复杂度为:O(logN)multiset的作用可以对元素进行排序 lower_bound、upper_bound和equal_range的使用 lower_bound(val)返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。 upper_bound(val)返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定则该方法返回的是 const 类型的双向迭代器。 equal_range返回一个区域的边界该区域包含容器中等效于 val 的所有元素。由于 set 容器中的所有元素都是唯一的因此返回的范围最多包含一个元素。 #includeiostream
using namespace std;
#includeset
int main()
{setint myset;//定义一个名为myset的关联式容器setint::iterator itlow, itup;for (int i 1; i 10; i)myset.insert(i * 10);//itlow myset.lower_bound(30);itlow myset.lower_bound(35);//itup myset.upper_bound(60);//myset.erase(itlow, itup);//迭代给的区间是左闭右开cout myset contains:;for (setint::iterator it myset.begin(); it ! myset.end(); it)//查询或者遍历set中的元素时可以用到iterator迭代器cout *it;cout \n;return 0;
}我们给的是下限val是35上限是val60那么会删除[40-70)的值域区间是左闭右开也就是删除40、50和60。
#include set
#includeiostream
using namespace std;
int main()
{std::setint myset;for (int i 1; i 5; i) myset.insert(i * 10); // myset: 10 20 30 40 50std::pairstd::setint::const_iterator, std::setint::const_iterator ret;ret myset.equal_range(30);std::cout the lower bound points to: *ret.first \n;std::cout the upper bound points to: *ret.second \n;return 0;
}这里我们用到了pair下面会讲pair的用法该函数返回一对其成员first是范围的下限与 lower_bound 相同second 是上限与 upper_bound 相同。因此equal_range只需要设定一个val就可以了那么这个set也可以说是指向元素的双向迭代器类型。
pair和make_pair
pair:此类将一对值耦合在一起这些值可能属于不同类型的因为pair的底层是struct实现的,不是class所以可以直接使用pair的成员变量first和second ,也就是说当一个函数需要返回2个数据的时候这2个数据可以是不同类型可以选择pair。 简单实现一下
#includeiostream
#includeset
using namespace std;
int main()
{//pair对象pairint, double p1;p1.first 1;p1.second 2.5;cout p1.first p1.second endl;return 0;}make_pair:模板类型可以从传递给的参数隐式推导,如果包含不同类型的其他对象是隐式可转换的则可以从包含不同类型的其他对象构造对象(利用make_pair创建新的pair对象) 简单实现一下
#includeiostream
#includeset
using namespace std;
int main()
{pairint, double p1;p1 make_pair(1, 1.5);cout p1.first p1.second endl;int a 10;string m loquot;pairint, string newObj;newObj make_pair(a, m);cout newObj.first newObj.second endl;system(pause);return 0;
}map的概念
定义map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。 实现map并统计出水果的次数
#includeiostream
#includemap
#includeset
#includestring
using namespace std;
int main()
{mapstring, string dict;//定义一个字典dict.insert(pairstring, string(排序, sort));dict.insert(pairstring, string(左边, left));dict.insert(pairstring, string(右边, right));dict.insert(make_pair(字符串, string));dict[迭代器] iterator;//插入修改dict[insert];//插入dict.insert(pairstring, string(左边, ***));//插入失败,搜索树只compare keydict[insert] 插入;//修改cout dict[左边] endl;//查找 //key在就是查找不在就是插入//mapstring, string::iterator it dict.begin();dict.insert(make_pair(字符串, string));auto it dict.begin();//while (it ! dict.end()) //{ // //cout(*it).first (*it).second endl;// //pair不支持流插入,struct类型没有访问限定符可以直接获取it的元素// cout it-first: it-second endl;// //类型是结构体的时候第一个箭头返回的是数据的指针第二个箭头访问这个值两个箭头不好看编译器做了处理省略了一个箭头// it;//} //统计次数for (const auto kv : dict){//dict的每一个值是pair,pair里的每一个值是string,不加引用就是string的拷贝构造代价太大cout kv.first : kv.second endl;//*it的元素赋值给了kv}string arr[] { 苹果,西瓜,香蕉,草莓,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉 };mapstring, int countMap;//mapstring,int::iterator itcountMap;
//for (auto e : arr){auto it countMap.find(e);//查找水果if (it countMap.end())//没有{countMap.insert(make_pair(e, 1));}else {it-second;//次数加加}}for (const auto kv : countMap){//dict的每一个值是pair,pair里的每一个值是string,不加引用就是string的拷贝构造代价太大cout kv.first : kv.second endl;//*it的元素赋值给了kv}return 0;}map中方括号[]的功能有三点 1.插入 2.修改 3.查找
用“[]”实现统计水果的次数
#includeiostream
#includemap
#includeset
#includestring
using namespace std;
int main()
{mapstring, string dict;//定义一个字典auto it dict.begin();//统计次数for (const auto kv : dict){//dict的每一个值是pair,pair里的每一个值是string,不加引用就是string的拷贝构造代价太大cout kv.first : kv.second endl;//*it的元素赋值给了kv}string arr[] { 苹果,西瓜,香蕉,草莓,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉 };mapstring, int countMap;
//用方括号也能实现统计次数
for (auto e : arr)
{countMap[e];
}
for (const auto kv : countMap)
{cout kv.first : kv.second endl;//*it的元素赋值给了kv}cout endl;return 0;
}总结
map中的的元素是键值对map中的key是唯一的并且不能修改默认按照小于的方式对key进行比较map中的元素如果用迭代器去遍历可以得到一个有序的序列map的底层为平衡搜索树(红黑树)查找效率比较高 O ( l o g 2 N ) O(log_2 N) O(log2N)支持[]操作符operator[]中实际进行插入查找
multimap的使用
定义multimap是多重映射是关联容器用于存储由键值和映射值的组合形成的元素遵循特定顺序并且多个元素可以具有等效的键,和multiset一样支持冗余。 #includeiostream
#includemap
#includeset
#includestring
using namespace std;
int main()
{multimapstring, string dict;dict.insert(make_pair(left, 左边));dict.insert(make_pair(left, 剩余));dict.insert(make_pair(string, 字符串));dict.insert(make_pair(left, xxx));for (const auto kv :dict){cout kv.first : kv.second endl; }string arr[] { 苹果,西瓜,香蕉,草莓,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉 };multimapstring, int countMap;//mapstring,int::iterator itcountMap;for (auto e : arr){auto it countMap.find(e);//查找水果if (it countMap.end())//没有{countMap.insert(make_pair(e, 1));}else{it-second;//次数加加}}for (const auto kv : countMap){cout kv.first : kv.second endl;//*it的元素赋值给了kv}cout endl;system(pause);return 0;}通过结果我们看到使用multimap也能很好的统计出水果出现的次数因为muitmap支持键值冗余我们使用的成员函数find会先查找此类水果有没有出现有就加加次数不会再反复insert没有我没再insert然后再加加次数。
