广州电子商城网站建设,公司注册官方网站,网站建设佰首选金手指七,郑州网站服务外包公司目录
一、关联式容器
二、键值对
三、树形结构的关联式容器
四、set的介绍及使用
4.1 set的介绍
4.2 set的使用
五、multiset的介绍及使用
六、map的介绍和使用
6.1 map的介绍
6.2 map的使用
七、multimap的介绍和使用 一、关联式容器 前面已经接触过 STL 中的部分…目录
一、关联式容器
二、键值对
三、树形结构的关联式容器
四、set的介绍及使用
4.1 set的介绍
4.2 set的使用
五、multiset的介绍及使用
六、map的介绍和使用
6.1 map的介绍
6.2 map的使用
七、multimap的介绍和使用 一、关联式容器 前面已经接触过 STL 中的部分容器比如vector、list、deque等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身
什么是关联式容器 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是 key, value 结构的键值对在数据检索时比序列式容器效率更高 set 和 map 便是关联式容器
二、键值对
什么是键值对 键值对是用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息 比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义 在 set 和 map 就使用了键值对这个键值对名为 pair他是一个 struct 定义的类模板即可以在外部访问 pair 里面的成员变量 SGI-STL中关于键值对的定义如下
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){}
};
pair文档介绍pair - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/utility/pair/?kwpair
成员类型介绍如下 如何使用 pair 下面介绍 set 和 map 再解释
三、树形结构的关联式容器 根据应用场景的不同STL总共实现了两种不同结构的管理式容器树型结构与哈希结构 树型结构的关联式容器主要有四种map、set、multimap、multiset这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列 四、set的介绍及使用
4.1 set的介绍
set文档介绍set - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/set/?kwset 翻译如下 set是按照一定次序存储元素的容器在set中元素的 value 也标识它(value就是key类型为T)并且每个value 必须是唯一的。set 中的元素不能在容器中修改(元素总是 const)但是可以从容器中插入或删除它们在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢但它们允许根据顺序对子集进行直接迭代set 在底层是用二叉搜索树(红黑树)实现的 set 的模板参数有三个 第三个模板参数 class Alloc allocatorT 是空间配置器不用理会第二个模板参数 class Compare lessT 是仿函数平时不用理会使用缺省值即可前面也介绍过了有需要再传参set 中元素默认按照小于来比较第一个模板参数 class T 是 set 中存放元素的类型实际在底层存储 value, value 的键值对注意 与 map/multimap 不同map/multimap 中存储的是真正的键值对 key, valueset/multiset 中只放 value但在底层实际存放的是由value, value构成的键值对set 中插入元素时只需要插入value 即可不需要构造键值对即 set/multiset 为 K模型map/multimap 为 KV模型使用set要包含头文件
#include set
注意set中的元素不可以重复(因此可以使用set进行去重)
4.2 set的使用
先介绍一下set的前四个成员类型 key_type 是第一个模板参数即Tvalue_type 也是第一个模板参数T value_type 对应键值对 pair 的第一个模板参数T1value_type 对应键值对 pair 的第一个模板参数T2即 key_typevalue_typekey_compare 是第二个模板参数Comparekey_compare 也是第二个模板参数Comparekey_compare 和 value_compare 也是键值对与上面类似1set 的构造函数 set 提供的构造函数有第一个空构造和 第二个迭代器区间构造一般都使用空构造第三个是拷贝构造函数
测试代码
void Test_Set()
{setint s1;//空构造setint s2(s1.begin(), s1.end());//区间构造setint s3(s1);//拷贝构造
}
2赋值重载 测试代码
void Test_Set()
{setint s1;//空构造setint s2(s1);//拷贝构造setint s3;s3 s1;//赋值重载
}
析构函数这个就不介绍了程序结束自动调用
4Iterators 使用 set 的迭代器遍历set中的元素可以得到有序序列 5 Capacity 6Modifiers set中的元素不允许修改 7find set 中查找某个元素时间复杂度为logN 以上接口都与之前学的容器接口用法大致相同就不再演示了
五、multiset的介绍及使用
multiset的文档介绍multiset - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/multiset/ 翻译 multiset是按照特定顺序存储元素的容器其中元素是可以重复的在multiset中元素的value也会识别它(因为multiset中本身存储的就是value, value组成的键值对因此value本身就是keykey就是value类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列multiset底层结构为二叉搜索树(红黑树)模板参数和成员类型与set一致不解释了
注意 multiset中再底层中存储的是value, value的键值对mtltiset的插入接口中只需要插入即可与set的区别是multiset中的元素可以重复set 是中value是唯一的使用迭代器对multiset中的元素进行遍历可以得到有序的序列multiset中的元素不能修改在multiset中找某个元素时间复杂度为O(logN)multiset的作用可以对元素进行排序multiset 的使用与 set一致最大区别就是set去重排序multiset元素可重复排序 注意查找的元素是相同元素的时候返回的是中序遇到相同的第一个元素的迭代器
使用 multiset 要包含头文件
#include set
六、map的介绍和使用
6.1 map的介绍
map的文档介绍map - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/map/map/?kwmap
翻译 map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与 value通过成员类型 value_type 绑定在一起为其取别名称为 pairtypedef pairconst Key, T value_type在内部map中的元素总是按照键值key进行比较排序的map中通过键值访问单个元素的速度通常比 unordered_map 容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列) map支持下标访问符即在[]中放入key就可以找到与key对应的 valuemap通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))map 的模板参数有4个 第四个模板参数 class Alloc allocatorpairconst Key, T 是空间配置器现在不用理会第三个模板参数 class Compare lessKey 是仿函数平时不用理会使用缺省值即可前面也介绍过了有需要再传参默认按照小于来比较第二个模板参数 class T 是键值对中 value 的类型第二个模板参数 class Key 是键值对中 key 的类型
注意Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
使用 map 需要包含头文件
#include map
注意map 也是去重排序
6.2 map的使用
先介绍 map成员类型 key_type 是第一个模板参数Keymapped_type 是第二个模板参数Tvalue_type 是 pairconst key_type, mapped_type 进行 typedef 得到的key_compare 是第三个模板参数Compare比较的是 key_typeKey缺省值为 lessvalue_compare 是用于比较元素的嵌套函数类
map接口跟 set差不多但是 map多了随机访问的接口对 map很重要下面介绍
1构造函数 测试代码
void Test_Map()
{//KV模型通过 Key查找Value//mapKey, Valuemapint, char m1;//空构造mapint, string m2;//空构造mapint, char m3(m1.begin(), m1.end());//区间构造mapint, char m4(m1);//拷贝构造
} 2赋值重载 void Test_Map()
{mapint, char m1;//空构造mapint, char m2(m1);//拷贝构造//赋值重载mapint, char m3;m3 m1;
}
析构函数自动调用不解释
3Iterators 支持迭代器则支持范围 for
测试代码
void Test_Map()
{mapint, char m1;//空构造//插入数据。后面解释m1.insert(make_pair(1, a));m1.insert(make_pair(2, b));m1.insert(make_pair(3, c));m1.insert(make_pair(4, d));m1.insert(make_pair(4, d));//key已存在则不插入map去重//遍历//mapint, char::iterator it m1.begin();auto it m1.begin();while (it ! m1.end()){//通过Key查找Value//first是Keysecond是ValueKV模型//键值对 pairT1, T2 --- pairfirst, secondcout it-first -- it-second endl;it;}cout endl;//范围forfor (auto e : m1)//建议加上引用否则数据大量的时候会带来拷贝大的代价{cout e.first -- e.second endl;}
}
运行结果 4Capacity 一个判空和一个返回数据的大小就不演示了
5Modifiers swap 和 clear 不演示了下面介绍 insert 和 erase erase接口如下 常用就是传 Key 删除节点不多解释
insert 接口如下 最常用就是第一个问题来了pairiterator, bool 是什么
先看 insert 接口解释 参数类型 value_type 是 pairconst key_type, mapped_type 进行 typedef 得到的也就是说参数是一个键值对并使用引用传参insert 第一个框起来的的返回类型为 pairiterator, boolpairiterator, bool 第一个iteratior是迭代器第二个是 bool用于反映是否插入成功成功返回true否则返回false如果插入成功即元素不存在进行插入返回为 pairiterator, true迭代器返回的是新插入元素位置的迭代器pair如果插入失败即元素已经存在返回为 pairiterator, false迭代器返回的是已存在元素位置的迭代器pair注这个对下面理解 [] 很重要
测试代码
void Test_Map()
{mapint, char m1;//空构造//插入也要指明键值对的类型 pairT1, T2m1.insert(pairint, char(1, a));m1.insert(pairint, char(2, b));// pairT1, T2 也可以写成 make_pairm1.insert(make_pair(3, c));m1.insert(make_pair(4, d));m1.insert(make_pair(4, d));//key已存在则不插入map去重for (auto e : m1)//建议加上引用否则数据大量的时候会带来拷贝大的代价{cout e.first -- e.second endl;}
}
运行结果 解释一下 make_pair make_pair 是一个模板函数在 pair 的文档有介绍 make_pair 定义如下: 简单来说这个函数的功能就像是给 pairT1, T2 进行 typedef 为 make_pair直接使用即可 注pairT1, T2x, y是一个匿名对象
下面解释 map的随机访问
6Element access
接口如下 operator[] 接口定义如下 operator[] 访问的条件是只需传入第一个模板参数即 Key 的值也就是说 [] 访问是通过 Key 来进行访问的
operator[] 详情如下 翻译 如果kKey与容器中元素的键匹配即Key存在则函数返回对其映射值的引用即返回 Key 值的引用如果kKey与容器中任何元素的键不匹配即Key不存在函数将插入具有该键的新元素并返回对其映射值的引用即返回 新插入 Key 值的引用注意即使没有为元素分配映射值即不给T传值T为空该元素使用其默认构造函数构造插入新元素后这会将容器大小增加1at 成员函数功能与 [] 类似但是在具有键的元素存在时具有相同的行为即查找的元素 Key 是存在的时候at 和 [] 的功能是一样的但在不存在时抛出异常即查找的 Key 不存在[] 的功能是把这个 Key 直接插入map中但是 at 是抛异常不会进行插入总结 [] 的功能是 查找修改插入 修改的原因是 [] 返回 mapped_typeT值的引用at 的功能是 查找修改不支持插入[] 等价于 (*((this-insert(make_pair(k, mapped_type()))).first)).second make_pair(k, mapped_type()) 第一个参数kKey为 pair 第一个模板参数T1第二个参数 mapped_type() 是一个匿名对象为 pair 第二个模板参数T2mapped_type 是 map 第二个模板参数T即T()
(*((this-insert( make_pair(k, mapped_type()) )).first)).secondmake_pair(k, mapped_type()) make_pair 返回的类型是 pairT1, T2make_pair 返回 pairT1, T2insert 进行接收 把 pairT1, T2 x, y作为insert 的参数即参数 const value_type val 也就是说
(*((this-insert( make_pair(k, mapped_type()) )).first)).second
可以转换为方便理解
mapped_type operator[] (const key_type k)
{return (*((this-insert( make_pair(k, mapped_type()) )).first)).second
}---
T operator[](const Key k)
{pairiterator,bool ret insert( make_pair(k, T());//insert 返回 pairiterator,bool//迭代器在pair的first的位置即用 . 可以访问pair的成员变量 first//迭代器内容访问方式为 -//- 操作符的重载前面篇章有过解释return ret.first-second;
}
假设给你一个 string要统计水果出现的次数
string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };
可以使用map进行统计代码如下
void Test_Map()
{//统计水果出现的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap1;for (auto e : arr){//mapstring, int::iterator it countMapauto it countMap1.find(e);if (it countMap1.end())//没有就进行插入{countMap1.insert(make_pair(e, 1));}else{it-second;}}for (const auto kv : countMap1){cout kv.first : kv.second endl;}cout endl;//使用 []mapstring, int countMap2;for (auto e : arr){//不存在则插入//[] 的功能是 查找修改插入//operator[]的原理是// 用key, T()构造一个键值对然后调用insert()函数将该键值对插入到map中// 如果key已经存在插入失败insert函数返回该key所在位置的迭代器// 如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器// operator[]函数最后将insert返回值键值对中的value返回countMap2[e];}for (const auto kv : countMap2){cout kv.first : kv.second endl;}
}
运行结果 总结 map中的的元素是键值对map中的key是唯一的并且不能修改默认按照小于的方式对key进行比较map中的元素如果用迭代器去遍历可以得到一个有序的序列map的底层为平衡搜索树(红黑树)查找效率logNmap支持[]操作符operator[]中实际进行插入查找 7 find 直接使用就不解释了不懂看文档
七、multimap的介绍和使用
multimap文档的介绍multimap - C Reference (cplusplus.com)https://legacy.cplusplus.com/reference/map/multimap/
翻译 Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对key,value其中多个键值对之间的key是可以重复的在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起value_type是组合key和value的键值对: typedef pairconst Key, T value_type;在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对key进行排序的multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列multimap在底层用二叉搜索树(红黑树)来实现注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的 multimap的使用和map一致就不解释了 注意 multimap中没有重载 operator[] 操作因为 multimap 的 Key 可能不唯一使用时与map包含的头文件相同----------------我是分割线---------------
文章到这里就结束了下一篇即将更新
