STL：哈希表和unordered系列容器的封装
一、unordered系列关联式容器的介绍
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是
其底层结构不同（哈希表）
1.1 unordered_map
unordered_map的介绍
1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。
6. 它的迭代器至少是前向迭代器。
7.unordered就是无序的意思
使用细节基本上和map一致
1.2 unordered_set
unordered_set的文档说明
1.3 性能对比
通过一个测试代码来比较unordered_set 和set的效率
void testop() //测试 底层是红黑树和哈希表的效率比对
{
const size_t N = 1000000;
unordered_set us;
set s;
vector v;
v.reserve(N);
srand((unsigned int)time(0));
for (size_t i = 0; i _next) _node = _node->_next;// 如果结点下一个不为空，就去找下一个
else //如果结点的下一个为空，那么就去哈希桶找下一个桶
{
KeyOfT kot;//控制data取出来的是什么
//先算一下自己在当前桶的位置
size_t hashi = _ht->bucket(kot(_node->_data)); //无法访问私有成员 要么用友元 要么封装gettable和getbucketsize这两个函数
++hashi;
while (hashi _buckets.size())
{
if (_ht->_buckets[hashi]) //如果找到了
{
_node = _ht->_buckets[hashi];
break;
}
++hashi; //继续找下一个桶
}
//此时可能有两种情况 一种是成功找到，一种是走到最后都没找到
if (hashi == _ht->_buckets.size()) _node = nullptr;
}
return *this;
}
Self operator++(int)
{
Self temp = *this;
++*this;
return temp;
}
};
// class Pred = equal_to
template
class HashTable
{
typedef HashNode Node;
//友元 为了能够让迭代器访问私有成员table 但是这样会破坏封装性 不推荐使用 还有一种方法是封装一个getbucketsize函数和gettables的函数
template
friend struct _HashIterator;
public:
~HashTable()
{
clear();
}
typedef _HashIterator iterator;
typedef _HashIterator const_iterator;
typedef HashTable Self;
iterator begin() //得找到第一个有效的桶
{
Node* cur = nullptr; //防止全部为空的时候
for (size_t i = 0; i _kv);
// cur = cur->_next;
// }
//}
//_buckets.swap(newht._buckets);
vector newtables(newsize, nullptr);
//将结点一个个解下来放到新表中 （复用的话会创建很多新的结点 其实没有什么必要 ） 所以这里不用第一种方法
for (Node*& cur : _buckets)
while (cur)
{
Node* next = cur->_next;
size_t hashi = bucket(kot(cur->_data)); //重新计算
//头插到新表
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_buckets.swap(newtables);//交换过来
}
size_t hashi = bucket(kot(data)); //只有整形是支持取模的，其他的类型是不一定的
//执行头插的逻辑
Node* newnode = new Node(data);
newnode->_next = _buckets[hashi];
_buckets[hashi] = newnode;//成为新的头
++_n;
return make_pair(iterator(newnode,this),true);
}
iterator Find(const K& key)
{
if (empty()) return end(); //为空 就没啥好找的了
KeyOfT kot;//控制data取出来的是什么
size_t hashi = bucket(key); //找到这个点
Node* cur = _buckets[hashi];
while (cur)
{
if (kot(cur->_data) == key) return iterator(cur, this);
cur = cur->_next;
}
return iterator(nullptr, this);
}
bool Erase(const K& key)
{
Hash hash;//控制模出来的情况 因为可能会是字符串什么的
KeyOfT kot;//控制data取出来的是什么
//这边就不能直接复用find了，因为只是拿到该结点，但是还得从里面删掉才有用
size_t hashi = bucket(key);//找到key对应的桶
Node* prev = nullptr;
Node* cur = _buckets[hashi];
while (cur)
{
if (kot(cur->_data) == key) //执行删除
{
if (prev == nullptr) _buckets[hashi] = cur->_next; //说明第一个就要删
else prev->_next = cur->_next;
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false; //说明找不到
}
void clear() //清空桶中的元素
{
for (Node*& cur : _buckets)
{
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
cur = nullptr;
}
}
size_t size() const //哈希表中的元素个数
{
return _n;
}
bool empty() const
{
return size() == 0;
}
void swap(Self& s)
{
_buckets.swap(s._buckets);
std::swap(_n, s._n);
}
//SGI版本 主要是数学上提到说如果表的长度是素数的话，模的时候更不容易冲突
//但是如果我们正常的扩2倍肯定是难以维持他是素数的，所以就有了这样一个解决方案，专门给了一个素数表 让哈希表的长度按照这个表去更新 这样可以保证长度一直是素数
//SGI版本是这么实现的
size_t GetNextPrime(size_t prime)
{
// SGI
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
}; //实际上是不可能扩到最大的 因为 2^32次方 哪怕是char类型都有4G了 指针都有16G了
/*1Byte（字节）=8bit（位）
1 KB = 1024 Byte
1 MB = 1024 KB
1 GB = 1024 MB
1TB = 1024GB*/
size_t i = 0;
for (; i prime)
return __stl_prime_list[i];
}
return __stl_prime_list[i]; //在表里依次遍历 找到比原先大的那个素数值
}
const size_t MaxBucketSize() const //统计桶的最大长度并返回 检测查找的效率 测试用的 不是刚需
{
size_t max = 0;
for (size_t i = 0; i %zd\n", i, size); //打印所有桶的长度 让我们看到具体的分布情况 这样就可以测出查找的时间复杂度
if (size > max) max = size;
}
return max;
}
size_t bucket(const K& key) const //返回key所在哈希桶的编号
{
Hash hash;//控制模出来的情况 因为可能会是字符串什么的
size_t hashi = hash(key) % _buckets.size(); //找到这个点
return hashi;
}
size_t bucket_size(size_t n) const //返回这个桶有多少个元素
{
Node* cur = _buckets[n];
size_t size = 0;
while (cur)
{
++size;
cur = cur->_next;
}
return size;
}
private:
vector _buckets; //指针数组 哈希桶集合
size_t _n = 0;//记录有效元素的个数
};
字符串哈希函数算法
由于string很常用，所以库里面有默认支持string类型的哈希函数，将哈希函数转化成可以取模的整数
3.2 unordered_set的封装
#pragma once
#include"HashTable.h"
namespace cyx
{
template //不要再Hashtable里面传 会写死 这样自定义类型的key就没有办法解决了
class unordered_set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
~unordered_set()
{
clear();
}
//取类模板的内嵌类型 一定要用typename 不然无法区分这是一个类型还是成员变量
typedef typename HashTable ::const_iterator iterator; //set的迭代器不可被修改
typedef typename HashTable::const_iterator const_iterator;
iterator begin() //普通迭代器转化const迭代器 就会去调用那个拷贝构造
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
pair insert(const K& key)
{
return _ht.Insert(key);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
void clear()
{
_ht.clear();
}
bool empty() const
{
return _ht.empty();
}
private:
HashTable _ht ;
};
}
3.3 unordered_map的封装
#pragma once
#include"HashTable.h"
namespace cyx
{
template
class unordered_map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair& kv) //帮助我们拿到key
{
return kv.first;
}
};
~unordered_map()
{
clear();
}
//取类模板的内嵌类型 一定要用typename 不然无法区分这是一个类型还是成员变量
typedef typename HashTable ::iterator iterator; //pair的key无论什么情况都不能修改 所以我们通过传const K控制
typedef typename HashTable::const_iterator const_iterator;
typedef unordered_map Self;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
const_iterator begin() const
{
return _ht.begin();
}
const_iterator end() const
{
return _ht.end();
}
pair insert(const pair& kv)
{
return _ht.Insert(kv);
}
iterator find(const K& key) const
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase();
}
V& operator[](const K& key) //重载方括号
{
pair ret = insert(make_pair(key, V()));
return ret.first->second;
}
void clear()
{
_ht.clear();
}
bool empty() const
{
return _ht.empty();
}
void swap(Self& s)
{
_ht.swap(s._ht);
}
private:
HashTable _ht;
};
3.4 自定义类型的key
class Date
{
friend struct HashDate; //确保能够访问其私有成员
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
bool operator==(const Date& d) const
{
return _year == d._year
&& _month == d._month
&& _day == d._day;
}
friend ostream& operator
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。
