std::unordered_map 查询时间复杂度

C++ 中的 std::unordered_map 是基于哈希表实现的，因此查询一个元素的时间复杂度通常是 O(1)，即常数时间复杂度。但是，在最坏情况下，所有的元素都会被哈希到同一个桶里，此时查询一个元素的时间复杂度会退化为 O(n)，其中 n 是 std::unordered_map 中元素的个数。因此，std::unordered_map 的查询时间复杂度是具有不确定性的，但是在平均情况下，查询一个元素的时间复杂度是比较优秀的。需要注意的是，std::unordered_map 在性能上通常比 std::map 更优秀，但是其元素的顺序不是按照插入顺序或者键值的大小排序的。

相关问题

std::unordered_map如何插入和查询

std::unordered_map是C++标准库中的关联容器，用于存储键值对，其特点是查找速度快（平均时间复杂度为O(1)），但插入和删除的时间复杂度为O(1)到O(n)之间，取决于哈希表的装载因子。下面是插入和查询的基本步骤：

插入（Insertion）:

创建一个std::unordered_map实例，例如：std::unordered_map<std::string, int> myMap;

使用insert或emplace方法添加元素。insert接受一个键值对作为参数，如果键已经存在，将替换旧的值；emplace则可以在构造时直接在内部创建新元素，不检查键是否存在：
插入已存在的键值对：myMap.insert({"key", value});

使用emplace根据键新建元素：myMap.emplace("key", value);

查询（Querying）:

通过键来获取对应的值，可以使用find方法：auto it = myMap.find("key");
if (it != myMap.end()) {
int val = it->second; // 如果找到，则val就是对应键的值
} else {
std::cout << "Key not found." << std::endl;
}

如果不确定键是否存在于映射中，也可以使用count方法检查键的数量，equal_range方法返回一个包含所有匹配键的范围。

需要注意的是，为了保持良好的性能，std::unordered_map依赖于哈希函数，所以键必须具有可哈希性。如果键类型不支持默认的哈希函数，你需要提供一个自定义的hash函数和等价操作符重载。

std::unordered_map 和map的差异

std::map和std::unordered_map都是C++ STL中的关联容器，它们都提供了类似于字典的key-value存储功能，但是它们的实现方式有所不同。
std::map是基于红黑树的实现，它的元素会按照key进行排序。因此，在std::map中查找元素的时间复杂度是O(logN)。由于其内部实现是红黑树，因此它的空间占用相对较大。std::map适合需要有序存储的场景。
std::unordered_map则是基于哈希表的实现，它不会对元素进行排序。查找元素时，它会根据key计算哈希值，并通过哈希值快速定位元素位置，因此查找元素的时间复杂度是O(1)。但是，哈希表需要额外的空间来存储哈希表本身，因此它的空间占用相对较小。std::unordered_map适合需要快速查找元素的场景。
需要注意的是，在使用std::unordered_map时，需要保证元素类型可以进行哈希运算，否则需要自定义哈希函数。