『 C++ - STL 』unordered_xxx系列关联式容器及其封装(万字)

文章目录

    • 🎡 unordered系列关联式容器
    • 🎡 哈希表的改造
      • 🎢 节点的设置与总体框架
      • 🎢 迭代器的封装
        • 🎠 迭代器的框架
        • 🎠 operator++()运算符重载
        • 🎠 其余成员函数/运算符重载
      • 🎢 迭代器begin()与end()
      • 🎢 Insert插入函数
      • 🎢 Find查找函数
      • 🎢 修改后哈希表整体代码(供参考)
    • 🎡 使用哈希表封装unordered_set
      • 🎢 基本框架
      • 🎢 setKeyOfT的实现
      • 🎢 unordered_set代码整体(供参考)
    • 🎡 使用哈希表封装unordered_map
      • 🎢 基本框架
      • 🎢 mapKeyOfT的实现
      • 🎢 operator[]的重载实现
      • 🎢 unordered_map代码整体(供参考)
    • 🎡 总结


🎡 unordered系列关联式容器

请添加图片描述

在之前的博客中有提到C++中存在一些列的关联式容器,例如mapset,其底层采用红黑树进行实现;

但除了mapset以外,还存在着对应的unordered_mapunordered_set关联式容器,当然也存在着对应的multi版本(unordered_multimapunordered_multiset);

mapset不同,unordered_mapunordered_set的底层实现为哈希表;

unordered系列关联式容器在C++11标准中被首次引入,与有序容器不同,unordered系列的关联式容器并不会去维护数据中各个元素的顺序,由于该系列容器为哈希表实现,所以整体的存储顺序是由哈希函数决定的,可以在一些不需要对数据进行排序的场景下提供更快的性能;

  • 时间复杂度

    • unordered系列关联式容器

      插入、删除和查找操作的平均时间复杂度为O(1),即常数时间。

      在极少数情况下,可能会出现O(N)的性能退化,特别是当哈希冲突频繁发生时。

    • 普通关联式容器

      插入、删除和查找操作的平均时间复杂度为O(log N),其中N是元素的数量。

      这是因为普通关联式容器使用树结构(通常是红黑树)来维护有序性。

  • 存储方式

    • unordered系列关联式容器

      使用哈希表来存储元素,哈希函数决定了元素的存储位置,不维护有序性。

      元素的存储顺序是无序的。

    • 普通关联式容器

      使用二叉树(通常是红黑树)来存储元素,维护元素的有序性。

      元素的存储顺序是按键排序的。

  • 稳定性

    • unordered系列关联式容器

      插入元素不会导致重新哈希或重新排列容器中的元素。

      因此,unordered系列容器的迭代器相对来说更稳定,即在插入操作后,现有的迭代器仍然有效。

      但需要注意,当容器的装载因子(load factor)过高时,可能需要扩展容器的大小,这可能会导致重新哈希,但这种情况相对较少。

    • 普通关联式容器

      插入或删除元素可能导致树的重新平衡,或者树结构的改变。

      这可能会使得现有的迭代器失效,因为树的结构发生变化。

      不过,由于树的平衡调整相对较少,这种情况的发生频率通常较低。

本篇文章重点以使用哈希表来封装unordered_xxx系列关联式容器为主题,包括哈希表中对于迭代器的实现;


🎡 哈希表的改造

请添加图片描述

首先在上篇博客『 C++ - Hash 』闭散列与开散列哈希表详解及其实现 ( 万字 )-CSDN博客 中提到了哈希表的实现;

在该篇文章当中有关哈希表的代码是一个pair容器来实现其Key Value的模型;

但实际上在STL的源码当中,哈希表的实现框架与红黑树的实现框架相同,因为其也要结合且兼顾unordered_mapunordered_set两个容器,即一个哈希表封装成两个容器,而在上一篇文章中的哈希表为pair,不符合STL的源码框架;

故在进行封装前应先对哈希表进行改造,将其能够像map,set容器的红黑树底层一样;

那么大体构造上即相同;


🎢 节点的设置与总体框架

请添加图片描述

在上一篇文章中节点的设置为一个pair容器;

template <class K, class V>
struct HashNode {
  // 哈希表的节点设置
  typedef HashNode<K, V> Node;
  Node* _next = nullptr;
  std::pair<K, V> _kv;

  HashNode(const std::pair<K, V> kv) : _kv(kv) {}
};

而真正需要使用泛型的特性使其能够兼顾两个容器那么必须将模板参数变为一个,且模板参数的传入为unordered_mapunordered_set两个容器;

  • unordered_map

    当容器为unordered_map时节点中模板参数传来的类型为std::pair<const K , V>;

  • unordered_set

    当容器为unordered_set时节点中模板参数传来的类型为const K;

template <class T>
struct HashNode {
  T _data;
  HashNode<T>* _next;

  HashNode(const T& data) : _data(data), _next(nullptr) {}
};

而至于大体框架而言变化并不大,在原本的哈希表当中实现的是KV模型;

template <class K, class V, class Hash = HashFunc<K>>
class HashTable {
 public:
  typedef HashNode<K, V> Node;
    //...
 private:
  std::vector<Node*> _hashtable;  // 哈希表整体构造
  size_t _n = 0;                  // 负载因子
};

为了实现确保泛型,其模板参数应该更改为KT模型,其中K为键Key,T则为data,即传入的数据类型,根据实现的容器进行传参;

  • unordered_map

    当容器为unordered_mapKpairkey的键,一般用于查找或者遍历,而T则为真正存储的类型;

  • unordered_set

    当容器为unordered_setKkey键,用于查找或遍历,而T则为真正存储的类型;

在真正的实现当中unordered_set容器为了妥协能够与unordered_map容器共同使用一个哈希表,其将会在封装时传入一个冗余的参数;

template <class K /*键*/, class T /*数据类型(pair或者K)*/,
          class KeyOfT /*仿函数 用于取出data中的Key*/,
          class Hash = HashFunc<K> /*仿函数 用于将数据进行size_t化*/>
class HashTable {
  friend struct __Hash_Iterator<
      K, T, T&, T*, KeyOfT, Hash>;  // 避免友元声明时出现的"模板参数阴影"问题

 public:
  typedef __Hash_Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;
  typedef __Hash_Iterator<K, T, const T&, const T*, KeyOfT, Hash>
      const_iterator;

  typedef HashNode<T> Node;
    //...
 protected:
 private:
  size_t _n = 0;  // 负载因子
  std::vector<Node*> _hashTable;
};

从该段代码当中可以看出实际上在修改后的哈希表的总体框架当中的模板参数甚至还多了一个模板参数;

这是因为与mapset相同;

由于是模板,所以不能确保所传进来的参数是什么,但是却都要对应的Key键;

所以在封装的过程中两个容器应该再传入一个仿函数,尤其是unordered_map,使其能够通过仿函数来取到pair容器中的Key键;

对应的仿函数与文章『 C++ - STL』map与set的封装 ( 万字 )-CSDN博客 中的仿函数相同,当然也将在下文中再次进行阐述;

代码段中所出现的对迭代器进行typedef从而能够更轻松的修改其他的代码内容;

其迭代器的实现将在下文进行阐述;


🎢 迭代器的封装

请添加图片描述

在上篇文章的哈希表实现当中并未对迭代器进行封装,该篇文章将对迭代器进行实现从而能够更好的使用哈希表能够封装两个容器;

哈希表的迭代器实际上是一个单向的迭代器,其在迭代期间不能使用类似于--的反向迭代,这也是在开始时拉链法的哈希表中桶下挂的是单链表而不是双向链表的原因之一;

那么既然是单向迭代器,其最重点的思考为:

  • 实现迭代器时其需要的具体参数是什么?

    从该点中可以想到,迭代器实际上是一个一个节点进行遍历,本质上是指针的运动;

    而为了实现迭代器的功能,其必须对指针进行封装,所以节点的指针至关重要;

    而我们实现的哈希表使用的是一个拉链法,即哈希桶的办法,那么在迭代过程中应该分为两种情况:

    1. 当前迭代器位置的下一个位置处于vector容器当中;
    2. 当前迭代器位置的下一个位置处于桶下的链表当中;

    当下一个位置是vector容器中时,则可以继续遍历vector容器,说明表的本体也至关重要;

    而下一个位置是链表时只需要对节点指向其_next指针即可;

    综上所述,重点需要的参数为节点指针哈希表本体;

  • 如何使其进行operator++()使其从当前迭代器位置移动至下一个位置?

    这个问题实际上考虑的是迭代器如何进行遍历,在上个问题的回答即阐明了如何对迭代器进行迭代;


🎠 迭代器的框架

请添加图片描述

template <
    class K /*键值*/, class T /*数据*/, class Ref /*引用 用于 opoerator* */,
    class Ptr /*指针 用于operator->*/, class KeyOfT,
    class
    Hash /*仿函数 该模板参数以及前一个模板参数KeyOfT都是用于实例化哈希表*/>
        
struct __Hash_Iterator {
  friend class HashTable<K,T,KeyOfT,Hash>;

  // 单向迭代器 只需要实现++
  typedef HashTable<K, T, KeyOfT, Hash> HsTable;
  typedef __Hash_Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
  typedef __Hash_Iterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
  typedef HashNode<T> Node;
    
      // 两个构造函数
  __Hash_Iterator(Node* node, HsTable* ht) : _Ht(ht), _node(node){}
  __Hash_Iterator(const Iterator& it) : _Ht(it._Ht), _node(it._node) {}

  
  HsTable* _Ht;// 需要哈希表本体
  Node* _node;  // 节点指针
};

在该段代码中可以发现这里采用了一个友元声明;

 friend class HashTable<K,T,KeyOfT,Hash>;

实际上友元声明的原因是确保在迭代器中能够正常的去访问哈希表中的私有成员;

当然这里还需要考虑一个声明顺序的原因,若你的哈希表定义处于迭代器的后面,你应该在迭代器定义前加上哈希表的前置声明,确保迭代器能够正确访问哈希表;

其中的Ref ,Ptr等模板参数在之前的文章与该代码段中都存在相应的注释,这里不再进行过多赘述;

而在代码段当中出现的构造函数一个为构造函数一个为拷贝构造函数;

拷贝构造函数能够通过普通版本的迭代器从而实现出const版本的迭代器;


🎠 operator++()运算符重载

请添加图片描述

对于该操作符的重载迭代思路可以参考上文中出现的迭代器的封装中所引出的问题答案之一;

// operator++();
  Self& operator++() {
    if (_node->_next != nullptr) {
      _node = _node->_next;
    } else {
      // 找下一个不为空的桶
      KeyOfT kot;
      Hash hash;
      // 算出我当前的桶位置
      size_t hashi = hash(kot(_node->_data)) % _Ht->_hashTable.size();
      ++hashi;
      while (hashi < _Ht->_hashTable.size()) {
        if (_Ht->_hashTable[hashi]) {
          _node = _Ht->_hashTable[hashi];
          break;
        } else {
          ++hashi;
        }
      } 
      // 没有找到不为空的桶
      if (hashi == _Ht->_hashTable.size()) {
        _node = nullptr;
      }
    }

    return *this;
  }


🎠 其余成员函数/运算符重载

请添加图片描述

其余成员函数于运算符重载主要着重为:

  • Ret operator*()
  • Ptr operator->()
  • bool operator==(const Iterator& it)
  • bool operator!=(const Iterator& it)
  // operator*();
  Ref operator*() { return _node->_data; }

  // operator->();
  Ptr operator->() { return &_node->_data; }

  // operator==();
  bool operator==(const Iterator& it) { return it._node == _node; }

  // operator!=();
  bool operator!=(const Iterator& it) { return it._node != _node; }


🎢 迭代器begin()与end()

请添加图片描述

在实现迭代器后即可以考虑如何找到迭代器的begin()位置与end()位置;

对于begin()位置而言,只需要对vector容器进行遍历,若是容器中的任意位置存在非空(nullptr)节点,则表示其begin()位置在该处;

而对于end()函数而言,只需要利用nullptr空指针构造迭代器即可;

对于const版本的迭代器也是如此;

  iterator begin() {  // 普通版本迭代器
    Node* cur = nullptr;
    size_t i = 0;
    for (; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        break;
      }
    }
    if (cur) {
      return iterator(cur, this);
    }
    return iterator(nullptr, this);
  }

//------------------------------

  iterator end() { return iterator(nullptr, this); }  // 普通版本迭代器

//------------------------------

  const_iterator begin() const {  // const版本迭代器
    size_t i = 0;
    Node* cur = nullptr;
    for (; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        break;
      }
    }
    if (cur) {
      return iterator(cur, this);
    }
    return iterator(nullptr, this);
  }

//------------------------------

  const_iterator end() const {
    return iterator(nullptr, this);
  }  // const版本迭代器

当然这里的返回值为迭代器或者是const版本的迭代器,在使用前应该对其进行typedef使得在哈希表中能够自由使用迭代器(下文内容也是如此);


🎢 Insert插入函数

请添加图片描述

对于Insert()函数而言,unordered系列容器中的insert()函数的返回值为std::pair<iterator,bool>类型的返回值;

而其insert()函数为调用哈希表中的Insert()函数;

在迭代器实现之后,更改后的Insert()函数也可以按照对应的返回值进行返回从而达到容器可以复用的效果;

std::pair<iterator, bool> Insert(const T& data) {

    KeyOfT kot;
    Hash hash;

    iterator isIn = Find(kot(data));//判断该数据是否存在 若是存在则不进行插入
    if (isIn != end()){
      return  std ::make_pair(iterator(nullptr, this), false);
    }

      if (_hashTable.size() == _n) {  // 负载因子 == 1 需要进行扩容
        size_t newSize = GetNextPrime(_hashTable.size());  // 获取新的节点大小
        std::vector<Node*> newTable(newSize,nullptr);

        for (size_t i = 0; i < _hashTable.size(); ++i) {
          Node* cur = _hashTable[i];
          while (cur) {
            Node* next = cur->_next;

            size_t hashi = hash(kot(cur->_data)) % newTable.size();
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _hashTable[i] = nullptr;
        }
        _hashTable.swap(newTable);
      }

    size_t hashi = hash(kot(data)) % _hashTable.size();
    Node* newnode = new Node(data);
    newnode->_next = _hashTable[hashi];
    _hashTable[hashi] = newnode;
    _n++;
    return std ::make_pair(iterator(newnode, this), true);
  }

在大体的思路上基本不变,唯一多了一个就是KeyOfT仿函数从而可以从T类型数据中取到其对应的Key;


🎢 Find查找函数

请添加图片描述

对于Find()而言,与Insert()函数相同,只需要更改其返回值为iterator类型即可;

iterator Find(const K& key) {
    Hash hash;
    KeyOfT kot;

    if (_hashTable.size() == 0) return end();
    size_t hashi = hash(key) % _hashTable.size();
    Node* cur = _hashTable[hashi];
    while (cur) {
      if (kot(cur->_data) == key) {
        return iterator(cur, this);
      }
      cur = cur->_next;
    }
    return end();
  }

🎢 修改后哈希表整体代码(供参考)

请添加图片描述

对于哈希表的改造在成员函数方面的改造着重对Insert()Find()进行阐述;

其他函数的改动微乎其微,至多只是加上了KeyOfT仿函数使其能够产生泛型属性,因此不进行赘述;

#pragma once

#include <iostream>
#include <string>
#include <vector>

namespace MyHash {
template <class T>
struct HashNode {
  T _data;
  HashNode<T>* _next;

  HashNode(const T& data) : _data(data), _next(nullptr) {}
};

template <class K>
struct HashFunc { /*仿函数 用于将数据进行size_t化*/
  size_t operator()(const K& key) { return key; }
};

template <>
struct HashFunc<std::string> { /*仿函数 用于将数据进行size_t化*/
  // 该处的仿函数需要使用字符串哈希的方式来确认整个string字符串的ASCII大小
  size_t operator()(const std::string& str) {
    size_t hash = 0;
    for (auto ch : str) {
      hash += ch;
      hash *= 31;
    }
    return hash;
  }
};

template <class K, class T, class KeyOfT, class Hash>
class HashTable;  // 前置声明


template <
    class K /*键值*/, class T /*数据*/, class Ref /*引用 用于 opoerator* */,
    class Ptr /*指针 用于operator->*/, class KeyOfT,
    class
    Hash /*仿函数 该模板参数以及前一个模板参数KeyOfT都是用于实例化哈希表*/>

struct __Hash_Iterator {
  friend class HashTable<K,T,KeyOfT,Hash>;

  // 单向迭代器 只需要实现++
  typedef HashTable<K, T, KeyOfT, Hash> HsTable;
  typedef __Hash_Iterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
  typedef __Hash_Iterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
  typedef HashNode<T> Node;



  // 两个构造函数
  __Hash_Iterator(Node* node, HsTable* ht) : _Ht(ht), _node(node){}
  __Hash_Iterator(const Iterator& it) : _Ht(it._Ht), _node(it._node) {}

  // operator++();
  Self& operator++() {
    if (_node->_next != nullptr) {
      _node = _node->_next;
    } else {
      // 找下一个不为空的桶
      KeyOfT kot;
      Hash hash;
      // 算出我当前的桶位置
      size_t hashi = hash(kot(_node->_data)) % _Ht->_hashTable.size();
      ++hashi;
      while (hashi < _Ht->_hashTable.size()) {
        if (_Ht->_hashTable[hashi]) {
          _node = _Ht->_hashTable[hashi];
          break;
        } else {
          ++hashi;
        }
      }

      // 没有找到不为空的桶
      if (hashi == _Ht->_hashTable.size()) {
        _node = nullptr;
      }
    }

    return *this;
  }

  // operator*();
  Ref operator*() { return _node->_data; }

  // operator->();
  Ptr operator->() { return &_node->_data; }

  // operator==();
  bool operator==(const Iterator& it) { return it._node == _node; }

  // operator!=();
  bool operator!=(const Iterator& it) { return it._node != _node; }

  // 需要哈希表本体
  HsTable* _Ht;
  Node* _node;  // 节点指针
};

template <class K /*键值*/, class T /*数据类型(pair或者K)*/,
          class KeyOfT /*仿函数 用于取出data中的Key*/,
          class Hash = HashFunc<K> /*仿函数 用于将数据进行size_t化*/>
class HashTable {
  friend struct __Hash_Iterator<
      K, T, T&, T*, KeyOfT, Hash>;  // 避免友元声明时出现的"模板参数阴影"问题

 public:
  typedef __Hash_Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;
  typedef __Hash_Iterator<K, T, const T&, const T*, KeyOfT, Hash>
      const_iterator;

  typedef HashNode<T> Node;
  iterator begin() {  // 普通版本迭代器
    Node* cur = nullptr;
    size_t i = 0;
    for (; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        break;
      }
    }
    if (cur) {
      return iterator(cur, this);
    }
    return iterator(nullptr, this);
  }

  ~HashTable() {
    Node* cur = nullptr;
    for (size_t i = 0; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        Node* next = cur->_next;
        while (cur) {
          delete cur;
          cur = next;
        }
      }
    }
  }

  iterator end() { return iterator(nullptr, this); }  // 普通版本迭代器

  const_iterator begin() const {  // const版本迭代器
    size_t i = 0;
    Node* cur = nullptr;
    for (; i < _hashTable.size(); ++i) {
      if (_hashTable[i]) {
        cur = _hashTable[i];
        break;
      }
    }
    if (cur) {
      return iterator(cur, this);
    }
    return iterator(nullptr, this);
  }

  const_iterator end() const {
    return iterator(nullptr, this);
  }  // const版本迭代器

  std::pair<iterator, bool> Insert(const T& data) {

    KeyOfT kot;
    Hash hash;

    iterator isIn = Find(kot(data));//判断该数据是否存在 若是存在则不进行插入
    if (isIn != end()){
      return  std ::make_pair(iterator(nullptr, this), false);
    }

      if (_hashTable.size() == _n) {  // 负载因子 == 1 需要进行扩容
        size_t newSize = GetNextPrime(_hashTable.size());  // 获取新的节点大小
        std::vector<Node*> newTable(newSize,nullptr);

        for (size_t i = 0; i < _hashTable.size(); ++i) {
          Node* cur = _hashTable[i];
          while (cur) {
            Node* next = cur->_next;

            size_t hashi = hash(kot(cur->_data)) % newTable.size();
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _hashTable[i] = nullptr;
        }
        _hashTable.swap(newTable);
      }

    size_t hashi = hash(kot(data)) % _hashTable.size();
    Node* newnode = new Node(data);
    newnode->_next = _hashTable[hashi];
    _hashTable[hashi] = newnode;
    _n++;
    return std ::make_pair(iterator(newnode, this), true);
  }

  iterator Find(const K& key) {
    Hash hash;
    KeyOfT kot;

    if (_hashTable.size() == 0) return end();
    size_t hashi = hash(key) % _hashTable.size();
    Node* cur = _hashTable[hashi];
    while (cur) {
      if (kot(cur->_data) == key) {
        return iterator(cur, this);
      }
      cur = cur->_next;
    }
    return end();
  }

  bool Erase(const K& key) {
    Hash hash;
    KeyOfT kot;

    size_t hashi = hash(key) % _hashTable.size();

    Node* prev = nullptr;
    Node* cur = _hashTable[hashi];

    while(cur){
        if(kot(cur->_data) == key){
            if(prev == nullptr){
              _hashTable[hashi] = cur->_next;
            }
            else{
              prev->_next = cur->_next;
            }
            --_n;
            delete cur;
            return true;
        }
        else{
          prev = cur;
          cur = cur->_next;
        }
    }
    return false;
  }

  size_t GetNextPrime(size_t prime) {
    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};

    size_t i = 0;
    for (; i < __stl_num_primes; ++i) {
      if (__stl_prime_list[i] > prime) {
        return __stl_prime_list[i];
      }
    }
    return __stl_prime_list[i];
  }

 protected:
 private:
  size_t _n = 0;  // 负载因子
  std::vector<Node*> _hashTable;
};

🎡 使用哈希表封装unordered_set

请添加图片描述

对于哈希表封装unordered_xxx系列容器的大部分操作与红黑树封装map,set基本相同;

即在容器当中调用数据结构(红黑树,哈希表)中的成员函数即可,迭代器也是调用数据结构中的迭代器即可;


🎢 基本框架

请添加图片描述

template <class K, class Hash = HashFunc<K>>
class unordered_set {
 public:
  typedef typename MyHash::HashTable<K, K, setKeyOfT, Hash>::iterator iterator;
  typedef typename MyHash::HashTable<K, K, setKeyOfT, Hash>::iterator
      const_iterator;
 protected:
 private:
  HashTable<K, K, setKeyOfT, Hash> _Ht;
};

在代码段中可以看出,在设置模板参数时其中出现了一个在哈希表中实现的Hash仿函数;

这个仿函数实际上在容器的实现当中并不起到很大的作用,只是单纯的在进行传参时所用到;

这里在对迭代器进行typedef时还使用了typename,这里的typename的用途是告知正在typedef是一个类型;

同时这里可以发现在上文中提到的unordered_set在实现当中妥协unordered_map而传入的冗余模板参数,即多传了一个K;


🎢 setKeyOfT的实现

请添加图片描述

在上文当中提到,哈希表的实现当中的模板参数中存在一个KeyOfT的仿函数,这个仿函数实际上是用来取出类型中的Key;

而这个仿函数是由容器传至哈希表中,所以定义是在容器当中;

这个仿函数可以直接以内部类的形式进行定义;

set容器当中,由于set容器的传参只有一个Key,所以只需要在仿函数中直接返回key即可;

   struct setKeyOfT {
    const K& operator()(const K& key) { return key; }
  };

由于是内部类,所以其可以直接访问其外部的模板参数,没必要再次定义模板参数;


🎢 unordered_set代码整体(供参考)

请添加图片描述

对于其他成员函数而言只需要直接调用哈希表中的成员函数即可;

#include <iostream>

#include "Hash.h"

template <class K, class Hash = HashFunc<K>>
class unordered_set {
 public:
  struct setKeyOfT {
    const K& operator()(const K& key) { return key; }
  };
  typedef typename MyHash::HashTable<K, K, setKeyOfT, Hash>::iterator iterator;
  typedef typename MyHash::HashTable<K, K, setKeyOfT, Hash>::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(); }

  std::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); }

 protected:
 private:
  HashTable<K, K, setKeyOfT, Hash> _Ht;
};

🎡 使用哈希表封装unordered_map

请添加图片描述

在上文当中已经提到了封装unordered_xxx系列容器的总体思路,在此不进行赘述;


🎢 基本框架

请添加图片描述

template <class K,class V, class Hash = HashFunc<K>>
class unordered_map {
 public:
  typedef typename MyHash::HashTable<K, std::pair<const K, V>, mapKeyOfT,
                                     Hash>::iterator iterator;
  typedef typename MyHash::HashTable<K, std::pair<const K, V>, mapKeyOfT,
                                     Hash>::iterator const_iterator;
    
 protected:
 private:
  HashTable<K,std::pair< const K, V>, mapKeyOfT, Hash> _Ht;
};

在该段代码中可以看出与unordered_set实现的框架只有在模板参数的传递中出现差异,其他大体相同;


🎢 mapKeyOfT的实现

请添加图片描述

由于unordered_map中所传递的类型是一个std::pair<const K,V>类型,所以显得其KeyOfT仿函数尤为重要;

需要使用仿函数在pair中找到其key;

  struct mapKeyOfT {
    const K& operator()(const std::pair<K,V>& data) { return data.first; }
  };

unordered_set相同也是一个内置类以至可以复用相同用的模板参数;


🎢 operator[]的重载实现

请添加图片描述

unordered_set不同的一点是unordered_map支持使用[]对数据进行访问;

其中[]的功能在unordered_map中既能实现查找插入,也能实现对其V值进行查找即修改;

  • [K]存在

    若是[K]存在则不进行插入,并返回对应的V值;

  • [K]不存在

    若是[K]不存在,则进行插入,并返回对应的V值;

  V& operator[](const K& key) {
    std::pair<iterator,bool> ret = insert(std::make_pair(key, V()));
    // ret.first 是 iterator 类型
    return ret.first->second;  // 访问 iterator 指向的 HashNode 的 _data 成员的 second 部分
  }

只需要通过返回的迭代器去访问其类型(pair)中的second即可;


🎢 unordered_map代码整体(供参考)

请添加图片描述

template <class K,class V, class Hash = HashFunc<K>>
class unordered_map {
 public:
  struct mapKeyOfT {
    const K& operator()(const std::pair<K,V>& data) { return data.first; }
  };
  typedef typename MyHash::HashTable<K, std::pair<const K, V>, mapKeyOfT,
                                     Hash>::iterator iterator;
  typedef typename MyHash::HashTable<K, std::pair<const K, V>, mapKeyOfT,
                                     Hash>::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(); }

  std::pair<iterator, bool> insert(const std::pair<K, V>& data) {
    return _Ht.Insert(data);
  }

  iterator find(const K& key) { return _Ht.Find(key); }

  bool erase(const K& key) { return _Ht.Erase(key); }

  V& operator[](const K& key) {
    std::pair<iterator,bool> ret = insert(std::make_pair(key, V()));
    // ret.first 是 iterator 类型
    return ret.first->second;  // 访问 iterator 指向的 HashNode 的 _data 成员的 second 部分
  }

 protected:
 private:
  HashTable<K,std::pair< const K, V>, mapKeyOfT, Hash> _Ht;
};

🎡 总结

请添加图片描述

在对unordered_xxx系列关联式容器进行封装时重点除了上述以外还应该检查在封装中出现的类型转换问题;

尤其是对const非const的转换进行检查,避免在封装中出现因为权限缩小问题所引发的报错;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/375553.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ES监控方法以及核心指标

文章目录 1. 监控指标采集1.1 部署elasticsearch_exporter1.2 prometheus采集elasticsearch_exporter的暴露指标1.3 promethues配置告警规则或者配置grafana大盘 2. 核心告警指标2.1 es核心指标2.2 es容量模型建议 3. 参考文章 探讨es的监控数据采集方式以及需要关注的核心指标…

ArcGIS的UTM与高斯-克吕格投影分带要点总结

UTM&#xff08;通用横轴墨卡托投影、等角横轴割椭圆柱投影&#xff09;投影分带投影要点&#xff1a; 1&#xff09;UTM投影采用6度分带 2&#xff09;可根据公式计算&#xff0c;带数&#xff08;经度整数位/6&#xff09;的整数部分31 3&#xff09;北半球地区&#xff0…

使用dbeaver导入Excel到mysql数据库

最近业务需要将Excel导入到mysql数据库中&#xff0c;之前一直用的heisql&#xff0c;但是heidisql的导入功能太弱了&#xff0c;后来用了dbeaver&#xff0c;功能很强大。 一、安装dbeaver 首先去官网下载dbeaver社区版&#xff0c;社区版免费&#xff1a;dbeaver.io/ dbea…

ISIS 特性验证(ATT置位、渗透、认证)

拓扑图 配置 sysname AR1 # isis 1is-level level-1cost-style widenetwork-entity 49.0001.0000.0000.0001.00 # interface GigabitEthernet0/0/0ip address 12.1.1.1 255.255.255.0 isis enable 1 # interface GigabitEthernet0/0/1ip address 13.1.1.1 255.255.255.0 isis e…

【Java安全】ysoserial-URLDNS链分析

前言 Java安全中经常会提到反序列化&#xff0c;一个将Java对象转换为字节序列传输&#xff08;或保存&#xff09;并在接收字节序列后反序列化为Java对象的机制&#xff0c;在传输&#xff08;或保存&#xff09;的过程中&#xff0c;恶意攻击者能够将传输的字节序列替换为恶…

ideal打包,如何访问项目根目录的libs中的jar包

参考&#xff1a;idea maven 导入lib中jar 并打包_maven引入lib中的jar包-CSDN博客 解决办法&#xff0c;只需要在pom文件中加入 <includeSystemScope>true</includeSystemScope> <build><!-- <includeSystemScope>true</includeSystemScope&g…

Matlab数据快速处理指南

文章目录 Excel文件转Mat或工作区从Excel文件读取数据并转换为.mat文件从Excel文件读取数据并加载到工作区 Mat文件转ExcelExcel快速实现万行级填充各种数据类型的操作创建结构体访问结构体字段修改结构体字段的值添加新字段删除字段遍历结构体字段 Excel文件转Mat或工作区 在…

Java中JVM常用参数配置(提供配置示例)

目录 前言一、内存参数配置二、垃圾收集器配置三、GC策略配置3.1、基础通用配置3.2、Parallel 和 Parallel Old 常用参数配置3.3、CMS 常用参数配置3.4、G1 常用参数配置 四、GC日志配置五、dump 日志参数配置5.1、OutOfMemory异常时生成dump文件5.2、发生Full GC时生成dump文件…

《Git 简易速速上手小册》第1章:Git 基础(2024 最新版)

文章目录 1.1 Git 简介&#xff1a;版本控制的演变1.1.1 基础知识讲解1.1.2 重点案例&#xff1a;协作开发流程优化案例&#xff1a;功能开发与分支策略 1.1.3 拓展案例 1&#xff1a;代码审查与合并1.1.4 拓展案例 2&#xff1a;冲突解决 1.2 安装和配置 Git&#xff1a;首次设…

WebSocket基础详解

文章目录 前言由来简介优缺点适用场景兼容性 API介绍构造函数实例方法send()close() 实例属性ws.readyState&#xff08;只读&#xff09;ws.bufferedAmount&#xff08;只读&#xff09;ws.binaryTypeextensions&#xff08;只读&#xff09;protocol&#xff08;只读&#xf…

React+Antd实现表格自动向上滚动

1、效果 2、环境 1、react18 2、antd 4 3、代码实现 原理&#xff1a;创建一个定时器&#xff0c;修改表格ant-table-body的scrollTop属性实现滚动&#xff0c;监听表层的元素div的鼠标移入和移出实现实现鼠标进入元素滚动暂停&#xff0c;移出元素的时候表格滚动继续。 一…

VXLAN网关技术及应用实例详解

1.特性概述 VXLAN是VLAN扩展方案草案&#xff0c;是NVo3中的一种网络虚拟化技术。采用MAC in UDP封装方式&#xff0c;将二层报文用三层协议进行封装&#xff0c;可对二层网络在三层范围进行扩展&#xff0c;同时支持24bits的VNIID ( 16M租户能力&#xff09;&#xff0c;满足…

项目02《游戏-09-开发》Unity3D

基于 项目02《游戏-08-开发》Unity3D &#xff0c; 本次任务是做抽卡界面&#xff0c;获取的卡片增添在背包中&#xff0c;并在背包中可以删除卡片&#xff0c; 首先在Canvas下创建一个空物体&#xff0c;命名为LotteryPanel&#xff0c;作为抽卡界面&#xff0c; …

华视 CVR-100UC 身份证读取 html二次开发模板

python读卡&#xff1a;python读卡 最近小唐应要求要开发一个前端的身份证读卡界面&#xff0c;结果华视CVR-100UC 的读取界面是在是有点&#xff0c;而且怎么调试连官方最基本的启动程序都执行不了。CertReader.ocx 已成功&#xff0c;后面在问询一系列前辈之后&#xff0c;大…

探索设计模式的魅力:设计之美-揭秘设计模式、原则与UML的魔法

设计模式专栏&#xff1a;http://t.csdnimg.cn/U54zu 目录 一、引言 二、设计模式与设计原则 设计模式 设计原则 三、面向对象设计原则 四、UML&#xff08;统一建模语言&#xff09; 4.1 UML是什么 UML是一种语言 UML是一种建模语言 UML是一种图形化语言 4.2 UML有什么 4.…

使用 git 上传文件时,运行 命令 git pull origin 时未成功,出现报错信息

项目场景&#xff1a; 背景&#xff1a; 使用 git 上传文件时&#xff0c;运行 命令 git pull origin 时未成功&#xff0c;出现报错信息 问题描述 问题&#xff1a; $ git pull origin print --allow-unrelated-histories error: Pulling is not possible because you hav…

蓝桥杯刷题day08——完全日期

1、题目描述 如果一个日期中年月日的各位数字之和是完全平方数&#xff0c;则称为一个完全日期。 例如&#xff1a;2021年6月5日的各位数字之和为20216516&#xff0c;而16是一个完全平方数&#xff0c;它是4的平方。所以2021年6月5日是一个完全日期。 请问&#xff0c;从200…

Maven详细配置整理

Maven的作用 在Javaweb开发中&#xff0c;需要使用大量的jar包&#xff0c;需要手动去导入&#xff0c;Maven能够自动帮我们导入和配置这个jar包。 对于新手Maven就是用来方便导入jar包的&#xff01; Maven的核心思想&#xff1a;约定大于配置 有约束&#xff0c;不要去违…

51 -25 Scene as Occupancy 3D占用作为场景表示 论文精读

本文阅读的文章是Scene as Occupancy&#xff0c;介绍了一种将物体表示为3D occupancy的新方法&#xff0c;以描述三维场景&#xff0c;并用于检测、分割和规划。 文章提出了OccNet和OpenOcc两个核心概念。 OccNet 3D占用网络是一种以多视图视觉为中心的方法&#xff0c;通过…

【TCP】高频面试题

前言 在IT行业的求职过程中&#xff0c;传输控制协议&#xff08;TCP&#xff09;作为网络通信的核心协议之一&#xff0c;其相关面试题常常出现在各大公司面试中。TCP的稳定性和可靠性是支撑互联网数据传输的基石&#xff0c;因此&#xff0c;对TCP有深入理解不仅能够帮助求职…