从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(中)

简介: 从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)

从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(上):https://developer.aliyun.com/article/1522330

884. 两句话中的不常见单词 - 力扣(LeetCode)

难度简单

句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。

如果某个单词在其中一个句子中恰好出现一次,在另一个句子中却 没有出现 ,那么这个单词就是 不常见的 

给你两个 句子 s1s2 ,返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

示例 1:

输入:s1 = "this apple is sweet", s2 = "this apple is sour"

输出:["sweet","sour"]


示例 2:

输入:s1 = "apple apple", s2 = "banana"

输出:["banana"]


提示:

  • 1 <= s1.length, s2.length <= 200
  • s1s2 由小写英文字母和空格组成
  • s1s2 都不含前导或尾随空格
  • s1s2 中的所有单词间均由单个空格分隔
class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
 
    }
};

解析代码:(等价于:在两个句子中一共只出现一次的单词。)

大家可以百度stringstream类用法,这里讲一个小技巧:可以将字符串中每个单词按空格隔开。

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> m;
        vector<string> retV;
 
        stringstream a, b; // 创建流对象
        string s;
        a << s1;  // 向流中传值
        b << s2;
 
        while (a >> s)
        {
            m[s]++;  //流向s中写入值,并且空格会自断开
            //cout << s << "+";
        }
        while (b >> s)
        {
            m[s]++;
        }
        for (const auto& m : m)
        {
            if (m.second == 1)
            {
                retV.push_back(m.first); //只需要看出现次数是1的单词
            }
        }
        return retV;
    }
};

如果解开注释:


2. 实现unordered_set和unordered_map

这里用我们上一篇写的开散列哈希桶的代码,闭散列不用就删掉,去掉命名空间复制一份过来:

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
template<class K, class V>
struct HashNode
{
  pair<K, V> _kv;
  HashNode* _next; // 不用存状态栏了,存下一个结点指针
 
  HashNode(const pair<K, V>& kv)
    :_kv(kv)
    , _next(nullptr)
  {}
};
 
template<class K>
struct HashFunc // 可以把闭散列的HashFunc放在外面直接用,但是这就不放了
{
  size_t operator()(const K& key)
  {
    return (size_t)key; // 负数,浮点数,指针等可以直接转,string不行
  }
};
 
template<>
struct HashFunc<string> // 上面的特化
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (const auto& ch : key)
    {
      val *= 131;
      val += ch;
    }
 
    return val;
  }
};
 
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
  typedef HashNode<K, V> Node;
 
  ~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;
    }
  }
 
  Node* Find(const K& key)
  {
    if (_tables.size() == 0)
    {
      return nullptr;
    }
 
    Hash hs;
    size_t hashi = hs(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur)
    {
      if (cur->_kv.first == key)
      {
        return cur;
      }
      cur = cur->_next;
    }
    return nullptr;
  }
 
  inline size_t __stl_next_prime(size_t n)
  {
    static const size_t __stl_num_primes = 28;
    static const size_t __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
    };
 
    for (size_t i = 0; i < __stl_num_primes; ++i)
    {
      if (__stl_prime_list[i] > n)
      {
        return __stl_prime_list[i];
      }
    }
 
    return -1; // 不会走到这,随便返回一个值
  }
 
  bool Insert(const pair<K, V>& kv)
  {
    if (Find(kv.first))
    {
      return false;
    }
 
    Hash hs;
    if (_size == _tables.size()) // 负载因子到1就扩容
    {
      //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
      vector<Node*> newTables;
      //newTables.resize(newSize, nullptr);
      newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数,前两注释改成这一条
 
      for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
 
          size_t hashi = hs(cur->_kv.first) % newTables.size();
          cur->_next = newTables[hashi];
          newTables[hashi] = cur;
 
          cur = next;
        }
 
        _tables[i] = nullptr;
      }
 
      _tables.swap(newTables);
    }
 
    size_t hashi = hs(kv.first) % _tables.size(); // 哈希映射
    Node* newnode = new Node(kv); // 头插
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_size;
    return true;
  }
 
  bool Erase(const K& key)
  {
    if (_tables.size() == 0) // 防止除零错误
    {
      return false;
    }
 
    Hash hs;
    size_t hashi = hs(key) % _tables.size();
    Node* cur = _tables[hashi];
    Node* prev = nullptr;
    while (cur)
    {
      if (cur->_kv.first == key)
      {
        if (prev == nullptr) // 头插,先把指针数组存的指针指向cur的下一个
        {
          _tables[hashi] = cur->_next;
        }
        else // 中间删
        {
          prev->_next = cur->_next;
        }
        delete cur; // 统一在这delete
        return true;
      }
 
      prev = cur; // 往后走
      cur = cur->_next;
    }
    return false; // 没找到
  }
 
  size_t Size() // 存的数据个数
  {
    return _size;
  }
 
  size_t TablesSize() // 表的长度
  {
    return _tables.size();
  }
 
  size_t BucketNum() // 桶的个数
  {
    size_t num = 0;
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      if (_tables[i]) // 如果不是空就有桶
      {
        ++num;
      }
    }
    return num;
  }
 
  size_t MaxBucketLenth() // 最长桶的长度
  {
    size_t maxLen = 0;
    for (size_t i = 0; i < _tables.size(); ++i)
    {
      size_t len = 0;
      Node* cur = _tables[i];
      while (cur)
      {
        ++len;
        cur = cur->_next;
      }
      if (len > maxLen)
      {
        maxLen = len;
      }
    }
    return maxLen;
  }
 
protected:
  vector<Node*> _tables; // 指针数组
  size_t _size;
};

有了封装set和map的和学习了哈希的经验,直接写出框架:

UnorderedSet.h:

#pragma once
 
#include "HashTable.h"
 
namespace rtx
{
  template<class K, class K>
  class unordered_map
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
 
  protected:
    HashTable<K, k, Hash, MapKeyOfT> _ht;
  };
}

UnorderedMap.h:

#pragma once
 
#include "HashTable.h"
 
namespace rtx
{
  template<class K, class V, class Hash = HashFunc<K>>
  class unordered_map
  {
    struct MapKeyOfT
    {
      const K& operator()(const pair<K, V>& kv)
      {
        return kv.first;
      }
    };
  public:
 
  protected:
    HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
  };
 
}

用命名空间和STL库区分,第二个参数对于unordered_set是key,对于unordered_map是piar,

现在应该把ashNode的两个参数改为一个参数T,_pair 改为 _data


再把HashTable的第二个参数改为T,再加一个获取key的仿函数:

(这里不能在第三个仿函数给默认的了)

2.1 哈希桶的迭代器

迭代器是所有容器必须有的,先来看迭代器的++是如何实现的:

如上图所示,一个哈希表,其中有四个哈希桶,迭代器是it。

++it操作:

  • 如果it不是某个桶的最后一个元素(桶里数据下一个不为空),则it指向下一个节点。
  • 如果it是桶的最后一个元素(桶里数据下一个为空),则it指向下一个桶的头节点。

       要想实现上面的操作,迭代器中不仅需要一个_node来记录当前节点,还需要一个哈希表的指针,以便找下一个桶,代码如下:(顺便写迭代器中的其他操作,如解引用,箭头,以及相等等运算符的重载就不再详细介绍了:)

template<class K, class T, class Hash, class KeyOfT>
class HashTable; // 前置声明
 
template<class K, class T, class Hash, class KeyOfT>
class __HashIterator
{
public:
  typedef HashNode<T> Node;
  typedef HashTable<K, T, Hash, KeyOfT> HT;
  typedef __HashIterator<K, T, Hash, KeyOfT> Self;
 
  Node* _node; // 数据结点
  HT* _pht; // 哈希表指针
 
  __HashIterator(Node* node, HT* pht)
    :_node(node)
    , _pht(pht)
  {}
 
  Self& operator++()
  {
    if (_node->_next) // 不是桶中的最后一个数据
    {
      _node = _node->_next;
    }
    else // 是桶中的最后一个数据,找下一个桶
    {
      Hash hs;
      KeyOfT kot;
      size_t i = hs(kot(_node->_data)) % _pht->_tables.size() + 1;//没+1是当前桶位置
      for (; i < _pht->_tables.size(); ++i)
      {
        if (_pth->tables[i]) // 向后迭代找到了有桶的位置
        {
          _node = _pth->tables[i]; // 把这个位置给_node
          break;
        }
      }
      if (_pht == _tables.size()) // 后面都没桶了
      {
        _node = nullptr;
      }
    }
    return *this; // this调用该函数的对象(迭代器),指向下一个后解引用返回
  }
 
  T& operator*()
  {
    return _node->_data;
  }
 
  T* operator->()
  {
    return &_node->_data;
  }
 
  bool operator!=(const Self& s) const
  {
    return s._node != _node;
  }
 
  bool operator==(const Self& s) const
  {
    return s._node == _node;
  }
};


t不是处于某个桶的末尾,直接指向下一个节点。

当it是某个桶的末尾时,指向下一个桶。

首先需要确定当前桶的位置:

       使用KeyOfT仿函数获取当前数据的key值(因为不知道是map还是set在调用)。再使用Hash仿函数将key值转换成可以模的整形(因为不知道key是整形还是字符串再或者其他自定义类型)。


然后开始寻找下一个桶:

       从当前哈希表下标开始向后寻找,直到找到下一个桶,将桶的头节点地址赋值给_node。如果始终没有找到,说明没有桶了,也就是没有数据了,it指向end,这里使用空指针来代替end。 将++后的迭代器返回。


       迭代器中有一个成员变量是哈希表的指针,如上图所示,所以在迭代器中typedef了HashTable成为 HT,方便我们使用。


       根据我们前面实现迭代器的经验,迭代器其实是封装在Hashtable中的,也就是说,在HashTable中也会typedef迭代器:此时HashTable和HashIterator就构成了相互typedef的关系。哈希表和迭代器类的定义势必会有一个先后顺序,这里在定义的时候,在代码顺序上就是先定义迭代器,再定义的哈希表。此时迭代器在typedef的时候就找不到哈希表的定义,因为编译器只会向上寻找而不会向下寻找。所以必须在HashIterator类前面先声明一下HashTable类,这种操作被叫做前置声明。


前置声明一定要放在类外面,如果放在迭代器类里面,编译器只会在迭代器的命名空间中寻找哈希表的定义,这样是找不到的。

前置声明放在类外面的时候,编译器会在整个命名空间中寻找哈希表的定义,就可以找到。

       在++迭代器的时候,会使用到哈希表指针,哈希表指针又会使用到HashTable中的_tables。(HashTable中的_tables是保护成员,在类外是不能访问的。)解决这个问题可以在HashTable中写一个公有的访问函数,也可以采用友元,这里用下友元。


       类模板的友元声明需要写模板参数,在类名前面加friend关键字。(迭代器要访问HashTable的保护,所以迭代器要成为HashTable的友元)

9e73076b01724a7fa2c355640a87688e.png

从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(下):https://developer.aliyun.com/article/1522332

目录
相关文章
|
1月前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
2月前
|
存储 Java API
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
37 6
【数据结构】map&set详解
|
1月前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
35 1
|
2月前
|
算法
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
36 5
|
2月前
|
存储 JavaScript 前端开发
js的map和set |21
js的map和set |21
|
2月前
|
存储 前端开发 API
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
该文章详细介绍了ES6中Set和Map数据结构的特性和使用方法,并探讨了它们在前端开发中的具体应用,包括如何利用这些数据结构来解决常见的编程问题。
ES6的Set和Map你都知道吗?一文了解集合和字典在前端中的应用
|
3月前
|
存储 安全 Java
java集合框架复习----(4)Map、List、set
这篇文章是Java集合框架的复习总结,重点介绍了Map集合的特点和HashMap的使用,以及Collections工具类的使用示例,同时回顾了List、Set和Map集合的概念和特点,以及Collection工具类的作用。
java集合框架复习----(4)Map、List、set
|
3月前
|
Java
【Java集合类面试二十二】、Map和Set有什么区别?
该CSDN博客文章讨论了Map和Set的区别,但提供的内容摘要并未直接解释这两种集合类型的差异。通常,Map是一种键值对集合,提供通过键快速检索值的能力,而Set是一个不允许重复元素的集合。
|
3月前
|
存储 JavaScript 前端开发
ES6新特性(四): Set 和 Map
ES6新特性(四): Set 和 Map
|
3月前
|
存储 Java 索引