C++ STL 进阶：unordered_set 与 unordered_map 模拟实现

C++ STL 进阶：unordered_set 与 unordered_map 模拟实现

引言

在 C++ 标准库中，unordered_set 和 unordered_map 提供了基于哈希表的高效查找能力。理解它们的底层实现原理，对于掌握高性能数据结构至关重要。本文将深入剖析这两个容器的模拟实现，从哈希表结构设计到迭代器逻辑，还原标准库的核心机制。

标准库实现背景

在早期的 SGI STL 版本（C++11 之前）中，并未包含标准的 unordered_set 和 unordered_map。当时使用的是非标准的 hash_set 和 hash_map，其核心实现依赖于 stl_hashtable.h。现代 C++11 标准引入的无序容器，本质上是对这一思想的标准化封装。

从源码结构来看，hash_set 和 hash_map 复用了同一个 hashtable 模板类，通过不同的类型参数适配存储需求：

• hash_set：向 hashtable 传递单纯的键值（Key）。
• hash_map：向 hashtable 传递键值对（pair<const Key, Value>）。

这种设计体现了高度的代码复用性，使得底层哈希桶管理逻辑可以统一处理。

核心代码实现

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;

        () : _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;
            Hash hashFunc;
            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_i = ((data)) % _tables.();
            newNode->_next = _tables[hash_i];
            _tables[hash_i] = newNode;
            ++_n;
             { (newNode, ),  };
        }

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

        {
             (, );
        }
    };
}