目录

unordered系列关联式容器

一、unordered_set

1. unordered_set的介绍

2. unordered_set的使用

3. unordered_set/unordered_multiset底层结构

二、unordered_map

1. unordered_map的介绍

2. unordered_map的使用

3. unordered_map/unordered_multimap底层结构

unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到

logN，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。unordered系列的底层结构是哈希表。

一、unordered_set

1. unordered_set的介绍

1. 
   
   unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。
   
   
2. 
   
   在unordered_set中，元素的值同时也是唯一地标识它的key。
   
   
3. 
   
   在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。
   
   
4. 
   
   unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。
   
   
5. 
   
   它的迭代器是单向迭代器。
   
   

2. unordered_set的使用

常用接口的介绍

迭代器的介绍

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

int main()
{
    unordered_set<int> us; //构造
    /****************插入操作*********************/
    //插入指定的元素（只有去重的功能，没有排序的功能）
    us.insert(7);
    us.insert(1);
    us.insert(1);
    us.insert(2);
    us.insert(6);
    us.insert(5);
    unordered_set<int> us1(us);//拷贝构造
    unordered_set<int> us2(us1.begin(), us1.end());//迭代器区间构造
    /****************遍历操作*********************/
    //遍历方式1 --- 范围for遍历
    for(auto e : us)
    {
        cout << e << " ";
    }
    cout << endl; // 打印结果：5 6 2 1 7（其结果不一定是按照插入的顺序打印的）

    //遍历方式2 --- 迭代器遍历
    unordered_set<int>::iterator it1 = us.begin();
    //auto it2 = us.begin(); //可以使用auto自动推到类型
    while(it1 != us.end())
    {
        cout << *it1 << " ";
        it1++;
    }
    cout << endl;// 打印结果：5 6 2 1 7
    /****************删除操作*********************/
    //删除方式1 --- 指定元素删除
    us.erase(5);
    //删除方式2 --- 通过find函数找到指定的元素删除
    unordered_set<int>::iterator pos1 = us.find(6);//查找元素6，并返回该迭代器
    //auto pos2 = us.find(6);//可以使用auto自动推到类型
    if(pos1 != us.end())
    {
        us.erase(6);
    }
    /****************其他操作*********************/
    cout << us.size() << endl; //容器中的元素个数
    cout << us.count(7) << endl;//容器中元素7的个数
    cout << us.empty() << endl; //判断容器是否为空
    us.clear();//清空容器
    return 0;
}

unordered_multiset容器与unordered_set容器的底层数据结构是一样的，都是哈希表，其次，它们所提供的成员函数的接口都是基本一致的，这里就不再列举了，这两种容器唯一的区别就是，unordered_multiset容器允许键值冗余，即unordered_multiset容器当中存储的元素是可以重复的。

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

int main()
{
    unordered_multiset<int> ums; 
    //插入指定的元素（允许元素重复）
    ums.insert(7);
    ums.insert(1);
    ums.insert(1);
    ums.insert(2);
    ums.insert(6);
    ums.insert(5);
    for(auto e : ums)
    {
        cout << e << " ";
    }
    cout << endl;// 5 6 2 1 1 7
    return 0;
}

由于unordered_multiset容器允许键值冗余，因此该容器中成员函数find和count的意义与unordered_set容器中的也有所不同：

3. unordered_set/unordered_multiset底层结构

底层结构会在后续博客中模拟实现，这里只需要大概了解即可。

二、unordered_map

1.




unordered_map的介绍

1. 
   
   unordered_map是存储<key, value>键值对的关联式容器，其允许通过keys快速的索引到与其对应的
   
   
   
   
   value。
   
   
2. 
   
   在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键
   
   
   
   
   和映射值的类型可能不同。
   
   
3. 
   
   在内部,unordered_map没有对<kye, value>按照任何特定的顺序排序, 为了能在常数范围内找到key所
   
   
   
   
   对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
   
   
4. 
   
   unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率
   
   
   
   
   较低。
   
   
5. 
   
   unordered_maps实现了直接访问操作符(operator[ ])，它允许使用key作为参数直接访问value。
   
   
6. 
   
   它的迭代器是单向迭代器。
   
   

2. unordered_map的




使用

常用接口的介绍

迭代器的介绍

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main()
{
    unordered_map<string, string> um;//构造
    /**********************插入操作****************************/
    //插入方式1 --- 通过匿名对象插入
    um.insert(pair<string, string>("left", "左边"));
    um.insert(pair<string, string>("right", "右边"));
    //插入方式2 --- 通过make_pair函数模板插入
    um.insert(make_pair("boy", "男孩"));
    um.insert(make_pair("girl", "女孩"));
    //插入方式3 --- 通过operator[]插入(常用)
    um["top"] = "顶部";
    um["bottom"] = "底部";
    um["map"] = "地图";
    unordered_map<string, string> um1(um); //拷贝构造
    unordered_map<string, string> um2(um1.begin(), um1.end());//迭代器区间构造

    /**********************遍历操作****************************/
    //遍历操作1 --- 范围for遍历
    for(auto e : um)
    {
        cout << e.first << "-->" << e.second << " ";
    }
    cout << endl;
    //遍历操作2 --- 迭代器遍历
    unordered_map<string, string>::iterator it1 = um.begin();
    //auto it2 = um.begin(); //自动推导
    while(it1 != um.end())
    {
        cout << it1->first << "-->" << it1->second << " ";
        //cout << (*it1).first << "-->" << (*it1).second << " "; //也可以通过解引用拿到pair对象，找到first和second
        it1++;
    }
    /**********************删除操作****************************/
    //删除方式1 --- 根据key删除
    um.erase("left");
    //删除方式2 --- 根据迭代器删除
    unordered_map<string, string>::iterator pos = um.find("right");
    if(pos != um.end())
    {
        um.erase(pos);
    }
    /**********************修改操作****************************/
    //修改操作1 --- 通过find函数获取对应的迭代器，进行修改
    pos = um.find("map");
    if(pos != um.end())
    {
        pos->second = "映射";
    }
    //修改操作2 --- 通过operator[]进行修改（常用）
    um["map"] = "地图、映射";
    /**********************其他操作****************************/
    cout << um.size() << endl; //容器的元素个数
    cout << um.count("map") << endl;//返回对应key值的个数
    cout << um.empty() << endl; //判断容器是否为空
    um.clear();//清空容器
    return 0;
}

unordered_multimap容器与unordered_map容器的底层数据结构是一样的，都是哈希表，其次，它们所提供的成员函数的接口都是基本一致的，这里就不再列举了，这两种容器唯一的区别就是，unordered_multimap容器允许键值冗余，即unordered_multimap容器当中存储的键值对的key值是可以重复的。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    unordered_multimap<string, string> umm;
    //插入键值对（允许键值重复）
    umm.insert(make_pair("map", "地图"));
    umm.insert(make_pair("map", "分布图"));
    umm.insert(make_pair("map", "映射"));
    for (auto e : umm)
    {
        cout << e.first << "->" << e.second << " ";
    }
    cout << endl; 
    return 0;
}

由于unordered_multimap容器允许键值对的键值冗余，因此该容器中成员函数find和count的意义与unordered_map容器中的也有所不同：

注：unordered_multi




map不支持operator[ ]。

3. unordered_map/unordered_multimap底层结构

底层结构会在后续博客中模拟实现，这里只需要大概了解即可。