从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

目录
相关文章
|
22天前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装,包括节点的创建、链表的初始化、数据的插入和删除,以及链表的打印等功能。
15 1
|
2月前
|
数据安全/隐私保护 C语言 C++
C++(七)封装
本文档详细介绍了C++封装的概念及其应用。封装通过权限控制对外提供接口并隐藏内部数据,增强代码的安全性和可维护性。文档首先解释了`class`中的权限修饰符(`public`、`private`、`protected`)的作用,并通过示例展示了如何使用封装实现栈结构。接着介绍了构造器和析构器的使用方法,包括初始化列表的引入以及它们在内存管理和对象生命周期中的重要性。最后,通过分文件编程的方式展示了如何将类定义和实现分离,提高代码的模块化和复用性。
|
4月前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
34 2
|
4月前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
46 0
|
6月前
|
存储 算法 C语言
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
56 5
|
6月前
|
存储 编译器 C语言
从C语言到C++_23(多态)抽象类+虚函数表VTBL+多态的面试题(下)
从C语言到C++_23(多态)抽象类+虚函数表VTBL+多态的面试题
59 1
|
6月前
|
存储 编译器 Linux
从C语言到C++_23(多态)抽象类+虚函数表VTBL+多态的面试题(中)
从C语言到C++_23(多态)抽象类+虚函数表VTBL+多态的面试题
65 1
|
6月前
|
编译器 C语言 C++
从C语言到C++_23(多态)抽象类+虚函数表VTBL+多态的面试题(上)
从C语言到C++_23(多态)抽象类+虚函数表VTBL+多态的面试题
46 0
|
6月前
|
编译器 程序员 C语言
从C语言到C++⑨(第三章_C&C++内存管理)详解new和delete+面试题笔试题(下)
从C语言到C++⑨(第三章_C&C++内存管理)详解new和delete+面试题笔试题
42 0
|
6月前
|
编译器 C语言 C++
从C语言到C++⑨(第三章_C&C++内存管理)详解new和delete+面试题笔试题(中)
从C语言到C++⑨(第三章_C&C++内存管理)详解new和delete+面试题笔试题
49 0