1.unordered_map

1.介绍

最近使用到一个c++的容器——unordered_map，它是一个关联容器，内部采用的是hash表结构，拥有快速检索的功能。

2.性质

• 关联性：一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。通过key去检索value，而不是通过绝对地址（和顺序容器不同）
• 无序性：使用hash表存储，内部无序，可以使用[]操作符来访问key值对应的value值。
• Map : 每个值对应一个键值
• 键唯一性：不存在两个元素的键一样
• 动态内存管理：使用内存管理模型来动态管理所需要的内存空间
• 1.2 Hashtable和bucket
• 由于unordered_map内部采用的hashtable的数据结构存储，所以，每个特定的key会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable是可能存在冲突的（多个key通过计算映射到同一个位置），在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个bucket是十分形象的（像桶子一样，可以装多个元素）。可以参考这篇介绍哈希表的文章

• 1)元素在容器无顺序，不提供按顺序遍历
  2）在极端条件下，查找时间复杂度不是O(1)，用的时间复杂度会提高很多
  3）占用的空间可能会更多
  4）在1000W以上不如set，hash冲突，性能降低很多；1000W以下就比set好
• 所以unordered_map内部其实是由很多哈希桶组成的，每个哈希桶中可能没有元素，也可能有多个元素。

3.模板

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

• 主要使用的也是模板的前2个参数<键，值>（需要更多的介绍可以点击这里这里）

unordered_map<const Key, T> map;

4.定义迭代器

• unordered_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值。

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>) 

• 它的键值分别是迭代器的first和second属性。

it->first;               // same as (*it).first   (the key value)
it->second;              // same as (*it).second  (the mapped value) 

5.功能函数

unordered_map的构造方式有几种：

• 构造空的容器
• 复制构造
• 范围构造
• 用数组构造

代码：

5.1构造函数

// constructing unordered_maps
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

typedef unordered_map<string,string> stringmap;//定义unordered_map容器

stringmap merge (stringmap a,stringmap b) {
  stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
}

int main ()
{
  stringmap first;                              				   // 空
  stringmap second ( {{"apple","red"},{"lemon","yellow"}} );       // 用数组初始
  stringmap third ( {{"orange","orange"},{"strawberry","red"}} );  // 用数组初始
  stringmap fourth (second);                    				   // 复制初始化
  stringmap fifth (merge(third,fourth));        				   // 移动初始化
  stringmap sixth (fifth.begin(),fifth.end());  		  		   // 范围初始化

  cout << "sixth contains:";
  for (auto& x: sixth) cout << " " << x.first << ":" << x.second;
  cout << endl;

  return 0;
}
//输出
sixth contains: apple:red lemon:yellow orange:orange strawberry:red

5.2 容量操作：size、empty

//size
size_type size() const noexcept;//返回unordered_map的大小

//empty
bool empty() const noexcept;	//为空返回true，不为空返回false，和用size() == 0判断一样。

5.3 元素操作：find、insert、at、erase、clear、swap、for循环打印

//查找
iterator find ( const key_type& k );//查找key所在的元素。找到：返回元素的迭代器。通过迭代器的second属性获取值，没找到：返回unordered_map::end

//插入
插入有几种方式：

复制插入(复制一个已有的pair的内容)
数组插入（直接插入一个二维数组）
范围插入（复制一个起始迭代器和终止迭代器中间的内容）
数组访问模式插入(和数组的[]操作很相似)

//查找并修改-at
mapped_type& at ( const key_type& k );
查找key所对应的值
如果存在：返回key对应的值，可以直接修改，和[]操作一样。
如果不存在：抛出 out_of_range 异常.
mymap.at(“Mars”) = 3396; //mymap[“Mars”] = 3396

//删除元素
iterator erase ( const_iterator position );//通过位置（迭代器）
size_type erase ( const key_type& k );	   //通过key
iterator erase ( const_iterator first, const_iterator last );//通过范围（两个迭代器）

//清空容器
void clear() noexcept	//清空unordered_map

//交换容器
void swap ( unordered_map& ump );//交换两个unordered_map（注意，不是交换特定元素，是整个交换两个map中的所有元素）

//遍历unorder_map代码
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
	string key="123";
	int value=4;
	unordered_map<string, int> unomap;//创建一个key为string类型，value为int类型的unordered_map
	unomap.emplace(key, value);//使用变量方式，插入一个元素
	unomap.emplace("456", 7);//也可以直接写上key和value的值
	cout<<unomap["123"];//通过key值来访问value

	cout<<endl;
	for(auto x:unomap)//遍历整个map，输出key及其对应的value值
		cout<<x.first<<"  "<<x.second<<endl;

	for(auto x:unomap)//遍历整个map，并根据其key值，查看对应的value值
		cout<<unomap[x.first]<<endl;
}

代码：

// unordered_map::insert
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

void display(unordered_map<string,double> myrecipe,string str)
{
    cout << str << endl;
    for (auto& x: myrecipe)
        cout << x.first << ": " << x.second << endl;
    cout << endl;
}

int main ()
{
    unordered_map<string,double>
    myrecipe,
    mypantry = {{"milk",2.0},{"flour",1.5}};

    /****************插入*****************/
    pair<string,double> myshopping ("baking powder",0.3);
    myrecipe.insert (myshopping);                        // 复制插入
    myrecipe.insert (make_pair<string,double>("eggs",6.0)); // 移动插入
    myrecipe.insert (mypantry.begin(), mypantry.end());  // 范围插入
    myrecipe.insert ({{"sugar",0.8},{"salt",0.1}});    // 初始化数组插入(可以用二维一次插入多个元素，也可以用一维插入一个元素)
    myrecipe["coffee"] = 10.0;  //数组形式插入

    display(myrecipe,"myrecipe contains:");

    /****************查找*****************/
    unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");

    if ( got == myrecipe.end() )
        cout << "not found";
    else
        cout << "found "<<got->first << " is " << got->second<<"\n\n";
    /****************修改*****************/
    myrecipe.at("coffee") = 9.0;
    myrecipe["milk"] = 3.0;
    display(myrecipe,"After modify myrecipe contains:");


    /****************擦除*****************/
    myrecipe.erase(myrecipe.begin());  //通过位置
    myrecipe.erase("milk");    //通过key
    display(myrecipe,"After erase myrecipe contains:");

    /****************交换*****************/
    myrecipe.swap(mypantry);
    display(myrecipe,"After swap with mypantry, myrecipe contains:");

    /****************清空*****************/
    myrecipe.clear();
    display(myrecipe,"After clear, myrecipe contains:");
    return 0;
	
	/****************打印*****************/
	for(auto x:unomap)//遍历整个map，输出key及其对应的value值
	{
	x.second = 0;	
	cout<<x.second<<endl;//全是  000；;	
	}
	cout<<x.second<<endl;//回复原来的数值的。彻底改变：使用find彻底找到这个数值，然后在进行改，可以保证作用域是整个程序。
	for(auto x:unomap)//遍历整个map，输出key及其对应的value值
	{
	auto it = umap.find(key) //改
	if(it != umap.end()) 
	    it->second = new_value; 
	}		

}

• 输出结果

myrecipe contains:
salt: 0.1
milk: 2
flour: 1.5
coffee: 10
eggs: 6
sugar: 0.8
baking powder: 0.3

found coffee is 10

After modify myrecipe contains:
salt: 0.1
milk: 3
flour: 1.5
coffee: 9
eggs: 6
sugar: 0.8
baking powder: 0.3

After erase myrecipe contains:
flour: 1.5
coffee: 9
eggs: 6
sugar: 0.8
baking powder: 0.3

After swap with mypantry, myrecipe contains:
flour: 1.5
milk: 2

After clear, myrecipe contains:

5.4 迭代器和bucket操作

//begin
iterator begin() noexcept;//begin() : 返回开始的迭代器（和你的输入顺序没关系，因为它的无序的）
local_iterator begin ( size_type n );//begin(int n) : 返回n号bucket的第一个迭代器

//end
iterator end() noexcept;	//end(): 返回结束位置的迭代器
local_iterator end( size_type n );//end(int n) : 返回n号bucket的最后一个迭代器

//bucket
size_type bucket ( const key_type& k ) const;
//返回通过哈希计算key所在的bucket（注意：这里仅仅做哈希计算确定bucket，并不保证key一定存在bucket中！）

//bucket_count
size_type bucket_count() const noexcept;//返回bucket的总数

//bucket_size
size_type bucket_size ( size_type n ) const;//返回第n个bucket的大小（这个位置的桶子里有几个元素，注意：函数不会判断n是否在count范围内）

代码：

// unordered_map::bucket_count
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main ()
{
    unordered_map<string,string> mymap =
    {
        {"house","maison"},
        {"apple","pomme"},
        {"tree","arbre"},
        {"book","livre"},
        {"door","porte"},
        {"grapefruit","pamplemousse"}
    };
    /************begin和end迭代器***************/
    cout << "mymap contains:";
    for ( auto it = mymap.begin(); it != mymap.end(); ++it )
        cout << " " << it->first << ":" << it->second;
    cout << endl;
    /************bucket操作***************/
     unsigned n = mymap.bucket_count();

    cout << "mymap has " << n << " buckets.\n";

    for (unsigned i=0; i<n; ++i)
    {
        cout << "bucket #" << i << "'s size:"<<mymap.bucket_size(i)<<" contains: ";
        for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)
            cout << "[" << it->first << ":" << it->second << "] ";
        cout << "\n";
    }

    cout <<"\nkey:'apple' is in bucket #" << mymap.bucket("apple") <<endl;
    cout <<"\nkey:'computer' is in bucket #" << mymap.bucket("computer") <<endl;

    return 0;
}

• 输出结果

mymap contains: door:porte grapefruit:pamplemousse tree:arbre apple:pomme book:livre house:maison
mymap has 7 buckets.
bucket #0's size:2 contains: [book:livre] [house:maison]
bucket #1's size:0 contains:
bucket #2's size:0 contains:
bucket #3's size:2 contains: [grapefruit:pamplemousse] [tree:arbre]
bucket #4's size:0 contains:
bucket #5's size:1 contains: [apple:pomme]
bucket #6's size:1 contains: [door:porte]

key:'apple' is in bucket #5

key:'computer' is in bucket #6

最后
unordered_map常用的功能函数介绍就这么多了，还有一些比较不常用的功能的介绍，可以参考这里

2.unordered_set

2.1性质

• unordered_set 容器提供了和 unordered_map 相似的能力，但 unordered_set 可以用保存的元素作为它们自己的键。T 类型的对象在容器中的位置由它们的哈希值决定，因而需要定义一个 Hash< T > 函数。基本类型可以省去Hash< T >方法。

• 不能存放重复元素。

• 可指定buckets个数，可进行初始化，也可后期插入元素

• 1、无序集是一种容器，它以不特定的顺序存储惟一的元素，并允许根据元素的值快速检索单个元素。
  2、在unordered_set中，元素的值同时是唯一标识它的键。键是不可变的，只可增删，不可修改
  3、在内部，unordered_set中的元素没有按照任何特定的顺序排序，而是根据它们的散列值组织成桶，从而允许通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。
  4、unordered_set容器比set容器更快地通过它们的键访问单个元素，尽管它们在元素子集的范围迭代中通常效率较低。
  5、容器中的迭代器至少是前向迭代器。

std::unordered_set<string> example;
std::unordered_set<string> things {16}; // 16 buckets
std::unordered_set<string> words {"one", "two", "three", "four"};// Initializer list
std::unordered_set<string> copy_wrds {words}; // Copy constructor

2.2 unordered_set函数

2.2.1 构造函数

2.2.2 迭代器

2.2.3 各种操作

• unordered_set<Key, Hash, KeyEqual, Allocator>::insert
  

• unordered_set<Key, Hash, KeyEqual, Allocator>::find
  

• unordered_set<Key, Hash, KeyEqual, Allocator>::erase
  

• 迭代
  

• 改变unordered_set中的值
  

• 在unordered_set中使用struct的完整例子
  HDUOJ 1004 选出频率最大的字符串

/**
 * @Copyright (C)  2019  all rights reserved
 * @file Max_Frequency.cpp
 * @author Rinko
 * @date 2019-09-17 
 */

#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
#define print(x) cout << x << endl
#define input(x) cin>>x

struct balloon{
    string color;           //颜色
    mutable int count;      //数量，初始为0，mutable表示可修改！！
    balloon(string n):color(n),count(0){}
    void addCount(){
        count++;
    }
};

//指定符合hash函数的operator==重载
//比较相等只看color
bool operator==(const struct  balloon & X,const struct balloon & Y){
    return hash<string>()(X.color) == hash<string>()(Y.color);
}

struct balloon_hash{     //指定hash函数，作为模板的第二个参数
    //hash值为color的hash值
    size_t operator()(const struct balloon& _r) const {
        string tmp=_r.color;
        return std::hash<string>()(tmp);
    }
};

int main()
{
    int n;
    while (cin >> n){
        if(n == 0)  break;
        unordered_set<balloon, balloon_hash> balloons;
        int maxCount = 0;
        string maxString = "";
        string temp;
        for(unsigned i = 0; i < n; ++i){
            input(temp);
            //成员函数 insert() 可以插入作为参数传入的单个元素。
            //在这种情况下，它会返回一个 pair 对象，
            //这个 pair 对象包含一个迭代器，以及一个附加的布尔值用来说明插入是否成功。
            //如果元素被插入，返回的迭代器会指向新元素；如果没有被插入，迭代器指向阻止插入的元素。
            //初始count = 0，若插入成功，则数量加一，若不成功，则已有的那个balloon数量加一
            auto x = balloons.insert(balloon(temp));
            x.first->count += 1;
        }
        unordered_set<balloon,balloon_hash>::iterator iter = balloons.begin();
        while(iter != balloons.end()){
            if(iter->count > maxCount){
                maxCount = iter->count;
                maxString = iter->color;
            }
            iter++;
        }
        print(maxString);
    }
    return 0;
}

2.3 代码使用案例 ：

• 案例1

#include <iostream>
#include <unordered_set>
#include <array>
#include <string>
using namespace std;

int main()
{
	unordered_set<string> myset1 = { "yellow", "green", "blue" };
	array<string, 2> myarray = { "black", "white" };
	string mystring = "red";

	myset1.insert(mystring);                        // copy insertion
	myset1.insert(mystring + "dish");                 // move insertion
	myset1.insert(myarray.begin(), myarray.end());  // range insertion
	myset1.insert({ "black", "white" });           // initializer list insertion


	unordered_set<std::string> myset2 =
	{ "USA", "Canada", "France", "UK", "Japan", "Germany", "Italy" };

	myset2.erase(myset2.begin());                    // erasing by iterator
	myset2.erase("France");                         // erasing by key
	myset2.erase(myset2.find("Japan"), myset2.end()); // erasing by range
	
	//capacity
	cout << myset1.size() << endl;
	cout << myset2.size() << endl;
	cout << myset1.empty() << endl;
	cout << myset2.empty() << endl;

	myset1.clear();
	myset2.clear();

	cout << myset1.size() << endl;
	cout << myset2.size() << endl;
	cout << myset1.empty() << endl;
	cout << myset2.empty() << endl;

	system("pause");
	return 0;
}

• 案例2

#include <iostream>
#include <unordered_set>
using namespace std;


namespace wzj001{
    void coutUnorderedSet(std::unordered_set<int>& m, string funcName) {
        std::unordered_set<int>::iterator it;
        std::cout << funcName << ": ";
        for ( it = m.begin(); it != m.end(); it++ )
            std::cout << *it << " ";
        std::cout << std::endl;
    }
    
    void initUnorderSet(unordered_set<int>& tmp)
    {
        for(int i = 0; i < 10; i++)
            tmp.insert(i);
    }
    
    string turnBoolToString(bool tmp)
    {
        return tmp ? "true" : "false";
    }
    
    void basicOperationUnorderedSet()
    {
        //定义
        std::unordered_set<int> c;
        // 普通插入,返回pair<迭代器,插入是否成功>
        pair<unordered_set<int>::iterator, bool> c_insert = c.insert(1);
        cout << "指向key的迭代器: " << *c_insert.first  << "   插入是否成功 "<< turnBoolToString(c_insert.second)<<endl;
        pair<unordered_set<int>::iterator, bool> c_insert2 = c.insert(2);
        cout << "指向key的迭代器: " << *c_insert2.first << "   插入是否成功 "<< turnBoolToString(c_insert2.second)<<endl;
        pair<unordered_set<int>::iterator, bool> c_insert3 = c.insert(1);
        cout << "指向key的迭代器: " << *c_insert3.first << "   插入是否成功 "<< turnBoolToString(c_insert3.second)<<endl;
        
        //按指定区域插入
        std::unordered_set<int> c_insert_region;
        c_insert_region.insert(c.begin(), c.end());
        coutUnorderedSet(c_insert_region, "按指定区域插入");
        
        //构造插入
        std::unordered_set<int> c_emplace;
        c_emplace.emplace(1);
        c_emplace.emplace(2);
        c_emplace.emplace(3);
        coutUnorderedSet(c_emplace, "构造插入");
        
        //迭代器插入
        std::unordered_set<int> c_emplace_hint;
        c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 1);
        c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 2);
        c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 3);
        coutUnorderedSet(c_emplace_hint, "迭代器插入");
        
        //删除
        std::unordered_set<int> c_erase;
        initUnorderSet(c_erase);
        coutUnorderedSet(c_erase, "初始化c_erase");
        //指定位置删除
        c_erase.erase(c_erase.begin());
        coutUnorderedSet(c_erase, "指定位置删除");
        
        //指定key删除
        c_erase.erase(8);
        coutUnorderedSet(c_erase, "指定key删除");
        
        //指定区域删除
        c_erase.erase(c_erase.begin(), c_erase.end());
        coutUnorderedSet(c_erase, "指定区域删除");
        
        //交换
        c.swap(c_emplace);
        coutUnorderedSet(c, "交换");
        
    }
    
    void unorderSetElementLookup()
    {
        //查找
        std::unordered_set<int> c_find;
        initUnorderSet(c_find);
        std::unordered_set<int>::iterator find_iter = c_find.find(10);
        if(find_iter != c_find.end())
        {
            cout<< "找到元素 : "<< *find_iter << endl;
        }
        else
            cout<< "没找到 !"<< endl;
        
        cout << "value出现次数 :" <<c_find.count(1)<< endl; //set key不可重复
        
        pair<std::unordered_set<int>::iterator, std::unordered_set<int>::iterator> tmp = c_find.equal_range(5);
        
        if(tmp.first != c_find.end()&& tmp.second != c_find.end())
        {
            cout << "该值所在区间为[" << *tmp.first << "," << *tmp.second << "]" << endl;
        }
    }
    
    void unorderSetBuckets()
    {
        //篮子操作
        std::unordered_set<int> c_buckets;
        initUnorderSet(c_buckets);
        cout << "篮子个数: "    << c_buckets.bucket_count()<< endl;
        cout << "篮子大小: " << c_buckets.bucket_size(1) << endl;
        cout << "最大篮子个数: " << c_buckets.max_bucket_count() << endl;
        cout << "该值所在篮子序号: " << c_buckets.bucket(3) << endl;
    }
    
    void unorderSetHashPolicy()
    {
        std::unordered_set<int> c_;
        cout << "负载: "<< c_.load_factor()<< endl;
        initUnorderSet(c_);
        cout << "负载: "<< c_.load_factor()<< endl;//使用的篮子数/篮子总数  默认的篮子数为11
        cout << "最大负载: "<< c_.max_load_factor() << endl;
        c_.reserve(100);//预设篮子数 ,但是还没有设定
        c_.rehash(3);//设定篮子数
    }
    
    void unorderSetObservers()
    {
        std::unordered_set<int> c_;
        initUnorderSet(c_);
        std::unordered_set<int>::hasher xxx = c_.hash_function();
        std::unordered_set<int>::key_equal zzz = c_.key_eq();
        cout << "hash_func: " << xxx(11111) << endl;
        cout << "key_eq: " << turnBoolToString(zzz(11111,11111)) << endl;
    }
}


int main()
{
    wzj001::basicOperationUnorderedSet();
    wzj001::unorderSetElementLookup();
    wzj001::unorderSetBuckets();
    wzj001::unorderSetHashPolicy();
    wzj001::unorderSetObservers();
}