C++ 头文件系列(unordered_map、unordered_set)
2024-10-10 21:22:03
简介
很明显,这两个头文件分别是map、set头文件对应的unordered版本。 所以它们有一个重要的性质就是:
- 乱序
如何乱序
这个unorder暗示着,这两个头文件中类的底层实现----Hash。 也是因为如此,你才可以在声明这些unordered模版类的时候,传入一个自定义的哈希函数,准确的说是哈希函数子(hash function object)。
具有相同相同哈希值的元素被放在同一个桶(bucket)中。
为何乱序
在提供映射、集合功能的情况下,侧重于元素的快速获取。
用树结构(红黑树、二叉搜索树等)实现的map、set,在查找、获取、修改元素的时候,通常需要从根结点自上而下一次遍历树结构,因此时间复杂度为线性 ; 而通过哈希表实现, 只要哈希函数以及桶的大小选取得当,时间复杂度会是常数(只需要调用一次函数,并进行小幅度的查找)。
单向迭代器
哈希表的实现复杂了该容器上的双向遍历,似乎没有一种合适的方法能够做到高效快速。 因此,unorder版本的map和set只提供前向迭代器(非unorder版本提供双向迭代器)。
少了什么函数
- lower_bound
- upper_bound
普通版本的map和set,它们是有序容器,对每一个元素都能都能判断它应该在哪个之前、在哪个之后; 而该版本的容器则不一样,因为它们是乱序的,不能确定每个元素的先后顺序。 因此,容器没有足够的信息来计算这两个边界(然而元素的相等性比较依旧是可行的)。
多了什么函数
出于实现的概念,该版本的类模版必不可少的多了些特殊的函数。
桶相关(Bucket)
- bucket_count : 桶数量。
- max_bucket_count : 最大桶数量。
- bucket_size : 桶大小,即容量。
- bucket : 定位给定元素的桶位置。
哈希策略
- load_factor : 返回load factor,即容器当前元素数量与桶数量之比。
- max_load_factor : 返回或设置最大load factor。
- rehash : 设置桶的数量,并重新对元素进行哈希映射。
- reserve : 请求保留桶的数量至给定值。
注意到,没有函数能改变桶的容量,可能桶也是动态增长的。
Observers
- hash_function : 返回哈希函数(在声明时作为参数传入,或默认的位于funtional头文件中的hash)。
- key_eq : 返回key的相等性谓词,情况与hash_function相似。
最新文章
- 【Win 10应用开发】使用RichEditBox控件应注意的问题
- ";SQL Server does not handle comparison of NText, Text, Xml, or Image data types.";
- DB2常用sql命令
- springMVC 缓存(入门 spring+mybaties+redis一)
- SQL基本CRUD
- Android进阶之大话设计模式
- javascript二维数组
- 经历:easyui的datagrid没有数据滚动条的显示
- vi 快捷键积累
- Selenium WebDriver java 简单实例
- 【.NET】电话号码打星号(隐藏部分)
- maven项目发布不成功的问题
- ";浏览器端"; 使用 commonjs 模块规范开发网页应用,像开发 node 那样开发网页应用
- Codeforces Round #449 (Div. 2) D. Ithea Plays With Chtholly
- 获得随机N位数不重复数字
- 不可不知 DDoS的攻击原理与防御方法
- 版本管理——git
- UI基础一:简单的BOL查询
- python内置函数每日一学 -- any()
- Sublime Text 2 快捷键(转)
热门文章
- PAT (Advanced Level) 1005. Spell It Right (20)
- BNU OJ 50999 BQG's Approaching Deadline
- Codeforces#363 Div2
- Frequent Distribution sorted by frequency
- EM 期望最大化算法
- mysql连接字符集default
- js Date 日期格式化(转)
- php+socket模拟表单发送请求
- 位图文件(BMP)格式以及Linux下C程序实现(转)
- ORACLE odbc驱动相关