【C++深度探索】unordered_set、unordered_map封装

news/2024/9/19 23:44:53/ 标签: c++, java, redis
🔥 个人主页：大耳朵土土垚
🔥 所属专栏：C++从入门至进阶

这里将会不定期更新有关C/C++的内容，欢迎大家点赞，收藏，评论🥳🥳🎉🎉🎉

文章目录

  • 前言
  • 1. unordered_set和unordered_map介绍
    • ✨unordered_map介绍
    • ✨unordered_set介绍
  • 2. 修改哈希表
  • 3. 迭代器
    • ✨const迭代器
  • 4. unordered_map的[]访问
  • 5. unordered_set和unordered_map封装
    • ✨修改后的哈希表
    • ✨unordered_map类
    • ✨unordered_set类
  • 6. 结语

前言

  前面我们学习过红黑树实现map、set的封装，而unordered_set和unordered_map的功能与map和set类似，所不同的是其存储元素是无序的，底层是使用哈希表，所以今天我们就可以利用之前学习过的哈希表的实现，来对C++STL库中的unordered_set和unordered_map进行模拟实现。


1. unordered_set和unordered_map介绍


  在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，例如：map、set。在查询时效率可达到 l o g 2 N log_2 N log2​N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。

✨unordered_map介绍

  介绍文档，点击跳转

  1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过key快速的索引到与其对应的value。
  2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
  3. 在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
  4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
  5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。

unordered_map和map核心功能重复90%，它们区别在于：

  1. 对键值对中key要求不同：
  • map：key要支持比较大小
  • unordered_map：key要支持转换成整型+比较相等
  1. map遍历有序，unordered_map遍历无序
  2. map有双向迭代器，unordered_map单向迭代器
  3. 它们之间性能有差异

unordered_map常见接口：

函数声明功能介绍
unordered_map()构造不同格式的unordered_map对象
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
cbegin返回unordered_map第一个元素的const迭代器
cend返回unordered_map最后一个元素下一个位置的const迭代器
operator[]返回与key对应的value
iterator find(const K& key)返回key在哈希桶中的位置
size_t count(const K& key)返回哈希桶中关键码为key的键值对的个数
insert向容器中插入键值对
erase删除容器中的键值对
void clear()清空容器中有效元素个数
void swap(unordered_map&)交换两个容器中的元素
size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

注意：operator[]函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回。这与之前的map类似，插入函数返回一个键值对，键存放指针，对存放bool值，用来判断是否插入成功。


✨unordered_set介绍

  文档介绍，点击跳转
  unordered_set与unordered_map类似，不同在于前者储存单个数据，后者储存键值对，这里就不过多介绍。


2. 修改哈希表


  因为我们要使用哈希表来实现对unordered_set和unordered_map的封装，之前实现的哈希表都是插入键值对，是没办法很好封装unordered_set的，所以我们先得对哈希表进行改造，改造类似于使用红黑树封装map和set对红黑树的改造，具体实现如下：


我们之前模拟实现过哈希表，插入的节点是键值对pair类型，而如果要使用哈希表来对unordered_set和unordered_map封装的话，unordered_set存储的应该是单个值，而不是键值对，所以我们就需要对哈希表进行修改，使得unordered_set和unordered_map都能适用：

  1. 首先哈希表存储节点的类需要从只能存储键值对改为能够存储任意数据：
  • 修改前：
template<class K,class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};
  • 修改后：
template<class T>
struct HashNode
{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}
};
  1. 相应的，哈希表的模板参数也需要修改：
  • 修改前：
//哈希表类
template<class K,class V, class Hash = HashFunc<K>>
class HashTable {
public:typedef HashNode<K,V> Node;Node* Find(const K& key);//查找函数private:vector<Node*> _tables;size_t _n;//记录存储数据个数
};

 因为节点类只有一个模板参数了，所以哈希表前面两个模板参数有点多余，但是如果将哈希表的模板参数也改为一个，如下面代码所示：

//哈希表
template<class T,class Hash = HashFunc<T>>
class HashTable 
{
public:typedef HashNode<T> Node;Node* Find(const T& key);//？查找函数private:vector<Node*> _tables;size_t _n;//记录存储数据个数
};

 那么对于class Hash这个模板参数不可能也传入一个键值对，此外在实现查找上面代码中的Find函数时，对于unordered_map查找时Find函数参数就得传一个完整的键值对，我们不可能把完整的键值对全部传过去查找，这样查找就没有意义，我们只需要获得键值对的键查找到相应的键值对即可，所以我们还应该传一个模板参数用于传给class Hash、Find和Erase函数：

//哈希表
template<class K,class T,class Hash = HashFunc<K>>//K存储键，T存储键值对
class HashTable 
{
public:typedef HashNode<T> Node;//传入键值对Node* Find(const K& key);//查找函数，只传键pair<Node*,bool> Insert(const T& data);//插入，传入Tbool Erase(const K& key);//删除，只传键
private:vector<Node*> _tables;size_t _n;//记录存储数据个数
};

这样对于不同函数的需求就可以传入不同的模板参数了🥳🥳

 如果是unordered_map存储的是键值对，我们就可以往哈希表的两个模板参数中传入一个键和一个键值对：

//unordered_map类
template<class K,class V>
class unordered_map {
public:
private:HashTable<K, pair<K,V>> _ht;
};

这样哈希表的第一个模板参数帮助我们解决仿函数传参、查找和删除函数传参的问题，第二个则是必须的，除了存储数据外，插入等函数也需要第二个模板参数

 如果是unordered_set存储的不是键值对，我们也可以复用上面的代码，传入两个一样的参数即可：

//unordered_set类
template<class K>
class unordered_set {
public:
private:HashTable<K, K> _ht;
};

虽然unordered_set看起来传了两个一模一样的参数是无意义的，但是这样就可以实现对哈希表的复用，不用单独为了unordered_set再写一个哈希表了，如下图所示：


  1. 插入函数的参数也得从键值对改为任意数据：
bool Insert(const T& data)//之前：bool Insert(const pair<K, V>& data)

 除此以外，我们在寻找插入的位置时不可避免需要通过节点中存储的_data使用哈希函数来获取插入的位置：

//通过Hash函数找到插入位置
Hash hs;
size_t addr = hs(data.first) % _tables.size();

 我们发现之前插入键值对都是使用键值对的键来传给哈希函数获取哈希值，当我们将哈希表改成可以存储任意数据后，就不支持上述获取哈希值的方式了。
 因此为了实现代码的复用，我们需要传入一个新的模板参数，以便在不同情况下都能按照我们需要的方式进行获取哈希值，因为如果是unordered_map需要通过键来获取，unordered_set则直接通过数据进行获取，所以我们可以在set类和map类中各定义一个类来获取传给哈希函数的数据，再传给哈希表：

// unordered_map类
template<class K,class V>
class unordered_map {
//定义一个类获取键值对里面的键
struct MapKeyOfT {const K& operator()(const pair<K, V>& data){return data.first;}
};private:HashTable<K, pair<K,V>, MapKeyOfT> _ht;//传给哈希表};

//unordered_set类
template<class K>
class unordered_set{
//也定义一个类返回data即可，虽然有点多此一举，但是可以实现代码复用
struct SetKeyOfT {const K& operator()(const K& data){return data;}
};private:HashTable<K, K, SetKeyOfT> _ht;//传给哈希表
};

看起来unordered_set定义的类似乎做了无用功，但是这一切都是为了能够实现哈希表的复用，unordered_map多传了一个参数，unordered_set也要多传。


 那么哈希表的模板参数也要修改一下：

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable {
public:typedef HashNode<T> Node;private:vector<Node*> _tables;size_t _n;//记录存储数据个数
};

 这样我们在插入函数进行比较时，就可以通过类模板KeyOfT定义一个对象然后使用括号来获取需要进行比较的数了：

bool Insert(const T& data)
{KeyOfT kot;//使用类模板，定义一个对象Hash hs;//1.先找是否已经插入过相同的值if (Find(kot(data)))return false;//2.判断是否需要扩容...//3.通过Hash函数找到插入位置size_t addr = hs(kot(data)) % _tables.size();//...}

这样就可以使用类模板定义的对象通过重载括号获取你想要的值，如果插入类型是键值对，那么就获得键值对中的键；如果不是键值对，括号返回的也是数据本身；这样不同的数据都可以传给哈希函数🥳🥳


3. 迭代器


  哈希表的迭代器与链表的迭代器类似，都是使用指针来构造：

//迭代器
template<class T>
struct HashTableIterator {typedef HashNode<T> Node;typedef HashTableIterator<T> self;T& operator*(){return _node->_data;}T* operator->(){return &(_node->_data);}bool operator!=(const self& t){return _node != t._node;}bool operator==(const self& t){return _node == t._node;}self& operator++(){//...}//构造HashTableIterator(Node* node):_node(node){}Node* _node;};

✨对于operator++：

 因为哈希表中是使用哈希桶，当一个桶遍历完，就需要寻找下一个桶，所以我们得将哈希表传过去来寻找下一个桶：

self& operator++()
{if (_node->_next)_node = _node->_next;//如果当前桶走完了，找下一个桶//1.先找到当前位置KeyOfT kot;Hash hs;size_t hash = hs(kot(_node->_data)) % _pht->_tables.size();++hash;while (hash < _pht->_tables.size()){if (_pht->_tables[hash])break;hash++;}if (hash >= _pht->_tables.size())_node = nullptr;else_node = _pht->_tables[hash];return *this;
}

可以看出上述代码使用了KeyOfT和Hash类分别获得传给哈希函数的值和哈希函数计算的哈希值，所以迭代器模板也要传入这两个参数：

template<class K, class T, class KeyOfT, class Hash>
truct HashTableIterator {typedef HashNode<T> Node;typedef HashTableIterator<K,T, KeyOfT, Hash> self;typedef HashTable<K, T, KeyOfT, Hash> HashTable;//...};

又因为获取哈希表需要传入四个参数，所以迭代器的参数也得包括这四个，所以除了KeyOfT和Hash还要传入K这个参数

然后在迭代器中除了需要定义一个指针外，还需要一个哈希表的指针以便将哈希表传过去：

template<class K, class T, class KeyOfT, class Hash>
truct HashTableIterator {typedef HashNode<T> Node;typedef HashTableIterator<K,T, KeyOfT, Hash> self;typedef HashTable<K, T, KeyOfT, Hash> HashTable;//构造HashTableIterator(Node* node, HashTable* pht):_node(node),_pht(pht){}Node* _node;HashTable* _pht;//传入哈希表指针
};

完整的普通迭代器类代码如下：

// 前置声明，因为迭代器类中要使用哈希表所以需要前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;//迭代器
template<class K, class T, class KeyOfT, class Hash>
struct HashTableIterator {typedef HashNode<T> Node;typedef HashTableIterator<K,T, KeyOfT, Hash> self;typedef HashTable<K, T, KeyOfT, Hash> HashTable;T& operator*(){return _node->_data;}T* operator->(){return &(_node->_data);}bool operator!=(const self& t){return _node != t._node;}bool operator==(const self& t){return _node == t._node;}self& operator++(){if (_node->_next)_node = _node->_next;//如果当前桶走完了，找下一个桶//1.先找到当前位置KeyOfT kot;Hash hs;size_t hash = hs(kot(_node->_data)) % _pht->_tables.size();++hash;while (hash < _pht->_tables.size()){if (_pht->_tables[hash])break;hash++;}if (hash >= _pht->_tables.size())_node = nullptr;else_node = _pht->_tables[hash];return *this;}//构造HashTableIterator(Node* node, HashTable* pht):_node(node),_pht(pht){}Node* _node;HashTable* _pht;};

✨const迭代器


  相较于普通迭代器，const迭代器指向的内容不可以被修改，也就是说operator*和operator->返回值不可以修改，所以只要在其返回值前加const修饰即可，为了与普通迭代器复用同一个迭代器类，我们需要在迭代器类的模板参数中多加两个：

// 前置声明
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 HashTableIterator {typedef HashNode<T> Node;typedef HashTableIterator<K,T,Ref, Ptr, KeyOfT, Hash> self;typedef const HashTable<K, T, KeyOfT, Hash> HashTable;//注意这里是constRef operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}bool operator!=(const self& t){return _node != t._node;}bool operator==(const self& t){return _node == t._node;}self& operator++(){if (_node->_next)_node = _node->_next;//如果当前桶走完了，找下一个桶//1.先找到当前位置KeyOfT kot;Hash hs;size_t hash = hs(kot(_node->_data)) % _pht->_tables.size();++hash;while (hash < _pht->_tables.size()){if (_pht->_tables[hash])break;hash++;}if (hash >= _pht->_tables.size())_node = nullptr;else_node = _pht->_tables[hash];return *this;}//构造HashTableIterator(Node* node, HashTable* pht):_node(node),_pht(pht){}Node* _node;HashTable* _pht;};

  这样在哈希表中如果是普通迭代器就传T，T&，T*这三个模板参数，如果是const迭代器就传T，const T&，const T*这三个模板参数，这样就很好限制了const迭代器修改指向的内容：

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable {
public:// 友元声明template<class K, class T, class Ref, class Ptr,class KeyOfT, class Hash>friend struct HashTableIterator;typedef HashNode<T> Node;typedef HashTableIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;Iterator Begin(){if (_n == 0)return End();int i = 0;while (i < _tables.size()){if (_tables[i] != nullptr)break;i++;}return Iterator(_tables[i],this);}Iterator End(){return Iterator(nullptr,this);}Const_Iterator Begin() const{if (_n == 0)return End();int i = 0;while (i < _tables.size()){if (_tables[i] != nullptr)break;i++;}return Const_Iterator(_tables[i], this);}Const_Iterator End() const{return Const_Iterator(nullptr, this);}//...
private:vector<Node*> _tables;size_t _n;//记录存储数据个数
};

因为在迭代器类中要使用哈希表中的数据，所以我们将迭代器设置为哈希表类的友元类

  有了迭代器之后，Find查找函数的返回值就可以使用迭代器了🥳🥳:

// 检测哈希表中是否存在值为key的节点，存在返回该节点的迭代器，否则返回End()
Iterator Find(const K& key)
{//先找到key对应的Hash值KeyOfT kot;Hash hs;size_t ht = hs(key) % _tables.size();Node* cur = _tables[ht];while (cur){if (kot(cur->_data) == key)return Iterator(cur,this);cur = cur->_next;}return End();
}

这里同样要注意，查找函数需要通过特定的值获取哈希值，所以我们可以利用之前在插入函数中使用的类模板继续创建一个对象来获取哈希值。


4. unordered_map的[]访问


  在unordered_map的使用介绍中，我们知道可以用[]来访问修改键值对以及插入数据：

//迭代器构造
std::vector<pair<string, string>> v = { {"上", "up"}, { "下", "down"}, { "左", "left"}, { "右", "right"} };
std::unordered_map<string, string> m(v.begin(), v.end());//[]访问
cout << m["上"] << endl;
cout << m["下"] << endl;
cout << m["左"] << endl;
cout << m["右"] << endl;//[]修改
m["右"] += "tutu";//[]插入
m["中"] = "center";cout << endl;
cout << "修改插入后：" << endl;
std::unordered_map<string, string>::iterator it = m.begin();
while (it != m.end())
{cout << it->first << ":" << it->second << endl;++it;
}
cout << endl;

结果如下：


  unordered_map的[]能够插入数据是因为其复用了插入函数，如果[]里面引用的值不存在unordered_map中就会插入并返回键值对的值，存在就直接返回键值对的值，而插入函数中恰好会先寻找合适的插入位置，并返回bool值，所以我们只需对插入函数返回的值进行修改，这与之前学习过的map类似：
我们将插入函数的返回值设为pair类型，如果插入成功就返回新节点的迭代器和true；如果插入失败，那么map中肯定以及有相同的值，那么返回该位置的迭代器和false

这样在[]中就可以复用插入函数完成插入和修改操作了：

	V& operator[](const K& key){pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));return ret.first->second;}

插入函数只需要修改返回值即可：

pair<Iterator,bool> Insert(const T& data)
{//...简写//1.插入成功return make_pair(Iterator(newnode,this),true);//2.插入失败return make_pair(it,false);//已有位置的迭代器
}

5. unordered_set和unordered_map封装


  我们对于unordered_set和unordered_map封装需要各种新开一个头文件unordered_set.h和unordered_map.h来进行，并且都需要包含Hash.h头文件，放在自己的命名空间内，避免与STL标准库中的map和set弄混。

✨修改后的哈希表

//哈希函数
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;}
};//哈希节点类
template<class T>
struct HashNode
{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 HashTableIterator {typedef HashNode<T> Node;typedef HashTableIterator<K,T,Ref, Ptr, KeyOfT, Hash> self;typedef const HashTable<K, T, KeyOfT, Hash> HashTable;Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}bool operator!=(const self& t){return _node != t._node;}bool operator==(const self& t){return _node == t._node;}self& operator++(){if (_node->_next)_node = _node->_next;//如果当前桶走完了，找下一个桶//1.先找到当前位置KeyOfT kot;Hash hs;size_t hash = hs(kot(_node->_data)) % _pht->_tables.size();++hash;while (hash < _pht->_tables.size()){if (_pht->_tables[hash])break;hash++;}if (hash >= _pht->_tables.size())_node = nullptr;else_node = _pht->_tables[hash];return *this;}//构造HashTableIterator(Node* node, HashTable* pht):_node(node),_pht(pht){}Node* _node;HashTable* _pht;};//哈希类template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>class HashTable {public:// 友元声明template<class K, class T, class Ref, class Ptr,class KeyOfT, class Hash>friend struct HashTableIterator;typedef HashNode<T> Node;typedef HashTableIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> Const_Iterator;Iterator Begin(){if (_n == 0)return End();int i = 0;while (i < _tables.size()){if (_tables[i] != nullptr)break;i++;}return Iterator(_tables[i],this);}Iterator End(){return Iterator(nullptr,this);}Const_Iterator Begin() const{if (_n == 0)return End();int i = 0;while (i < _tables.size()){if (_tables[i] != nullptr)break;i++;}return Const_Iterator(_tables[i], this);}Const_Iterator End() const{return Const_Iterator(nullptr, this);}HashTable(){_tables.resize(10, nullptr);}~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;}}pair<Iterator, bool> Insert(const T& data){KeyOfT kot;//1.先找是否已经插入过相同的值Iterator it = Find(kot(data));if (it != End())return make_pair(it,false);Hash hs;//2.判断是否需要扩容//如果负载因子为1就扩容if (_n == _tables.size()){HashTable<K, T, KeyOfT> h;h._tables.resize(2 * _tables.size(), nullptr);//只需要将哈希桶插入即可for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){size_t hash = hs(kot(cur->_data)) % h._tables.size();Node* Next = cur->_next;cur->_next = h._tables[hash];h._tables[hash] = cur;cur = Next;}_tables[i] = nullptr;}_tables.swap(h._tables);}//3.通过Hash函数找到插入位置size_t addr = hs(kot(data)) % _tables.size();//4.头插到新表if (_tables[addr] == nullptr)//如果是空，_n就需要++_n++;Node* newnode = new Node(data);newnode->_next = _tables[addr];_tables[addr] = newnode;return make_pair(Iterator(newnode,this), true);}Iterator Find(const K& key){//先找到key对应的Hash值Hash hs;KeyOfT kot;size_t ht = hs(key) % _tables.size();Node* cur = _tables[ht];while (cur){if (kot(cur->_data) == key)return Iterator(cur,this);cur = cur->_next;}return End();}bool Erase(const K& key){//1.先找到删除的位置Hash hs;KeyOfT kot;size_t ht = hs(key) % _tables.size();Node* cur = _tables[ht];Node* parent = nullptr;while (cur){if (kot(cur->_data) == key)break;parent = cur;cur = cur->_next;}if (cur == nullptr)return false;//2.删除对应节点if (parent)parent->_next = cur->_next;else_tables[ht] = cur->_next;//修改_nif (_tables[ht] == nullptr)_n--;//3.释放原节点delete cur;return true;}private:vector<Node*> _tables;size_t _n;//记录存储数据个数};

✨unordered_map类

#include"Hash.h"
// unordered_map类
namespace tutu
{
template<class K, class V>
class unordered_map {
public://定义一个类获取键值对里面的键struct MapKeyOfT {const K& operator()(const pair<K, V>& data){return data.first;}};typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::Iterator iterator;typedef typename HashTable<K, pair<K, V>, MapKeyOfT>:: 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();}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);}bool Erase(const K& key){return _ht.Erase(key);}private:HashTable<K, pair<K, V>, MapKeyOfT> _ht;//传给哈希表};//测试函数void test_map(){unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}
}

结果如下：


✨unordered_set类

#include"Hash.h"
namespace tutu{template<class K>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashTable<K, const K, SetKeyOfT>::Iterator iterator;typedef typename HashTable<K, const K, SetKeyOfT>::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();}pair<iterator, 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:HashTable<K, const K, SetKeyOfT> _ht;};void Print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){// *it += 1;cout << *it << " ";++it;}cout << endl;}void test_set()
{unordered_set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };for (auto e : a){s.insert(e);}for (auto e : s){cout << e << " ";}cout << endl;unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it += 1;cout << *it << " ";++it;}cout << endl;Print(s);
}}

结果如下：


6. 结语

  unordered_map和unordered_set的底层都是使用哈希表来实现的，然后在外面套了一层壳，为了能够更好的实现代码复用，我们对哈希表进行了很多修改还使用了仿函数，封装了普通迭代器和const迭代器等，最终成功对unordered_map和unordered_set实现了封装，它们和使用红黑树对map和set封装非常类似，大家可以一起参考学习。以上就是今天所有的内容啦~ 完结撒花 ~🥳🎉🎉


http://www.ppmy.cn/news/1511901.html

相关文章

String、StringBuffer与StringBuilder的区别？

String、StringBuffer与StringBuilder的区别？

在 Java 中&#xff0c;String、StringBuffer 和 StringBuilder 都用于处理字符串&#xff0c;但它们在可变性、线程安全性和性能等方面存在一些重要的区别。下面详细说明这三者的区别&#xff1a; 1. String 定义&#xff1a;String 是不可变的&#xff08;immutable&#xf…
阅读更多...
电脑如何录屏？三款电脑录屏工具分享

电脑如何录屏？三款电脑录屏工具分享

电脑如何录屏&#xff1f;作为一个经常需要录制电脑屏幕大职场人&#xff0c;不是为了制作教程、记录会议&#xff0c;就是偶尔想自己做个游戏解说视频。市面上的录屏软件琳琅满目&#xff0c;经过一番尝试和比较&#xff0c;我选出了三款我个人认为表现不错的软件&#xff0c;…
阅读更多...
C++：C/C++的内存管理

C++：C/C++的内存管理

目录 C/C内存分布 C语言中动态内存管理方式 C内存管理方式 new/delete操作内置类型 new/delete操作自定义类型 operator new与operator delete函数 new和delete的实现原理 定位new表达式 常见问题 malloc/free和new/delete的区别 内存泄漏 C/C内存分布 我们先来看以…
阅读更多...
第R1周: RNN-心脏病预测

第R1周: RNN-心脏病预测

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 一、什么是RNN RNN&#xff08;Recurrent Neural Network&#xff09;是一种特殊的神经网络&#xff0c;它能够处理序列数据&#xff0c;如时间序列、文本序列…
阅读更多...
最前端｜Git如此重要的6条高效命令，你不会还没学会吧？

最前端｜Git如此重要的6条高效命令，你不会还没学会吧？

Git作为一款分布式版本控制系统&#xff0c;是现代软件开发中不可缺少的工具之一&#xff0c;更是现在开发工程师必备的技能。可大多数工程师还是只会最基本的保存、拉取、推送&#xff0c;遇到一些commit管理的问题就束手无策&#xff0c;或者用一些不优雅的方式解决。 本文分…
阅读更多...
防范小程序隐私合规风险，筑牢用户信任防线

防范小程序隐私合规风险，筑牢用户信任防线

随着国内APP软件生态的成熟&#xff0c;依托于头部APP的小程序逐渐成为零售、娱乐、出行等行业必选的获客渠道之一。较低的开发成本和成熟的用户营销功能&#xff0c;令小程序的数量在过去几年呈指数级增长。截止2023年&#xff0c;头部APP内集成的小程序总量已超千万。然而&am…
阅读更多...
Python | Leetcode Python题解之第345题反转字符串中的元音字母

Python | Leetcode Python题解之第345题反转字符串中的元音字母

题目&#xff1a; 题解&#xff1a; class Solution:def reverseVowels(self, s: str) -> str:def isVowel(ch: str) -> bool:return ch in "aeiouAEIOU"n len(s)s list(s)i, j 0, n - 1while i < j:while i < n and not isVowel(s[i]):i 1while j …
阅读更多...
Spring Boot的自动装配机制？(Spring Boot怎么完成自动装配的?)----面试常问

Spring Boot的自动装配机制？(Spring Boot怎么完成自动装配的?)----面试常问

Spring Boot的自动装配机制&#xff1f;(Spring Boot怎么完成自动装配的?) 目录 一、概念版&#xff08;重要&#xff09; 二、实操版 1. 依赖管理 (pom.xml导坐标) 2. 自动配置类 2.1 SpringBootApplication 注解 2.2 EnableAutoConfiguration 2.3 Import({AutoCon…
阅读更多...
旅游网站

旅游网站

TOC springboot281旅游网站 第1章 绪论 1.1 课题背景 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。所以各行业&#xff0…
阅读更多...
【自用13.1】C++推箱子游戏

【自用13.1】C++推箱子游戏

以下是初版代码&#xff0c;进行了初步的简单优化&#xff0c;具体思路以及优化步骤已经在备注中标明。 后期根据情况会出详细版的讲解。 #include <graphics.h> #include <iostream> #include <stdlib.h> #include <string> #include <conio.h&g…
阅读更多...
Axios vs Fetch：哪种网络请求工具在 Vue 项目中更胜一筹？

Axios vs Fetch：哪种网络请求工具在 Vue 项目中更胜一筹？

在 Vue.js 项目中进行网络请求是开发过程中不可避免的一部分&#xff0c;而常用的两种工具就是 axios 和原生的 fetch。这两者各有优劣&#xff0c;开发者在选择时需要根据具体需求进行权衡。本文将详细对比 axios 和 fetch&#xff0c;并展示如何在 Vue 项目中封装和使用它们。…
阅读更多...
ubuntu查看CPU、内存、硬盘

ubuntu查看CPU、内存、硬盘

1、查看CPU cat /proc/cpuinfo 我这台机器CPU是2核&#xff0c;所以这里是2核 或者使用如下命令也可以查看 lscpu 查看CPU使用率 top 2、查看内存 查看内存信息&#xff1a; free -h 查看内存使用情况&#xff1a; vmstat 3、硬盘 查看硬盘使用情况&#xff1a; df -…
阅读更多...
FPGA进阶教程15 使用mdio接口定义百兆以太网

FPGA进阶教程15 使用mdio接口定义百兆以太网

我们接上一讲&#xff0c;要搞懂这一节的内容需要仔细分析一下mdio_ctrl的代码&#xff0c;在百兆以太网中&#xff0c;我们使用的YT8511芯片是需要关闭自协商模式的&#xff0c;也就是寄存器地址为0X00的第12位要置为0&#xff0c;寄存器定义如下图所示&#xff1a; 其次&…
阅读更多...
选择金赛增，孩子轻松长高的科学方案

选择金赛增，孩子轻松长高的科学方案

最初我意识到孩子身高矮的时候&#xff0c;其实走了很多弯路&#xff0c;什么钙铁锌硒&#xff0c;各种营养品没少吃&#xff0c;可能是心里不愿意面对孩子可能是生病了这件事&#xff0c;还试了很多偏方&#xff0c;最后实在是不见长&#xff0c;才去了医院。 一开始去市医院…
阅读更多...
异构数据同步 datax （3） xxl-job 分布式任务调度

异构数据同步 datax （3） xxl-job 分布式任务调度

datax 需要手动执行 python 脚本来满足需求&#xff0c;可通过XXL-JOB 进行任务调度实现&#xff0c;满足自动化数据同步需求。 1、nacos 配置 # 配置 xxxx:job:runScript: /home/midware/datax/script/mysql_ps_test.shpythonScriptPath: /home/midware/datax/bin/datax.py j…
阅读更多...
MiniCPM-V: A GPT-4V Level MLLM on Your Phone论文阅读

MiniCPM-V: A GPT-4V Level MLLM on Your Phone论文阅读

大模型的趋势&#xff1a;模型性能越来越好&#xff0c;模型参数变小&#xff0c;端边设备计算能力变强。 MiniCPM-V优点 结果好、OCR能力突出、多分辨率、多语言、易于部署 模型结构 图片encoder适用vit。输入整体以及切片。切片使用自适应算法&#xff0c;通过计算分数&am…
阅读更多...
linux shell 脚本 let 数学计算

linux shell 脚本 let 数学计算

linux shell 脚本 let 数学计算 http://www.codebaoku.com/it-shell/ let命令中的算术表达式必须用双引号括起来&#xff0c;以避免解释器对特殊字符进行处理。 在变量的计算中&#xff0c;不需要使用$符号来表示变量&#xff0c; #!/bin/shweek_daydate %u echo $week_day…
阅读更多...
MCU复位RAM会保持吗，如何实现复位时变量数据保持

MCU复位RAM会保持吗，如何实现复位时变量数据保持

在使用MCU时&#xff0c;通常大家默认MCU复位时RAM会被复位清零&#xff0c;那实际MCU复位时RAM是什么状态&#xff1f;如何让mcu复位时RAM保持不变呢&#xff1f; MCU复位有电源复位、Standby复位、内核复位、看门狗复位、引脚复位等。 其中内部会有掉电动作的复位有电源复位…
阅读更多...
笔试练习day5

笔试练习day5

目录 游游的you题目解析解法方法一贪心方法二 腐烂的苹果题目解析例子1例子2解法多源BFS最短路径代码代码解析 JZ62 孩子们的游戏(圆圈中最后剩下的数)题目解析解法方法一模拟环形链表模拟数组模拟 方法二递推/递归/动态规划状态表示状态转移方程代码 感谢各位大佬对我的支持,如…
阅读更多...
全新分支版本！微软推出Windows 11 Canary Build 27686版

全新分支版本！微软推出Windows 11 Canary Build 27686版

已经很久没有看到 Windows 11 全新的分支版本了&#xff0c;今天微软发布 Windows 11 Canary 新版本&#xff0c;此次版本号已经转移到 Build 27xxx&#xff0c;首发版本为 Build 27686 版。 此次更新带来了多项改进&#xff0c;包括 Windows Sandbox 沙盒功能切换到 Microsof…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站