unordered_set和unordered_map的封装-阿里云开发者社区

一、前言

在C++11中，STL提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，但是效率却提高了。

unordered系列的关联式容器之所以效率比较高，是因为unordered系列的关联式容器的底层使用了我们前面所讲到的哈希结构。那么今天我们就来看看 unordered_set和unordered_map这两个容器的使用及其实现。

二、容器的使用

1、unordered_map

1、 unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。

2、在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3、在内部unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。

4、 unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。

5、unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问value。

int main()
{
  unordered_map<string, int> countMap;
  string arr[] = { "苹果","香蕉","苹果","葡萄"，"西瓜" };
  for (auto& e : arr)
  {
    auto it = countMap.find(e);
    /*if (it == countMap.end())
    {
      countMap.insert(make_pair(e, 1));
    }
    else
    {
      it->second++;
    }*/
    countMap[e]++;
  }
  for (auto& kv : countMap)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  return 0;
}

从运行结果我们可以看出 unordered_map里面的数据是无序且数据是可以有重复的。

2、unordered_set

1、不再以键值对的形式存储数据，而是直接存储数据的值。

2、容器内部存储的各个元素的值都互不相等，且不能被修改。

3、不会对内部存储的数据进行排序。

int main()
{
  unordered_set<int> us;
  us.insert(10);
  us.insert(1);
  us.insert(10);
  us.insert(3);
  us.insert(4);
  us.insert(4);
  auto it = us.begin();
  while (it != us.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  return 0;
}

从运行结果我们可以看出 unordered_set里面的数据是无序且没有重复的。

三、哈希表的改造

从标准库中我们知道，unordered_set和unordered_map这两个容器的底层结构都是哈希表。但是两个容器所存储的数据类型不同，前者存储的是 key类型的数据，后者存储的是 key/value类型的数据。所以为了方便，我们需要像实现 map和set的底层红黑树那样，去实现一个通用的哈希表。所以我们需要对哈希表改造一下，来满足两个容器都可以使用。

1、结点

首先，我们需要对节点改造，使其能够满足两种存储方式。

template<class T>
struct HashNode
{
  T _data;
  HashNode<T>* _next;
  HashNode(const T& data)
    :_data(data)
    , _next(nullptr)
  {}
};

2、哈希表的迭代器

我们需要对哈希表指针和结点指针进行封装。

template<class K, class T, class Hash, class KeyOfT>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct _HashIterator
{
  typedef HashNode<T> Node;
  typedef HashTable<K, T, Hash, KeyOfT> HT;
  typedef _HashIterator<K, T, Hash, KeyOfT> Self;
  Node* _node;
  HT* _ht;
};

* 构造函数

_HashIterator(Node* node, HT* ht)
  :_node(node)
  , _ht(ht)
{}

* 重载 *

T& operator*()
{
  return _node->_data;
}

* 重载 ->

T* operator->()
{
  return &_node->_data;
}

* 重载 ++

思路：如果当前的哈希桶还有节点（即下一个结点不为空），那么++就是当前桶的当前节点的下一个节点，如果当前元素是所在桶的最后一个元素，那么++就是找下一个非空的哈希桶。

Self& operator++()
  {
    if (_node->_next)
    {
      //当前桶迭代
      _node = _node->_next;
    }
    else
    {
      // 找下一个桶
      Hash hash;
      KeyOfT kot;
      size_t i = hash(kot(_node->_data)) % _ht->_tables.size();
      i++;
      for (; i < _ht->_tables.size(); i++)
      {
        if (_ht->_tables[i])
        {
          _node = _ht->_tables[i];
          break;
        }
      }
      //说明后面没有有数据的桶了
      if (i == _ht->_tables.size())
      {
        _node = nullptr;
      }
    }
    return *this;
  }

* 重载 != 和 ==

bool operator!=(const Self& s)const
{
  return _node != s._node;
}
bool operator==(const Self& s)const
{
  return _node == s._node;
}

3、哈希表的析构

~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;
  }
}

4、unordered_map的 [] 实现

我们知道，unordered_map的操作中可以通过[]来访问数据，并修改value值，那么这是怎么做到的呢？

其实要想实现[]，我们需要先把insert的返回值修改成pair<iterator,bool>，最后的返回值也要一起修改。如果有重复的元素就返回这个位置的迭代器，没有重复的就返回新节点newnode的迭代器。

pair<iterator, bool> insert(const T& data)
  {
    Hash hash;
    KeyOfT kot;
    //去重
    iterator ret = Find(kot(data));
    if (ret != end())
    {
      return make_pair(ret, false);
    }
    //扩容
    if (_size == _tables.size())
    {
      size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10;
      vector<Node*> newTables;
      newTables.resize(newsize, nullptr);
      //将旧表中结点移动映射到新表
      for (size_t i = 0; i < _tables.size(); i++)
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
          size_t hashi = hash(kot(cur->_data)) % newTables.size();
          cur->_next = newTables[hashi];
          newTables[hashi] = cur;
          cur = next;
        }
        _tables[i] = nullptr;
      }
      _tables.swap(newTables);
    }
    size_t hashi = hash(kot(data)) % _tables.size();
    Node* newnode = new Node(data);
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    _size++;
    return make_pair(iterator(newnode, this), true);
  }

有了上面的插入，我们就可以在unordered_map中实现[]的操作了。

5、修改后的哈希表

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;
template<class T>
struct HashNode
{
  T _data;
  HashNode<T>* _next;
  HashNode(const T& data)
    :_data(data)
    , _next(nullptr)
  {}
};
//前置声明
template<class K, class T, class Hash, class KeyOfT>
class HashTable;
template<class K, class T, class Hash, class KeyOfT>
struct _HashIterator
{
  typedef HashNode<T> Node;
  typedef HashTable<K, T, Hash, KeyOfT> HT;
  typedef _HashIterator<K, T, Hash, KeyOfT> Self;
  Node* _node;
  HT* _ht;
  _HashIterator(Node* node, HT* ht)
    :_node(node)
    , _ht(ht)
  {}
  T& operator*()
  {
    return _node->_data;
  }
  T* operator->()
  {
    return &_node->_data;
  }
  Self& operator++()
  {
    if (_node->_next)
    {
      //当前桶迭代
      _node = _node->_next;
    }
    else
    {
      // 找下一个桶
      Hash hash;
      KeyOfT kot;
      size_t i = hash(kot(_node->_data)) % _ht->_tables.size();
      i++;
      for (; i < _ht->_tables.size(); i++)
      {
        if (_ht->_tables[i])
        {
          _node = _ht->_tables[i];
          break;
        }
      }
      //说明后面没有有数据的桶了
      if (i == _ht->_tables.size())
      {
        _node = nullptr;
      }
    }
    return *this;
  }
  bool operator!=(const Self& s)const
  {
    return _node != s._node;
  }
  bool operator==(const Self& s)const
  {
    return _node == s._node;
  }
};
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 val = 0;
    for (auto ch : key)
    {
      val *= 131;
      val += ch;
    }
    return val;
  }
};
template<class K, class T, class Hash, class KeyOfT>
class HashTable
{
  typedef HashNode<T> Node;
  template<class K, class T, class Hash, class KeyOfT>
  friend struct _HashIterator;
public:
  typedef _HashIterator<K, T, Hash, KeyOfT> iterator;
  iterator begin()
  {
    for (size_t i = 0; i < _tables.size(); i++)
    {
      if (_tables[i])
      {
        return iterator(_tables[i], this);
      }
    }
    return end();
  }
  iterator end()
  {
    return iterator(nullptr, this);
  }
  ~HashTable()
  {
    for (size_t i = 0; i < _tables.size(); i++)
    {
      Node* cur = _tables[i];
      while (cur)
      {
        Node* next = cur->_next;
        free(cur);
        cur = next;
      }
      _tables[i] = nullptr;
    }
  }
  pair<iterator, bool> insert(const T& data)
  {
    Hash hash;
    KeyOfT kot;
    //去重
    iterator ret = Find(kot(data));
    if (ret != end())
    {
      return make_pair(ret, false);
    }
    //扩容
    if (_size == _tables.size())
    {
      size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 10;
      vector<Node*> newTables;
      newTables.resize(newsize, nullptr);
      //将旧表中结点移动映射到新表
      for (size_t i = 0; i < _tables.size(); i++)
      {
        Node* cur = _tables[i];
        while (cur)
        {
          Node* next = cur->_next;
          size_t hashi = hash(kot(cur->_data)) % newTables.size();
          cur->_next = newTables[hashi];
          newTables[hashi] = cur;
          cur = next;
        }
        _tables[i] = nullptr;
      }
      _tables.swap(newTables);
    }
    size_t hashi = hash(kot(data)) % _tables.size();
    Node* newnode = new Node(data);
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    _size++;
    return make_pair(iterator(newnode, this), true);
  }
  iterator Find(const K& key)
  {
    if (_tables.size() == 0)
      return end();
    Hash hash;
    KeyOfT kot;
    size_t hashi = hash(key) % _tables.size();
    Node* cur = _tables[hashi];
    while (cur)
    {
      if (kot(cur->_data) == key)
        return iterator(cur, this);
      else
        cur = cur->_next;
    }
    return end();
  }
  bool erase(const K& key)
  {
    if (_tables.size() == 0)
    {
      return false;
    }
    Hash hash;
    KeyOfT kot;
    size_t hashi = hash(key) % _tables.size();
    Node* cur = _tables[hashi];
    Node* prev = nullptr;
    while (cur)
    {
      if (kot(cur->_data) == key)
      {
        // 1、头删
        // 2、中间删
        if (prev == nullptr)
        {
          _tables[hashi] = cur->_next;
        }
        else
        {
          prev->_next = cur->_next;
        }
        delete cur;
        _size--;
        return true;
      }
      prev = cur;
      cur = cur->_next;
    }
    return false;
  }
private:
  vector<Node*> _tables;
  size_t _size = 0;
};

四、 unordered_set的实现

#pragma once
#include"HashTable.h"
namespace zdl
{
  template<class K, class Hash = HashFunc<K>>
  class unordered_set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    typedef typename HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      return _ht.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      return _ht.insert(key);
    }
  private:
    HashTable<K, K, Hash, SetKeyOfT> _ht;
  };

五、unordered_map的实现

#pragma once
#include"HashTable.h"
namespace zdl
{
  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:
    typedef typename HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;
    iterator begin()
    {
      return _ht.begin();
    }
    iterator end()
    {
      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;
    }
  private:
    HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;
  };
}

unordered_set和unordered_map的封装