empty()：检查集合是否为空

发布时间：2025-06-24 20:31:13  作者：北方职教升学中心  阅读量：959


哈希表的查找效率通常是常数时间复杂度 O(1)，但最坏情况下是 O(n)。插入的元素是唯一的，如果尝试插入重复元素，unordered_set会忽略它。

  • unordered_set底层是使用哈希桶实现的，查找的效率为O(1)；但是数据不再有序，所以取名为unordered_set。它们与 set和 map的主要区别在于，它们使用 哈希表作为底层数据结构，因此它们的元素并不是按照某种顺序存储的，而是根据元素的哈希值存储。

    3. unordered_map的基本用法

    unordered_map是一个哈希表实现的键值对容器，类似于 map，但是它的元素不按键排序。

    • 4. 性能分析

    这一部分，我们要学习底层哈希表以后才会深入理解；这里简单说一下

    底层的哈希表使用的是哈希桶结构（就是顺序表中存储链表，这样可以避免冲突的问题）。

    2.3 unordered_set和set的区别

    通过查看文档已经使用unoedered_set，我们可以发现unordered_set和set支持的增删查改是一模一样的，我们现在就来看一下它们有什么不同：

    • 首先set的底层是红黑树，而unordered_set底层是哈希表。常用操作包括插入元素、
    • erase()：删除指定键值对。
    • unordered_set底层存储数据的内存都是从空间适配器中申请的，如果自己有需求实现内存池，要传给第四个模版参数
    • 一般我们在使用的时候不需要传后三个模版参数。
    • 其次它们对于key的要求不同，set要求key支持比较；而unoedered_set要求key支持转化成整型且要支持比较。

    这里对于其他的函数，就需要去了解它底层的哈希桶结构了，在实现哈希结构时再去深入探究。插入和删除操作平均时间复杂度为 O(1)。

    6. unordered_multimap和unordered_multiset

    • unordered_multimap/unordered_multiset和multimap/multiset功能完全类似，支持key冗余

    这里就不过多描述了，有需要了解的可以参考一下之前的文章讲解：

    【map与set】—— 我与C++的不解之缘（二十二）

    到这里本篇文章内容就结束了，感谢各位的支持！！！

    我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

  • find()：用于查找元素。

    3.1 基本操作

    #include<iostream>#include<unordered_map>usingnamespacestd;voidtest_unordered_map(){//创建一个 unordered_mapunordered_map<string,int>umap;//和map的operator[]一样，可以用来插入数据umap["apple"]=2;umap["banana"]=5;umap["orange"]=3;//输出cout <<"unordered_map contains:"<<endl;for(constauto&pair :umap){cout <<pair.first <<": "<<pair.second <<endl;}//查找autoit =umap.find("banana");if(it !=umap.end())cout <<"Found 'banana' with value "<<it->second <<endl;elsecout <<"'banana' not found in the unordered_map!"<<endl;//删除umap.erase("orange");cout <<"After erasing 'orange', unordered_map contains:"<<endl;for(constauto&pair :umap)cout <<pair.first <<": "<<pair.second <<endl;// 检查是否存在某个keyif(umap.count("apple")>0)std::cout <<"'apple' exists in the unordered_map."<<std::endl;}intmain(){test_unordered_map();return0;}

    运行结果：

    unordered_map contains:apple: 2banana: 5orange: 3Found 'banana' with value 5After erasing 'orange', unordered_map contains:apple: 2banana: 5"apple" exists in the unordered_map.

    3.2 解释

    • 插入元素：unordered_map支持通过下标（[]）或者 insert()插入元素。删除元素、
    • erase()：用于删除指定元素。
    • 其次它们对于key的要求不同，map要求key支持比较；而unoedered_map要求key支持转化成整型且要支持比较。查找元素等。

    2.1 基本操作

    #include<iostream>#include<unordered_set>usingnamespacestd;voidtest_unordered_set(){// 创建一个 unordered_setunordered_set<int>uset;// 插入元素uset.insert(10);uset.insert(20);uset.insert(30);uset.insert(40);// 输出所有元素cout <<"unordered_set contains: ";for(constauto&e :uset){cout <<e <<" ";}cout <<endl;// 查找if(uset.find(20)!=uset.end())cout <<"Found 20 in the unordered_set!"<<endl;elsecout <<"20 not found in the unordered_set!"<<endl;// 删除元素uset.erase(30);cout <<"After erasing 30, unordered_set contains: ";for(constauto&e :uset)cout <<e <<" ";cout <<endl;// 判断是否为空if(uset.empty())cout <<"The unordered_set is empty."<<endl;elsecout <<"The unordered_set is not empty."<<endl;}intmain(){test_unordered_set();return0;}

    运行结果：

    unordered_set contains: 10 20 30 40Found 20 in the unordered_set!After erasing 30, unordered_set contains: 10 20 40The unordered_set is not empty.

    2.2 解释

    • insert()：向 unordered_set中插入元素。
    • 最后就是性能上的差异，对于大多数场景下unoedered_set增删查改的效率要高于set的；（红黑树的效率是O(log N)，哈希表的效率是O(1)。

      • unordered_set声明如下，Key就是unordered_set底层关键字的类型
      • unordered_set默认要求Key可以转化为整形，如果不支持或者有自己的需求的需要自己实现仿函数(将Key转化为整形)传给第二个模版参数。
      • count()：检查容器中是否存在指定的键。

        unordered_map和unordered_set都是用哈希表进行封装实现的，这里就不过多描述了，和unordered_set十分相似。

      至于其中细节上的不同，要了解了unordered_set的底层哈希表，才能真正理解。不过，由于哈希冲突的存在，最坏情况下时间复杂度会退化为 O(n)，即所有元素都映射到同一个哈希桶中。

      unordered_set和 unordered_map的查找、

    • 然后就是迭代器的不同，set的iterator是双向迭代器，而unordered_set的iterator是单向迭代器；set底层是红黑树，set的迭代器是有序+去重的；而unoedered_set底层是哈希桶，unoedered_set是无序+去重的。

      1. unordered_set和 unordered_map简介

      在 C++ 标准库中，unordered_set和 unordered_map都属于 无序关联容器。

      unordered_map和map的区别与unordered_set和set的区别是大差不差的。

    更多详细内容可以参考文档：unordered_set 和 unordered_map

    2. unordered_set的基本用法

    unordered_set是一个存储唯一元素的集合，其中元素按哈希值进行存储。如果找到，返回指向该元素的迭代器；否则返回 end()。

    • 哈希冲突：为了减少哈希冲突，C++ 中的 unordered_set和 unordered_map使用了哈希表和动态扩展机制，使得哈希表的负载因子保持在合理范围内，避免性能急剧下降。

      • 首先map的底层是红黑树，而unordered_map底层是哈希表。若键已存在，通过下标访问时会更新其对应的值。
      • 负载因子：容器的负载因子是元素数量与桶数量的比值，当负载因子达到某个阈值时，容器会自动增加桶的数量，从而保持查找效率。
      • find()：查找给定键是否存在，返回指向该元素的迭代器，如果元素不存在，返回 end()。
      • 然后就是迭代器的不同，map的iterator是双向迭代器，而unordered_map的iterator是单向迭代器；map底层是红黑树，map的迭代器是有序+去重的；而unoedered_map底层是哈希桶，unoedered_map是无序+去重的。

      3.3 unordered_map和map的区别

      这里set和map都是使用红黑树封装实现的，而unordered_set和unordered_map都是使用哈希表封装实现的。

    • 最后就是性能上的差异，对于大多数场景下unoedered_map增删查改的效率要高于map的；（红黑树的效率是O(log N)，哈希表的效率是O(1)。

      • unordered_set：是一个无序的集合容器，只存储唯一的元素，类似于 set，但是内部没有元素的顺序。
      • unordered_map：是一个无序的映射容器，存储键值对，每个键唯一，类似于 map，但是不保证按键的顺序排列。
      • empty()：检查集合是否为空。