C++之unordered容器

2020-12-23

无序容器以一种随意顺序包含插入进去的所有元素。并以一种随机的次序访问他们。unordered_set和unordered_multiset存放的是特定类型的个别value,而unordered_map和unordered_multimap存放的元素都是key/value pair,其中key用来作为存放和查找特定元素的依据。unordered_set, unordered_multiset, unordered_map unordered_multimap的实现都是以hash table为底层数据结构。和map,set一样，unordered_set和unordered_map不允许有重复的元素，而unordered_multiset和unordered_multimap允许元素重复。unordered_set, unordered_multiset,位于头文件,unordered_map unordered_multimap位于头文件.

unordered_set和unordered_multiset的元素类型，必须是可比较的。

unordered_map和unordered_multimap是key/value类型的，对于其中的key、value的要求如下：

key和value都必须可以复制和可以移动（movable）
key必须是可以等价准则比较的。

对于模板中的参数Hash用来定义hash函数，如果是自己定义的类型，就必须指定hash函数。

对于无序容器的构造函数与set和map的构造函数类似，不过可以对于自己定义的类型，需要自己定义特殊的hash 函数。这个hash函数的要求是一个必须是个函数或者是一个function object它接受一个value作为参数，并返回一个std::size_t的value.

无序容器的接口与set和map的接口差不多，但是相比于set和map而言，无序容器不支持双向迭代器，它的迭代器是一个单向的迭代器。

构造函数，拷贝构造，拷贝赋值，析构函数

操作	功能
Unordered c;	默认构造函数，创建一个空的无序容器
Unordered c(bnum)	建立一个空的Unordered对象，内部至少使用bnum个bucket
Unordered c(bnum,hf)	建立一个空的Unordered对象，内部至少使用bnum个bucket,并以hf作为hash 函数
Unordered c(bnum,hf,cmp)	建立一个空的Unordered对象，内部至少使用bnum个bucket,并以hf作为hash 函数，并以cmp作为predicate用来鉴定value
Unordered c(c2)	copy constructor
Unordered c = c2;	copy constructor
Unordered c(rv)	move constructor.rv的所有资源被释放
Unordered c = rv	move constructor.rv的所有资源被释放
Unordered c(beg,end)	以区间[beg,end)内的元素为c的初值
Unordered c(beg,end,bnum)	以区间[beg,end)内的元素为c的初值，内部至少使用bnum个bucket
Unordered c(beg,end,bnum,hf)	以区间[beg,end)内的元素为c的初值，内部至少使用bnum个bucket，并以hf作为hash 函数
Unordered c(beg,end,bnum,hf,cmp)	以区间[beg,end)内的元素为c的初值，内部至少使用bnum个bucket，并以hf作为hash 函数并以cmp作为predicate用来鉴定value
Unordered c(initlist)	列表初始化
Unordered c = initlist	列表初始化
c.~ Unordered ()	析构函数

其中 Unordered的形式为以下几种：

unordered_set / unorderd_set<Elem,Hash> / unordered_set<Elem,Hash,Cmp>

unordered_multiset / unorderd_multiset<Elem,Hash> / unordered_multiset<Elem,Hash,Cmp>

unordered_map / unorderd_map<Elem,Hash> / unordered_map<Elem,Hash,Cmp>

unordered_multimap / unorderd_multimap<Elem,Hash> / unordered_multimap<Elem,Hash,Cmp>

无序容器的布局函数：

操作	效果
c.hash_function()	返回hash函数
c.key_eq()	返回相等性判断式
c.bucket_count()	返回当前的bucket个数
c.max_bucket_count()	返回bucket的最大可能数量
c.load_factor()	返回当前的负载因子
c.max_load_factor()	返回当前的最大负载系数
c,max_load_factor(val)	设定当前的最大负载系数为val
c.rehash(bnum)	将容器重新计算hash，使其bucket至少为bnum
c．reverse(num)	将容器重新计算hash，使其至少可以容纳num个元素

非更改操作：

操作	功能
c.empty()	容器是否为空
c.size()	目前的元素个数
c.max_size()	元素个数的最大可能量
c1 == c2	c1是否等于c2(每个元素调用 == )
c1 != c2	c1 是否不等于 c2

查找函数：

操作	功能
c.count(val)	返回容器中key为val的个数
c.find(val)	返回容器中第一个元素为key为val的元素，找不到返回val
c.equal_range(val)	返回key为val可被插入的第一个位置和最后一个位置即key==val的元素区间

赋值操作：

操作	效果
c = c1	copy assignment，将c2元素赋值给c
c = rv	move assignment,
c = initilist	将初值列的元素赋值给c
c1.swap(c2)	交换c1和c2的元素
swap(c1,c2)	交换c1和c2的元素

迭代器：

操作	效果
c.begin()	返回一个 forward iterator指向第一元素
c.end()	返回一个 forward iterator指向末尾元素的下一位置
c.cbegin()	返回一个 const forward iterator指向第一元素
c.cend()	返回一个 const forward iterator指向末尾元素的下一位置
c.rbegin()	返回一个 reverse iterator指向反向迭代的第一元素
c.rend()	返回一个 reverse iterator指向反向迭代的末尾元素的下一位置
c.crbegin()	返回一个 const reverse iterator指向反向迭代的第一元素
c.crend()	返回一个const reverse iterator指向反向迭代的末尾元素的下一位置

元素操作：(下面的元素指的是 key/value pair)

操作	效果
c.insert(val)	插入val,并返回新元素的位置
c.insert(pos,val)	以pos为起点在[pos,end)中插入val，返回新元素的位置
c.insert(beg,end)	将区间[beg,end)内的元素插入到c中
c.insert(initlist)	将初值列的元素插入到c中
c.emplace(args…)	插入一个args元素的值，并返回新元素的位置
c.emplace_hint(pos,args…)	以pos为起点在[pos,end)中插入args，返回新元素的位置
c.erase(val)	移除与 val相等的所有元素，返回被移除的个数
c.erase(pos)	移除iterator位置pos上的元素，无返回值
c.erase(beg,end)	移除区间[beg,end)内的元素，无返回值
c.clear()	将容器清空

关联式操作：

操作	效果
c[key]	如果key存在，则返回key元素的值，如果不存则插入一个key/value元素
c.at(key)	返回对应key/value中对应key的value

示例如下：

 #include <unordered_set>
#include <iterator>
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
void test_set(){
    cout << " ------------unordered_set----------" << endl;
    unordered_set<int> coll = {1,2,3,5,7,11,12,17,19,77};
    //
    copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
    cout << '\n';

    coll.insert({-7,17,33,-11,17,19,1,13});
    copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
    cout << '\n';
    if (coll.find(19) != coll.end()){
        cout << "19 is available" << endl;
    }
    for(auto pos = coll.begin();pos != coll.end();){
        if (*pos < 0){
            pos = coll.erase(pos);
        }else{
            ++pos;
        }
    }
    copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
    cout << '\n';
}
void test_multiset(){
    cout << " ------------unordered_multiset----------" << endl;
    unordered_multiset<int> coll = {1,2,3,5,7,11,12,17,19,77};
    //
    copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
    cout << '\n';

    coll.insert({-7,17,33,-11,17,19,1,13});
    copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
    cout << '\n';
    if (coll.find(19) != coll.end()){
        cout << "19 is available" << endl;
    }
    for(auto pos = coll.begin();pos != coll.end();){
        if (*pos < 0){
            pos = coll.erase(pos);
        }else{
            ++pos;
        }
    }
    copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));
    cout << '\n';
}
void test_map(){
    cout << " ------------unordered_map----------" << endl;
    unordered_map<int,double> coll;
    for (int i = 1; i <10 ; ++i) {
        coll[i] = static_cast<double>(i) / 10;
    }
    for(auto pos = coll.begin();pos != coll.end();++pos){
        cout << "coll[" <<  pos->first << "] = " << pos->second <<endl;
    }
    coll.insert({100,0.01});
    coll.insert({101,0.01});
    coll.insert({102,0.01});
    coll.insert({103,0.01});
    for(auto pos = coll.begin();pos != coll.end();){
        if (pos->first > 100){
            pos = coll.erase(pos);
        }else{
            ++pos;
        }
    }
    for(auto pos = coll.begin();pos != coll.end();++pos){
        cout << "coll[" <<  pos->first << "] = " << pos->second <<endl;
    }
}
void test_multimap(){
    cout << " ------------unordered_multimap----------" << endl;
    unordered_multimap<int,double> coll;
    for (int i = 1; i <10 ; ++i) {
        coll.insert({i,static_cast<double>(i) / 10});
    }
    for(auto pos = coll.begin();pos != coll.end();++pos){
        cout << "coll[" <<  pos->first << "] = " << pos->second <<endl;
    }
    coll.insert({100,0.01});
    coll.insert({100,0.02});
    coll.insert({100,0.03});
    coll.insert({103,0.01});
    for(auto pos = coll.begin();pos != coll.end();){
        if (pos->first > 100){
            pos = coll.erase(pos);
        }else{
            ++pos;
        }
    }
    for(auto pos = coll.begin();pos != coll.end();++pos){
        cout << "coll[" <<  pos->first << "] = " << pos->second <<endl;
    }
}
int main(int argc,char *argv[])
{
    test_multiset();
    test_set();
    test_map();
    test_multimap();
    return 0;
}