加强档案网站建设,网络营销产品的整体概念,上海工程相关的公司,绍兴h5建站目录
1.关联式容器和序列式容器
2.键值对
3.树型结构的关联式容器
4.set
5.multiset 6.map 7.multimap 1.关联式容器和序列式容器
set#xff1a;关联式容器——数据之间关联紧密
线性表#xff08;vector#xff0c;list#xff0c;deque#xff09;#xff1a;序…目录
1.关联式容器和序列式容器
2.键值对
3.树型结构的关联式容器
4.set
5.multiset 6.map 7.multimap 1.关联式容器和序列式容器
set关联式容器——数据之间关联紧密
线性表vectorlistdeque序列式容器——数据之间关联性基本为0
2.键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量键值key和对应的信息val
比如现在想要统计十个成语出现的次数那么成语这个字符串和他的次数就有紧密的一一对应关系
第一个模板参数是T1类型就是key的类型第二个是val的类型
键值对是一个类T1和T2的类型允许不同两个成员变量first和second都是公有的 template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1 a, const T2 b) : first(a), second(b){}
};
3.树型结构的关联式容器
根据不同的应用场景STL实现了两种功能不同的管理式容器树型结构和哈希结构
树形结构一般有四种setmapmultisetmultimap
这四种容器的特点是底层结构使用红黑树平衡搜索二叉树中序遍历是有序的
4.set 注意 1. 与map/multimap不同map/multimap中存储的是真正的键值对key, valueset中只放 value但在底层实际存放的是由value, value构成的键值对。 2. set中插入元素时只需要插入value即可不需要构造键值对。 3. set中的元素不可以重复(因此可以使用set进行去重)。 4. 使用set的迭代器遍历有序 5. set中的元素默认按照小于比较 6. set中查找某个元素时间复杂度为logn 7. set中的元素不允许修改随意修改会破坏二叉搜索树的结构 8. set中的底层使用二叉搜索树(红黑树)来实现。 并且看到最后一种初始化方式set可以拷贝构造
set支持迭代器也就是set支持范围for int main()
{int arr[] { 0,12,3,4,5,65,7,1,4,1,4,7,4 };setint s1;for (auto e : arr){s1.insert(e);e;}setint s2(s1);for (auto e : s2){cout e ;e;}return 0;
} 很明显观察到set去重排序
注意set一般不喜欢用push而是使用insert
5.multiset 他也在set的头文件无需新加
他的功能从字面上就是可以允许重复元素
multiset排序
其余和set没区别只是set和multiset都有count函数因为这个计算特殊val个数的函数在头文件set中虽然计数对于set没啥用因为去重但是对于multiset还是很有用 int main()
{int arr[] { 0,12,3,4,5,65,7,1,4,1,4,7,4 };multisetint s1;for (auto e : arr){s1.insert(e);e;}multisetint s2(s1);for (auto e : s2){cout e ;e;}return 0;
}
那么允许重复怎么通过val找到位置答案是找中序的第一个val 那么set/multiset的find和算法库里面的find有什么区别
肯定是原理不同find是暴力查找但是set.find()是按搜索树顺序查找更快 6.map 清楚看到。map的类模板有key的类型val类型和比较函数模板还有空间适配器申请底层空间现在不需要了解
并且map中元素都是成对出现的key值主要是用来排和唯一标识元素而val值主要是存储key值的信息这让我想起来法语的复合时态etre/avoirv. 第一个单词无实意是用来表明时态的过去或者将来之类的而动词的用法常常表明意思这一对组合起来构成map的成员类型他是一个键值对
看两个函数 说明lower_bound是闭区间 upper_bound 是开区间 erase删除的区间也是左闭右开 这段代码的iulow是找小于等于b的元素itup是指找大于‘d’的map中最小的元素
所以最后的结果是 int main()
{std::mapchar, int mymap;std::mapchar, int::iterator itlow, itup;mymap[a] 20;mymap[b] 40;mymap[c] 60;mymap[d] 80;mymap[e] 100;itlow mymap.lower_bound(b); // itlow points to bitup mymap.upper_bound(d); // itup points to e (not d!)mymap.erase(itlow, itup); // erases [itlow,itup)// print content:for (std::mapchar, int::iterator it mymap.begin(); it ! mymap.end(); it)std::cout it-first it-second \n;return 0;
}
看一下map是怎么使用的吧 int main()
{mapstring, string dict;dict.insert(pairstring,string(string,字符串));dict.insert(pairstring, string(left, 左));dict.insert(pairstring, string(is, 是));for (auto e : dict){cout e.first e.second endl;}return 0;
}
但是这样每次自己写pair很繁琐所以以后这种过程可以简化为 这是自己创建map那么对于一个数组我想统计每一个字符串出现的次数怎么看呢
用一个find函数找map中是不是有e对应的字符串find返回值是一个迭代器 迭代器的类型是value_type上面说过就是map的key和val合起来的类型就是pair类 迭代器的second在我的Map就是int类型用来记录每一个字符串出现次数 int main()
{string s[] { 苹果,香蕉,柿子,苹果,香蕉 ,香蕉,柿子,香蕉 };mapstring, int Map;for (auto e : s){auto it Map. find(e);if (it Map.end())Map.insert(make_pair(e, 1));elseit-second;}for (auto e : Map){cout e.first : e.second endl;}return 0;
}但是这样写其实是笨笨的
因为map有一个很神奇的运算符重载就是方括号[ ] 居然一排就搞定了那么这个方括号的作用到底是什么 我们一起慢慢看这段文字
首先方括号的运算符重载函数的参数是key返回值是val
也就是你传入一个key我就给你他的val,并且返回引用具体的值是用默认的构造函数构造的
那如果你给的key不在map里我给你new一个key盛装你传过来的参数
并且他还贴心的告诉我们有一个方括号同样功能的函数at行为一样吗只不过如果你传的key不在map抛异常老操作了之前讲的很多支持下标随机访问的容器也都支持at都是如果不成功那么抛异常
最后看一下他给的一行奇怪原理
他说调用方括号函数的时候是这样调用的 肯定是从内往外看 首先他通过this指针调用insert函数插入一个键值对键值对的key就是你传过来的参数keyval的部分调用一个匿名构造 然后insert有返回值 insert的返回值是一个键值对这个键值对的第一个成员变量first会设置一个迭代器指向新插入的元素或者指向在map中有相同key的元素
第二个成员变量second被设置成bool类型如果这个元素成功插入原来map中没有keysecondtrue否则map存在keysecondfalse 无论如何insert的返回值就是一个键值对也就橙色框现在是一个键值对通过.的方式访问类的first成员变量来到红色框然后解引用找到对应的second返回second的值
验证一下我们的解释 当第一次遇到苹果香蕉柿子的时候second都是false0
再遇到就变成true1因为map中已经有这三个字符串
小小总结这个强大的函数[ ]:
他有三层功能插入查找修改 7.multimap
允许相同的key存在多个不同的val 他的功能和map是一样的但是他不支持[ ]
因为在multimap中一个key可能对应好多个val通过first找second会乱套
他也给我们提供一个很好的思路——一个key可以对应多个val int main()
{//multimap可以录入一个单词的不同意思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;}//同时map可以的功能除了[ ]他也行/string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };multimapstring, int countMap;for (auto e : arr){//mapstring, int::iterator it countMapauto it countMap.find(e);if (it countMap.end())countMap.insert(make_pair(e, 1));elseit-second;}for (const auto kv : countMap)cout kv.first : kv.second endl;return 0;
}
