当前位置：首页 > news >正文

unordered_set和unordered_map

news 2025/5/16 11:50:24

std::unordered_set和std::unordered_map都是基于哈希表实现的容器。它们都利用哈希函数将元素映射到存储位置，从而实现高效的查找、插入和删除操作。不过，它们在具体用途和存储结构上有所不同。让我来详细解释一下它们的特点和区别。

1.哈希表的基本原理
哈希表是一种通过哈希函数将键（key）映射到存储位置的数据结构。它的主要优点是能够提供平均时间复杂度为O(1)的查找、插入和删除操作。哈希表的关键在于哈希函数的设计和冲突解决机制。

• 哈希函数：将键转换为一个整数，通常用于确定元素在存储数组中的位置。

• 冲突解决：当两个不同的键映射到同一个位置时，需要通过某种机制解决冲突，常见的方法包括链地址法（拉链法）和开放寻址法。

2.std::unordered_set
std::unordered_set是一个存储唯一元素的容器，基于哈希表实现。它的主要特点是：

• 存储唯一元素：容器中的每个元素都是唯一的，不允许重复。

• 无序存储：元素的存储顺序是不确定的，取决于哈希函数和冲突解决机制。

• 高效查找：提供平均时间复杂度为O(1)的查找操作。

示例代码

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> mySet;// 插入元素mySet.insert(1);mySet.insert(2);mySet.insert(3);// 查找元素if (mySet.find(2) != mySet.end()) {std::cout << "Found 2" << std::endl;}// 删除元素mySet.erase(2);// 遍历元素for (int num : mySet) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

3.std::unordered_map
std::unordered_map是一个存储键值对的容器，基于哈希表实现。它的主要特点是：

• 存储键值对：每个键都对应一个值，键是唯一的。

• 无序存储：键值对的存储顺序是不确定的，取决于哈希函数和冲突解决机制。

• 高效查找：提供平均时间复杂度为O(1)的查找操作。

示例代码

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> myMap;// 插入键值对myMap[1] = "apple";myMap[2] = "banana";myMap[3] = "cherry";// 查找键值对if (myMap.find(2) != myMap.end()) {std::cout << "Found key 2 with value: " << myMap[2] << std::endl;}// 删除键值对myMap.erase(2);// 遍历键值对for (const auto& pair : myMap) {std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;}return 0;
}