首页 > 其他分享 >STL-unordered_hashtable模拟实现

STL-unordered_hashtable模拟实现

时间:2024-02-27 22:57:48浏览次数:23  
标签:node tables cur iterator STL hashi hashtable unordered size

#pragma once

#include<vector>
#include<string>
#include<iostream>
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;


namespace HashBucket 
{

    template<class T>
    struct HashNode
    {
        HashNode* _next = nullptr;
        T _data; 

        HashNode(const T& data)
            :_data(data)
        {}

    }; //HashNode_end


    //见27.
    template<class K>
    struct HashFunc 
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };
    template<>
    struct HashFunc<std::string> 
    {
        size_t operator()(const std::string& s)
        {
            size_t ret = 0;
            for (auto ch : s)
            {
                ret += ch;
                ret *= 31;
            }
            return ret;
        }
    };


    //根据声明顺序,使用下面的类需要前置声明
    template<class K, class T, class keyOfT, class Hash >
    class HashTable; 

    template<class K , class T, class Ref, class Ptr, class keyOfT,class Hash>
    struct __Hash_iterator
    {
//迭代器怎么写?
/**
 * 1.迭代器需要什么模板类?
 * -> 先写符号重载,看需要什么:写了++,需要结点,哈希表
 * 
 * 2.需要什么函数重载?
 * -> ++ . -- , != , * , -> ,
 * 
 * 3.写外部函数调用,看需要什么
 */

        typedef __Hash_iterator<K, T, T&, T*, keyOfT, Hash > iterator;
        typedef __Hash_iterator<K, T, Ref, Ptr, keyOfT, Hash > Self;

        typedef HashNode<T> node;
        typedef HashTable<K, T, keyOfT,Hash> HashTable;

        node* _node;
        const HashTable* _ht; //不允许修改

        __Hash_iterator(node* node, const HashTable* ht) //普通构造函数 --- 绝对不能用引用,因为迭代器是有可能会修改指针,使用引用可能会改崩原指针,
            :_node(node)
            ,_ht(ht)
        {}

        __Hash_iterator(const iterator& it)
            :_node(it._node)
            ,_ht(it._ht)
        {}

        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        bool operator!=(const Self& s)
        {
            return _node != s._node;
        }

        Self& operator++() //迭代器++返回什么? 返回新的迭代器
        {
            /** 迭代器怎么++ ?
             * 条件:
             * 
             * 1.当前结点为空
             *  a.循环,计算哈希值,找下一个不为空的数组
             *   循环出口:1.哈希值超过数组最大长度 2.找到不为空的元素
             *   循环入口:1
             *   循环结束后:返回空--没找到
             * 
             * 2.当前结点非空
             *  a.返回下一个位置
             * 
             */
            Hash hash;
            keyOfT kot;
            if (_node->_next)  //_node&& _node->_next  迭代器不会为空,直到end为止,end再加就崩了,看库怎么限制法
            {
                _node = _node->_next;
                
            }
            else
            {
                size_t hashi = hash(kot(_node->_data))% _ht->_tables.size();//计算哈希值
                ++hashi;//这个已经是空了,从下一个开始,
                size_t sz = _ht->_tables.size();
                while (hashi < sz)
                {
                    if (_ht->_tables[hashi])
                    {
                        _node = _ht->_tables[hashi];
                        break;
                    }
                    ++hashi;
                }
                if (sz == hashi)
                {
                    _node = nullptr;
                }
            }
            return *this;
        } //operater++_end;



    }; //iterator_end;

    template<class K, class T,class keyOfT,class Hash >
    class HashTable
    {
        template<class K, class T, class Ref, class Ptr, class keyOfT, class Hash>
        friend struct __Hash_iterator;


    public:
        typedef HashNode<T> node;
        typedef __Hash_iterator<K, T, T&, T*, keyOfT, Hash> iterator;
        typedef __Hash_iterator<K, T, const T&,const T*, keyOfT, Hash> const_iterator;
    private:
        size_t _n = 0;
        std::vector<node*> _tables;

    public:
        iterator begin() 
        {
            node* cur = nullptr;
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                if (_tables[i])
                {
                    cur = _tables[i];
                    break;
                }
            }
            return iterator(cur,this);
        } // begin_end;

        iterator end()
        {
            return iterator(nullptr, this);
        }

        const_iterator begin() const
        {
            return begin(); //类型转换即可
        }

        const_iterator end() const
        {
            return end(); //类型转换即可
        }

        ~HashTable()
        {
            for (auto& cur : _tables)
            {
                while (cur)
                {
                    node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
            }
            //析构,只需要析构主动申请的空间,栈空间不需要,防止内存泄漏
        }


        size_t GetNextPrime(size_t prime)
        {
            static const int __stl_num_primes = 28;
            static const unsigned long __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
            };
            size_t i = 0;
            for ( ;i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > prime) 
                    return __stl_prime_list[i];   
            }

            return __stl_prime_list[i];
        }


        pair<iterator,bool> insert(const T& data)
        {
            keyOfT kot;
            Hash hash;
            iterator it = find(kot(data));
            if (it!=end())
            {
                return make_pair(it,false);
            }

            if (_n == _tables.size())
            {
                size_t newsize = GetNextPrime(_tables.size());

                std::vector<node*> newht(newsize, nullptr);

                for (auto& cur : _tables)
                {
                    while (cur) 
                    {
                        node* next = cur->_next;

                        size_t hashi = hash(kot(cur->_data)) % newht.size();

                        cur->_next = newht[hashi];
                        newht[hashi] = cur;

                        cur = next;
                    }
                }
                _tables.swap(newht); 
            }
            size_t hashi = hash(kot(data)) % _tables.size();

            node* newnode = new node(data);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;

            return make_pair(iterator(_tables[hashi],this),true);
        }//insert_end

        iterator find(const K& key)
        {
            keyOfT kot;
            Hash hash;

            if (_n == 0)
            {
                return end();
            }
            size_t hashi = hash(key) % _tables.size();
            node* cur = _tables[hashi];

            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    break;
                }
                cur = cur->_next;
            }

            return iterator(cur,this);
        } //find_end

        bool erase(const K& key) //可以返回bool,库中返回 1或0 和 迭代器,选择bool也可以
        {
            keyOfT kot;

            Hash hash;
            size_t hashi = hash(key) % _tables.size();

            node* cur = _tables[hashi];
            node* prev = nullptr;
            while (cur)
            {
                if (kot(cur->_data) == key)
                {
                    if (!prev)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;

                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            
            return false;
        }//erase_end

        size_t MaxBucketSize()
        {
            size_t max = 0;
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                auto cur = _tables[i];
                size_t size = 0;
                while (cur)
                {
                    ++size;
                    cur = cur->_next;
                }

                if (size > max)
                {
                    max = size;
                }
            }

            return max;
        }


    };//HashBucket_end

    
}

 

标签:node,tables,cur,iterator,STL,hashi,hashtable,unordered,size
From: https://www.cnblogs.com/DSCL-ing/p/18038616

相关文章

  • STL-RBT_map,set模拟实现
    set#include"26RBT_container.h"namespacetest{//set通过普通迭代器使用const迭代器实现限制key不能被修改template<classK>classset{private:structsetKeyOfT//命名?返回RBT的类型T接收的set的key{constK&......
  • STL-bitset模拟实现
    #include<time.h>#include<string>#include<vector>#include<iostream>usingstd::cout;usingstd::endl;usingstd::string;namespacetest{/**位图概念*所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。......
  • STL-priority_queue模拟实现
    #include<deque>//测试用#include<vector>//测试用#include"9Date.h"//测试用#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{template<classT>structless{booloperator()(constT&......
  • STL-string模拟实现
    1#pragmaonce23#include<iostream>4#include<string.h>5#include<assert.h>6usingstd::cout;7usingstd::endl;8usingstd::cin;9namespacetest{1011classstring{12//friendstd::ostream&......
  • C++ STL 容器 forward_list类型
    C++STL容器forward_list类型介绍std::forward_list是C++标准模板库(STL)中的一个单向链表容器。与std::list不同,std::forward_list只允许从头部到尾部的单向迭代,不支持反向迭代。因此,std::forward_list在某些操作上可能比std::list更高效,尤其是在插入和删除元素时......
  • STL-vector模拟实现
    #pragmaonce#include<assert.h>#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//#include<algorithm>//模板参数省略:1.作为时2.作为类型名template<classT>//数组名:类型名:xx数组classvector......
  • STL-list模拟实现
    #pragmaonce#include"16my_Itetator.h"//测试用#include<iostream>//测试用usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//struct默认权限是public,一般也不会加权限,class才会(需要封装时使用class)//结点使用struct的好处是开放结点,......
  • STL-stack模拟实现
    #pragmaonce#include<assert.h>#include<list>#include<vector>#include<deque>#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//template<classT,classContainers=std::vector&......
  • STL-queue模拟实现
    #include<list>#include<assert.h>#include<deque>#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//template<classT,classContainers=std::list<T>>template<classT,c......
  • C++ STL 容器 list类型
    C++STL容器list类型list对于异常支持很好,要么成功,要么不会发生什么事情以下是std::list在异常处理方面表现良好的几个原因:动态内存管理:std::list使用动态内存分配来存储元素,这意味着它会在需要时自动分配内存,并在不再需要时释放内存。这种自动管理可以减少内存泄漏和悬......