STL學習筆記— —無序容器（Unordered Container）

簡介

在頭檔案<unordered_set>和<unordered_map> 中定義

namespace std 
{
    template <typename T,
            typename Hash = hash<T>,
            typename EqPred = equal_to<T>,
            typename Allocator = allocator<T> >
        class unordered_set;

    template <typename T,
            typename Hash = hash<T>,
            typename EqPred = equal_to<T>,
            typename Allocator = allocator<T> >
        class unordered_multiset;

    template <typename Key, typename T,
            typename Hash = hash<T>,
            typename EqPred = equal_to<T>,
            typename Allocator = allocator<pair<const Key, T> > >
        class unordered_map;

    template <typename Key, typename T,
            typename Hash = hash<T>,
            typename EqPred = equal_to<T>,
            typename Allocator = allocator<pair<const Key, T> > >
        class unordered_multimap;
}
           

unordered_set、unodered_multiset、unordered_map、unodered_multimap都是無序容器，都是以哈希表實作的。

unordered_set、unodered_multiset結構

unordered_map、unodered_multimap結構

Unord和multiUnord操作

構造、複制與析構

Unord c //預設構造函數；建立一個空無序容器

Unord c(bnum) //建立一個空無序容器，内部至少使用了bnum個桶

Unord c(bnum,hf) //建立一個空無序容器，内部至少使用了bnum個桶,hf作為哈希函數

Unord c(bnum,hf,cmp) //建立一個空無序容器，内部至少使用了bnum個桶,hf作為哈希函數,cmp用來識别相等的值

Unord c = c2 //複制構造函數；建立一個新的無序容器作為c2的副本（所有元素都被複制）

Unord c = c2 //複制構造函數；建立一個新的無序容器作為c2的副本（所有元素都被複制）

Unord c(rv) //移動構造函數；使用右值對象rv建立一個新無序容器

Unord c = rv //移動構造函數；使用右值對象rv建立一個新無序容器

Unord c(beg,end) //建立一個無序容器，并使用beg到end範圍内的值進行初始化

Unord c(beg,end,bnum) //建立一個無序容器，并使用beg到end範圍内的值初始化，内部至少使用了bnum個桶

Unord c(beg,end,bnum,hf) //建立一個無序容器，并使用beg到end範圍内的值初始化，内部至少使用了bnum個桶,hf作為哈希函數

Unord c(beg,end,bnum,hf,cmp) //建立一個無序容器，并使用beg到end範圍内的值初始化，内部至少使用了bnum個桶,hf作為哈希函數,cmp用來識别相等的值

Unord c(initlist) //建立一個無序容器，并使用初始化清單進行初始化

Unord c = initlist //建立一個無序容器，并使用初始化清單進行初始化

c.~Unord() //銷毀所有元素并釋放記憶體
           

在這裡Unord可能是如下的一種：

unordered_set<Elem> //一個無序set，使用預設hash<>，預設比較equal_to<>

unordered_set<Elem,Hash> //一個無序set，使用Hash作為hash函數，預設比較equal_to<>

unordered_set<Elem,Hash,Cmp> //一個無序set，使用Hash作為hash函數，使用Cmp進行比較

unordered_multiset<Elem> //一個無序multiset，使用預設hash<>，預設比較equal_to<>

unordered_multiset<Elem,Hash> //一個無序multiset，使用Hash作為hash函數，預設比較equal_to<>

unordered_multiset<Elem,Hash,Cmp> //一個無序multiset，使用Hash作為hash函數，使用Cmp進行比較

unordered_map<Key,T> //一個無序map，使用預設hash<>，預設比較equal_to<>

unordered_map<Key,T,Hash> //一個無序map，使用Hash作為hash函數，預設比較equal_to<>

unordered_map<Key,T,Hash,Cmp> //一個無序map，使用Hash作為hash函數，使用Cmp進行比較

unordered_multimap<Key,T> //一個無序multimap，使用預設hash<>，預設比較equal_to<>

unordered_multimap<Key,T,Hash> //一個無序multimap，使用Hash作為hash函數，預設比較equal_to<>

unordered_multimap<Key,T,Hash,Cmp> //一個無序multimap，使用Hash作為hash函數，使用Cmp進行比較
           

布局操作

c.hash_function() //傳回哈希函數

c.key_eq() //傳回用于比較鍵的相等性的函數

c.bucket_count() //傳回目前桶的個數

c.max_bucket_count() //傳回桶的可能的最大數目

c.load_factor() //傳回目前桶内的負載的元素數量

c.max_load_factor() //傳回桶能夠負載的最大元素數量

c.max_load_factor(val) //設定桶最大負責數量為val

c.rehash(bnum) //重新生産哈希表，使桶的數目至少為bnum

c.reserve(num) //重新生産哈希表，以至于有足夠的空間存放num個元素
           

非變動性操作

c.empty() //判斷容器是否為空，與size()==0相同，但可能更快

c.size() //傳回目前元素數量

c.max_size() //傳回可容納的元素最大數量

c1 == c2 //判斷c1與c2是否相等

c1 != c2 //判斷c1與c2是否不相等，等同于!(c1==c2)
           

特殊查詢操作

c.count(key) //傳回鍵值為key的元素個數

c.find(key) //傳回第一個鍵值為key的位置，若沒找到傳回end()

c.equal_range(key) //傳回所有鍵值為key的範圍，如key可以被插入的第一個位置到最後一個位置
           

指派

c = c2 //将c2所有元素指派給c

c = rv //将右值對象rv的所有元素移動指派給c

c = initlist //使用初始化清單進行指派

c1.swap(c2) //交換c1和c2的數

swap(c1,c2) //交換c1和c2的數
           

疊代器相關函數

c.begin() //傳回一個前向疊代器，指向第一個元素

c.end() //傳回一個前向疊代器，指向最後一個元素

c.cbegin() //傳回一個前向常疊代器，指向第一個元素

c.cend() //傳回一個前向常疊代器，指向最後一個元素

c.rbegin() //傳回一個逆向疊代器，指向逆向疊代的第一個元素

c.rend() //傳回一個逆向疊代器，指向逆向疊代的最後一個元素

c.crbegin() //傳回一個逆向常疊代器，指向逆向疊代的第一個元素

c.crend() //傳回一個逆向常疊代器，指向逆向疊代的最後一個元素
           

插入和移除元素

c.insert(val) //插入一個val的副本，傳回新元素位置（對Unord來說不論成功與否）

c.insert(pos,val) //插入一個val副本，傳回新元素位置（pos應該是插入的搜尋起點）

c.insert(beg,end) //将範圍beg到end的所有元素的副本插入到c（無傳回值）

c.insert(initlist) //插入初始化清單的所有元素的副本（無傳回值）

c.emplace(args...) //插入一個使用args初始化的元素副本，傳回新元素位置（對Unord來說不論成功與否）

c.emplace_hint(pos,args...) //插入一個使用args初始化的元素副本，傳回新元素位置（pos應該是插入的搜尋起點）

c.erase(val) //移除所有與val值相等的元素，并返移除的元素個數

c.erase(pos) //移除疊代器位置的元素，并傳回下個元素的位置

c.erase(beg,end) //移除beg到end範圍内的所有元素，并傳回下個元素的位置

c.clear() //移除是以元素，清空容器
           

bucket接口

c.bucket_count() //傳回目前桶的個數

c.bucket(val) //傳回值val會被查詢到的桶的索引

c.bucket_size(buckidx) //傳回buckidx桶内的元素個數

c.begin(buckidx) //傳回buckidx桶内指向第一個元素的前向疊代器

c.end(buckidx) //傳回buckidx桶内指向第一個元素的前向疊代器

c.cbegin(buckidx) //傳回buckidx桶内指向第一個元素的前向常疊代器

c.cend(buckidx) //傳回buckidx桶内指向第一個元素的前向常疊代器
           

把unordered_map當作關聯數組使用

c[key] //傳回一個指向鍵值為key的元素的引用，如果不存在就插入這個元素

c.at(key) //傳回一個指向鍵值為key的元素的引用