【C++庖丁解牛】底层为红黑树结构的关联式容器--哈希容器(unordered_map和unordered_set)

2024-04-14 14:12
文章标签 c++ 哈希 set 底层 容器 map 关联 unordered 树结构 庖丁解牛

本文主要是介绍【C++庖丁解牛】底层为红黑树结构的关联式容器--哈希容器(unordered_map和unordered_set)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

🍁你好，我是 RO-BERRY
📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识
🎄感谢你的陪伴与支持 ，故事既有了开头，就要画上一个完美的句号，让我们一起加油

在这里插入图片描述

目录

  • 1. unordered系列关联式容器
    • 1.1 unordered_map
      • 1.1.1 unordered_map的文档介绍
      • 1.1.2 unordered_map的接口说明
    • 1.2 unordered_set
      • 1.2.1 unordered_set的构造
      • 1.2.2 unordered_set的修改操作
      • 1.2.3 unordered_set的查找操作
      • 1.2.4 unordered_set的容量
      • 1.2.5 unordered_set的迭代器
      • 1.2.5 unordered_set的其他操作
  • 2.set与unordered_set的区别
  • 3. 比较set和unordered_set的性能差异
      • 1.4.1 set和unordered_set的效率对比
  • 4. unordered_map应用OJ题
    • 4.1 leecode-961. 在长度 2N 的数组中找出重复 N 次的元素
    • 4.2 leecode-349. 两个数组的交集

1. unordered系列关联式容器

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

nordered系列关联式容器是C++标准库中提供的一组无序容器，用于存储键值对。它们的特点是使用哈希函数来实现快速的查找、插入和删除操作，而不是使用传统的红黑树等数据结构。

unordered系列关联式容器包括以下几种：

  • unordered_set：无序集合，存储唯一的键值，不允许重复。
  • unordered_multiset：无序多重集合，存储键值，允许重复。
  • unordered_map：无序映射，存储键值对，键唯一。
  • unordered_multimap：无序多重映射，存储键值对，键可以重复。

这些容器的底层实现使用了哈希表，通过将键值映射到哈希桶中来实现快速的查找和插入操作。在哈希冲突时，采用链地址法解决冲突。

使用unordered系列关联式容器时，需要注意以下几点：

  1. 需要提供自定义的哈希函数和相等比较函数（或者使用默认的std::hash和std::equal_to）。
  2. 由于无序容器不会对元素进行排序，因此迭代器遍历元素的顺序是不确定的。
  3. 插入和查找操作的平均时间复杂度为O(1)，但最坏情况下可能达到O(n)。

1.1 unordered_map

1.1.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. 它的迭代器至少是前向迭代器。

1.1.2 unordered_map的接口说明

  1. unordered_map的构造
函数声明功能介绍
unordered_map构造不同格式的unordered_map对象
  1. unordered_map的容量
函数声明功能介绍
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数
  1. unordered_map的迭代器
函数声明功能介绍
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器
cbegin返回unordered_map第一个元素的const迭代器
cend返回unordered_map最后一个元素下一个位置的const迭代器
  1. unordered_map的元素访问
函数声明功能介绍
operator[]返回与key对应的value，没有一个默认值

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶
中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，
将key对应的value返回。

  1. unordered_map的查询
函数声明功能介绍
iterator find(const K& key)返回key在哈希桶中的位置
size_t count(const K& key)返回哈希桶中关键码为key的键值对的个数

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1

  1. unordered_map的修改操作
函数声明功能介绍
insert向容器中插入键值对
erase删除容器中的键值对
void clear()清空容器中有效元素个数
void swap(unordered_map&)交换两个容器中的元素
  1. unordered_map的桶操作
函数声明功能介绍
size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

1.2 unordered_set

1.2.1 unordered_set的构造

函数声明功能介绍
默认构造函数：unordered_set< T > set;创建一个空的unordered_set对象，其中T是元素的类型。
区间构造函数：unordered_set< T > set(first, last);创建一个unordered_set对象，并将[first, last)区间内的元素插入到集合中。
拷贝构造函数：unordered_set< T > set(other_set);创建一个unordered_set对象，并将另一个unordered_set对象other_set中的元素拷贝到新的集合中。
移动构造函数：unordered_set< T > set(std::move(other_set));创建一个unordered_set对象，并从另一个unordered_set对象other_set中移动元素到新的集合中。
初始化列表构造函数：unordered_set< T > set = {val1, val2, …};创建一个unordered_set对象，并将初始化列表中的元素插入到集合中。

1.2.2 unordered_set的修改操作

函数声明功能介绍
insert(val)将元素val插入到unordered_set中。
insert(first, last)将[first, last)范围内的元素插入到unordered_set中。
erase(val)删除unordered_set中值为val的元素。
erase(iterator)删除迭代器指向的元素。
erase(first, last)删除[first, last)范围内的元素。

1.2.3 unordered_set的查找操作

函数声明功能介绍
find(val)返回指向值为val的元素的迭代器，如果不存在则返回end()。
count(val)返回值为val的元素在unordered_set中出现的次数，要么是0，要么是1。

1.2.4 unordered_set的容量

函数声明功能介绍
size()返回unordered_set中元素的个数。
empty()判断unordered_set是否为空。

1.2.5 unordered_set的迭代器

函数声明功能介绍
begin()返回指向unordered_set第一个元素的迭代器。
end()返回指向unordered_set末尾的迭代器。

1.2.5 unordered_set的其他操作

函数声明功能介绍
clear()清空unordered_set中的所有元素。
swap(other)交换当前unordered_set和另一个unordered_set的内容。

2.set与unordered_set的区别

#include<iostream>
#include<unordered_map>
#include<map>
#include<unordered_set>
#include<set>
using namespace std;void test_set1()
{set<int> s;s.insert(3);s.insert(1);s.insert(5);s.insert(7);for (auto e : s){cout << e << " ";}cout << endl;unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(7);for (auto e : us){cout << e << " ";}cout << endl;
}int main()
{test_set1();return 0;
}

在这里插入图片描述

map是有序的，unordered_set是无序的

3. 比较set和unordered_set的性能差异

#include<iostream>
#include<unordered_map>
#include<map>
#include<unordered_set>
#include<set>
using namespace std;
int main()
{const size_t N = 100000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; ++i){v.push_back(rand()); // N比较大时，重复值比较多   因为rand函数产生不重复的值最大上限只有30000多个，我们这里有十万个数据v.push_back(rand()+i); // 重复值相对少v.push_back(i); // 没有重复，有序}size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert:" << end1 - begin1 << endl;size_t begin2 = clock();for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert:" << end2 - begin2 << endl;size_t begin3 = clock();for (auto e : v){s.find(e);}size_t end3 = clock();cout << "set find:" << end3 - begin3 << endl;size_t begin4 = clock();for (auto e : v){us.find(e);}size_t end4 = clock();cout << "unordered_set find:" << end4 - begin4 << endl << endl;cout <<"插入数据个数："<< s.size() << endl;cout <<"插入数据个数：" << us.size() << endl << endl;size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase:" << end5 - begin5 << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "unordered_set erase:" << end6 - begin6 << endl << endl;return 0;
}

1.4.1 set和unordered_set的效率对比

  1. Release版本(十万个数据)

在这里插入图片描述

  1. Debug版本(十万个数据)

在这里插入图片描述

  1. Release版本(一百万个数据)

在这里插入图片描述

  1. Debug版本(一百万个数据)

在这里插入图片描述

  • 插入性能均是unordered_set更优，时间耗费更少
  • 查找性能Release无区别，Debug版本是unordered_set更优，时间耗费更少
  • 删除性能均是unordered_set更优，时间耗费更少

4. unordered_map应用OJ题

4.1 leecode-961. 在长度 2N 的数组中找出重复 N 次的元素

给你一个整数数组 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] <= 104
nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

解题代码：

class Solution {
public:int repeatedNTimes(vector<int>& A) {size_t N = A.size() / 2;// 用unordered_map统计每个元素出现的次数unordered_map<int, int> m;for (auto e : A)m[e]++;// 找出出现次数为N的元素for (auto& e : m){if (e.second == N)return e.first;}//不可能的情况return -1;}
};

4.2 leecode-349. 两个数组的交集

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

示例 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) {// 用unordered_set对nums1中的元素去重unordered_set<int> s1;for (auto e : nums1)s1.insert(e);// 用unordered_set对nums2中的元素去重unordered_set<int> s2;for (auto e : nums2)s2.insert(e);// 遍历s1，如果s1中某个元素在s2中出现过，即为交集vector<int> vRet;for (auto e : s1){if (s2.find(e) != s2.end())vRet.push_back(e);}return vRet;}
};

这篇关于【C++庖丁解牛】底层为红黑树结构的关联式容器--哈希容器(unordered_map和unordered_set)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/903198。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
poj 3050 dfs + set的妙用

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。 解析： dfs + set去重搞定。 代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2