【STL】关联容器 — hash_set

【STL】关联容器 — hash_set

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

容器hash_set是以hash table为底层机制的,差点儿所有的操作都是转调用hash table提供的接口。因为插入无法存储同样的键值,所以hash_set的插入操作所有都使用hash table的insert_unique接口,代码例如以下:

pair<iterator, bool> insert(const value_type& obj)
{
    pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
    return pair<iterator, bool>(p.first, p.second);
}

再看一下一个构造函数:
private:
  typedef hashtable<Value, Value, HashFcn, identity<Value>, 
                    EqualKey, Alloc> ht;
  ht rep;   // 底层机制——hash table
 
public:
  hash_set() : rep(100, hasher(), key_equal()) {}   // 默认大小为100

这里把hash table的表格大小,也就是vector大小设置为了100,那么在初始化hash table时,会自己主动选择最接近的质数为197。也就是说一開始hash_set便拥有了197个“桶”。

以下来比較一下set和hash_set的异同:
set的底层机制为红黑树,hash_set的底层机制为hash table,两者都能进行高效率的搜索。红黑树利用了二叉搜索树的特性,而hash table则利用散列技术。
但红黑树有自己主动排序功能而hash table没有,反映出来的结果就是,set的元素有自己主动排序功能而hash_set没有。以下是測试代码:

#include <iostream>
#include <hash_set>
 
using namespace std;
using namespace __gnu_cxx;
 
int main()
{
    hash_set<int> set;
 
    set.insert(3);
    set.insert(196);
    set.insert(1);
    set.insert(389);
    set.insert(194);
    set.insert(387);
 
    hash_set<int>::iterator iter = set.begin();
 
    for ( ; iter != set.end(); ++iter)
        cout << *iter << ' ';
 
    return 0;
}

执行结果:

【STL】关联容器 — hash_set


因为有197个桶,所以元素1、194、387被散列到1号桶;3、196、389被散列到3号桶。但新元素是插入到每一个桶指向的链表的前端,所以就有了这种输出顺序。

參考:
《STL源代码剖析》 P270.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118071.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 概率(Probability)的定义和性质

    描述性定义:在相同的条件下,独立重复地做NNN次试验,当试验次数NNN很大时,如果事件AAA发生的频率fN(A)fN(A)f_N(A)稳定地在[0,1][0,1][0,1]内的某一个数值ppp,而且一般来说随着试验次数的增多,这种摆动的幅度会越来越小,则称数值ppp为事件AAA发生的概率,记为P(A)=pP(A)=pP(A)=p…

  • 在 RT-Thread Nano 上添加控制台与 FinSH

    在 RT-Thread Nano 上添加控制台与 FinSH本片文档分为两部分:第一部分是实现UART控制台,该部分只需要实现两个数即可完成UART控制台打印功能。第二部分是实现移植FinSH组件,实现在控制台输入命令调试系统,该部分…

  • 查看mysql日志命令_linux查看mysql安装路径

    查看mysql日志命令_linux查看mysql安装路径centos是linux吗_网站服务器运行维护centos是一个基于RedHatLinux提供的可自由使用源代码的企业级Linux发行版本,它是来自于RedHatEnterpriseLinux依照开放源代码规定释出的源代码所编译而成。Linux中MySQL日志在哪Linux中MySQL日志一般保存在/var/log/目录下,但还需要看具体的配置文件才能确定,具体方法如下:1、首先登陆…

    2022年10月14日
  • 联想拯救者y7000按键功能_联想Y7000P屏幕闪现白色横条

    联想拯救者y7000按键功能_联想Y7000P屏幕闪现白色横条前阶段买了一个拯救者Y7000P,记录一下功能键的使用:1、一些基本的使用就不详细说了Fn+F1-F11(音量亮度调节等等):其中Fn+F4是关闭开启麦克风,Fn+F7是用来设置扩展屏幕的场景Fn+F9进入设置界面Fn+F10关闭开启摄像头Fn+F11关闭开启触摸板开启关闭切换键盘灯:Fn+Space(空格)切换三种工作模式:Fn+Q键开启关闭屏幕上的Y字logo:Fn+L键2、Fn+Q切换的三种模式:(切换时需接通电源)安静模式:

  • pytest的使用_实例调用和类调用

    pytest的使用_实例调用和类调用Pytest执行用例规则Pytest在命令行中支持多种方式来运行和选择测试用例1.对某个目录下所有的用例pytest2.对模块中进行测试pytesttest_mod.py3.对文件夹进行

  • 拼多多买手机可靠不_官网买手机可靠吗

    拼多多买手机可靠不_官网买手机可靠吗拼多多,经过短短几年的发展,现如今一跃成为国内排名前三的网店,但因为开店门槛较低,所以导致假冒伪劣商品层出不穷,前些年还被人们戏称为山寨品集中营,因此拼多多给人们留下的印象并不好,那么在拼多多买手机靠谱吗?笔者2019年曾在拼多多帮朋友买过一部iPhoneXSMax,过程如下:9月22号晚上,在拼多多某店铺下单(当时正好有百亿补贴活动)9月23号下午,显示手机已经出单,到了晚上的时候就能看到物流信息了,发的是顺丰9月24号中午,快递送达,取回家以后就进行了拆机,查验三码合一,全.

    2022年10月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号