• 【C++】-- STL之unordered_map/unordered_set详解

    目录

    一、map/set和unordered_map/unordered_set的区别

    二、unordered_set

    1.特点 

    2.构造

    （1）构造一个空的 unordered_set对象

    （2） 用迭代器范围构造unordered_set对象

    （3） 拷贝构造一个unordered_set对象

    3.容量

    （1）empty( )

    （2）size( ) 

    （3）max_size( ) 

    4.迭代器

    （1）begin( )

    （2）end( )

    5.查找

    （1）find( )

    （2）count( ) 

    6.元素修改

    （1）insert( )

    （2）erase( )

    （3）clear( )

    （4）swap( )

    三、 unordered_map

    1.特点 

    2.构造  

    （1）构造一个空的unordered_map对象

    （2）用迭代器范围构造unordered_set对象

    （3）拷贝构造一个unordered_set对象

    3.容量

    （1）empty( )

    （2）size( )

    （3）max_size( )

    4.迭代器

    （1）begin( )

    （2）end( ) 

    5.元素操作符[ ]

    6.查找

    （1）find( ) 

    （2）count( )

    7.元素修改

    （1）insert( )

    （2）erase( )

    （3）clear( )

    （4）swap( )

    一、map/set和unordered_map/unordered_set的区别

    STL有两种容器:序列式容器和关联式容器，序列式容器vetor/lost/deque，用来存储数据。关联式容器map/set/unordered_map/unordered_set用来存储数据+查找数据。

    unordered_map和unordered_set是c++里面两个提供哈希表的容器，map和set底层是红黑树，unordered_map和unordered_set的底层是哈希表（散列表），是一种映射。

    对于set和unordered_set的增删查，在10000个数据、100000个数据、1000000个数据的情况下分别作了对比：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. void test_unordered_set()
    9. {
    10. 	vector<int> v;
    11. 	v.reserve(10000);//100000、1000000
    12. 	srand((unsigned int)time(NULL));
    13.  
    14. 	for (int i = 0; i < 10000; i++)//100000、1000000
    15. 	{
    16. 		v.push_back(rand());
    17. 	}
    18.  
    19. 	//插入
    20. 	set<int> s;
    21. 	size_t begin1 = clock();
    22. 	for (auto e : v)
    23. 	{
    24. 		s.insert(e);
    25. 	}
    26. 	size_t end1 = clock();
    27.  
    28. 	unordered_set<int> us;
    29. 	size_t begin2 = clock();
    30. 	for (auto e : v)
    31. 	{
    32. 		us.insert(e);
    33. 	}
    34. 	size_t end2 = clock();
    35.  
    36. 	cout << "set insert time：" << end1 - begin1 << endl;
    37. 	cout << "unorder_set insert time：" << end2 - begin2 << endl;
    38.  
    39. 	//查找
    40. 	size_t begin3 = clock();
    41. 	for (auto e : v)
    42. 	{
    43. 		s.find(e);//set自带的查找效率是O(logn)
    44. 	}
    45. 	size_t end3 = clock();
    46.  
    47. 	size_t begin4 = clock();
    48. 	for (auto e : v)
    49. 	{
    50. 		us.find(e); //unordered_set自带的查找，优点：使用哈希特性查找，效率高--O(1)
    51. 	}
    52. 	size_t end4 = clock();
    53.  
    54. 	cout << "set find time：" << end3 - begin3 << endl;
    55. 	cout << "unorder_set find time：" << end4 - begin4 << endl;
    56.  
    57. 	//删除
    58. 	size_t begin5 = clock();
    59. 	for (auto e : v)
    60. 	{
    61. 		s.erase(e);
    62. 	}
    63. 	size_t end5 = clock();
    64.  
    65. 	size_t begin6 = clock();
    66. 	for (auto e : v)
    67. 	{
    68. 		us.erase(e);
    69. 	}
    70. 	size_t end6 = clock();
    71.  
    72. 	cout << "set erase time：" << end5 - begin5 << endl;
    73. 	cout << "unorder_set erase time：" << end6 - begin6 << endl;
    74. }
    75.  
    76. int main()
    77. {
    78.  
    79. 	test_unordered_set();
    80.  
    81. 	return 0;
    82. }

    10000个数据的时间：

    100000个数据的时间：

     

     1000000个数据的时间：

     

     可以看到，当数据量越大时，unordered_set相比于set所消耗的时间越少，这是因为unordered_set的底层是哈希表，增删查的效率更高。

    二、 unordered_set

    1.特点 

    （1） unordered_map是存储键值对的关联式容器，对value进行快速索引。
    （2）在unordered_set中，元素的值同时是其键，是唯一标识，键和映射值的类型相同，键不可修改。unordered_set中的元素在容器不可修改，但是可以插入和删除元素。
    （3）unordered_set中的元素不按任何特定顺序排序，而是根据其哈希值组织到存储桶中，允许直接根据value快速访问各个元素（平均时间复杂度是一定的）。
    （4）unordered_set比set通过键访问单个元素的速度更快，但它通常在遍历元素子集的范围迭代方面效率较低。
    （5）容器中的迭代器至少有正向迭代器。

    2.构造

     有以下几种构造方式：

    1. explicit unordered_set ( size_type n = /* see below */,
    2.                          const hasher& hf = hasher(),
    3.                          const key_equal& eql = key_equal(),
    4.                          const allocator_type& alloc = allocator_type() );//构造空的unordered_set对象
    5.  
    6. template <class InputIterator>
    7.          unordered_set ( InputIterator first, InputIterator last,
    8.                          size_type n = /* see below */,
    9.                          const hasher& hf = hasher(),
    10.                          const key_equal& eql = key_equal(),
    11.                          const allocator_type& alloc = allocator_type() );//用迭代器范围构造unordered_set对象
    12.  
    13. unordered_set ( const unordered_set& ust );//拷贝构造一个unordered_set对象

    （1）构造一个空的 unordered_set对象

        unordered_set<int> us1;

    向里面插入元素：

    1. 	us1.insert(2);
    2. 	us1.insert(72);
    3. 	us1.insert(6);
    4. 	us1.insert(35);
    5. 	us1.insert(291);
    6. 	us1.insert(327);

    （2） 用迭代器范围构造unordered_set对象

    用us1的迭代器范围构造us2： 

        unordered_set<int> us2(us1.begin(), us1.end());

    （3） 拷贝构造一个unordered_set对象

     用us2拷贝构造us3：

        unordered_set<int> us3(us2);

    3.容量

    （1）empty( )

    判断unordered_set是否为空：

    cout << us3.max_size() << endl;

    判断us3是否为空： 

        cout << us3.empty() << endl;//判断us3是否为空

     不为空：

    （2）size( ) 

    返回unordered_set中的元素个数

    size_type size() const noexcept;

     求us3中的元素个数：

        cout << us3.size() << endl;

     

    （3）max_size( ) 

    返回unordered_set可存储的最大元素个数：

    size_type max_size() const noexcept;

    求us3最大元素个数 ：

        cout << us3.max_size() << endl;

     

     

    4.迭代器

    （1）begin( )

    返回迭代器开始： 

    iterator begin() noexcept;

     返回us3迭代器开始：

        unordered_set<int>::iterator it = us3.begin();

    （2）end( )

    返回迭代器结尾：

    iterator end() noexcept;

    返回us3迭代器结尾： 

        us3.end();

     

    5.查找

    （1）find( )

    如果找到元素就返回元素所在位置，否则返回元素结尾：

    iterator find ( const key_type& k );

    在us3中查找327： 

    1. 	unordered_set<int>::iterator ret = us3.find(327);
    2. 	if (ret != us3.end())
    3. 	{
    4. 		cout << "找到了" << endl;
    5. 	}
    6. 	else
    7. 	{
    8. 		cout << "没找到" << endl;
    9. 	}

     

    （2）count( ) 

     统计容器中值为k的元素的个数：

    size_type count ( const key_type& k ) const;

     统计us3中值为291的元素的个数：

        cout << us3.count(291) << endl;

     

     

    6.元素修改

    （1）insert( )

    1. pairbool> insert ( const value_type& val );//插入元素，成功返回的pair的第二个元素为true，失败则为false
    2. iterator insert ( const_iterator hint, const value_type& val );//返回插入元素的位置
    3. template <class InputIterator>
    4.     void insert ( InputIterator first, InputIterator last );//插入一段区间
    5. void insert ( initializer_list il );//将列表作为元素插入容器中

    ①插入元素 

    1. 	cout << us2.insert(568).second << endl;//不存在，插入成功
    2. 	cout << us2.insert(291).second << endl;//已存在，插入失败

     

     

     ②返回插入元素的位置

        cout << *us2.insert(us3.begin(), 65) << endl;

     

    ③ 插入一段区间

    1.     unordered_set<int> us2;
    2. 	us2.insert(us1.begin(), us1.end());
    3. 	unordered_set<int>::iterator it = us2.begin();
    4. 	while (it != us2.end())
    5. 	{
    6. 		cout << *it << " ";
    7. 		it++;
    8. 	}
    9. 	cout << endl;

     

     

    ④将列表作为元素插入容器中

    1. 	unordered_set us4;
    2. 	us4.insert({ "int", "string", "float" });
    3. 	unordered_set::iterator it = us4.begin();
    4. 	while (it != us4.end())
    5. 	{
    6. 		cout << *it << " ";
    7. 		it++;
    8. 	}
    9. 	cout << endl;

     

    （2）erase( )

     删除元素：

    1. iterator erase ( const_iterator position );//删除position位置的元素，并返回删除元素的位置
    2. size_type erase ( const key_type& k );//返回删除值为k的元素的个数
    3. iterator erase ( const_iterator first, const_iterator last );//删除从first到last区间的元素，并返回删除的last元素的位置

     ①删除position位置的元素，并返回删除元素的位置

    1. 	unordered_set<int> us2;
    2. 	us2.insert(us1.begin(), us1.end());
    3. 	cout << *us2.erase(us2.find(6)) << endl;

     

    ② 删除值为k的元素的，k存在返回1，k不存在返回0

        cout << us2.erase(72) << endl;

    ③ 删除从first到last区间的元素，并返回删除的last元素的位置

        cout << *us2.erase(us2.find(6), us2.find(291)) << endl;

     

    （3）clear( )

     删除容器中所有元素

    void clear() noexcept;

     清空us2中所有元素：

        us2.clear();

    （4）swap( )

     交换两个同类型容器中的元素

    1. unordered_set<int> us1;
    2. 	us1.insert(2);
    3. 	us1.insert(72);
    4. 	us1.insert(6);
    5. 	us1.insert(35);
    6. 	us1.insert(291);
    7. 	us1.insert(327);
    8.  
    9. 	unordered_set<int> us5;
    10. 	us5.insert(56);
    11. 	us5.insert(57);
    12. 	us5.insert(58);
    13. 	us5.insert(59);
    14. 	us5.insert(60);
    15. 	us5.insert(61);
    16.  
    17. 	us1.swap(us5);
    18. 	
    19. 	unordered_set<int>::iterator it1 = us1.begin();
    20. 	while (it1 != us1.end())
    21. 	{
    22. 		cout << *it1 << " ";
    23. 		it1++;
    24. 	}
    25. 	cout << endl;
    26.  
    27. 	unordered_set<int>::iterator it5 = us5.begin();
    28. 	while (it5 != us5.end())
    29. 	{
    30. 		cout << *it5 << " ";
    31. 		it5++;
    32. 	}
    33. 	cout << endl;

     

    哈系桶和哈希策略的函数等介绍完哈希表之后才能理解。

    三、 unordered_map

    1.特点 

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

    2.构造  

    1. explicit unordered_map ( size_type n = /* see below */,
    2.                          const hasher& hf = hasher(),
    3.                          const key_equal& eql = key_equal(),
    4.                          const allocator_type& alloc = allocator_type() );//构造空的unordered_map对象
    5.  
    6. template <class InputIterator>
    7.   unordered_map ( InputIterator first, InputIterator last,
    8.                   size_type n = /* see below */,
    9.                   const hasher& hf = hasher(),
    10.                   const key_equal& eql = key_equal(),
    11.                   const allocator_type& alloc = allocator_type() );//用迭代器范围构造unordered_map对象
    12.  
    13. unordered_map ( const unordered_map& ump );//拷贝构造一个unordered_map对象

    （1）构造一个空的unordered_map对象

        unordered_mapint> um1;

    向里面插入元素：

    1.     um1.insert(make_pairint>("自行车", 8));
    2. 	um1.insert(make_pairint>("消防车", 1));
    3. 	um1.insert(make_pairint>("洒水车", 6));
    4. 	um1.insert(make_pairint>("搅拌车", 7));
    5. 	um1.insert(make_pairint>("小汽车", 5));

    （2）用迭代器范围构造unordered_set对象

    用um1的迭代器范围构造um2:

        unordered_mapint> um2(um1.begin(), um1.end());

    （3）拷贝构造一个unordered_set对象

    用um2拷贝构造um3：

        unordered_mapint> um3(um2);

    3.容量

    （1）empty( )

    判断unordered_map是否为空： 

    bool empty() const noexcept;

     判断um1是否为空： 

        cout << um1.empty() << endl;

     

    （2）size( )

     返回unordered_map中的元素个数：

    size_type size() const noexcept;

    求um1中元素的个数：

        cout << um1.size() << endl;

     

    （3）max_size( )

    返回 unordered_map可存储的最大元素个数：

    size_type max_size() const noexcept;

    求um1最大元素个数 ： 

        cout << um1.max_size() << endl;

     

     

    4.迭代器

    （1）begin( )

    返回迭代器开始： 

    iterator begin() noexcept;

     返回um1迭代器开始：

        unordered_mapint>::iterator it = um1.begin();

    （2）end( ) 

    返回迭代器结尾：

    iterator end() noexcept;

     返回um1迭代器结尾：

        um1.end();

    5.元素操作符[ ]

    访问key为k的元素，如果存在就返回value的引用： 

    mapped_type& operator[] ( const key_type& k );

     访问key为小汽车的元素，并返回小汽车对应的value的引用：

        cout << um1["小汽车"] << endl;

     

     

    6.查找

    （1）find( ) 

    根据k返回k所在位置的迭代器，如果没找到就返回end

    iterator find ( const key_type& k );

     查找洒水车：

        cout << um1.find("洒水车")->second << endl;

    （2）count( )

     统计容器中key为k的元素的个数：

    size_type count ( const key_type& k ) const;

     统计um1中key为"搅拌车"的元素个数：

        cout << um1.count("搅拌车") << endl;

     

    7.元素修改

    （1）insert( )

    1. pairbool> insert ( const value_type& val );//插入元素，成功返回的pair的第二个元素为true，失败则为false
    2. iterator insert ( const_iterator hint, const value_type& val );//返回插入元素的位置
    3. template <class InputIterator>
    4.     void insert ( InputIterator first, InputIterator last );//插入一段区间
    5. void insert ( initializer_list il );//将列表作为元素插入容器中

     ①插入元素

    1. 	cout << um1.insert(make_pairint>("大货车", 9)).second << endl;//不存在，插入成功
    2. 	cout << um1.insert(make_pairint>("搅拌车", 1)).second << endl;//已存在，插入失败

     

      ②返回插入元素的位置

        cout << um1.insert(um1.begin(), make_pairint>("扫地车", 10))->second << endl;

     

    ③ 插入一段区间 

    1.     unordered_mapint> um2(um1.begin(), um1.end());
    2. 	unordered_mapint>::iterator it2 = um2.begin();
    3.  
    4. 	while (it2 != um2.end())
    5. 	{
    6. 		cout << it2->first << ":" << it2->second << endl;
    7. 		it2++;
    8. 	}
    9. 	cout << endl;

     ④将列表作为元素插入容器中

    1.     unordered_mapint> um3;    
    2.     um3.insert({ { "摩托车",3 }, { "电动车",7 }});
    3. 	unordered_mapint>::iterator it3 = um3.begin();
    4. 	while (it3 != um3.end())
    5. 	{
    6. 		cout << it3->first << ":" << it3->second << endl;
    7. 		it3++;
    8. 	}
    9. 	cout << endl;

     

     

    （2）erase( )

      删除元素：

    1. iterator erase ( const_iterator position );//删除position位置的元素，并返回删除元素的位置
    2. size_type erase ( const key_type& k );//返回删除值为k的元素的个数
    3. iterator erase ( const_iterator first, const_iterator last );//删除从first到last区间的元素，并返回删除的last元素的位置

     ①删除position位置的元素，并返回删除元素的位置

    删除搅拌车： 

        cout << um1.erase(um1.find("搅拌车"))->first << endl;

     

    ② 删除值为k的元素的，k存在返回1，k不存在返回0：

        cout << um1.erase("自行车") << endl;

     

    ③ 删除从first到last区间的元素，并返回删除的last元素的位置 

     

        cout << um1.erase(um1.find("消防车"), um1.find("扫地车"))->first << endl;

     

    （3）clear( )

    清空所有元素： 

    void clear() noexcept;

     清空um1中所有元素：

        um1.clear();

    （4）swap( )

    交换两个同类型容器中的元素：

    1. 	unordered_map um4;
    2. 	um4.insert(make_pair("spring", "春天"));
    3. 	um4.insert(make_pair("summer", "夏天"));
    4. 	um4.insert(make_pair("autumn", "秋天"));
    5. 	um4.insert(make_pair("winter", "冬天"));
    6.  
    7. 	unordered_map um5;
    8. 	um5.insert(make_pair("east", "东"));
    9. 	um5.insert(make_pair("south", "南"));
    10. 	um5.insert(make_pair("west", "西"));
    11. 	um5.insert(make_pair("north", "北"));
    12.  
    13. 	um4.swap(um5);
    14.  
    15. 	unordered_map::iterator it4 = um4.begin();
    16. 	while (it4 != um4.end())
    17. 	{
    18. 		cout << it4->first << ":" << it4->second << endl;
    19. 		it4++;
    20. 	}
    21. 	cout << endl;
    22.  
    23. 	unordered_map::iterator it5 = um5.begin();
    24. 	while (it5 != um5.end())
    25. 	{
    26. 		cout << it5->first << ":" << it5->second << endl;
    27. 		it5++;
    28. 	}
    29. 	cout << endl;

     

     

     系桶和哈希策略的函数等介绍完哈希表之后才能理解。

  • 相关阅读:
    agileBPM 广州宏天BPM功能对比
    Django思维导图-视图
    Nginx一网打尽：动静分离、压缩、缓存、黑白名单、跨域、高可用、性能优化...想要的这都有！
    python计算机毕业设计之基于django的在线学习系统 elementui
    #力扣：1684. 统计一致字符串的数目@FDDLC
    Python复习（持续更新）
    Vue中双向绑定数据详解
    直流有刷电机驱动基于STM32F302R8+X-NUCLEO-IHM07M1（一）
    SMB over QUIC帮助实现文件服务器在公网安全共享
    【java】【SpringBoot】【四】原理篇 bean、starter、核心原理
  • 原文地址：https://blog.csdn.net/gx714433461/article/details/126768864