石河子市建设局网站,网站建设销售话术开场白,网站建设合作伙伴,网址域名大全每一个不曾起舞的日子都是对生命的辜负 map和setmap和set一.关联式容器二.set2.1 set的介绍2.2 set的使用1.set的模板参数列表2.set的构造3.set的迭代器4.set修改操作5.bound函数三.multiset四.map3.1 map的介绍3.2 map的使用1.map的模板参数说明2.pair的介绍3.map的[]重载五.m… 每一个不曾起舞的日子都是对生命的辜负 map和setmap和set一.关联式容器二.set2.1 set的介绍2.2 set的使用1.set的模板参数列表2.set的构造3.set的迭代器4.set修改操作5.bound函数三.multiset四.map3.1 map的介绍3.2 map的使用1.map的模板参数说明2.pair的介绍3.map的[]重载五.multimapmap和set
本节目标 关联式容器 键值对 树形结构的关联式容器
一.关联式容器 在初阶阶段我们已经接触过STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 键值对 用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。 树形结构的关联式容器 根据应用场景的不桶STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。**树型结构的关联式容器主要有四种map、set、multimap、multiset。**这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。 二.set
2.1 set的介绍 set的底层为二叉搜索树也就是上一节中所实现的不过在此之上set作为容器来说封装了和以前的vector、list、deque相关的迭代器、运算符重载等方便我们去进行一系列的操作。 仍然是需要看文档
set - C Reference (cplusplus.com) 可以发现这与之前我们所学的容器的方法几乎差不多。只不过有了些许特征 set是按照一定次序存储元素的容器在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。set没有[]重载。
注意
与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放value但在底层实际存放的是由value, value构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。et中的元素不可以重复(二叉搜索树中重复则不会插入并且返回false因此可以使用set进行去重)。使用set的迭代器遍历set中的元素可以得到有序序列set中的元素默认按照小于来比较set中查找某个元素时间复杂度为log2nlog_2 nlog2n 实际上是二叉搜索树的高度次set中的元素不允许修改(为什么?)set中的底层使用二叉搜索树(红黑树)来实现。
2.2 set的使用
头文件当然是#includeset
1.set的模板参数列表 T: set中存放元素的类型实际在底层存储value, value的键值对。 **Compare**set中元素默认按照小于来比较 **Alloc**set中元素空间的管理方式使用STL提供的空间配置器管理 对于Compare来说利用仿函数默认小于就是默认按照升序去处理的即上一讲中的二叉搜索树中序从小到大。 2.set的构造
函数声明功能介绍set (const Compare comp Compare(), const Allocator Allocator() );构造空的setset (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() );用[first, last)区间中的元素构造setset ( const setKey,Compare,Allocator x);set的拷贝构造
3.set的迭代器
对于set的迭代器和之前的vector、list相同有正向迭代器、反向迭代器、const迭代器。名称都是一样的。 容量的函数也是如此就不一一展示了看上面文档就行如果知道vector、list的容量函数也可以不看。 4.set修改操作
pairiterator,bool insert (const value_type x )在set中插入元素x实际插入的是x, x构成的键值对如果插入成功返回该元素在set中的位置true,如果插入失败说明x在set中已经存在返回x在set中的位置falsevoid erase ( iterator position )删除set中position位置上的元素size_type erase ( constkey_type x )删除set中值为x的元素返回删除的元素的个数void erase ( iterator first,iterator last )删除set中[first, last)区间中的元素void swap (setKey,Compare,Allocatorst );交换set中的元素实际上只需交换搜索树根节点的指针iterator find ( constkey_type x ) const返回set中值为x的元素的位置size_type count ( constkey_type x ) const返回set中值为x的元素的个数对于第一个pair,实际上就是KV模型下面会展示。erase的重载也没什么交换函数值得一提的是由于底层是二叉搜索树因此swap只需交换根节点的指针。对于find,count, 由于set是去重的元素因此上面提到的返回位置以及元素个数并不需要在意因为每一个元素都是唯一的。而也有不唯一的容器multisetmultiset只排序不去重下面讲这个的时候会知道返回位置是中序遍历的第一个。 演示1
#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);setint::iterator it s.begin();//auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s)//范围for底层就是迭代器{cout e ;}cout endl;auto pos s.find(3); //这个更快因为借用搜索树的特性//auto pos find(s.begin(), s.end(), 3);//底层实现不一样这个是暴力查找if (pos ! s.end()){s.erase(pos);}cout s.erase(1) endl;cout s.erase(3) endl;s.erase(1);s.erase(1);for (auto e : s)//范围for底层就是迭代器{cout e ;}cout endl;
}
int main()
{test_set1();return 0;
}演示2 5.bound函数
在文档中发现有两个函数lower_boundupper_bound这两个实际上也是迭代器类型传入的只有一个参数同样是左闭右开传值之后可以标记对应的位置
int main()
{setint myset;setint::iterator itlow, itup;for (int i 1; i 10; i){myset.insert(i * 10);//10 20 30 40 50 60 70 80 90 }itlow myset.lower_bound(35);itup myset.upper_bound(70);myset.erase(itlow, itup);for (setint::iterator it myset.begin(); it ! myset.end(); it){cout *it;}cout endl;return 0;
}可见对于erase也有迭代器为参数的重载函数此外通过bound类型的迭代器可以保存位置。即便没有该元素同样可以标记因为元素是有序。 如果把70变成75itup同样会得到80的位置所以upper_bound返回的是大于该位置的边界可以对标end()而lower_bound对标begin返回的是大于等于的边界。这就非常方便获得一个左闭右开的范围。但这个东西实际上用的不多。 三.multiset
与set不同的是multiset虽然会排序但并不会进行去重因此是由重复值的存在的。底层仍然是二叉搜索树。
#includeiostream
#includeset
#includestring
using namespace std;
void test_set2()
{multisetint s;//单纯排序没有去重s.insert(3);s.insert(1);s.insert(4);s.insert(7);s.insert(2);s.insert(1);s.insert(1);s.insert(1);s.insert(3);cout s.count(1) endl;//1的数量for (auto e : s)//范围for底层就是迭代器{cout e ;}cout endl;
}
int main()
{test_set2();return 0;
} 需要注意的是查找的返回值是中序遍历的第一个。 四.map
3.1 map的介绍 map的底层当然也是二叉搜索树但就好比set是K模型一样map就是上篇二叉搜索树提到的KV模型即一一对应的方式。 文档说明
www.cplusplus.com
. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair typedef pairconst key, T value_type;在内部map中的元素总是按照键值key进行比较排序的map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。map支持下标访问符即在[]中放入key就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
3.2 map的使用
头文件当然是#includemap
1.map的模板参数说明 key: 键值对中key的类型 T 键值对中value的类型 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) **Alloc**通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器 而对于map的构造迭代器的一些与之前的容器使用方式相同就不展示了需要可以自行查看文档。 2.pair的介绍
我们需要知道pair first就是Keysecond是Value。就是KV模型的结构。在搜索树定义的时候我们是直接定义了两个变量类型KV。那为什么需要pair这个东西将两个值放在一起呢实际上是为了map能够更方便的操作举个例子对于map,如果是迭代器访问返回的时候不可能返回两个参数这时候以pair为参数的函数就派上用场了直接返回pair类型就好了。
、
但pair类型也不支持流插入所以就需要一个一个的访问
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));//make_pair是一个函数模板//mapstring, string::iterator it dict.begin();auto it dict.begin();//这样方便while (it ! dict.end()){//cout *it endl;//pair不支持流插入因此这样不行//cout (*it).first : (*it).second endl; //这样可以cout it-first : it-second endl;//返回的是数据的地址/指针it;}cout endl;for (const auto kv : dict)//注意加引用不加就是拷贝构造代价大{cout kv.first : kv.second endl;}return 0;
}3.map的[]重载
如果想通过map统计水果出现的次数可以这样
int main()
{//map统计水果操作的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓, 西瓜,苹果, 苹果,西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;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;}return 0;
}但这样看起来麻烦很多实际上可以通过这种方式
int main()
{//map统计水果操作的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓, 西瓜,苹果, 苹果,西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (const auto kv : countMap)//注意加引用不加就是拷贝构造代价大{cout kv.first : kv.second endl;}return 0;
}方括号支持的是随机访问而对于这个括号来说括号里的实际上是key,countMap[e]就是value。 上面所标注的就是map[]重载的返回值发现还有insert的操作所以我们应该先知道insert的返回值
发现insert返回类型为pairiterator, bool类型看看文档是如何说明的
因此我们可以将最上面的map重载的返回值进行解释了可以转化成这样了
V operator[](const K k)
{pairiterator, bool ret insert(make_pair(k, V()));return ret.first-second;
}这样我们就知道operator返回的就是mapstring, int的第二个参数并且是引用返回所以map的映射关系就是这样的。 可以看出Cmap的[]有很多功能 插入修改查找 因此了解底层之后我们也可以直接这样写
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));//make_pair是一个函数模板dict[迭代器] iterator; // 插入修改dict[insert];//单纯的插入默认构造的va为//dict.insert(pairstring, string(左边, XXX));//这样会插入失败因为已经有了左边dict[insert] 插入;//修改cout dict[左边] endl;// 查找//key在就是查找不在就是插入return 0;
}因此用[]代替insert很方便而且对于已有的key如果想再插入相同的key无论对应的value是否相同都不能成功因为pairiterator, bool对应的bool会返回false。如果想修改指定key的value就用[]。 对于词典来说由于一词多义key和value也可能不是一一映射的关系有可能是一个key对应多个value这个时候可以这样mapstring, vectorstring除此之外也可以利用multimap下面将会提到。 再次说明map中用pair保存值。 五.multimap
和multset一样multimap与map相比也是不会进行去重只是有序。
那继续看一下用multimap完成上面说的”一词多义“
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{multimapstring, string dict;dict.insert(pairstring, string(left, 左边));dict.insert(pairstring, string(left, 剩余));dict.insert(pairstring, string(string, 字符串));dict.insert(pairstring, string(left, xxx));for (const auto kv : dict){cout kv.first : kv.second endl;}return 0;
}multimap是不支持[]重载的文档里面也没有
multimap - C Reference (cplusplus.com)
但multimap同样可以统计次数因为下面的方式是先find再加入或者值。
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{string arr[] { 苹果, 西瓜, 香蕉, 草莓, 西瓜,苹果, 苹果,西瓜,苹果, 香蕉, 苹果, 香蕉 };multimapstring, int countMap;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;}return 0;
}这样也可以统计次数。
