C++ STL 无序容器 unordered_set 与 unordered_map 模拟实现

C++ STL 无序容器 unordered_set 与 unordered_map 模拟实现

前言

在 C++11 标准引入之前，STL 中并没有 unordered_set 和 unordered_map。这两个容器基于哈希表实现，提供了平均 O(1) 的查找、插入和删除性能。本文将深入探讨如何从零开始模拟实现这两个容器，涵盖底层哈希表结构、迭代器设计以及扩容机制。

标准库中的实现原理

SGI STL30 版本（C++11 之前）实现了非标准的 hash_set 和 hash_map，它们复用同一个 hashtable 核心结构。unordered_set 和 unordered_map 的设计思路与之高度相似：

• hash_set：传递给 hashtable 的是单纯的 key。
• hash_map：传递给 hashtable 的是 pair<const key, value> 这种键值对形式。

核心文件通常包括 stl_hashtable.h、stl_hash_set 和 stl_hash_map。通过泛型封装，我们可以复用同一套哈希表逻辑来适配不同的存储需求。

代码实现架构

1. 哈希表基础 (HashTable.h)

这是整个容器的底层支撑，负责管理桶数组、节点链表以及扩容逻辑。

#pragma once
#include <iostream>
#include <vector>
using namespace std;

/*------------------ 任务：定义哈希表函数的'通用类模板'------------------*/
template<class K>
struct HashFunc {
    // 重载 () 运算符 ---> 作用：将 K 类型转化为 size_t 类型，用于计算哈希值
    size_t operator()(const K& key) {
        return (size_t)key; // 注意：默认为直接转换，适用于 int、long 等整数类型
    }
};

/*------------------ 任务：定义哈希函数的'模板特化'------------------*/
<>
 <string> {
    
    {
        
         hash = ;
         ( it : s) {
            hash += it;
            hash *= ; 
        }
         hash;
    }
};


   _stl_next_prime(  n) {
       _stl_num_primes = ;
        _stl_prime_list[_stl_num_primes] = {
        , , , , , , , , , , , ,
        , , , , , , , ,
        , , , , , ,
        , 
    };
      * first = _stl_prime_list;
      * last = _stl_prime_list + _stl_num_primes;
      * pos = (first, last, n);
     pos == last ? *(last - ) : *pos;
}

 hash_bucket {
    
    < >
      {
        T _data;
        HashNode<T>* _next;
        ( T& data) : _data(data), _next() {}
    };

    
    < ,  ,  ,  ,  ,  >
      {
        HashNode<T>* _node;
         HashTable<K, T, KeyOfT, Hash>* _ht;

         HashNode<T> Node;
         HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
         HashTable<K, T, KeyOfT, Hash> HT;

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

        Ref *() {  _node->_data; }
        Ptr ->() {  &_node->_data; }
         !=( Self& other) {  _node != other._node; }
         ==( Self& other) {  _node == other._node; }

        Self& ++() {
             (_node->_next) {
                _node = _node->_next;
            }  {
                
                KeyOfT kot;
                Hash hashFunc;
                 hash_i = ((_node->_data)) % _ht->_tables.();
                ++hash_i; 
                 (hash_i < _ht->_tables.()) {
                    _node = _ht->_tables[hash_i];
                     (_node) ;
                    ++hash_i;
                }
                 (hash_i == _ht->_tables.()) {
                    _node = ;
                }
            }
             *;
        }
    };

    
    < ,  ,  ,  >
      {
    :
        vector<HashNode<T>*> _tables;
         _n;
         HashNode<T> Node;

          <K, T, T&, T*, KeyOfT, Hash>;
          <K, T,  T&,  T*, KeyOfT, Hash>;

    :
         HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
         HTIterator<K, T,  T&,  T*, KeyOfT, Hash> ConstIterator;

        {
             (_n == )  ();
             ( i = ; i < _tables.(); i++) {
                 (_tables[i])  (_tables[i], );
            }
             ();
        }

        {  (, ); }

        {
             (_n == )  ();
             ( i = ; i < _tables.(); i++) {
                 (_tables[i])  (_tables[i], );
            }
             ();
        }

        {  (, ); }

        () : _tables(_stl_next_prime()), _n() {}

        ~() {
             ( i = ; i < _tables.(); ++i) {
                Node* current = _tables[i];
                 (current) {
                    Node* next = current->_next;
                     current;
                    current = next;
                }
                _tables[i] = ;
            }
        }

        {
            KeyOfT kot;
            Hash hashFunc;
             hash_i = (key) % _tables.();
            Node* current = _tables[hash_i];
             (current) {
                 ((current->_data) == key)  (current, );
                current = current->_next;
            }
             ();
        }

        {
            KeyOfT kot;
            Hash hashFunc;
             hash_i = (key) % _tables.();
            Node* curr = _tables[hash_i];
            Node* prev = ;
             (curr) {
                 ((curr->_data) == key) {
                     (prev == ) _tables[hash_i] = curr->_next;
                     prev->_next = curr->_next;
                     curr;
                    --_n;
                     ;
                }
                prev = curr;
                curr = curr->_next;
            }
             ;
        }

        {
            KeyOfT kot;
            Iterator it = ((data));
             (it != ())  { it,  };

             (_n == _tables.()) {
                ;
                 ( i = ; i < _tables.(); i++) {
                    Node* current = _tables[i];
                     (current) {
                        Node* next = current->_next;
                         hash_i = ((current->_data)) % newVector.();
                        current->_next = newVector[hash_i];
                        newVector[hash_i] = current;
                        current = next;
                    }
                    _tables[i] = ;
                }
                _tables.(newVector);
            }

            Node* newNode =  (data);
            Hash hashFunc;
             hash_i = ((data)) % _tables.();
            newNode->_next = _tables[hash_i];
            _tables[hash_i] = newNode;
            ++_n;
             { (newNode, ),  };
        }
    };
}