【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)


相关推荐

  • 在某个范围内随机生成一些数据_cut out删除造句

    在某个范围内随机生成一些数据_cut out删除造句根据yolov4文献中提到的cutout数据增广方式,进行扩展阅读。Cutout&RandomErasing1、Cutout论文地址:https://arxiv.org/pdf/1708.04552.pdf代码地址:https://github.com/Dingzixiang/cutout/blob/master/cutout.py出发点:文章的出发点除了解决遮挡问题外,还有从dropout上得到启发。众所周知…

  • python2 nonlocal_python关键字及用法

    python2 nonlocal_python关键字及用法python变量引用顺序:从当前作用域开始寻找变量,如果没找到就往上一层作用域寻找,没找到就再上一层……即:当前作用域局部变量-&gt;外层作用域变量-&gt;再外层作用域变量-&gt;……-&gt;当前模块全局变量-&gt;pyhton内置变量global:全局变量nonlocal:外层嵌套函数的变量使用总结:局部作用域改变全局变量用global,global同时还可以定义新的…

  • vscode快捷键重置及快捷键恢复

    vscode快捷键重置及快捷键恢复在用vscode设置快捷键的时候,有的快捷键和自己设置的有重复和冲突现象,为了图方便我把与自己冲突的快捷键都删除了,结果导致键盘的删除按键用不了,相当于自己写的代码无法删除了。最后还是在官网上找到解决办法。 首先找到键盘快捷设置 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20191128152918849.png) ![在这里插入图片描述](http…

  • CentOS7 安装以太坊 geth 客户端、创建私有区块链及挖矿

    CentOS7 安装以太坊 geth 客户端、创建私有区块链及挖矿安装以太坊源码,即安装GoEthereum(安装Geth)1、安装Golang可以直接使用yum这个包管理器安装Golangyuminstallgolang2、下载以太坊源码(GoEthereum)首先下载geth源码go-ethereum,这里以go-ethereum-1.9.7.tar.gz,直接在GitHub下载3、安装以太坊源码(安装Geth)接下来解压源码:tar-xzfgo-ethereum-1.9.7.tar.gz用下…

  • Node.js

    Node.js

  • Linux命令之解压缩:tar、zip、rar 命令

    Linux命令之解压缩:tar、zip、rar 命令一、简介解压缩是一个常用的操作,在Linux中通常比较常用的是tar命令,zip和rar命令则是Windows中比较常用。二、快速使用1.tar命令语法:tar[主选项+辅选项]文件或目录示例:#压缩文件file1和目录dir2到test.tar.gztar-zcvftest.tar.gzfile1dir2#…

发表回复

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

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