unordered_map和unordered_set底层采用的是哈希桶的数据结构,说白了就是一个指针数组。每个数组单位称为一个桶,这个桶就是一个结点单链表。通过哈希散列函数映射到数组中的具体某个位置后,将数据形成一个新的桶结点插入进单链表。
namespace HASH_BUCKET
{
template<class K, class V, class Hash, class GetKey>
class HashTable;//前置声明
//K:键值
//V:值
//Hash:hash函数
//GetKey:根据V获取key
template<class T>
struct HashNode
{
HashNode(const T& val)
:_data(val)
{
}
HashNode<T>* next = nullptr;
T _data;
};
template<class K, class V, class Hash, class GetKey>
class HashTableIterator
{
typedef typename HashTableIterator<K, V, Hash, GetKey> iterator;
typedef typename HashNode<V> Node;
typedef typename HashTable<K, V, Hash, GetKey> Table;
public:
HashTableIterator(Node* node, Table* table)
:elem(node), _ptable(table)
{
}
iterator operator++()
{
//1.判断当前桶后面是否还有元素
Node* cur = elem->next;
if (!cur)
{
int index = get_key(elem->_data);
while (!cur&&++index < _ptable->_hashtable.size())
cur = _ptable->_hashtable[index];
}
elem = cur;
return *this;
}
V& operator*() const
{
return elem->_data;
}
V* operator->() const
{
return &(operator*());
}
private:
Node* elem;
Table* _ptable;
};
template<class K, class V, class Hash, class GetKey>
class HashTable
{
typedef typename HashTableIterator<K, V, Hash, GetKey> iterator;
typedef typename HashNode<V> Node;
GetKey get_key;
public:
pair<iterator, bool> Insert(const V& _kv)
{
//判断是否需要新表
if (_dataNum == _hashtable.size())
{
HashTable newTable;
int newSize = _hashtable.size() == 0 ? 10 : _hashtable.size() * 2;
newTable._hashtable.resize(newSize);
for (int i = 0; i < _hashtable.size(); ++i)
{
Node* cur = _hashtable[i];
while (cur)
{
newTable.Insert(cur->_data);
newTable._dataNum++;
cur = cur->next;
}
}
_hashtable.swap(newTable._hashtable);
}
//为待插入元素初始化并开辟空间,源码用的是alloc
Node* newNode = new Node(_kv);
//判断插入bucket number
size_t key = get_key(_kv);
int index = HashFunc(key, _hashtable.size());
//头插
Node* head = _hashtable[index];
while (head)
{
if (get_key(head->_data) == get_key(_kv))
{
iterator it(head, this);
return make_pair(it, false);
}
head = head->next;
}
newNode->next = _hashtable[index];
_hashtable[index] = newNode;
++_dataNum;
iterator it(newNode, this);
return make_pair(it, true);
}
iterator Find(const K& key)
{
int index = HashFunc(key, _hashtable.size());
Node* cur = _hashtable[index];
while (cur)
{
if (get_key(cur->_data) == key)
return iterator(cur,this);
++cur;
}
return end();
}
bool Erase(K& key)
{
int index = HashFunc(key, _hashtable.size());
Node* cur = _hashtable[index];
Node* prev = cur;
while (cur)
{
if (get_key(cur->_data) == key)
{
if (cur == _hashtable[index])
_hashtable[index] = nullptr;
else
prev->next = cur->next;
delete cur;
return true;
}
prev = cur;
cur = prev->next;
}
return false;
}
bool Erase(iterator& it)
{
K key = get_key(it.elem->_data);
return Erase(key);
}
iterator& operator [](const K& key)
{
if (_hashtable[get_key(key)] != nullptr)
return iterator(_hashtable[get_key(key)], this);
else
return end();
}
//哈希散列函数
size_t HashFunc(const K& key, size_t size)
{
Hash hash;
return hash(key) % size;
}
iterator begin()
{
for (int i = 0; i < _hashtable.size(); i++)
if (_hashtable[i])
return iterator(_hashtable[i], this);
return end();
}
iterator end()
{
return iterator(0, this);
}
void clear()
{
for (int i = 0; i < _hashtable.size(); i++)
{
while (_hashtable[i])
{
cur = _hashtable[i];
_hashtable[i] = cur->next;
delete cur;
}
}
}
private:
vector<Node*> _hashtable;
//记录当前哈希桶中数据个数。
size_t _dataNum = 0;
};
}
namespace lei
{
template<class K, class V, class Hash = _Hash<K>, class GetKey = _Select<pair<K, V>>>
class unordered_set;//前置声明
template<class V>
struct _Select
{
size_t operator()(const V& value)
{
return value;
}
};
template<class K>
struct _Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct _Hash<string>
{
size_t operator()(const string& str)
{
int sum = 0;
for (int i = 0; i < str.size(); i++)
{
sum = sum + sum * 131 + str[i];
}
return sum;
}
};
template<class K, class Hash = _Hash<K>, class GetKey = _Select<K>>
class unordered_set
{
public:
typedef HASH_BUCKET::HashTable<K, pair<K, K>, Hash, GetKey> HashSet;
typedef typename HASH_BUCKET::HashTableIterator < K, pair<K, K>, Hash, GetKey> Iterator;
public:
size_t size() const
{
return _set._dataNum;
}
size_t bucket_count() const
{
return _set._hashtable.size();
}
bool empty() const
{
return _set._dataNum == 0;
}
Iterator begin()
{
return _set.begin();
}
Iterator end()
{
return _set.end();
}
pair<Iterator, bool> insert(const pair<K, K>& _kv)
{
return _set.Insert(_kv);
}
bool erase(const K& key)
{
return _set.Erase(key);
}
bool erase(Iterator& it)
{
return _set.Erase(it);
}
void clear()
{
return _set.clear();
}
private:
HashSet _set;
};
}
namespace lei
{
template<class K, class V, class Hash = _Hash<K>, class GetKey = _Select<pair<K, V>>>
class unordered_map;//前置声明
template<class V>
struct _Select
{
size_t operator()(const V& value)
{
return value.first;
}
};
template<class K>
struct _Hash
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct _Hash<string>
{
size_t operator()(const string& str)
{
int sum = 0;
for (int i = 0; i < str.size(); i++)
{
sum = sum + sum * 131 + str[i];
}
return sum;
}
};
template<class K, class V, class Hash = _Hash<K>, class GetKey = _Select<pair<K,V>>>
class unordered_map
{
public:
typedef HASH_BUCKET::HashTable<K, pair<K,V>, Hash, GetKey> HashMap;
typedef typename HASH_BUCKET::HashTableIterator < K, pair<K, V>, Hash, GetKey> Iterator;
public:
size_t size() const
{
return _map._dataNum;
}
size_t bucket_count() const
{
return _map._hashtable.size();
}
bool empty() const
{
return _map._dataNum == 0;
}
Iterator begin()
{
return _map.begin();
}
Iterator end()
{
return _map.end();
}
pair<Iterator, bool> insert(const pair<K, V>& _kv)
{
return _map.Insert(_kv);
}
bool erase(const K& key)
{
return _map.Erase(key);
}
bool erase(Iterator& it)
{
return _map.Erase(it);
}
void clear()
{
return _map.clear();
}
private:
HashMap _map;
};
}
文章浏览阅读1.2k次。关注了就能看到更多这么棒的文章哦~An attic for LibreOffice OnlineBy Jonathan CorbetJanuary 27, 2022DeepL assist..._collabora online局域网
文章浏览阅读2.5k次。关键是小,才几十M。针对只是浏览、看图,这绝对是很好的工具。 它是最专业的2D/3D CAD查看器,编辑器和转换器。支持30多种光栅和矢量图形格式,包括AutoCAD DWG, DXF, DWF, Hewlett-Packard HPGL, PLT, HGL, CGM, SVG, IGES/IGS, STEP/STP, STL, 3DS, TIFF, BMP, JPG, GIF等图像格式,并可以精确的调整图像或转换其它文件格式。程序具有批处理功能。作为一个多用途的程序,它有着拖放图象..._abviewer
文章浏览阅读836次。HTML:超文本标记语言(hypertext marker language)_head first html and css第一版
文章浏览阅读82次。MSM--Memcached_Session_Manager介绍及使用 我们都知道对于一些大型的web2.0的网站,在正式部署时一般是部署在不同故障域的多台应用服务器上,以j2ee应用为例,一般我们都会部署在tomcat下,假如我们部署了10台tomcat服务器,那这10台t..._transcoderfactoryclass="de.javakaffee.web.msm.serializer.javolution.javoluti
文章浏览阅读9.5k次,点赞20次,收藏137次。二叉树详解_二叉树c语言
文章浏览阅读320次。How Many Numbers? IIClick here to get problem.Problem Description:We want to find the numbers higher or equal than 1000 that the sum of every four consecutives digits cannot be higher than a certai..._how many numbers
文章浏览阅读383次。原帖地址:http://blog.csdn.net/phunxm/article/details/42174937/仅供我个人收藏学习,原博主如不同意请联系qq651263878进行删除,在此表示感谢以及歉意。1.iPhone尺寸规格后续上市的iPhone7以及iPhone7plus 与六代相同1 inch = 2.54cm = 25.4mm上表中的宽高(width/height)为手机的物理尺..._ios html注入屏幕尺寸适配
文章浏览阅读7.8k次。之前部署完成的网站今天却无法打开,浏览器报出错误:未能从程序集“System.ServiceModel, Version=3.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089”中加载类型“System.ServiceModel.Activation.HttpModule”。根据提示分析应该是前几天安装了高版本的.net fr..._未能从程序集“system.servicemodel, version=3.0.0.0, culture=neutral, publick
文章浏览阅读584次。UWB的带宽很宽,多径分辨能力强,能够分辨并剔除大部分多径干扰信号的影响,得到精度很高的定位结果。3)电磁兼容性强:UWB 的发射功率低,信号带宽宽,能够很好地隐蔽在其它类型信号和环境噪声之中,传统的接收机无法识别和接收,必须采用与发射端一致的扩频码脉冲序列才能进行解调,所以不会对其他通信业务造成干扰,同时也能够避免其他通信设备对其造成干扰。现在比较常用的A-GNSS,是通过陆基的移动通信网络,传送增强改正数据,提供辅助信息,加强和加快卫星导航信号的搜索跟踪性能和速度,缩短定位时间,提高定位精度。_uwb技术
文章浏览阅读339次。function dirs($path) { if(!is_dir($path)) { return null; } $dh = opendir($path); while(($row=readdir($dh))!=false) { if(($row==".") || ($row=="..")) { con_php遍历创建文件夹和文件
文章浏览阅读6.7k次,点赞4次,收藏28次。win10 + ubuntu16.04 双系统 无法进入ubuntu遇到问题参考链接遇到问题U盘成功安装之后,电脑重启直接进入到window10中,开机没有grub界面(选择哪个操作系统),解决过程在BIOS设置中Secure > Secure Boot选择Disable后,还是未解决由于我的电脑BIOS是UEFI, 下载EasyUEFI 来修复引导,但发现除了window boot manage 之外都是处于 禁用 隐藏状态,即使按照教程之后,添加新的引导项之后,重启之后还是进入wind_双系统无法进入ubuntu
文章浏览阅读260次。一、关于搜索引擎各位知道,搜索程序一般由索引链及搜索组件组成。索引链功能的实现需要按照几个独立的步骤依次完成:检索原始内容、根据原始内容来创建对应的文档、对创建的文档进行索引。搜索组件用于接收用户的查询请求并返回相应结果,一般由用户接口、构建可编程查询语句的方法、查询语句执行引擎及结果展示组件组成。著名的开源程序Lucene是为索引组件,它提供了搜索程序的核心索引和搜索模块,例..._elasticsearch的工作原理