【C++】哈希封装map与set

news/2024/9/23 7:54:44/

目录

前言：

一，底层哈希结构

1-1，迭代器的封装

1-2，哈希表的封装

二，unordered_map的封装

三，unordered_set的封装

前言：

        上一篇文章说明了哈希结构，这一篇文章来说明如何使用哈希结构来实现哈希容器unordered_map与unordered_set。这里的封装逻辑跟用红黑树封装map与set一样，map与set都只是套了一层膜，实际上是创建一颗红黑树，而这里的底层结构功能都是依靠哈希结构来实现，实际上是创建了一个哈希表。

        封装思想：跟map与set封装一样，map和set是建立红黑树结构，unordered_map与unordered_set是建立哈希表结构。无论是查找find、插入insert、删除erase，还是迭代器的实现，都是调用哈希结构。哈希结构这里采用拉链法实现。unordered_map与unordered_set向哈希结构中传递的模板参数我们来做以下分析。

        unordered_map与unordered_set的模板参数跟map与set一样，map中的V对应pair<const K, V>，set中的V对应const K，在向哈希结构传递模板参数时要传递K和对应的V。

        map与set后面的关键码都是K，上一篇的哈希结构在取关键码中我们都是直接从pair中取K，由于这里无法确定是map还是set，所以这里也需要传递跟map与set封装一样的转换K类型的伪函数Key。

        哈希结构的封装中哈希函数的关键码必须是正整数，因此这里还需传递将关键码转换成正整数的伪函数Con。

具体代码设计如下：

//哈希结构的头文件
#include "Unordered_HashTable.h" 
//unordered_set的结构封装
template <class K, class Con = Conversion<K>> //Con伪函数与上一篇哈希结构一样，将K转换成正整型
class unordered_set
{
    //伪函数—转换K类型
    struct key
    {
        const K& operator()(const K& data)
        {
            return data;
        }
    };
public:
    //.........
private:
    HashTable<K, const K, key, Con> _hashset;  //哈希表 
};


//哈希结构的头文件
#include "Unordered_HashTable.h"
//unordered_map的结构封装
template <class K, class V, class Con = Conversion<K>> //Con伪函数与上一篇哈希结构一样，将K转换成正整型
class unordered_map
{
    //伪函数—转换K类型
    struct key
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };
public:
    //........
private:
    HashTable<K, pair<const K, V>, key, Con> _hashmap;  //哈希表
};

一，底层哈希结构

1-1，迭代器的封装

        迭代器的基本功能有*，->，++，--，==，!=。在设计迭代器时只要能满足这些功能即可。所有功能中主要是++和--的实现。不难发现，若直接在表中传递结点是可以实现的，只不过要在++和--中利用顺序表vector空间顺序存储的特点，运用二级指针来进行前后表空间的移动。这种方式的实现比较麻烦，因为这里我们还要知道表的边界。其实这里有更好的方法，我们直接向迭代器中传入表结构即可。但需注意传入这里需用哈希表指针，不能使用对象，防止浅拷贝析构函数释放两次空间。具体代码实现如下：

//转换
template<class K>
struct Conversion  //转换正整型
{
    size_t operator()(const K& data)
    {
        return data;
    }
};
template<>  //特殊处理串
struct Conversion<string>
{
    size_t operator()(const string& data)
    {
        size_t count = 0;
        for (auto e : data)
        {
            count += e;
            count *= 131;
        }
        return count;
    }
};


//结点: unordered_map中T是pair<const K, V>  unordered_set中T是const K
template<class T>
struct HashNode
{
    T _data;
    HashNode<T>* _next;    HashNode(const T& data = T())
        : _data(data)
        , _next(nullptr)
    {    }
};

//声明HashTable,因为封装的迭代器里面需要使用
template <class K, class T, class Key, class Con = Conversion<K>>
class HashTable;


//迭代器结构
template <class K, class T, class Key, class Con = Conversion<K>>
struct HashIterator
{
    typedef HashNode<T> Node;   //结点
    typedef HashTable<K, T, Key, Con> HT; //哈希表
    typedef HashIterator<K, T, Key, Con> Self;

    Node* _node;
    //HT _hashtable; 这里不能直接创建对象，因为下面迭代器构造函数的哈希表初始化是浅拷贝。表中结点都是动态开辟的空间，若创建对象，当开始释放迭代器空间时，里面哈希表中的析构函数会释放空间，原哈希表也会释放这块空间，导致释放了两次而出错，因此这里应使用指针，避免了浅拷贝发生析构函数释放动态空间两次的影响。
    //具体运用浅拷贝还是深拷贝，一定要思考动态开辟空间时析构函数释放空间的情况，若不存在这种情况可以进行浅拷贝
    HT* _hashtable; //_hashtable是类，当访问成员时可直接使用库中的->访问

    

    //哈希表是vector，vector底层空间都是连续的，这里可传入结点的指针，不传入哈希表指针，即vector内部空间的地址（指针的指针），当进行++或--时，直接跳转一小块空间。

    HashIterator(Node* node = nullptr, HT* hashtable = nullptr)
        :_node(node)
        , _hashtable(hashtable)
    {    }


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

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

    //++分两种情况: 要么此时结点不是桶的最底端结点，要么此时结点是桶的最底端结点
    Self& operator++() //前置++
    {
        assert(_node && _hashtable);
        //当此时结点不是桶的最底端结点时，直接返回桶的下一个结点位置
        if (_node->_next) _node = _node->_next;
        //当此时结点是桶的最底端结点时需要往表的后面遍历，直到找到表中第一个桶的头结点为止
        else
        {
            Key key;
            Con conversion;
            size_t pos = conversion(key(_node->_data)) % _hashtable->_table.size() + 1;
            while (pos < _hashtable->_table.size() && !_hashtable->_table[pos])    pos++;
            if (pos >= _hashtable->_table.size())
            {
                _node = nullptr;
                return *this;
            }
            _node = _hashtable->_table[pos];
        }
        return *this;
    }
    Self operator++(int) //后置++
    {
        assert(_node && _hashtable);
        //这里不存在动态开辟空间，因此浅拷贝即可
        Self s(*this);
        if (_node->_next) _node = _node->_next;
        else
        {
            Key key;
            Con conversion;
            size_t pos = conversion(key(_node->_data)) % _hashtable->_table.size() + 1;
            while (pos < _hashtable->_table.size() && !_hashtable->_table[pos]) pos++;
            if (pos >= _hashtable->_table.size())
            {
                _node = nullptr;
                return s;
            }
            _node = _hashtable->_table[pos];
        }
        return s;
    }
    //--分两种情况: 要么此时结点不是桶的头结点，要么此时结点是桶的头结点
    Self& operator--() //前置--
    {
        assert(_node && _hashtable);
        Key key;
        Con conversion;
        size_t pos = conversion(key(_node->_data)) % _hashtable->_table.size();
        //当此时结点不是桶的头结点时返回上一个结点        
        if (_hashtable->_table[pos] != _node)
        {
            Node* cur = _hashtable->_table[pos];
            while (cur->_next != _node) cur = cur->_next;
            _node = cur;
        }
        //当此时结点是桶的头结点时需要往前面遍历，直到找到表前面第一个桶的头结点
        else
        {
            pos--;
            while (pos >= 0 && !_hashtable->_table[pos]) pos--;
            if (pos < 0) assert(false);
            _node = _hashtable->_table[pos];
        }
        return *this;
    }
    Self operator--(int) //后置--
    {
        assert(_node && _hashtable);
        Self s(*this); //这里不存在动态开辟空间，因此浅拷贝即可
        Key key;
        Con conversion;
        size_t pos = conversion(key(_node->_data)) % _hashtable->_table.size();
        if (_hashtable->_table[pos] != _node)
        {
            Node* cur = _hashtable->_table[pos];
            while (cur->_next != _node) cur = cur->_next;
            _node = cur;
        }
        else
        {
            pos--;
            while (pos >= 0 && !_hashtable->_table[pos]) pos--;
            if (pos < 0) assert(false);
            _node = _hashtable->_table[pos];
        }
        return s;
    }

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

1-2，哈希表的封装

        哈希表封装unordered_map和unordered_set只需稍微变动插入、查找、删除功能和添加迭代器功能即可，具体代码和说明如下：

//声明中已有缺省类型，因为缺省类型使用了模板，所以为了避免缺省类型冲突系统不允许这里Con再次使用缺省类型
template <class K, class T, class Key, class Con>
class HashTable
{
    typedef HashNode<T> Node;
    //因为迭代器要访问哈希表，这里需声明友元。模板类型在声明友元后需加上模板类型
    friend struct HashIterator<K, T, Key, Con>;
public:
    typedef HashIterator<K, T, Key, Con> Iterator;

    HashTable(const size_t n = 10)
        : _count(0)
    {
        _table.resize(n, nullptr);
    }

    ~HashTable()
    {
        for (size_t i = 0; i < _table.size(); i++)
        {
            Node* cur = _table[i];
            while (cur)
            {
                _table[i] = cur->_next;
                delete cur;
                _count--;
                cur = _table[i];
            }
        }
    }

    //封装begin和end()，用于赋值给迭代器
    Iterator begin()
    {
        for (size_t i = 0; i < _table.size(); i++)
        {
            if (_table[i])
            {
                //注意，由于迭代器构造函数参数有两个，这里无法直接返回。类这种情况可以使用以下创建匿名对象的方法进行转换。

                //当向迭代器时赋值时，是将当前对象的begin进行赋值，所以这里要传入此时对象的表指针，即this，以下同理。
                return Iterator(_table[i], this); //匿名对象实现隐式类型转换返回
            }
        }
        return Iterator(nullptr, this); //匿名对象实现隐式类型转换返回
    }
    Iterator end()
    {
        return Iterator(nullptr, this); //匿名对象实现隐式类型转换返回
    }

    Iterator Find(const K& data)
    {
        Con conversion;
        Key key;
        size_t pos = conversion(data) % _table.size();
        Node* cur = _table[pos];
        while (cur)
        {
            if (key(cur->_data) == data) return Iterator(cur, this);
            cur = cur->_next;
        }
        return end();
    }

    pair<Iterator, bool> Insert(const T& data)
    {
        Key key;
        Con conversion;
        if (Find(key(data)) != end()) return make_pair(Find(key(data)), false);
        //负载因子到1就扩容
        if (_count == _table.size())
        {
            //为保证效率这里不采用创建对象，直接创建表来重新搬运结点数据
            vector<Node*> newtable;
            newtable.resize(2 * _table.size(), nullptr);
            for (size_t i = 0; i < _table.size(); i++)
            {
                Node* cur = _table[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    size_t pos = conversion(key(cur->_data)) % newtable.size();
                    cur->_next = newtable[pos];
                    newtable[pos] = cur;
                    cur = next;
                }
            }
            _table.swap(newtable);
        }
        size_t pos = conversion(key(data)) % _table.size();
        Node* node = new Node(data);
        node->_next = _table[pos];
        _table[pos] = node;
        _count++;
        return make_pair(Find(key(data)), true);
    }

    bool Erase(const K& data)
    {
        Con conversion;
        Key key;
        if (Find(data) == end()) return false;
        size_t pos = conversion(data) % _table.size();
        Node* cur = _table[pos];
        Node* prv = nullptr;
        while (key(cur->_data) != data)
        {
            prv = cur;
            cur = cur->_next;
        }
        if (cur == _table[pos]) _table[pos] = cur->_next;
        else prv->_next = cur->_next;
        delete cur;
        cur = nullptr;
        _count--;
        return true;
    }
private:
    vector<Node*> _table;
    size_t _count;
};

二，unordered_map的封装

        unordered_map的结构明白之后这里的封装就只是套了哈希结构的功能，即有关迭代器的begin、end()和功能接口的insert、find、erase，[]，跟map封装一样。

#include "Unordered_HashTable.h"  //哈希结构头文件

template <class K, class V, class Con = Conversion<K>>
class unordered_map
{
    struct key
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };
public:
    typedef typename Hash_bucket::HashTable<K, pair<const K, V>, key, Con>::Iterator iterator;

    iterator begin()
    {
        return _hashmap.begin();
    }

    iterator end()
    {
        return _hashmap.end();
    }

    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
        return _hashmap.Insert(kv);
    }

    iterator find(const K& data)
    {
        return _hashmap.Find(data);
    }

    bool erase(const K& data)
    {
        return _hashmap.Erase(data);
    }

    V& operator[](const K& key)
    {
        _hashmap.Insert(make_pair(key, V()));
        iterator it = find(key);
        return it->second;
    }
private:
    HashTable<K, pair<const K, V>, key, Con> _hashmap;
};

样例测试：

void test_map1()
{
    unordered_map<string, string> dict;
    dict.insert(make_pair("sort", ""));
    dict.insert(make_pair("left", ""));
    dict.insert(make_pair("right", "L"));
    dict.insert(make_pair("string", ""));

    for (auto& kv : dict)
    {
        kv.second += 'y';

        cout << kv.first << ":" << kv.second << endl;
    }
    cout << endl;

    unordered_map<string, string>::iterator it = dict.begin();
    while (it != dict.end())
    {
        cout << it->first << ": " << it->second << endl;
        it++;
    }

    string n;
    cin >> n;
    if (dict.find(n) == dict.end())
    {
        cout << "No data" << endl;
    }
    else
    {
        it = dict.find(n);
        cout << "Exist data: " << it->first << ":" << it->second << endl;
    }

    dict.erase("string");
    dict.erase("left");
    cout << "After Erase string and left: ";
    for (auto& kv : dict) cout << kv.first << ":" << kv.second << "  ";
    cout << endl;
}

三，unordered_set的封装

        unordered_set与unordered_map同理，唯一要注意的是此容器没有重载"[]"，且这里哈希重载迭代器->功能不能在unordered_set中运用，是为了在unordered_map中运用的，因为数据_data不是迭代器里面的数据。封装->的本质是左边是右边的地址，然后调用系统库中->访问类里面的数据，而unordered_map数据类型是pair，虽然迭代器中不存在数据，但C++pair库中专门封装了first和second访问数据，因此可以使用重载的->，封装代码如下：

#include "Unordered_HashTable.h"
template <class K, class Con = Conversion<K>>
class unordered_set
{
    struct key
    {
        const K& operator()(const K& data)
        {
            return data;
        }
    };
public:
    typedef typename Hash_bucket::HashTable<K, const K, key, Con>::Iterator iterator;

    iterator begin()
    {
        return _hashset.begin();
    }

    iterator end()
    {
        return _hashset.end();
    }

    pair<iterator, bool> insert(const K& data)
    {
        return _hashset.Insert(data);
    }

    iterator find(const K& data)
    {
        return _hashset.Find(data);
    }

    bool erase(const K& data)
    {
        return _hashset.Erase(data);
    }
private:
    HashTable<K, const K, key, Con> _hashset;
};

样例测试：

void test_set1()
{
    unordered_set<int> us;
    us.insert(3);
    us.insert(1);
    us.insert(7);
    us.insert(5);
    us.insert(15);
    us.insert(45);
    us.insert(7);

    unordered_set<int>::iterator it = us.begin();
    while (it != us.end())
    {
        //注意: 这里不能使用it->_data，因为_data不是迭代器里面的数据，封装->的本质是左边是右边的地址，然后调用系统库中->访问类里面的数据
        //cout << it->_data;错误使用
        cout << *it << " ";
        it++;
    }
    cout << endl;

    for (auto& e : us)
    {
        cout << e << " ";
    }
    cout << endl;

    it = us.begin()++;
    cout << "后置begin++: " << *it << endl;
    it = ++us.begin();
    cout << "前置begin++: " << *it << endl;
    cout << endl;

    for (int i = 0; i < 2; i++) it++;
    cout << "Iterator: " << *it << endl;
    unordered_set<int>::iterator its;
    its = --it;
    cout << "前置--: " << *it << endl;
    cout << endl;

    cout << "Iterator: " << *it << endl;
    its = it--;
    cout << "后置--: " << *its << endl;
    cout << endl;
}


http://www.ppmy.cn/news/1426652.html

相关文章

【JavaEE多线程】线程安全、锁机制及线程间通信

【JavaEE多线程】线程安全、锁机制及线程间通信

目录 线程安全线程安全问题的原因 synchronized 关键字-监视器锁monitor locksynchronized的特性互斥刷新内存可重入 synchronized使用范例 volatilevolatile能保证内存可见性volatile不保证原子性synchronized 也能保证内存可见性 wait 和 notifywait()方法notify()方法notify…
阅读更多...
【c基础】文件操作

【c基础】文件操作

1.fopen和fclose函数 函数原型 FILE *fopen(const char *path, const char *mode); 参数解释&#xff1a; 返回值&#xff1a;fopen打开成功&#xff0c;则返回有效file的有效地址&#xff0c;失败返回NULL。path是文件路径&#xff0c;可以相对路径&#xff0c;可以绝对路径…
阅读更多...
进来学习K8s中的网络资源对象Service！

进来学习K8s中的网络资源对象Service！

进来学习K8s中的网络资源对象Service&#xff01; Kubernetes&#xff08;K8s&#xff09;是一个强大的容器编排平台&#xff0c;它不仅能够管理容器的生命周期&#xff0c;还能提供复杂的网络功能&#xff0c;使得在集群中的服务发现和访问变得简单。在 Kubernetes 中&#x…
阅读更多...
手把手教你实现贪吃蛇

手把手教你实现贪吃蛇

前言 在实现贪吃蛇前&#xff0c;我们需要熟练地掌握C语言知识&#xff0c;对初阶数据结构中的链表有一定的掌握&#xff0c;并且我们还会使用到Win 32 API 的知识&#xff0c;下面我会对需要使用到的API接口函数进行解释。最终的代码我放在后面&#xff0c;有需要的可以自取。…
阅读更多...
怎么看自己是不是公网IP？

怎么看自己是不是公网IP？

当我们需要进行网络连接或者网络配置的时候&#xff0c;经常会遇到需要知道自己是否拥有公网IP的情况。公网IP是全球唯一的IP地址&#xff0c;在互联网上可直接访问和被访问&#xff0c;而私有IP则是在本地网络中使用&#xff0c;无法从互联网上直接访问。我们将介绍如何查看自…
阅读更多...
springboot+java照相馆预约管理系统ssm

springboot+java照相馆预约管理系统ssm

框架&#xff1a;ssm/springboot都有 jdk版本&#xff1a;1.8 及以上 ide工具&#xff1a;IDEA 或者eclipse 数据库: mysql 编程语言: java 前端&#xff1a;layuibootstrapjsp 详细技术&#xff1a;HTMLCSSJSjspspringmvcmybatisMYSQLMAVENtomcat 开发工具 IntelliJ IDEA: 一…
阅读更多...
【SpringBoot】springboot的启动初步理解

【SpringBoot】springboot的启动初步理解

springboot的启动初步理解 我们会发现开发一个Spring Boot&#xff0c;都会有一个注解SpringBootApplication和一个类定义SpringApplication.run&#xff0c;点击源码可以查看到如下代码&#xff1a; Target({ElementType.TYPE}) Retention(RetentionPolicy.RUNTIME) Document…
阅读更多...
Modelsim与Verilog入门

Modelsim与Verilog入门

0.什么是Modelsim&#xff1f; Modelsim是一个支持多语言的仿真环境&#xff0c;比如我知道的Verilog和VHDL语言都可以在里边使用&#xff0c;这俩都是硬件描述语言&#xff1b; 即就是个软件&#xff0c;你可以用Verilog语言来写代码&#xff0c;然后编译&#xff0c;仿真出…
阅读更多...
最新文章

Copyright @ 2022~2023