有没有做粤菜的网站自媒体网站建设要求

有没有做粤菜的网站,自媒体网站建设要求,百度高级搜索引擎,建设厅网站怎么查询安全员c考试成绩1. 源码及框架分析SGI-STL30版本源代码中没有unordered_map和unordered_set#xff0c;SGI-STL30版本是C11之前的STL版本#xff0c;这两个容器是C11之后才更新的。但是SGI-STL30实现了哈希表#xff0c;只容器的名字是hash_map和hash_set#xff0c;他是作为⾮标准的容器出…1. 源码及框架分析SGI-STL30版本源代码中没有unordered_map和unordered_setSGI-STL30版本是C11之前的STL版本这两个容器是C11之后才更新的。但是SGI-STL30实现了哈希表只容器的名字是hash_map和hash_set他是作为⾮标准的容器出现的非标准是指非C标准规定必须实现的源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中hash_map和hash_set的实现结构框架核⼼部分截取出来如下stl_hash_settemplate class Value, class HashFcn hashValue, class EqualKey equal_toValue, class Alloc alloc class hash_set { private: typedef hashtableValue, Value, HashFcn, identityValue, EqualKey, Alloc ht; ht rep; public: typedef typename ht::key_type key_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::const_iterator iterator; typedef typename ht::const_iterator const_iterator; hasher hash_funct() const { return rep.hash_funct(); } key_equal key_eq() const { return rep.key_eq(); } };stl_hash_maptemplate class Key, class T, class HashFcn hashKey, class EqualKey equal_toKey, class Alloc alloc class hash_map { private: typedef hashtablepairconst Key, T, Key, HashFcn, select1stpairconst Key, T , EqualKey, Alloc ht; ht rep; public: typedef typename ht::key_type key_type; typedef T data_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; }; // stl_hashtable.h template class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc class hashtable { public: typedef Key key_type; typedef Value value_type; typedef HashFcn hasher; typedef EqualKey key_equal; private: hasher hash; key_equal equals; ExtractKey get_key; typedef __hashtable_nodeValue node; vectornode*, Alloc buckets; size_type num_elements; public: typedef __hashtable_iteratorValue, Key, HashFcn, ExtractKey, EqualKey, Alloc iterator; pairiterator, bool insert_unique(const value_type obj); const_iterator find(const key_type key) const; }; template class Value struct __hashtable_node { __hashtable_node* next; Value val; };这⾥我们就不再画图分析了通过源码可以看到结构上hash_map和hash_set跟map和set的完全类似复⽤同⼀个hashtable实现key和key/value结构hash_set传给hash_table的是两个keyhash_map传给hash_table的是pairconst key, value需要注意的是源码⾥⾯跟map/set源码类似命名⻛格⽐较乱这⾥比map和set还乱hash_set模板参数居然⽤的Value命名hash_map⽤的是Key和T命名可⻅⼤佬有时写代码也不规范乱弹琴。下⾯我们模拟⼀份自己的出来就按自己的风格走了。2. 模拟实现unordered_map和unordered_set2.1 实现出复用哈希表的框架并支持insert参考源码框架unordered_map和unordered_set复⽤之前我们实现的哈希表。我们这里相比源码调整⼀下key参数就用Kvalue参数就⽤V哈希表中的数据类型我们使用T。其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂⼀点但是大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K还是pairK, V那么insert内部进⾏插⼊时要⽤K对象转换成整形取模和K⽐较相等因为pair的value不参与计算取模且默认支持的是key和value⼀起比较相等我们需要时的任何时候只需要⽐较K对象所以我们在unordered_map和unordered_set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象再转换成整形取模和K比较相等具体细节参考如下代码实现。实现步骤实现哈希表封装unordered_map和unordered_set的框架 解决KeyOfTiteratorconst_iteratorkey不支持修改的问题perator[]UnorderedSet.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class Hash HashFuncK class unordered_map { // 仿函数set(K)和map(pair)比较大小时不一样 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: bool insert(const K key) { return _ht.Insert(key); } private: hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht; }; }UnorderedMap.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class Hash HashFuncK class unordered_map { // 仿函数set(K)和map(pair)比较大小时不一样 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: bool insert(const K key) { return _ht.Insert(key); } private: hash_bucket::HashTableK, K, SetKeyOfT, Hash _ht; }; }HashTable.h:与上一章介绍的HashTable.h区别用T替代了KV解决了KeyOfT问题#pragma once #pragma once #includevector #includestring using namespace std; 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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //特化 template struct HashFuncstring { /* 字符串转换成整形可以把字符ascii码相加即可 但是直接相加的话类似abcd和bcad这样的字符串计算出是相同的 这⾥我们使⽤BKDR哈希的思路用上次的计算结果去乘以⼀个质数这个质数⼀般取31131 等效果会比较好*/ size_t operator()(const string key) { // abcd size_t hash 0; for (auto e : key) { hash hash e; hash hash * 131; } return hash; } }; namespace hash_bucket { templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) , _next(nullptr) {} }; // hash_bucket::HashTableK, pairK, V, MapKeyOfT _ht; // hash_bucket::HashTableK, K, SetKeyOfT _ht; templateclass K, class T, class KeyOfT, class Hash class HashTable { typedef HashNodeT Node; public: HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) {} ~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; } _n 0; } bool Insert(const T data) { KeyOfT kot; if (Find(kot(data))) return false; Hash hs; // 负载因子 1就开始扩容 if (_n _tables.size()) { // 方法二, 只创建vector表直接将旧表的结点链接到新表中 vectorNode* newtables(__stl_next_prime(_tables.size() 1), nullptr); for (size_t i 0; i _tables.size(); i) { //遍历旧表旧表结点重新映射挪动到新表 Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 头插法 size_t hashi hs(kot(cur-_data)) % newtables.size(); cur-_next newtables[hashi]; newtables[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(newtables); } size_t hashi hs(kot(data)) % _tables.size(); // 头插法 Node* newnode new Node(kv); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return true; } Node* Find(const K key) { KeyofT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { return cur; } cur cur-_next; } return nullptr; } bool Erase(const K key) { KeyOfT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* pre nullptr; Node* cur _tables[hashi]; while (cur) { // 删除 if (kot(cur-_data) key) { // 桶中第一个结点 if (pre nullptr) { _tables[hashi] cur-_next; } else { pre-_next cur-_next; } --_n; delete cur; return true; } pre cur; cur cur-_next; } return false; } private: vectorNode* _tables; // 指针数组 size_t _n; }; }2.2 支持iterator的实现iterator实现思路分析begin()返回第一个桶中第一个节点指针构造的迭代器这里end()返回迭代器可以用空表示。由于HTIterator的类定义在HashTable之前而且两者类内都有对方所以HTIterator前面要添加前置声明// 前置声明 templateclass K, class T, class KeyOfT, class Hash class HashTable; templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct HTIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOfT, Hash HT; typedef HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; Node* _node; const HT* _pht; // 哈希表的指针 HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) {} Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { KeyOfT kot; Hash hs; if (_node-_next) // 当前桶没走完 { _node _node-_next; } else // 当前桶走完了找到下一个桶的第一个节点 { // 算出当前桶的位置 size_t hashi hs(kot(_node-_data)) % _pht-_tables.size(); hashi; while(hashi _pht-_tables.size()) { if (_pht-_tables[hashi]) // 找到下一个不为空的桶 { _node _pht-_tables[hashi]; break; } else { hashi; } } if (hashi _pht-_tables.size()) // 最后一个桶走完了,要到end()位置 { // end()中_node是空 return nullptr; } } return *this; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } };注意HashTable中的HTIterator也要有友元声明class HashTable { // 友元声明 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash friend struct HIIterator; typedef HashNodeT Node; public: typedef HTIteratorK, T, T, T*, KeyOfT, Hash Iterator; typedef HTIteratorK, T, const T, const T*, KeyOfT, Hash ConstIterator; Iterator Begin() { if (_n 0) { return End(); } for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return Iterator(_tables[i], this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { if (_n 0) { return End(); } for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return ConstIterator(_tables[i], this); } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) {} ...unordered_set的迭代器也不支持修改把unordered_set的第二个模板参数改成const K即可unordered_map的iterator不支持修改key但是可以修改value我们把unordered_map的第二个模板参数pair的第一个参数改成const K即可2.3 map支持[]2.4 unordered_map和unordered_set代码实现UnorderedSet.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class Hash HashFuncK class unordered_set { // 仿函数set(K)和map(pair)比较大小时不一样 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, const K, SetKeyOfT, Hash::ConstIterator 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(); } pairiterator, bool 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); } private: hash_bucket::HashTableK, const K, SetKeyOfT, Hash _ht; }; }UnorderedMap.h:#pragma once #includeHashTable.h namespace xiaohan { templateclass K, class V, class Hash HashFuncK class unordered_map { struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::Iterator iterator; typedef typename hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash::ConstIterator 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(); } pairiterator, bool insert(const pairK, V kv) { return _ht.Insert(kv); } V operator[](const K key) { pairiterator, bool ret insert({ key, V() }); return ret.first-second; } iterator find(const K key) { return _ht.Find(key); } bool erase(const K key) { return _ht.Erase(key); } private: hash_bucket::HashTableK, pairconst K, V, MapKeyOfT, Hash _ht; }; }HashTable.h:#pragma once #pragma once #includevector #includestring using namespace std; 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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; // n const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; //特化 template struct HashFuncstring { /* 字符串转换成整形可以把字符ascii码相加即可 但是直接相加的话类似abcd和bcad这样的字符串计算出是相同的 这⾥我们使⽤BKDR哈希的思路用上次的计算结果去乘以⼀个质数这个质数⼀般取31131 等效果会比较好*/ size_t operator()(const string key) { // abcd size_t hash 0; for (auto e : key) { hash hash e; hash hash * 131; } return hash; } }; namespace hash_bucket { templateclass T struct HashNode { T _data; HashNodeT* _next; HashNode(const T data) :_data(data) , _next(nullptr) {} }; // 前置声明 templateclass K, class T, class KeyOfT, class Hash class HashTable; templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash struct HTIterator { typedef HashNodeT Node; typedef HashTableK, T, KeyOfT, Hash HT; typedef HTIteratorK, T, Ref, Ptr, KeyOfT, Hash Self; Node* _node; const HT* _pht; // 哈希表的指针 HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) {} Ref operator*() { return _node-_data; } Ptr operator-() { return _node-_data; } Self operator() { KeyOfT kot; Hash hs; if (_node-_next) // 当前桶没走完 { _node _node-_next; } else // 当前桶走完了找到下一个桶的第一个节点 { // 算出当前桶的位置 size_t hashi hs(kot(_node-_data)) % _pht-_tables.size(); hashi; while(hashi _pht-_tables.size()) { if (_pht-_tables[hashi]) // 找到下一个不为空的桶 { _node _pht-_tables[hashi]; break; } else { hashi; } } if (hashi _pht-_tables.size()) // 最后一个桶走完了,要到end()位置 { // end()中_node是空 _node nullptr; } } return *this; } bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } }; // hash_bucket::HashTableK, pairK, V, MapKeyOfT _ht; // hash_bucket::HashTableK, K, SetKeyOfT _ht; templateclass K, class T, class KeyOfT, class Hash class HashTable { // 友元声明 templateclass K, class T, class Ref, class Ptr, class KeyOfT, class Hash friend struct HTIterator; typedef HashNodeT Node; public: typedef HTIteratorK, T, T, T*, KeyOfT, Hash Iterator; typedef HTIteratorK, T, const T, const T*, KeyOfT, Hash ConstIterator; Iterator Begin() { if (_n 0) { return End(); } for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return Iterator(_tables[i], this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { if (_n 0) { return End(); } for (size_t i 0; i _tables.size(); i) { if (_tables[i]) { return ConstIterator(_tables[i], this); } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } HashTable() :_tables(__stl_next_prime(1), nullptr) , _n(0) {} ~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; } _n 0; } pairIterator, bool Insert(const T data) { KeyOfT kot; auto it Find(kot(data)); if (it ! End()) return { it, false }; Hash hs; // 负载因子 1就开始扩容 if (_n _tables.size()) { // 方法二, 只创建vector表直接将旧表的结点链接到新表中 vectorNode* newtables(__stl_next_prime(_tables.size() 1), nullptr); for (size_t i 0; i _tables.size(); i) { //遍历旧表旧表结点重新映射挪动到新表 Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 头插法 size_t hashi hs(kot(cur-_data)) % newtables.size(); cur-_next newtables[hashi]; newtables[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(newtables); } size_t hashi hs(kot(data)) % _tables.size(); // 头插法 Node* newnode new Node(data); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return {Iterator(newnode, this), true}; } Iterator Find(const K key) { KeyOfT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* cur _tables[hashi]; while (cur) { if (kot(cur-_data) key) { return {cur, this}; // {}初始化 } cur cur-_next; } return {nullptr, this}; } bool Erase(const K key) { KeyOfT kot; Hash hs; size_t hashi hs(key) % _tables.size(); Node* pre nullptr; Node* cur _tables[hashi]; while (cur) { // 删除 if (kot(cur-_data) key) { // 桶中第一个结点 if (pre nullptr) { _tables[hashi] cur-_next; } else { pre-_next cur-_next; } --_n; delete cur; return true; } pre cur; cur cur-_next; } return false; } private: vectorNode* _tables; // 指针数组 size_t _n; // std::vectorstd::listK, V _tables; }; }测试代码#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includeunordered_map using namespace std; #includeUnorderedSet.h #includeUnorderedMap.h void Print(const xiaohan::unordered_setint s) { xiaohan::unordered_setint::const_iterator it s.begin(); while (it ! s.end()) { // *it 1; cout *it ; it; } cout endl; } int main() { xiaohan::unordered_setint us; us.insert(3); us.insert(1000); us.insert(2); us.insert(102); us.insert(2111); us.insert(22); xiaohan::unordered_setint::iterator it us.begin(); while (it ! us.end()) { //*it 1; cout *it ; it; } cout endl; Print(us); xiaohan::unordered_mapstring, string dict; dict.insert({ string, ַ字符串 }); dict.insert({ string, ַ字符串1 }); dict.insert({ left, 左边 }); dict.insert({ right, 右边 }); // 可修改 dict[left] 左边剩余; // dict[insert]; // dict[map] 地图; for (auto [k, v] : dict) { //k x; //v x; cout k : v endl; } return 0; }结果