从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(上)

简介: 从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)

1. unordered_set和unordered_map

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


       unordered_multiset和unordered_multimap可查看文档介绍。unordered系列和前面学习的map和set几乎一模一样,只是多了前面的unordered。正如它的名字一样,unordered系列和map/set比起来,unordered系列打印出来的数据是无序的。

1.1 unordered_map

1. unordered_map是存储键值对的关联式容器,其允许通过keys快速索引到与其对应的value。

2. 在unordered_map中,键值通常用于惟一地标识元素,而映射值是一个对象,其内容与此键关联。键和映射值的类型可能不同。

3. 在内部, unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value,unordered_map将相同哈希值的键值对放在相同的桶中。

4. unordered_map容器通过key访问单个元素要比map快,但它通常在遍历元素子集的范围迭代方面效率较低。

5. unordered_maps实现了直接访问操作符(operator[ ]),它允许使用key作为参数直接访问value。

6. 它的迭代器至少是前向迭代器。

常用接口函数:可以参考map的函数使用,还有一些关于哈希的接口后面再讲解


1.2 unordered_set

1、无序集是一种容器,它以不特定的顺序存储唯一的元素,并允许根据元素的值快速检索单个元素。

2、在unordered_set中,元素的值同时是唯一标识它的键。键是不可变的,只可增删,不可修改。

3、在内部,unordered_set中的元素没有按照任何特定的顺序排序,而是根据它们的散列值组织成桶,从而允许通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。

4、unordered_set容器比set容器更快地通过它们的键访问单个元素,尽管它们在元素子集的范围迭代中通常效率较低。

5、容器中的迭代器至少是前向迭代器。

       unordered_set 容器提供了和 unordered_map 相似的能力,但 unordered_set 可以用保存的元素作为它们自己的键。T 类型的对象在容器中的位置由它们的哈希值决定,因而需要定义一个 Hash< T > 函数。基本类型可以省去Hash< T >方法。不能存放重复元素。可指定buckets个数,可进行初始化,也可后期插入元素

常用接口函数:可以参考set的函数使用,还有一些关于哈希的接口后面再讲解


1.3 unordered系列写OJ

(困难题唯唯诺诺,简单题多次重拳出击)

961. 在长度 2N 的数组中找出重复 N 次的元素 - 力扣(LeetCode)

难度简单

给你一个整数数组 nums ,该数组具有以下属性:

  • nums.length == 2 * n.
  • nums 包含 n + 1不同的 元素
  • nums 中恰有一个元素重复 n

找出并返回重复了 n 次的那个元素。

示例 1:

输入:nums = [1,2,3,3]

输出:3


示例 2:

输入:nums = [2,1,2,5,3,2]

输出:2


示例 3:

输入:nums = [5,1,5,2,5,3,5,4]

输出:5


提示:

  • 2 <= n <= 5000
  • nums.length == 2 * n
  • 0 <= nums[i] <= 10^4
  • numsn + 1 不同的 元素组成,且其中一个元素恰好重复 n
class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
 
    }
};

解析代码:(和map一样用)(以下代码改成map也能过,OJ平均效率低一些,后面就知道了)

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        unordered_map<int,int> countMap;
        for(const auto& e : nums)
        {
            countMap[e]++;
        }
 
        unordered_map<int,int> Map;
        for(const auto& kv : countMap)
        {
            if(kv.second == nums.size() / 2)
            {
                return kv.first;
            }
        }
        return -1; // 不会走到这,顺便返回一个值
    }
};

349. 两个数组的交集 - 力扣(LeetCode)

难度简单

给定两个数组 nums1nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]

输出:[2]


示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出:[9,4]

解释:[4,9] 也是可通过的


提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 
    }
};

解析代码:(这题在从C语言到C++_26讲过了)(当时用set排序了,现在不排序写写)


当时是力扣题解2,现在是力扣题解1:使用哈希集合存储元素,则可以在O(1)的时间内判断一个元素是否在集合中,从而降低时间复杂度。首先使用两个集合分别存储两个数组中的元素,然后遍历较小的集合(随便遍历一个也行,就是效率低点),判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。


该方法的时间复杂度可以降低到O(m+n)。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set s1(nums1.begin(),nums1.end()); // 去重
        unordered_set s2(nums2.begin(),nums2.end());
 
        vector<int> retV;
        if(s1.size() <= s2.size())
        {
            for(const auto& e : s1)
            {
                if(s2.find(e) != s2.end())
                {
                    retV.push_back(e);
                }
            }
        }
        else
        {
            for(const auto& e : s2)
            {
                if(s1.find(e) != s1.end())
                {
                    retV.push_back(e);
                }
            }
        }
        return retV;
    }
};

217. 存在重复元素 - 力扣(LeetCode)

难度简单

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false

示例 1:

输入:nums = [1,2,3,1]

输出:true

示例 2:

输入:nums = [1,2,3,4]

输出:false

示例 3:

输入:nums = [1,1,1,3,3,4,3,2,4,2]

输出:true


提示:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
 
    }
};

解析代码:(看看返回值,前两个和模拟实现set的一样)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> s;
        for(const auto& e : nums)
        {
            if(s.insert(e).second == false)
            {
                return true;
            }
        }
        return false;
    }
};

从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)(中):https://developer.aliyun.com/article/1522331

目录
相关文章
|
2天前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
9 2
|
2天前
|
存储 C++ 容器
【C++】map和set深度讲解(下)
【C++】map和set深度讲解(下)
11 2
|
2天前
|
存储 自然语言处理 Java
【C++】map和set深度讲解(上)
【C++】map和set深度讲解(上)
13 2
|
8天前
|
存储 算法 C++
C++一分钟之-扁平化映射与unordered_map
【7月更文挑战第5天】C++的STL `unordered_map`是键值对的快速查找容器,基于哈希表。常见问题包括哈希函数选择、键类型限制、内存管理和迭代顺序不确定性。要避免问题,需优化哈希函数,确保自定义类型支持哈希和比较操作,合理管理内存,不依赖迭代顺序。提供的代码示例展示了如何为自定义类型定义哈希函数并操作`unordered_map`。正确使用能提升代码效率。
21 0
C++一分钟之-扁平化映射与unordered_map
|
11天前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(二)
15 1
|
2天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
9 0
|
8天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
14 0
|
11天前
|
存储 JavaScript 前端开发
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(一)
JavaScript编码之路【ES6新特性之 Symbol 、Set 、Map、迭代器、生成器】(一)
10 0
|
13天前
|
存储 算法 C++
C++一分钟之-扁平化映射与unordered_map
【6月更文挑战第30天】`std::unordered_map`在C++中提供O(1)平均操作的无序键值对存储。文章讨论了扁平化映射,用于简化多级数据结构,例如将配置文件展平。常见问题包括哈希碰撞、内存管理和键类型选择。示例展示了如何创建和访问扁平化配置映射。通过理解哈希冲突解决、内存管理和键要求,可以优化使用。
21 0
|
18天前
|
Dart
Dart之集合详解(List、Set、Map)
Dart之集合详解(List、Set、Map)
18 1