快捷導(dǎo)航

C++11引入的STL中的unordered系列關(guān)聯(lián)式容器

更新時(shí)間：2025年10月03日 09:32:55 作者：oi嘉菲貓

STL中的unordered系列容器是C++11引入的基于哈希表實(shí)現(xiàn)的關(guān)聯(lián)式容器,STL unordered系列容器基于哈希表,支持快速查找但遍歷效率低,適用于無序場(chǎng)景；樹形容器基于紅黑樹,有序且性能穩(wěn)定,適用于需要有序的場(chǎng)景

1.補(bǔ)充認(rèn)識(shí)

STL中的unordered系列容器的底層就是哈希表，包括unordered_set、unordered_map、unordered_multiset、unordered_multimap四個(gè)。

底層哈希原理

補(bǔ)充：從底層來說應(yīng)該分別類似的命名為tree_map和hash_map，也就是樹形結(jié)構(gòu)和哈希結(jié)構(gòu)的，但是由于map之類的出來的早，后面的為了對(duì)應(yīng)就把hash實(shí)現(xiàn)的命名為unordered_xx。

2.unordered_set

2.1容器原型

C++——16.STL的unordered系列容器_迭代器

unordered_set是存儲(chǔ)key鍵值的關(guān)聯(lián)式容器，其允許通過keys快速的索引到與其對(duì)應(yīng)的value。
在unordered_set中，鍵值通常用于惟一地標(biāo)識(shí)元素。
在內(nèi)部,unordered_set沒有對(duì)kye按照任何特定的順序排序, 為了能在常數(shù)范圍內(nèi)找到key，unordered_set將相同哈希值的鍵值放在相同的桶中。
unordered_set容器通過key訪問單個(gè)元素要比set快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
它的迭代器至少是前向迭代器。

2.2常用接口

C++——16.STL的unordered系列容器_迭代_02

3.unordered_multiset

和set與multiset的區(qū)別一樣，unordered_multiset相對(duì)于unordered_set支持相同關(guān)鍵碼的存放。

接口區(qū)別：

C++——16.STL的unordered系列容器_迭代器_03

4.unordered_map

4.1容器原型

C++——16.STL的unordered系列容器_迭代_04

unordered_map是存儲(chǔ)<key, value>鍵值對(duì)的關(guān)聯(lián)式容器，其允許通過keys快速的索引到與其對(duì)應(yīng)的value。
在unordered_map中，鍵值通常用于惟一地標(biāo)識(shí)元素，而映射值是一個(gè)對(duì)象，其內(nèi)容與此鍵關(guān)聯(lián)。鍵和映射值的類型可能不同。
在內(nèi)部,unordered_map沒有對(duì)<kye, value>按照任何特定的順序排序, 為了能在常數(shù)范圍內(nèi)找到key所對(duì)應(yīng)的value，unordered_map將相同哈希值的鍵值對(duì)放在相同的桶中。
unordered_map容器通過key訪問單個(gè)元素要比map快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
unordered_maps實(shí)現(xiàn)了直接訪問操作符(operator[])，它允許使用key作為參數(shù)直接訪問value。
它的迭代器至少是前向迭代器。

4.2常用接口

與unordered_set相比，unordered_map就是鍵值對(duì)KV模型，并且提供了[]重載和at接口，這兩個(gè)與map相似功能。

其他接口功能與unordered_set相同。

5.unordered_multimap

unordered_multimap和unordered_map的區(qū)別就是unordered_multiset和unordered_multiset的區(qū)別。

另外就是unordered_multimap不支持[]和at。

6.樹形關(guān)聯(lián)容器和哈希關(guān)聯(lián)容器的對(duì)比

特性	哈希容器	樹形容器
底層結(jié)構(gòu)	哈希表（順序表+順序表/紅黑表）	紅黑樹（平衡二叉搜索樹）
元素順序	無序	有序
平均時(shí)間復(fù)雜度	O(1)	O(log_2 N)
最壞時(shí)間復(fù)雜度	O(N)（所有元素都沖突，實(shí)際幾乎不可能）	O(log_2 N)
迭代器	單向迭代器	雙向迭代器
關(guān)鍵特性	增刪查改都很快，遍歷較慢。性能依賴哈希函數(shù)。	插入后自然有序。
適用場(chǎng)景	快速查找，不關(guān)注順序。	需要元素有序。

小總結(jié)：除非有有序的要求，不然都可以先考慮哈希容器。

7.unordered系列模擬實(shí)現(xiàn)

7.1重要補(bǔ)充

1）具體存放什么數(shù)據(jù)類型應(yīng)該是set和map層面決定的，底層的哈希表只是存放數(shù)據(jù)，所以需要一個(gè)從存放數(shù)據(jù)提取關(guān)鍵碼的KeyOfT反函數(shù)。

2）另外還需要一個(gè)哈希函數(shù)來處理不能直接取模的情況。

3）哈希表的迭代器迭代邏輯：單鏈表迭代+順序表的哈希桶迭代。

4）如果使用自定義類型取作為樹形關(guān)聯(lián)容器的關(guān)鍵碼的話，需要提供一個(gè)小于比較仿函數(shù)，有了小于也就有了大于和等于。

5）如果使用自定義類型取作為哈希關(guān)聯(lián)容器的關(guān)鍵碼的話，需要提供一個(gè)等于比較仿函數(shù)。

6）set的迭代器無論是普通迭代器還是const迭代器在底層都是使用const迭代器。

7.2代碼

源碼

7.2.1哈希表

#pragma once 
#include <iostream>
// 使用哈希桶解決哈希表的哈希沖突
#include <vector>
#include <utility>

using namespace std;

namespace lbq
{
    // 將輸入轉(zhuǎn)成整型的哈希函數(shù)
    template<class K>
    struct HashFunc 
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };
    
    // 針對(duì)常用的字符串類型的特化
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& str)
        {
            size_t ret = 0;
            for(auto& ele : str)
            {
                ret = ret * 131 + ele;
            }
    
            return ret;
        }
    };

    // 哈希桶具體存儲(chǔ)的數(shù)據(jù)類型
    // 實(shí)際為一個(gè)單鏈表節(jié)點(diǎn)
    template<class T>
    struct _HashNode
    {
        T _data;
        _HashNode<T>* _next;

        _HashNode(const T& data)
            : _data(data)
            , _next(nullptr)
        {}
    };

    // 哈希表的迭代器，其實(shí)是順序表迭代+鏈表迭代
    template<class K, class T, class KeyOfT, class Hash > class HashTable;   // 迭代器中需要訪問，提前聲明
    template<class K, class T, class KeyOfT, class Hash>
    struct _HashTableIterator
    {
        typedef _HashNode<T> Node;
        typedef HashTable<K, T, KeyOfT, Hash> HT;
        typedef _HashTableIterator<K, T, KeyOfT, Hash> Iterator;

        Node* _node;
        HT* _ht;

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

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

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

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

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

        Iterator operator++()
        {
            if(_node->_next != nullptr)
            {
                _node = _node->_next;
            }
            else 
            {
                // 找下一個(gè)桶的位置
                size_t table_index = Hash()(KeyOfT()(_node->_data)) % _ht->_table.size();
                while(++table_index < _ht->_table.size())
                {
                    if(_ht->_table[table_index] != nullptr)
                    {
                        _node = _ht->_table[table_index];
                        break;
                    }
                }

                // 如果后面已經(jīng)沒有桶了
                if(table_index == _ht->_table.size())
                {
                    _node = nullptr;
                }
            }

            return *this;
        }

        Iterator operator++(int)
        {
            Iterator tmp(_node, _ht);
            operator++();
            return tmp;
        }
    };

    // 使用除留余數(shù)法作為哈希表的哈希函數(shù)，使用哈希桶解決沖突
    // K：關(guān)鍵碼數(shù)據(jù)類型
    // T：存儲(chǔ)的數(shù)據(jù)類型，Key或者pair<K, V>
    // KeyOfT：從存儲(chǔ)的數(shù)據(jù)中提取關(guān)鍵碼
    // Hash：將關(guān)鍵碼轉(zhuǎn)成整型用于取模運(yùn)算
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable
    {
    private:
        typedef _HashNode<T> Node;
        friend struct _HashTableIterator<K, T, KeyOfT, Hash>;

    public:
        typedef _HashTableIterator<K, T, KeyOfT, Hash> iterator;

        iterator begin()
        {
            for(size_t i = 0; i < _table.size(); i++)
            {
                if(_table[i] != nullptr)
                {
                    return iterator(_table[i], this);
                }
            }

            return end();
        }

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

        //HashTable()
        //{
        //    _table.resize(10, nullptr);
        //    _sz = 0;
        //}

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

        pair<iterator, bool> insert(const T& data)
        {
            Hash hash;
            KeyOfT kot;
            iterator find_it = find(kot(data));
            if(find_it != end())
            {
                // 已經(jīng)存在相同的元素
                return make_pair(find_it, false);
            }
            
            if(_table.size() == 0 || _sz == _table.size())
            {
                // 順序表為空，或者載荷因子大于1時(shí)增容
                size_t new_size = _table.size() == 0 "h14">7.2.2unordered_set

#pragma once 
// hash set模擬實(shí)現(xiàn)
#include "hashtable.hpp"

namespace lbq
{
    template<class K, class Hasher = HashFunc<K>>
    class unordered_set 
    {
    private:
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

        typedef HashTable<K, K, SetKeyOfT, Hasher> HT;

    public:
        typedef typename HT::iterator iterator;

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

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

        bool empty()
        {
            return _ht.empty();
        }

        size_t size()
        {
            return _ht.size();
        }

        iterator find(const K& key)
        {
            return _ht.find(key);
        }

        size_t count(const K& key)
        {
            return _ht.count(key);
        }

        pair<iterator, bool> insert(const K& key)
        {
            return _ht.insert(key);
        }

        bool erase(const K& key)
        {
            return _ht.erase(key);
        }

        size_t bucket_count()
        {
            return _ht.bucket_count();
        }

        size_t bucket_size(size_t n)
        {
            return _ht.bucket_size(n);
        }


    private:
        HT _ht;
    };
}

`7.2.3unordered_map`

#pragma once 
// unorder_map 模擬實(shí)現(xiàn)
#include "hashtable.hpp"

namespace lbq
{
    template<class K, class V, class Hasher = HashFunc<K>>
    class unordered_map 
    {
    private:
        typedef pair<K, V> T;
        struct MapKeyOfT
        {
            const K& operator()(const T& kv)
            {
                return kv.first;
            }
        };
        typedef HashTable<K, T, MapKeyOfT, Hasher> HT;

    public:
        typedef typename HT::iterator iterator;

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

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

        size_t size()
        {
            return _ht.size();
        }

        bool empty()
        {
            return _ht.empty();
        }

        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = _ht.insert(make_pair(key, V()));
            return ret.first->second;
        }

        iterator find(const K& key)
        {
            return _ht.find(key);
        }

        size_t count(const K& key)
        {
            return _ht.count(key);
        }

        pair<iterator, bool> insert(const T& kv)
        {
            return _ht.insert(kv);
        }

        bool erase(const K& key)
        {
            return _ht.erase(key);
        }

        size_t bucket_count()
        {
            return _ht.bucket_count();
        }

        size_t bucket_size(const size_t& n )
        {
            return _ht.bucket_size(n);
        }

    private:
        HT _ht;
    };
}

到此這篇關(guān)于C++11引入的STL中的unordered系列關(guān)聯(lián)式容器的文章就介紹到這了,更多相關(guān)C++的STL中的unordered容器內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！