中型电商网站维护费用,怎样建一个自己公司的网站,wordpress文章分享无标题,网站开通后快乐的流畅#xff1a;个人主页 个人专栏#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火#xff0c;在为久候之人燃烧#xff01; 文章目录 引言一、哈希表#xff08;改造版#xff09;1.1 结点1.2 迭代器1.2.1 operator 1.3 本体1.3.1 成员变量和… 快乐的流畅个人主页 个人专栏《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火在为久候之人燃烧 文章目录 引言一、哈希表改造版1.1 结点1.2 迭代器1.2.1 operator 1.3 本体1.3.1 成员变量和默认成员函数1.3.2 begin和end1.3.3 Find1.3.4 Insert1.3.5 Erase 二、unordered_set2.1 成员变量与仿函数2.2 begin和end2.3 find2.4 insert2.5 erase 三、unordered_map3.1 成员变量与仿函数3.2 begin和end3.3 find3.4 insert3.5 operator[ ]3.6 erase 引言
STL库中set类和map类都是红黑树作为底层实现的与之类似unordered系列的unordered_set类和unordered_map类都是通过哈希表作为底层来实现的。
一、哈希表改造版
1.1 结点
templateclass T
struct HashNode
{HashNodeT* _next;T _data;HashNode(const T data): _next(nullptr), _data(data){}
};细节
将数据类型改为T因为要同时适用unordered_set存储键值和unordered_map存储键值对
1.2 迭代器
改造后的哈希表最重要的功能之一就是支持单向迭代器
templateclass K, class T, class KeyOfT, class Hash
class HashTable;//前置声明templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash
struct HashIterator
{typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash Ht;typedef HashIteratorK, T, Ref, Ptr, KeyOfT, Hash Self;typedef HashIteratorK, T, T, T*, KeyOfT, Hash Iterator;Node* _node;const Ht* _ht;HashIterator(Node* node, const Ht* ht): _node(node), _ht(ht){}HashIterator(const Iterator it): _node(it._node), _ht(it._ht){}Ref operator*(){return _node-_data;}Ptr operator-(){return (operator*());}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};细节
一些基本的迭代器范式操作已经给出重点的操作后面详细实现增加_ht成员变量原因当一条单链表走到空则需要走到下一个哈希桶的位置需要哈希表的地址这里存在相互引用的问题所以前置声明哈希表const修饰_ht使const迭代器能够被构造迭代器的拷贝构造函数有两个用途 以普通迭代器拷贝出普通迭代器普通迭代器调用时以普通迭代器拷贝出const迭代器const迭代器调用时
1.2.1 operator
Self operator()
{if (_node-_next){_node _node-_next;}else{int flag 0;size_t hashi Hash()(KeyOfT()(_node-_data)) % _ht-_tables.size();for (size_t i hashi 1; i _ht-_tables.size(); i){if (_ht-_tables[i]){_node _ht-_tables[i];flag 1;break;}}if (!flag){_node nullptr;}}return *this;
}Self operator(int)
{Self tmp *this;*this;return tmp;
}细节
前置的思路 下一个结点不为空则跳到下一位下一个结点为空则先取模算出哈希地址再往后探测不为空的哈希桶 后置复用前置返回临时对象
1.3 本体
1.3.1 成员变量和默认成员函数
templateclass K, class T, class KeyOfT, class Hash
class HashTable
{templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hashfriend struct HashIterator;
protected:typedef HashNodeT Node;
public:HashTable(){_tables.resize(10);}~HashTable(){for (auto cur : _tables){while (cur){Node* del cur;cur cur-_next;delete del;}}}
protected:vectorNode* _tables;size_t _n 0;//有效数据个数
};细节
将迭代器声明为友元使迭代器内部可操作_tables第三个模板参数为KeyOfT仿函数类型用于获取不同数据T的键值key来进行比较第四个模板参数为Hash仿函数类型用于将不同类型key转换为整型来进行取模
1.3.2 begin和end
typedef HashIteratorK, T, T, T*, KeyOfT, Hash iterator;
typedef HashIteratorK, T, const T, const T*, KeyOfT, Hash const_iterator;iterator begin()
{for (size_t i 0; i _tables.size(); i){if (_tables[i]){return iterator(_tables[i], this);}}return iterator(nullptr, this);
}const_iterator begin() const
{for (size_t i 0; i _tables.size(); i){if (_tables[i]){return const_iterator(_tables[i], this);}}return const_iterator(nullptr, this);
}iterator end()
{return iterator(nullptr, this);
}const_iterator end() const
{return const_iterator(nullptr, this);
}细节
begin返回最开始不为空的哈希桶的迭代器end返回空迭代器构造迭代器需要传入哈希表本身的地址这里直接传this指针即可
1.3.3 Find
iterator Find(const K key)
{size_t hashi Hash()(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (KeyOfT()(cur-_data) key){return iterator(cur, this);}cur cur-_next;}return iterator(nullptr, this);
}细节
返回迭代器运用两个仿函数Hash转整型KeyOfT获取键值
1.3.4 Insert
pairiterator, bool Insert(const T data)
{KeyOfT kot;iterator it Find(kot(data));if (it._node)//保持key唯一{return make_pair(it, false);}Hash hash;if (_n _tables.size())//负载因子为1时扩容{size_t newsize _tables.size() * 2;vectorNode* newtables(newsize);for (auto cur : _tables){while (cur){Node* next cur-_next;//将旧表结点重新映射到新表上size_t hashi hash(kot(cur-_data)) % newsize;cur-_next newtables[hashi];newtables[hashi] cur;//跳回旧表的下一结点cur next;}}_tables.swap(newtables);}size_t hashi hash(kot(data)) % _tables.size();Node* newnode new Node(data);//头插newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return make_pair(iterator(newnode, this), true);
}细节
返回pair第一个参数为迭代器第二个参数为布尔值记录是否插入成功运用两个仿函数Hash转整型KeyOfT获取键值
1.3.5 Erase
bool Erase(const K key)
{size_t hashi Hash()(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (KeyOfT()(cur-_data) key){if (prev nullptr){_tables[hashi] cur-_next;}else{prev-_next cur-_next;}delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;
}细节运用两个仿函数Hash转整型KeyOfT获取键值
二、unordered_set
2.1 成员变量与仿函数
templateclass K, class Hash HashFuncK
class unordered_set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:
protected:HashTableK, K, SetKeyOfT, Hash _ht;
};细节
unordered_set类仿函数直接返回参数key成员变量的第二个模板参数为K第三个模板参数为SetKeyOfT模板Hash可以根据特定需要而传手动实现的哈希化函数
2.2 begin和end
typedef typename HashTableK, K, SetKeyOfT, Hash::const_iterator iterator;
typedef typename HashTableK, K, SetKeyOfT, Hash::const_iterator const_iterator;iterator begin()
{return _ht.begin();
}const_iterator begin() const
{return _ht.begin();
}iterator end()
{return _ht.end();
}const_iterator end() const
{return _ht.end();
}细节
加上typename关键字编译器才能识别类型unordered_set中存储的键值key均不允许修改所以其普通迭代器和const迭代器均为哈希表的const迭代器由于unordered_set的普通迭代器也是哈希表的const迭代器调用普通begin()时便有从普通迭代器到const迭代器的转换此时之前写的拷贝构造以普通迭代器拷贝构造const迭代器便派上用场了。
2.3 find
iterator find(const K key)
{return _ht.Find(key);
}2.4 insert
pairiterator, bool insert(const K key)
{return _ht.Insert(key);
}细节
插入参数类型为K键值此时也有从普通迭代器到const迭代器的转换
2.5 erase
bool erase(const K key)
{return _ht.Erase(key);
}三、unordered_map
3.1 成员变量与仿函数
templateclass K, class V, class Hash HashFuncK
class unordered_map
{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};
public:
protected:HashTableK, pairconst K, V, MapKeyOfT, Hash _ht;
};细节
unordered_map类仿函数返回参数pair的first成员变量的第二个模板参数为pair第三个模板参数为MapKeyOfT模板Hash可以根据特定需要而传手动实现的哈希化函数
3.2 begin和end
typedef typename HashTableK, pairconst K, V, MapKeyOfT, Hash::iterator iterator;
typedef typename HashTableK, pairconst K, V, MapKeyOfT, Hash::const_iterator const_iterator;iterator begin()
{return _ht.begin();
}const_iterator begin() const
{return _ht.begin();
}iterator end()
{return _ht.end();
}const_iterator end() const
{return _ht.end();
}细节
加上typename关键字编译器才能识别类型unordered_map同样不允许修改key故加上const修饰但是允许修改存储的value所以普通和const迭代器一一对应
3.3 find
iterator find(const K key)
{return _ht.Find(key);
}3.4 insert
pairiterator, bool insert(const pairconst K, V kv)
{return _ht.Insert(kv);
}细节插入参数类型为pair键值对
3.5 operator[ ]
unordered_map最好用的重载运算符[ ]我们肯定也要实现平常插入和修改使用[ ]更加方便。
V operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;
}细节
插入成功便是插入插入失败便是查找修改返回value的引用可以直接插入或修改
3.6 erase
bool erase(const K key)
{return _ht.Erase(key);
}真诚点赞手有余香
