本文介绍 C++ STL 中 unordered_set 和 unordered_map 的基本使用方法，包括插入、查找、删除等操作。详细讲解了底层哈希表节点的改造、迭代器的实现原理（包括 ++ 操作符处理桶遍历）、以及 key 值获取仿函数的设计。通过对比 set 和 unordered_set 的性能测试，展示了哈希表在大数据量下的 O(1) 时间复杂度优势。最后提供了完整的模拟实现代码，涵盖 HashTable、iterator 及容器封装。
#include <iostream>
#include <unordered_set>
using namespace std;
void test1() {
unordered_set<int> st;
st.insert(1);
st.insert(3);
st.insert(2);
st.insert(4);
unordered_set<int>::iterator it = st.begin();
while (it != st.end()) {
cout << *it << " ";
++it;
}
cout << endl;
it = st.find(3);
if (it != st.end()) cout << *it << "存在" << endl;
st.erase(1);
if (st.count(1)) cout << "1存在" << endl;
}
// unordered_set 的负载因子最大是 1
void test2() {
unordered_set<int> st;
st.insert(1);
st.insert(3);
st.insert(2);
st.insert(4);
cout << st.load_factor() << endl; //0.5
cout << st.max_load_factor() << endl; //1
st.insert(6);
st.insert(8);
cout << st.load_factor() << endl; //0.75
cout << st.max_load_factor() << endl; //1
st.insert(5);
st.insert(7);
cout << st.load_factor() << endl; //1
cout << st.max_load_factor() << endl; //1
}
void test3() {
unordered_set<int> st;
for (int i = 0; i < 100000; i++) st.insert(rand() + i);
cout << "当前桶数：" << st.bucket_count() << endl;
cout << "最大桶数：" << st.max_bucket_count() << endl;
// 安全的检查桶大小
if (33 < st.bucket_count()) {
cout << "33 号桶的大小：" << st.bucket_size(33) << endl;
}
// 安全的查找元素 33
auto it = st.find(33);
if (it != st.end()) {
cout << "元素 33 在桶" << st.bucket(33) << "中" << endl;
} else {
cout << "元素 33 不存在" << endl;
}
}
int main() {
test1();
test2();
test3();
return 0;
}
#include <iostream>
#include <unordered_map>
using namespace std;
void test1() {
unordered_map<int, int> mp;
mp.insert(make_pair(1, 1));
mp.insert(make_pair(5, 5));
mp.insert(make_pair(2, 2));
mp.insert(make_pair(4, 4));
mp.insert(make_pair(3, 3));
unordered_map<int, int>::iterator it = mp.begin();
while (it != mp.end()) {
cout << it->first << ":" << it->second << endl;
it++;
}
it = mp.find(3);
if (it != mp.end()) {
cout << "找到了 " << it->first << ":" << it->second << endl;
}
mp.erase(it);
if (!mp.count(3)) {
cout << "没有找到 3" << endl;
}
mp[3] = 5;
cout << mp[3] << endl;
}
void test2() {
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
unordered_map<string, int> mp;
for (auto& e : arr) {
unordered_map<string, int>::iterator ret = mp.find(e);
if (ret != mp.end()) {
ret->second++;
} else {
mp.insert(make_pair(e, 1));
}
}
for (auto& e : mp) {
cout << e.first << " " << e.second << endl;
}
}
int main() {
test1();
test2();
return 0;
}
模拟实现的整体思路与 set & map 的模拟实现非常类似，因此很多相同的地方就不过多展开介绍了。
底层哈希桶并不知道封装自己的是 unordered_map 还是 unordered_set，因此将数据类型设为 T。
template<class T> class HashNode {
public:
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data), _next(nullptr) {}
};
哈希表的迭代器依旧是一个类，类中封装了节点指针，从而使得迭代器对象可以模拟指针的行为。
template<class T, class Ref, class Ptr> struct __HTIterator {
typedef HashNode<T> Node;
typedef __HTIterator<T, Ref, Ptr> self;
Node* _node;
__HTIterator(Node* node) :_node(node) { }
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
bool operator!=(const self& s) { return _node != s._node; }
};
重点来了，迭代器++如何实现？迭代器++的本质是找下一个节点，而哈希表中如何找当前节点的下一个节点呢？由于我们底层使用的是哈希桶结构，因此找下一个节点分为两种情况：
_node = _node->_next;_tables 数组。因此我们需要在迭代器中再加入一个成员，那就是哈希表：HashTable<K, T, KeyOfT, Hash>* _pht。
因此我们需要将 哈希表的模版参数全部加到 迭代器的模版参数上。
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator {
//哈希表迭代器的 3 个成员变量
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
size_t _hashi; //当前节点所在桶的编号
};
此时我们在编译的时候会报错，因为迭代器类 是位于 哈希表类之前的，而迭代器类中也用到了 哈希表类，会有"相互依赖的"问题，也就是编译器在编译 迭代器类的代码时还不认识 哈希表呢，因此需要在迭代器类之前添加哈希表前置声明：
//迭代器和哈希表相互依赖，需要前置声明
template<class K, class T, class KeyOfT, class Hash> class HashTable;
此外，由于我们在迭代器内部会使用到 哈希表的 私有成员_tables，因此还需要将 迭代器类声明为 哈希表的 友元类：
template<class K, class T, class KeyOfT, class Hash> class HashTable {
//迭代器内部用到了 哈希表的私有成员 _tables，需要友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
};
operator++：如果下一个节点为空，需要寻找下一个有元素的桶，因此还需要知道当前桶的编号，我们可以通过下面一行代码来计算出当前桶的编号，但确实比较麻烦，因此我们在迭代器中再加入一个成员：当前节点所在桶的编号：_hashi。
size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();
那么在构造迭代器时就需要初始化三个成员。
__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi) :_node(node), _pht(pht), _hashi(hashi) { }
operator++ 的实现如下：
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else //当前桶遍历完了，寻找下一个有元素的桶
{
_hashi++;
while (_hashi < _pht->_tables.size()) {
if (_pht->_tables[_hashi]) {
_node = _pht->_tables[_hashi];
break;
}
_hashi++;
}
if (_hashi == _pht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
注：需要说明的是我们提供的迭代器访问顺序是 按照桶的编号顺序，而库中迭代器访问顺序是 按照元素的插入顺序。
template<class K, class T, class KeyOfT, class Hash> class HashTable {
typedef HashNode<T> Node;
//迭代器内部用到了 哈希表的私有成员 _tables，需要友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
public:
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator; //普通迭代器
typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator; //const 迭代器
public:
//迭代器接口
iterator begin() //返回第一个桶的第一个元素
{
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) {
return iterator(_tables[i], this, i);
}
}
return end();
}
iterator end() {
return iterator(nullptr, this, -1);
}
const_iterator begin() const {
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) {
return const_iterator(_tables[i], this, i);
}
}
return end();
}
const_iterator end() const {
return const_iterator(nullptr, this, -1);
}
};
注意，此时编译会有问题，const 版本的 begin 和 end 接口在返回的时候 构造迭代器 会有权限放大的问题。因此我们将构造函数的参数以及 _pht 成员都加上 const。
**unordered_set：**内部元素不能修改，因此无论是 普通迭代器，还是 const 迭代器，底层封装的都是哈希表的 const 迭代器。
namespace dck {
template<class K, class Hash = HashFunc<K>> class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) { return key; }
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
**unordered_map：**普通迭代器的 key 不能修改，value 可以修改，const 迭代器 的 key 和 value 都不能修改，因此 普通迭代器底层是哈希表的普通迭代器，const 迭代器底层是哈希表的 const 的 迭代器，给 pair 中的 key 带上 const 确保无论是普通迭代器还是 const 迭代器，key 都无法修改。
namespace dck {
template<class K, class V, class Hash = HashFunc<K>> class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
哈希表的 Find 接口的返回值我们需要从 bool 改造成 iterator，也要在需要用到 key 的地方将仿函数套上去
iterator Find(const K& key) {
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) return iterator(cur, this, hashi);
cur = cur->_next;
}
return end();
}
unordered_set / unordered_map 的 find 接口：
iterator find(const K& key) { return _ht.Find(key); }
哈希表的 Insert 接口的返回值我们需要从 bool 改造成 pair<iterator，bool>，也要在需要用到 key 的地方将仿函数套上去
pair<iterator, bool> Insert(const T& data) {
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end()) return make_pair(it, false);
Hash hf;
if (_n == _tables.size()) //哈希桶的负载因子我们设置为 1
{
size_t newSize = _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
//头插新节点
size_t hashi = hf(kot(data)) % _tables.size();
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return make_pair(iterator(newNode, this, hashi), true);
}
unordered_map 的 insert 接口：
pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
unordered_set 的 insert 接口：
pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }
注意，unordered_set 的 insert 接口 采用上面这种写法会直接编译报错。正确的写法：使用返回的 普通迭代器的三个成员变量构造出 const 迭代器即可。
pair<iterator, bool> insert(const K& key) {
auto ret = _ht.Insert(key);
return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
}
bool Erase(const K& key) {
Hash hf;
size_t hashi = hf(key) % _tables.size(); // 映射位置
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr) // 处理删除第一个节点的情况
{
_tables[hashi] = cur->_next;
}
else {
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
unordered_set / unordered_map 的 erase 接口：
iterator erase(const K& key) { return _ht.Erase(key); }
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
#include <unordered_set>
#include "MyUnorderedSet.h"
#include "MyUnorderedMap.h"
void test_unordered_set() {
dck::unordered_set<int> st;
st.insert(4);
st.insert(1);
st.insert(2);
st.insert(3);
dck::unordered_set<int>::iterator it = st.begin();
while (it != st.end()) {
cout << *it << " ";
++it;
}
cout << endl;
//1 2 3 4 (我们自己迭代器的实现按照桶的顺序）
unordered_set<int> st1;
st1.insert(4);
st1.insert(1);
st1.insert(2);
st1.insert(3);
unordered_set<int>::iterator it1 = st1.begin();
while (it1 != st1.end()) {
cout << *it1 << " ";
//4 1 2 3 (库中迭代器的实现按照插入顺序)
++it1;
}
cout << endl;
}
//测试 unordered_map 的 const 迭代器
void print(const dck::unordered_map<int, int>& mp) {
dck::unordered_map<int, int>::const_iterator it = mp.begin();
while (it != mp.end()) {
cout << it->first << " " << it->second << endl;
++it;
}
cout << endl;
}
void test_unordered_map() {
dck::unordered_map<int, int> mp;
mp.insert(make_pair(4, 4));
mp.insert(make_pair(1, 1));
mp.insert(make_pair(2, 2));
mp.insert(make_pair(3, 3));
print(mp);
dck::unordered_map<int, int>::iterator it = mp.begin();
while (it != mp.end()) {
it->first++; //err
it->second++;
cout << it->first << " " << it->second << endl;
++it;
}
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
dck::unordered_map<string, int> countMap;
for (auto x : arr) countMap[x]++;
for (auto t : countMap) {
cout << t.first << " " << t.second << endl;
}
cout << endl;
}
int main() {
test_unordered_set();
test_unordered_map();
return 0;
}
哈希桶中提供 Some 接口测试 哈希桶使用情况、最大桶长度、平均桶长度等指标。
void Some() {
size_t bucketSize = 0;
size_t maxBucketLen = 0;
size_t sum = 0;
double averageBucketLen = 0;
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
if (cur) {
++bucketSize;
}
size_t bucketLen = 0;
while (cur) {
++bucketLen;
cur = cur->_next;
}
sum += bucketLen;
if (bucketLen > maxBucketLen) {
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)sum / (double)bucketSize;
printf("all bucketSize:%d\n", _tables.size()); //表的大小
printf("bucketSize:%d\n", bucketSize); //使用了多少个桶
printf("maxBucketLen:%d\n", maxBucketLen); //最长的桶挂了多少个元素
printf("averageBucketLen:%lf\n\n", averageBucketLen); //平均桶长度
}
#include <set>
#include <unordered_set>
#include "HashTable.h"
void test() {
const size_t N = 1000000;
unordered_set<int> us;
set<int> s;
hash_bucket::HashTable<int, int> ht;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; ++i) {
//v.push_back(rand()); // N 比较大时，重复值比较多
v.push_back(rand() + i); // 重复值相对少
//v.push_back(i); // 没有重复，有序
}
// 21:15
size_t begin1 = clock();
for (auto e : v) {
s.insert(e);
}
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << endl;
size_t begin2 = clock();
for (auto e : v) {
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
size_t begin10 = clock();
for (auto e : v) {
ht.Insert(make_pair(e, e));
}
size_t end10 = clock();
cout << "HashTbale insert:" << end10 - begin10 << endl << endl;
size_t begin3 = clock();
for (auto e : v) {
s.find(e);
}
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << endl;
size_t begin4 = clock();
for (auto e : v) {
us.find(e);
}
size_t end4 = clock();
cout << "unordered_set find:" << end4 - begin4 << endl;
size_t begin11 = clock();
for (auto e : v) {
ht.Find(e);
}
size_t end11 = clock();
cout << "HashTable find:" << end11 - begin11 << endl << endl;
cout << "插入数据个数：" << us.size() << endl << endl;
ht.Some();
size_t begin5 = clock();
for (auto e : v) {
s.erase(e);
}
size_t end5 = clock();
cout << "set erase:" << end5 - begin5 << endl;
size_t begin6 = clock();
for (auto e : v) {
us.erase(e);
}
size_t end6 = clock();
cout << "unordered_set erase:" << end6 - begin6 << endl;
size_t begin12 = clock();
for (auto e : v) {
ht.Erase(e);
}
size_t end12 = clock();
cout << "HashTable Erase:" << end12 - begin12 << endl << endl;
}
int main() {
test();
return 0;
}
可以看到，在数据量比较大的情况下，unordered_set 的插入、查找、删除等性能都是高于 set 的，并且最长的桶下面只挂了两个元素，平均桶长度只有 1.28 左右，时间复杂度接近 O(1)，而我们实现的哈希表之所以比 STL 库的哈希表还快的主要原因是 库中哈希表的迭代器遍历是按照插入顺序实现的，因此还要额外维护一些信息，执行一些操作，时间复杂度就比较高了。
HashTable.h：
#pragma once
#include <iostream>
#include <vector>
using namespace std;
//哈希函数 (默认，整数)
template<class K> struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key; //将负数转化为正数
}
};
//类模板特化
template<> struct HashFunc<string> {
//字符串不能直接取模，先用字符串映射一个整形，就能取模了!
size_t operator()(const string& key) {
size_t hash = 0;
for (auto& e : key) {
hash *= 31; //解决字母完全一样但是顺序不一样而导致冲突的问题
hash += e;
}
return hash;
}
};
//仿函数
//struct HashFuncString
//{
// size_t operator()(const string& key)
// {
// size_t hash = 0;
// for (auto& e : key)
// {
// hash *= 31; //解决字母完全一样但是顺序不一样而导致冲突的问题
// hash += e;
// }
// cout << key << ":" << hash << endl;
// return hash;
// }
//};
//哈希桶
namespace hash_bucket {
template<class T> class HashNode {
public:
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data), _next(nullptr) {}
};
//迭代器和哈希表相互依赖，需要前置声明
template<class K, class T, class KeyOfT, class Hash> class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> struct __HTIterator {
typedef HashNode<T> Node;
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> self;
Node* _node;
const HashTable<K, T, KeyOfT, Hash>* _pht;
size_t _hashi;
//构造函数
__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi) :_node(node), _pht(pht), _hashi(hashi) { }
//找下一个节点
self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else //当前桶遍历完了，寻找下一个有元素的桶
{
_hashi++;
while (_hashi < _pht->_tables.size()) {
if (_pht->_tables[_hashi]) {
_node = _pht->_tables[_hashi];
break;
}
_hashi++;
}
if (_hashi == _pht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
bool operator!=(const self& s) { return _node != s._node; }
};
template<class K, class T, class KeyOfT, class Hash> class HashTable {
typedef HashNode<T> Node;
//迭代器内部用到了 哈希表的私有成员 _tables，需要友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator;
public:
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator; //普通迭代器
typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator; //const 迭代器
public:
//迭代器接口
iterator begin() //返回第一个桶的第一个元素
{
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) {
return iterator(_tables[i], this, i);
}
}
return end();
}
iterator end() {
return iterator(nullptr, this, -1);
}
const_iterator begin() const {
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) {
return const_iterator(_tables[i], this, i);
}
}
return end();
}
const_iterator end() const {
return const_iterator(nullptr, this, -1);
}
public:
//构造函数
HashTable() { _tables.resize(10); }
//析构函数
~HashTable() {
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
//查找函数
iterator Find(const K& key) {
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) return iterator(cur, this, hashi);
cur = cur->_next;
}
return end();
}
pair<iterator, bool> Insert(const T& data) {
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end()) return make_pair(it, false);
Hash hf;
if (_n == _tables.size()) //哈希桶的负载因子我们设置为 1
{
size_t newSize = _tables.size() * 2;
vector<Node*> newTables;
newTables.resize(newSize);
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hf(kot(cur->_data)) % newSize;
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
//头插新节点
size_t hashi = hf(kot(data)) % _tables.size();
Node* newNode = new Node(data);
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
++_n;
return make_pair(iterator(newNode, this, hashi), true);
}
//删除函数
bool Erase(const K& key) {
Hash hf;
size_t hashi = hf(key) % _tables.size(); // 映射位置
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr) // 处理删除第一个节点的情况
{
_tables[hashi] = cur->_next;
}
else {
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n; //当前哈希表中的元素个数
};
}
MyUnorderedSet.h：
#pragma once
#include "HashTable.h"
namespace dck {
template<class K, class Hash = HashFunc<K>> class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) { return key; }
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
pair<iterator, bool> insert(const K& key) {
auto ret = _ht.Insert(key);
return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
}
iterator find(const K& key) { return _ht.Find(key); }
iterator erase(const K& key) { return _ht.Erase(key); }
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
}
MyUnorderedMap.h：
#pragma once
#include "HashTable.h"
namespace dck {
template<class K, class V, class Hash = HashFunc<K>> class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key) { return _ht.Find(key); }
iterator erase(const K& key) { return _ht.Erase(key); }
iterator begin() { return _ht.begin(); }
iterator end() { return _ht.end(); }
const_iterator begin() const { return _ht.begin(); }
const_iterator end() const { return _ht.end(); }
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online