• C++:unordered_map/unordered_set


    "只有我,守着安静的沙漠。等待着花开。"


     (一)unorderd系列容器;

    (1)来源;

    准确来说unordered系列关联式容器,是在C++ 11出来的。因为在C++98中引入了以红黑树为底层的map/set,但是当树的高度足够高,节点足够多时,查询的效率是不理想的。

    本文中只对unordered_mapunordered_set进行介绍

    unordered_multimap和unordered_multiset 和 multimap/multiset 异曲同工

     

    (2)文档说明;

     

    unordered_set; 

     

    unordered_map;

     


     (二)关联式容器模拟实现;

    unorderd 系列 底层封装的 哈希结构;

    (1)结构

    1. template<class K>
    2. class unordered_set
    3. {
    4. public:
    5. struct SetOFT
    6. {
    7. K& operator()(const K& key)
    8. {
    9. return key;
    10. }
    11. };
    12. private:
    13. OpenHash::HashBuckets _us;
    14. };
    15. template<class K,class V>
    16. class unordered_map
    17. {
    18. public:
    19. struct MapOFT
    20. {
    21. K& operator()(const pair& kv)
    22. {
    23. return kv.first;
    24. }
    25. };
    26. private:
    27. OpenHash::HashBuckets,MapOFT> _um;
    28. };

    插入部分也要相应更改;

     


    (2) 迭代器;

    哈希并没有提供 双向 迭代器。因为其底层本身就是实现的是单链表。  

     

    注意的坑; 

    1. template<class K, class T, class KeyOFT, class HashFunc = Hash>
    2. struct _Hashiterator
    3. {
    4. typedef HashData Node;
    5. Node* _node;
    6. typedef _Hashiterator Self;
    7. typedef HashBuckets HT;
    8. HT* _hp;
    9. _Hashiterator(Node* node, HT* hp)
    10. :_node(node),
    11. _hp(hp)
    12. {}
    13. T& operator*()
    14. {
    15. return _node->_data;
    16. }
    17. T* operator->()
    18. {
    19. return &_node->_data;
    20. }
    21. Self& operator++()
    22. {
    23. if (_node->_next)
    24. {
    25. //这里说明 同一块区域的 节点还没走完
    26. _node = _node->_next;
    27. }
    28. else
    29. {
    30. //需要换节点
    31. //找到当前 index
    32. size_t index = HashFunc()(KeyOFT()(_node->_data)) % _hp->_table.size();
    33. ++index;
    34. //index 完就结束
    35. while (index < _hp->_table.size())
    36. {
    37. if (_hp->_table[index])
    38. {
    39. //不为空 就说明 下面挂了节点
    40. _node = _hp->_table[index];
    41. return *this;
    42. }
    43. else
    44. {
    45. ++index;
    46. }
    47. }
    48. //说明已经没有节点了
    49. _node = nullptr;
    50. }
    51. return *this;
    52. }
    53. bool operator !=(const Self& s)
    54. {
    55. return _node != s._node;
    56. }
    57. bool operator ==(const Self& s)
    58. {
    59. return _node == s._node;
    60. }
    61. };

     

     ①迭代器封装;

    1. iterator begin()
    2. {
    3. size_t i = 0;
    4. while (i < _table.size())
    5. {
    6. if (_table[i])
    7. {
    8. //this 可以作为 迭代器的哈希表传过去!
    9. return iterator(_table[i], this);
    10. }
    11. ++i;
    12. }
    13. return end();
    14. }
    15. iterator end()
    16. {
    17. return iterator(nullptr,this);
    18. }

     

     (3)插入+[];

    ①unordered_map

    1. template<class K,class V>
    2. class unordered_map
    3. {
    4. struct MapOFT
    5. {
    6. K& operator()(const pair& kv)
    7. {
    8. return kv.first;
    9. }
    10. };
    11. public:
    12. typedef typename OpenHash::HashBuckets, MapOFT>::iterator iterator;
    13. iterator begin()
    14. {
    15. return _um.begin();
    16. }
    17. iterator end()
    18. {
    19. return _um.end();
    20. }
    21. pairbool> insert(const pair& kv)
    22. {
    23. return _um.insert(kv);
    24. }
    25. V& operator[](const K& key)
    26. {
    27. pairbool>* ret = _um.insert(make_pair(key, V()));
    28. return ret->first.second;
    29. }
    30. private:
    31. OpenHash::HashBuckets, MapOFT> _um;
    32. };

    ②unordered_set;

    1. template<class K>
    2. class unordered_set
    3. {
    4. struct SetOFT
    5. {
    6. K& operator()(const K& key)
    7. {
    8. return key;
    9. }
    10. };
    11. public:
    12. typedef typename OpenHash::HashBuckets::iterator iterator;
    13. iterator begin()
    14. {
    15. return _us.begin();
    16. }
    17. iterator end()
    18. {
    19. return _us.end();
    20. }
    21. pairbool> insert(const K& key)
    22. {
    23. return _us.insert(key);
    24. }
    25. private:
    26. OpenHash::HashBuckets _us;
    27. };

    ③HashBuckets;

    1. pair bool > insert(const T& data)
    2. {
    3. HashFunc hf;
    4. KeyOFT kot;
    5. Node* ret = find(kot(data));
    6. if (ret)
    7. {
    8. return make_pair(iterator(ret,this), false);
    9. }
    10. //哈希桶同样也需要 扩容
    11. //当负载因子 为 1 到时候扩容
    12. if (_n == _table.size())
    13. {
    14. vector NTable;
    15. // NTable._table.resize(_table.size() * 2);
    16. NTable.resize(GetNextPrime(_table.size()));
    17. // 这里不是拷贝赋值 而是让旧表里的指针
    18. //链接进新表
    19. for (int i = 0; i < _table.size() ; i++)
    20. {
    21. if (_table[i])
    22. {
    23. //旧表节点
    24. Node* cur = _table[i];
    25. while (cur)
    26. {
    27. //记录 cur 的下一个 因为 头插 会改变cur->next
    28. Node* next = cur->_next;
    29. //重新计算映射位置
    30. size_t index = hf(kot(data)) % NTable.size();
    31. //头插
    32. cur->_next = NTable[index];
    33. NTable[index] = cur;
    34. cur = next;
    35. }
    36. _table[i] = nullptr;
    37. }
    38. }
    39. _table.swap(NTable);
    40. }
    41. //插入 哪个位置
    42. size_t index = hf(kot(data)) % _table.size();
    43. //去构建 一个节点nenode 以备插入
    44. Node* newnode = new Node(data);
    45. //插入选择头插 因为效率高
    46. newnode->_next = _table[index];
    47. _table[index] = newnode;
    48. ++_n;
    49. return make_pair(iterator(newnode,this),true);
    50. }

    unordered_set 

     unordered_map;

     


    (4)成员函数;

    1. //构造
    2. HashBuckets() = default;//显示指定生成 默认构造
    3. HashBuckets(const HashBuckets& HB)
    4. {
    5. _n = HB._n;
    6. _table.resize(HB._table.size());
    7. for (size_t i = 0;i < _table.size();++i)
    8. {
    9. Node* cur = HB._table[i];
    10. while (cur)
    11. {
    12. Node* copy = new Node(cur->_data);
    13. //再头插
    14. copy->_next = _table[i];
    15. _table[i] = copy;
    16. cur = cur->_next;
    17. }
    18. }
    19. }
    20. //赋值
    21. HashBuckets& operator=(HashBuckets hb)
    22. {
    23. _table.swap(hb._table);
    24. swap(_n, hb._hp);
    25. return *this;
    26. }

     


    本篇就到此为止,谢谢你的阅读

    祝你好运~

     

  • 相关阅读:
    Git基本应用<一>:Git安装及GitHub连接
    87、一文带你了解网络操作系统,除了windows、linux,还有你没听过的
    扫雷(C语言)
    【机器学习】使用scikitLearn对数据进行降维处理:PCA法及增量训练
    口袋参谋:如何快速挑选宝贝核心关键词?三种方法,简单有效!
    Django实战项目-学习任务系统-需求说明
    因JVM OOM而进行JVM 垃圾回收器调优更换的一次案例 -ParallelGC和ConcMarkSweepGC
    Java面试八股文整理
    我国农业科学数据共享协议
    VMware 中 Centos7 安装 Hyperledge Fabric v2.4.4 测试网络
  • 原文地址:https://blog.csdn.net/RNGWGzZs/article/details/126070945