【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]

简介: 【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]

前言

欢迎各位大佬们的关顾,本文将介绍unordered系列容器以及其中的两个重要成员:unordered_mapunordered_set。unordered_map是一种无序的关联容器,它使用哈希表来存储键值对,并提供高效的插入、查找和删除操作。在本文中,我们将首先介绍unordered_map的基本概念和特点,然后详细讲解其接口和用法。接下来,我们将介绍unordered_set,它是一种无序的集合容器,同样基于哈希表实现。我们将对unordered_set进行简要介绍,并深入探讨其接口和用法。通过学习本文,您将对unordered系列容器有更加清晰的理解,并能够灵活运用它们解决实际问题。下面话不多说,坐稳扶好咱们要开车了😍

一、unordered系列容器

在C++98中,STL提供了一系列底层为红黑树结构的关联式容器,包括setmultisetmapmultimap。这些容器在查询操作时的时间复杂度为O(logN),其中N是容器中元素的数量。

为了提高查询效率,C++11引入了unordered_map和unordered_set这两个底层基于哈希表的关联式容器。与红黑树结构的关联式容器相比,unordered系列容器在平均情况下具有更高的查询效率,时间复杂度为常数级别O ( 1 ) O(1)O(1)。当哈希函数设计得好且没有太多的冲突时,它们可以在插入、查找和删除等操作上表现出很好的性能。

unordered_map是一种键值对存储的容器,每个键唯一对应一个值;而unordered_set是一种存储唯一元素的容器。它们的使用方式与红黑树结构的关联式容器类似,提供了insert、erase、find等方法来操作元素。

🚨🚨注意:unordered_map和unordered_set的元素顺序是根据哈希函数计算的哈希值来确定的,因此它们无法保证元素的顺序稳定。如果需要有序的容器,仍然可以使用红黑树结构的关联式容器。

二、unordered_map

| ===============================

| 🔴 unordered_map在线文档说明

| ===============================

1. unordered_map简介

unordered_map是C++标准库中的一个关联式容器,它是基于哈希表实现的。unordered_map提供了一种存储键值对的方式,每个键唯一对应一个值。它被设计为在平均情况下具有常数时间复杂度的插入、查找和删除操作。

unordered_mapmap的用法类似,但其内部结构不同。unordered_map使用哈希函数将键映射到桶(bucket)中,并在桶内使用链表或其他数据结构解决冲突。通过哈希函数和桶的结构,可以快速定位键对应的值。

⭕函数特点

  1. 常数时间复杂度:平均情况下,unordered_map的插入、查找和删除操作都具有常数时间复杂度。这是因为哈希表充分利用了哈希函数的散列性质,快速定位元素。
  2. 无序存储:与map不同,unordered_map不会按照键的顺序进行存储,而是根据哈希函数计算得到的哈希值进行存储。因此,遍历unordered_map的结果是无序的。
  3. 自定义哈希函数:unordered_map支持自定义哈希函数,可以根据键的类型,实现一个符合需求的哈希函数来提高查询效率。如果不提供自定义哈希函数,会使用默认的哈希函数。
  4. 冲突处理:由于哈希函数的限制,可能会出现多个元素映射到同一个桶的情况,这就是冲突。unordered_map使用链表或其他数据结构来解决冲突,保证键值对的正确存储和查找。
  5. 支持各种数据类型:unordered_map可以存储各种数据类型的键值对,包括内置类型和自定义类型

🚨🚨注意:使用unordered_map时,需要包含头文件<unordered_map>,并使用std命名空间,或者使用using语句简化操作。

2. unordered_map接口

- 构造函数

默认构造函数:

unordered_map<Key, T> myMap;

使用默认构造函数创建一个空的unordered_map对象。

列表初始化构造函数:

unordered_map<Key, T> myMap = {{key1, value1}, {key2, value2}, ...};

使用初始化列表创建unordered_map对象并初始化其中的键值对。

区间构造函数:

template<class InputIt>
unordered_map(InputIt first, InputIt last);

从指定范围内的元素创建unordered_map对象。范围由迭代器firstlast指定,可以是数组、容器或其他实现了前向迭代器的数据结构。

拷贝构造函数:

unordered_map(const unordered_map& other);

使用另一个unordered_map对象进行拷贝构造,创建一个与原unordered_map相同的副本。

移动构造函数:

unordered_map(unordered_map&& other) noexcept;

使用另一个unordered_map对象进行移动构造,创建一个新的unordered_map对象,并从原对象中窃取资源。

构造函数 功能介绍
unordered_map() 默认构造函数,创建一个空的unordered_map对象。
unordered_map(initializer_list<pair<const Key, T>>) 列表初始化构造函数,使用初始化列表创建unordered_map对象并初始化其中的键值对。
unordered_map(const unordered_map&) 拷贝构造函数,创建一个与原unordered_map相同的副本。
unordered_map(unordered_map&&) noexcept 移动构造函数,创建一个新的unordered_map对象,并从原对象中窃取资源。
unordered_map(size_type) 构造函数,创建具有指定桶数的unordered_map对象。
nordered_map(size_type, const hasher&, const key_equal&) 构造函数,创建具有指定桶数、哈希函数和相等比较操作符的unordered_map对象。
template unordered_map(InputIt, InputIt) 区间构造函数,从指定范围内的元素创建unordered_map对象。

- unordered_map的容量

unordered_map的容量相关的成员函数主要包括:

函数声明 功能介绍
unordered_map::size 返回unordered_map中键值对的个数。
unordered_map::empty 判断unordered_map是否为空,返回true或false。
unordered_map::max_size 返回unordered_map所能容纳的最大元素数量。

- unordered_map的迭代器

unordered_map提供了以下迭代器:

迭代器类型 功能介绍
unordered_map::iterator 用于遍历和修改unordered_map中的键值对,可以通过解引用操作符*和箭头操作符->访问元素。
unordered_map::const_iterator 用于遍历unordered_map中的键值对,但不允许修改元素值。

你可以使用以下成员函数来获取迭代器:

函数声明 功能介绍
unordered_map::begin 返回指向unordered_map起始位置的迭代器。
unordered_map::end 返回指向unordered_map末尾位置的迭代器。
unordered_map::find 返回指向键对应的元素的迭代器,如果键不存在,则返回尾部迭代器。

使用迭代器可以遍历unordered_map中的所有元素,示例代码如下所示:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
    
    // 使用迭代器遍历unordered_map并打印键值对
    for (auto it = map.begin(); it != map.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }
    
    // 使用find函数查找指定键的元素
    auto findIt = map.find(2);
    if (findIt != map.end()) {
        std::cout << "Key: " << findIt->first << ", Value: " << findIt->second << std::endl;
    }
    
    return 0;
}

输出结果:

Key: 1, Value: one
Key: 2, Value: two
Key: 3, Value: three
Key: 2, Value: two

通过迭代器,我们可以依次访问unordered_map中的键值对,并通过迭代器的解引用操作符 -> 来访问元素的键和值。使用find函数可以查找指定键的元素,并返回一个指向该元素的迭代器。

- unordered_map的元素访问

下标运算符 []:使用键作为索引来访问和修改unordered_map中的元素。如果键存在,则返回对应的值;如果键不存在,则将该键插入到unordered_map中,并返回一个默认构造的值

std::unordered_map<std::string, int> map = {{"apple", 1}, {"banana", 2}, {"orange", 3}};

int value = map["apple"];  // 访问键"apple"对应的值
map["banana"] = 5;         // 修改键"banana"对应的值
map["grape"] = 4;          // 插入新键"grape"并对应一个值

使用成员函数 at():使用键作为参数来访问和修改unordered_map中的元素。如果键存在,则返回对应的值;如果键不存在,则抛出std::out_of_range异常。

std::unordered_map<std::string, int> map = {{"apple", 1}, {"banana", 2}, {"orange", 3}};

int value = map.at("apple");  // 访问键"apple"对应的值
map.at("banana") = 5;         // 修改键"banana"对应的值
map.at("grape") = 4;          // 抛出异常,因为键"grape"不存在

nordered_map的修改操作

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

- unordered_map的桶操作

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

三、unordered_set

|===============================

| 🔴 unordered_set在线文档说明

|===============================

1. unordered_srt简介

std::unordered_set 是 C++ STL 提供的一个哈希表实现的无序集合容器。与 std::set 不同,std::unordered_set 中元素的顺序是不确定的,它使用哈希函数来快速访问、插入和删除元素。哈希函数将元素的键转换为一个哈希值,然后用该哈希值来映射到对应的桶中,每个桶中存储一组键值相同的元素。当需要访问、插入或删除某个元素时,首先根据哈希函数计算出该元素对应的桶的位置,然后在该桶中查找该元素。

⭕函数特点

  • 元素的顺序是不确定的,不能保证元素的插入顺序就是元素的访问顺序。
  • 访问、插入和删除元素的平均时间复杂度是 O(1)。
  • 查找元素的时间复杂度取决于哈希函数的质量,最坏情况下会退化为线性时间复杂度 O(n)。
  • 支持使用自定义类型作为元素,需要提供哈希函数和相等比较函数。
  • 内部结构是一个哈希表,具有一定的空间浪费和碰撞问题。

2. unordered_set接口

std::unordered_set 是 C++ STL 提供的一个哈希表实现的无序集合容器。它提供了一系列成员函数用于插入、删除、查找和遍历元素。下面是 std::unordered_set 常用的成员函数:

insert(): 向 unordered_set 中插入元素。有多种重载形式,可以接受单个元素、区间或者初始化列表作为参数。插入操作的平均时间复杂度是 O(1)。

std::unordered_set<int> set;

set.insert(10);                  // 插入单个元素
set.insert({20, 30, 40});        // 插入初始化列表
set.insert(begin(vec), end(vec)); // 插入区间

erase(): 从 unordered_set 中删除元素。有多种重载形式,可以接受单个元素、区间或者迭代器作为参数。删除操作的平均时间复杂度是 O(1)。

std::unordered_set<int> set = {10, 20, 30, 40};

set.erase(20);                // 删除单个元素
set.erase(begin(set), end(set)); // 删除整个区间
set.erase(set.find(30));      // 删除指定迭代器位置的元素

find(): 查找元素,返回一个迭代器指向该元素的位置,如果元素不存在,则返回 end()。查找操作的平均时间复杂度是 O(1)。

std::unordered_set<int> set = {10, 20, 30, 40};

auto it = set.find(20);     // 查找元素
if (it != set.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Not found" << std::endl;
}

count(): 获取某个元素在 unordered_set 中出现的次数,返回值为0或1。可以用于判断元素是否存在。

std::unordered_set<int> set = {10, 20, 30, 40};

if (set.count(20) > 0) {
    std::cout << "Element 20 exists in the set" << std::endl;
} else {
    std::cout << "Element 20 does not exist in the set" << std::endl;
}

size(): 获取 unordered_set 中当前存储的元素数量。

std::unordered_set<int> set = {10, 20, 30, 40};

std::cout << "Size of set: " << set.size() << std::endl;

empty(): 检查 unordered_set 是否为空,如果为空返回 true,否则返回 false

std::unordered_set<int> set;

if (set.empty()) {
    std::cout << "Set is empty" << std::endl;
} else {
    std::cout << "Set is not empty" << std::endl;
}

clear(): 清空 unordered_set 中的所有元素。

std::unordered_set<int> set = {10, 20, 30, 40};

set.clear();

🚨🚨注意:std::unordered_set 并不提供按索引方式访问元素的功能,因为 unordered_set 是无序的。 若要遍历 unordered_set 中的元素,可以使用迭代器

std::unordered_set<int> set = {10, 20, 30, 40};

for (auto it = set.begin(); it != set.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

以上是 std::unordered_set 常用的几个成员函数。通过这些函数,可以方便地进行元素的插入、删除、查找和遍历操作。更多的操作可见官方文档的描述。

温馨提示

感谢您对博主文章的关注与支持!另外,我计划在未来的更新中持续探讨与本文相关的内容,会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新,不要错过任何精彩内容!

再次感谢您的支持和关注。期待与您建立更紧密的互动,共同探索C++、算法和编程的奥秘。祝您生活愉快,排便顺畅!

目录
相关文章
|
1天前
|
存储 算法 NoSQL
C++一分钟之-map与set容器详解
【6月更文挑战第21天】C++ STL的`map`和`set`是基于红黑树的关联容器,提供有序存储和高效查找。`map`存储键值对,键唯一,值可重复;`set`仅存储唯一键。两者操作时间复杂度为O(log n)。常见问题包括键的唯一性和迭代器稳定性。自定义比较函数可用于定制排序规则,内存管理需注意适时释放。理解和善用这些工具能提升代码效率。
9 3
|
3天前
|
存储 编译器 C++
|
3天前
|
C++
C++类和类模板——入门
C++类和类模板——入门
9 1
|
4天前
|
存储 C++ 容器
C++一分钟之-变量与数据类型入门
【6月更文挑战第18天】**C++编程基础:变量与数据类型概览** 了解变量(存储数据的容器)和数据类型是编程入门的关键。声明变量如`int age = 25;`,注意初始化和类型匹配。基本数据类型包括整型(int等)、浮点型(float、double)、字符型(char)和布尔型(bool)。理解类型范围和精度,使用字面量后缀增强可读性。深入学习数组、指针、结构体和类,以及动态内存管理,避免数组越界和内存泄漏。不断实践以巩固理论知识。
17 1
|
7天前
|
存储 安全 编译器
【C++入门】—— C++入门 (中)_引用
【C++入门】—— C++入门 (中)_引用
17 5
|
7天前
|
存储 编译器 C语言
【C++入门】—— C++入门 (下)_内联函数
【C++入门】—— C++入门 (下)_内联函数
12 2
|
7天前
|
人工智能 安全 编译器
【C++入门】—— C++入门 (上)_命名空间
【C++入门】—— C++入门 (上)_命名空间
13 2
|
7天前
|
JavaScript 前端开发 编译器
【C++初阶】C++模板编程入门:探索泛型编程的奥秘
【C++初阶】C++模板编程入门:探索泛型编程的奥秘
14 0
|
2天前
|
存储 JavaScript 前端开发
JavaScript进阶-Map与Set集合
【6月更文挑战第20天】JavaScript的ES6引入了`Map`和`Set`,它们是高效处理集合数据的工具。`Map`允许任何类型的键,提供唯一键值对;`Set`存储唯一值。使用`Map`时,注意键可以非字符串,用`has`检查键存在。`Set`常用于数组去重,如`[...new Set(array)]`。了解它们的高级应用,如结构转换和高效查询,能提升代码质量。别忘了`WeakMap`用于弱引用键,防止内存泄漏。实践使用以加深理解。
|
11天前
|
存储 安全 Java
Java集合详解:Set, Map, Vector, List的对比与联系
Java集合框架核心包括List、Set、Map和Vector。List允许重复元素,如ArrayList(适合读取)和LinkedList(适合插入删除)。Set不允许重复,有HashSet(无序)和TreeSet(排序)。Map存储键值对,HashMap(无序)和TreeMap(排序)。Vector是线程安全的ArrayList替代品,但在多线程环境下使用。选择集合类型应根据应用场景,如有序、无序、键值对需求及线程安全考虑。