C++第三十九弹---C++ STL中的无序容器:unordered_set与unordered_map使用详解

server/2025/1/12 7:55:52/

个人主页: 熬夜学编程的小林

💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】

目录

1 unordered_set

1.1 unordered_set的接口说明

1.1.1 unordered_set的构造

1.1.2. unordered_set的容量

1.1.3. unordered_set的迭代器

1.1.4. unordered_set的查询

1.1.5. unordered_set的修改操作

1.1.6. unordered_set的桶操作

2 unordered_map

1.2 unordered_map的接口说明

1.2.1. unordered_map的构造

1.2.2. unordered_map的容量

1.2.3. unordered_map的迭代器

1.2.4. unordered_map的元素访问

6. unordered_map的修改操作

7. unordered_map的桶操作


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

1 unordered_set

  • 1. unordered_set 是以不特定顺序存储唯一元素的容器,并允许根据其值快速检索单个元素。
  • 2. 在unordered_set中,元素的值同时是其键,它唯一地标识它。键是不可变的,因此,unordered_set中的元素不能在容器中修改一次,但是,它们可以插入和删除。
  • 3. 在内部,unordered_set中的元素不按任何特定顺序排序,而是根据其哈希值组织到桶中,以便直接通过其值快速访问各个元素(平均平均时间复杂度恒定)。
  • 4. unordered_set容器通过其键访问单个元素的速度比设置的容器更快,尽管它们在通过其元素子集进行范围迭代时通常效率较低。
  • 5. 容器中的迭代器至少是正向迭代器。

1.1 unordered_set的接口说明

1.1.1 unordered_set的构造

代码演示 

#include<unordered_set>
int main()
{// 构造空对象unordered_set<int> s1;// 列表构造对象unordered_set<int> s2 = { 1,3,4,9,2,7 };return 0;
}

 测试结果

1.1.2. unordered_set的容量

函数声明功能介绍
bool empty() const检测unordered_set是否为空
size_t size() const获取unordered_set的有效元素个数

 代码演示

#include<unordered_set>
int main()
{unordered_set<int> s1 = { 1,3,4,9,2,7 };cout << "empty() = " << s1.empty() << endl;cout << "size() = " << s1.size() << endl;return 0;
}

测试结果 

 

1.1.3. unordered_set的迭代器

函数声明功能介绍
begin返回unordered_set第一个元素的迭代器
end返回unordered_set最后一个元素下一个位置的迭代器

代码演示

#include<unordered_set>
int main()
{unordered_set<int> s1 = { 1,3,4,9,2,7 };// 获取unordered_set第一个元素的迭代器unordered_set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";++it1;}cout << endl;return 0;
}

测试结果

1.1.4. unordered_set的查询

函数声明功能介绍
iterator find(const K& key)返回key在哈希桶中的位置
size_t count(const K& key)返回哈希桶中key的个数

代码演示

#include<unordered_set>
int main()
{unordered_set<int> s1 = { 1,3,4,9,2,7,4 };// 查找数值3的位置,并打印该位置的值auto pos = s1.find(3);cout << *pos << endl;// 计算数值4的个数size_t countFour = s1.count(4);cout << "countFour = " << countFour << endl;return 0;
}

测试结果

注意:unordered_set中key是不能重复的,因此count函数的返回值最大为1。


1.1.5. unordered_set的修改操作

函数声明功能介绍
insert向容器中插入key值
erase删除容器中的key值
void clear()清空容器中有效元素个数
void swap(unordered_set&)交换两个容器中的元素

代码演示

#include<unordered_set>
int main()
{unordered_set<int> s1;// 插入值s1.insert(1);s1.insert(4);s1.insert(5);// 支持迭代器,因此也支持范围forfor (auto e : s1){cout << e << " ";}cout << endl;// 删除6,没有该值则不删除s1.erase(6);// 删除4,有该值则删除该值s1.erase(4);for (auto e : s1){cout << e << " ";}cout << endl;return 0;
}

测试结果

 

1.1.6. unordered_set的桶操作

函数声明功能介绍
size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

代码演示

#include<unordered_set>
int main()
{unordered_set<int> s1 = { 1,4,6,9,3,7,5 };// 获取桶的总个数cout << "bucket_count() = " << s1.bucket_count() << endl;// 获取2号桶有效元素个数cout << "bucket_size(2) = " << s1.bucket_size(2) << endl;// 数值6所在的桶号cout << "bucket(6) = " << s1.bucket(6) << endl;return 0;
}

测试结果

2 unordered_map

  • 1. unordered_map是存储<key, value>键值对的关联式容器,其允许通过key快速的索引到与其对应的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.2 unordered_map的接口说明

1.2.1. unordered_map的构造

函数声明功能介绍
unordered_map构造一个空的 unordered_map 对象
unordered_map(initializer_list<T> il)

使用列表的内容初始化容器。

代码演示

#include<unordered_map>
int main()
{// 构造空对象unordered_map<string,int> m1;// 列表构造对象unordered_map<string, string> m2 = {{"insert","插入"},{"erase","删除"},{"string","字符串"} };return 0;
}

测试结果

1.2.2. unordered_map的容量

函数声明功能介绍
bool empty() const检测unordered_map是否为空
size_t size() const获取unordered_map的有效元素个数

代码演示

#include<unordered_map>
int main()
{unordered_map<string, string> m1 = {{"insert","插入"},{"erase","删除"},{"string","字符串"} };cout << "empty() = " << m1.empty() << endl;cout << "size() = " << m1.size() << endl;return 0;
}

测试结果

1.2.3. unordered_map的迭代器

函数声明功能介绍
begin返回unordered_map第一个元素的迭代器
end返回unordered_map最后一个元素下一个位置的迭代器

代码演示

#include<unordered_map>
int main()
{unordered_map<string, string> m1 = {{"insert","插入"},{"erase","删除"},{"string","字符串"} };// 获取第一个元素的迭代器,使用auto更简便//unordered_map<string, string>::iterator it = m1.begin();auto it = m1.begin();while (it != m1.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;return 0;
}

测试结果 

1.2.4. unordered_map的元素访问

函数声明功能介绍
operator[]返回与key对应的value,没有一个默认值

代码演示

#include<unordered_map>
int main()
{// 统计各自水果的个数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };unordered_map<string, int> countMap;for (auto& e : arr){// 水果没有出现则插入该水果,出现则将个数++countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;return 0;
}

测试结果 

注意:该函数中实际调用哈希桶的插入操作,用参数key与V()构造一个默认值往底层哈希桶中插入,如果key不在哈希桶中,插入成功,返回V()插入失败,说明key已经在哈希桶中,将key对应的value返回。此处与map中的operator[]原理类似。


1.2.5. unordered_map的查询

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

代码演示

#include<unordered_map>
int main()
{unordered_map<string, int> m1 = {{"string",1 }, { "insert",2 }, { "left",3 } };// 查找left的位置,打印该位置键值对的值auto pos = m1.find("left");cout << pos->first << ":" << pos->second << endl;// 计算key为string的键值对个数size_t count = m1.count("string");cout << "count = " << count << endl;return 0;
}

测试结果 

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

6. unordered_map的修改操作

函数声明功能介绍
insert向容器中插入键值对
erase删除容器中的键值对
void clear()清空容器中有效元素个数
void swap(unordered_map&)交换两个容器中的元素

代码演示

#include<unordered_map>
int main()
{unordered_map<string, int> m1;pair<string, int> kv1("string", 1);// 插入值m1.insert(kv1);// 有名对象m1.insert({ "left",2 });m1.insert(make_pair("right", 3));for (auto e : m1){cout << e.first << ":" << e.second << endl;}cout << endl;// 删除key为string的键值对m1.erase("string");for (auto e : m1){cout << e.first << ":" << e.second << endl;}cout << endl;return 0;
}

测试结果 

7. unordered_map的桶操作

函数声明功能介绍
size_t bucket_count()const返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const返回n号桶中有效元素的总个数
size_t bucket(const K& key)返回元素key所在的桶号

代码演示

#include<unordered_map>
int main()
{unordered_map<string, int> m1 = {{"string",1},{"right",2},{"insert",3}};// 获取桶的总个数cout << "bucket_count() = " << m1.bucket_count() << endl;// 获取3号桶有效元素个数cout << "bucket_size(2) = " << m1.bucket_size(3) << endl;// key为right所在的桶号cout << "bucket(right) = " << m1.bucket("right") << endl;return 0;
}

测试结果 


http://www.ppmy.cn/server/105262.html

相关文章

【数据结构篇】~栈和队列(附源码)

【数据结构篇】~栈和队列 前言一、栈的实现1.头文件2.源文件3.一个算法题——[有效的括号](https://leetcode.cn/problems/valid-parentheses/description/%E2%80%8B) 二、队列1.头文件2.源文件 前言 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入…

快充协议方案 TYPE-C取电 PD:5V、9V、12V、15V、20V

PD快充是一种由USB-IF组织制定的快速充电规范&#xff0c;是主流的快充之一。它通过USB电缆与连接器增加电力的输出来扩展USB应用中的电缆总线的供电功能&#xff0c;从而实现更高的电压与电流&#xff0c;并且可以自由改变电力输出的方向。 PD协议的应用非常广泛&#xff0c;…

c# 读取文本解析

1、filepath是文件路径 public void JXFile(string filepath) { //解析文件 string filename filepath; m_filename Path.GetFileNameWithoutExtension(filename); string …

如何巧妙减小Uniapp打包后的小程序体积?

随着移动互联网的发展&#xff0c;小程序成为越来越多企业和开发者的选择。而uniapp作为一款多端开发框架&#xff0c;也越来越受到开发者的青睐。然而&#xff0c;在使用uniapp开发小程序的过程中&#xff0c;有很多开发者都遇到了同样的问题——打包后的小程序体积太大。那么…

yolact导出onnx

github上有yolact-onnx仓库可以导出不带有nms和两个分支的矩阵相乘的部分&#xff0c;但是无法导出带有nms的部分。 一、导出的代码 注意opset版本最低要求14&#xff0c; torch.onnx.export的输入要求是真实图片&#xff0c;否则后续推理会报错。 import torch import cv2f…

【JS基础】call apply bind

三者的区别 三者多可以显式绑定函数的this指向三者第一个参数都是this指向的对象&#xff0c;若该参数为undefined或null,this则默认指向全局window传参不同&#xff0c;apply是数组&#xff0c;call是参数列表&#xff0c;而bind可以分为多次传入&#xff0c;实现参数合并cal…

GOPATH GOBIN GO modules

go 代码组织 go 程序组成package, 一个package是一组在相同目录的源代码共同编译而成。在同一个包里&#xff0c;函数、类型、变量、和常量是彼此可见的。一系列相关的包组成了module。一个repo包含一个或者多个module。 GOPATH & GOBIN go build生成bin文件&#xff0c…

windows vs2022 MFC使用webview2嵌入网页

Microsoft Edge WebView2 控件允许在本机应用中嵌入 web 技术(HTML、CSS 以及 JavaScript)。 WebView2 控件使用 Microsoft Edge 作为绘制引擎&#xff0c;以在本机应用中显示 web 内容。 一、通过菜单“项目”-“管理NuGet程序包”&#xff0c;下载相关包 二、安装 Microsof…