网站建设与管理办法,个人网站规划书模板,广东省住房和城乡建设部网站,网站建设成本包括什么本期我们来学习map和set
目录
关联式容器
键值对
pair
树形结构的关联式容器
set
multiset
map
multimap 关联式容器 我们已经接触过 STL 中的部分容器#xff0c;比如#xff1a; vector 、 list 、 deque 、forward_list(C11)等#xff0c;这些容器统称为序列式…本期我们来学习map和set
目录
关联式容器
键值对
pair
树形结构的关联式容器
set
multiset
map
multimap 关联式容器 我们已经接触过 STL 中的部分容器比如 vector 、 list 、 deque 、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那什么是关联式容器它与序列式容器有什么区别 关联式容器 也是用来存储数据的与序列式容器不同的是其 里面存储的是 key, value 结构的 键值对在数据检索时比序列式容器效率更高 键值对 用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量 key 和 value key 代 表键值 value 表示与 key 对应的信息 。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该应该单词在词典中就可以找到与其对应的中文含义。 SGI-STL中关于键值对的定义
pair
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)
{}
};
树形结构的关联式容器 根据应用场景的不桶 STL 总共实现了两种不同结构的管理式容器树型结构与哈希结构。 树型结 构的关联式容器主要有四种 map 、 set 、 multimap 、 multiset 。这四种容器的共同点是使用平衡搜索树( 即红黑树 ) 作为其底层结果容器中的元素是一个有序的序列。下面一依次介绍每一个容器。 set 1. set 是按照一定次序存储元素的容器 2. 在 set 中元素的 value 也标识它 (value 就是 key 类型为 T) 并且每个 value 必须是唯一的。 set 中的元素不能在容器中修改 ( 元素总是 const) 但是可以从容器中插入或删除它们。 3. 在内部 set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行排序。 4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢但它们允许根据顺序对 子集进行直接迭代。 5. set 在底层是用二叉搜索树 ( 红黑树 ) 实现的。 注意 1. 与 map/multimap 不同 map/multimap 中存储的是真正的键值对 key, value set 中只放 value 但在底层实际存放的是由 value, value 构成的键值对。 2. set 中插入元素时只需要插入 value 即可不需要构造键值对。 3. set 中的元素不可以重复 ( 因此可以使用 set 进行去重 ) 。 4. 使用 set 的迭代器遍历 set 中的元素可以得到有序序列 5. set 中的元素默认按照小于来比较 6. set 中查找某个元素时间复杂度为 $log_2 n$ 7. set 中的元素不允许修改 ( 为什么 ?) 8. set 中的底层使用二叉搜索树 ( 红黑树 ) 来实现 我们发现set的模板参数比我们之前学的多了一个compare这是仿函数支持key比较大小的 我们来看它的构造有拷贝构造默认构造以及迭代器区间初始化 set的迭代器是双向迭代器 这里的key_type和value_type都是T这里我们后面会讲
下面我们简单使用一下 使用没什么问题我们在这里还发现一个问题它的输出结果是有序的因为它走的是中序遍历 而且还会去重去重的原理是如果一个值已经有了那就不插入 也可以使用范围for遍历 erase支持迭代器位置值已经迭代器区间 我们根据情况选择即可 如果直接删除值值不存在没什么问题但如果用find先查找的话这里就会报错因为pos不存在 我们再看看这两个find有什么区别一个是set自己的find另一个是算法库里的
set自己的find最多查找高度次时间复杂度是O(longN)而算法库的find是暴力查找是O(N)所以我们最好不要用库里面的 还有一个count这个set这里基本用不到 和find差不多我们传一个元素如果在返回1不在就返回0 find是返回迭代器而count是返回1或者0 还有这三个函数是寻找边界的特殊情况用的我们来看看例子就明白了 比如我们查找30和60itlow得到的就是30而itup是比60大的因为迭代器区间是左闭右开这样就可以和迭代器适配可以保证30到60之间删除包括60 如果我们找35得到的是40lower_bound查找的是的值upper_bound是 equal_range也是一样会查找一个左闭右开的区间
multiset 我们再看这个容器它用起来和set是一样的 它和set的区别就是它允许有重复 如果我们要删除所有的5我们上面的equal_range就是这样使用的 count也是在这里使用这里可以算出有多少个5我们可以认为这两个接口就是专门为multiset设计的set有这两个接口只是为了保持接口一致罢了 当有重复值时find返回的是中序的第一个
equal_range返回的是如果给的值不存在返回的就是不存在的区间
map 1. map 是关联容器它按照特定的次序 ( 按照 key 来比较 ) 存储由键值 key 和值 value 组合而成的元素。 2. 在 map 中键值 key 通常用于排序和惟一地标识元素而值 value 中存储与此键值 key 关联的 内容。键值 key 和值 value 的类型可能不同并且在 map 的内部 key 与 value 通过成员类型 value_type 绑定在一起为其取别名称为 pair: typedef pairconst key, T value_type; 3. 在内部 map 中的元素总是按照键值 key 进行比较排序的。 4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢但 map 允许根据顺序 对元素进行直接迭代 ( 即对 map 中的元素进行迭代时可以得到一个有序的序列 ) 。 5. map 支持下标访问符即在 [] 中放入 key 就可以找到与 key 对应的 value 。 6. map 通常被实现为二叉搜索树 ( 更准确的说平衡二叉搜索树 ( 红黑树 )) 。 map这里也有三个type下面我们简单使用一下 我们先看insert map是kv模型所以使用起来非常麻烦那么可不可以像我们以前那样直接传呢答案是可以的 原因是有make_pair 就像这样这里就是map的插入 当然还可以更简洁一点直接用{ }括起来这是因为C11支持多参数的构造函数隐式类型转换也就是说这种写法在C98是不能用的 接着我们来遍历但是按照我们之前写的遍历这里就出错了原因是pair不支持流插入和流提取 那为什么这里不像我们写的那样直接用key和value而要使用一个pair
原因是operator*返回的话不方便如果直接使用C是不支持返回两个值的所以设计了一个pair结构 所以得这样写 如果觉得上面的写法麻烦还可以用- 大概就是这样 我们之前也说过如果不是编译器优化这里是要有两个箭头的 第一个是运算符重载第二个是访问 也可以用范围for first是不允许修改的second可以修改 如果key相同value不同是不能插入了key相同时不插入不覆盖 也就是插入过程中只比较keyvalue无所谓 erase也是一样只看key在不在 下面我们来看看[ ] 我们来看这个统计次数我们以后就可以直接用map 而且代码可以优化我们可以使用 [ ]
map的[ ] 不是常规的而是给key返回对应的value
后面的我们懂但是水果第一次出现是怎么回事呢 它返回了这么个东西借助了insert的返回值 我们可以看到insert的返回值是一个pair 大致翻译一下这里返回一个pair这个pair的first被设置为迭代器要么指向新插入的元素要么指向和key相等的元素second被设计为true如果key在里面返回false
也就是说key已经在树里面返回pair树里面key所在节点的iterator,false如果key不在树里面返回pair新插入key所在节点的iteratortrue 如果我们自己设计就是这样ret里除了key另一个是匿名对象根据value的变化而变化如果key不在树里面 那就插入成功如果value是int那就是0如果是string就是空的string如果插入失败也没有影响因为insert只看key而return时first是迭代器有了迭代器我们就可以取到second 我们结合起来理解一下水果第一次出现时insertkey是水果value是intint的匿名对象缺省值是0然后返回这个次数一下就变成了1如果有的话那就插入失败再返回次数次数就可以计数了 我们来一步一步看这个 我们经过dict[sort]时是不影响的 这里是可以读的也就是说这里是查找读 经过dict[map]时监视窗口多了一个mapvalue是空的和我们前面看到的一样[ ] 的本质是insert 接着我们修改了value空的value 这次我们修改了insert的value 最后一个就是插入修改了修改空的value [ ] 的功能非常多我们用的时候也就要小心一点
multimap 这个也没啥好说的对于map就和multiset对于set似的就是可以有重复的key
不同的地方在于multimap没有提供operator[ ]所以insert也不一样了不提供pair了插入永远成功其他功能一样
以上即为本期全部内容希望大家可以有所收获
如有错误还请指正
