C++ unordered_map 容器详解[编辑 | 编辑源代码]

unordered_map是C++标准模板库(STL)中提供的一种关联容器，它存储的元素是键值对(key-value pair)，并通过哈希表实现高效查找。与`map`不同，`unordered_map`不会自动对键进行排序，因此平均情况下能提供O(1)时间复杂度的查找性能。

基本特性[编辑 | 编辑源代码]

无序存储：元素不按键的顺序存储
唯一键：每个键只能在容器中出现一次
哈希实现：使用哈希表作为底层数据结构
快速访问：平均情况下插入、删除和查找操作都是O(1)时间复杂度
动态大小：容器大小会根据需要自动增长

头文件与声明[编辑 | 编辑源代码]

使用unordered_map需要包含头文件：

#include <unordered_map>

基本声明语法：

std::unordered_map<KeyType, ValueType> map_name;

构造函数[编辑 | 编辑源代码]

unordered_map提供多种构造函数：

构造函数	描述
`unordered_map()`	默认构造函数，创建空容器
`unordered_map(size_type n)`	创建容器并预留n个桶的空间
`unordered_map(const unordered_map& other)`	拷贝构造函数
`unordered_map(initializer_list<value_type> il)`	使用初始化列表构造

示例：

// 默认构造
std::unordered_map<std::string, int> wordCount;

// 初始化列表构造
std::unordered_map<std::string, int> colors = {
    {"red", 0xFF0000},
    {"green", 0x00FF00},
    {"blue", 0x0000FF}
};

常用成员函数[编辑 | 编辑源代码]

元素访问[编辑 | 编辑源代码]

operator[]：访问或插入元素（键不存在时会创建）
at()：访问元素（键不存在时抛出异常）

示例：

std::unordered_map<std::string, int> ageMap = {{"Alice", 25}, {"Bob", 30}};

// 使用operator[]
ageMap["Charlie"] = 28;  // 插入新元素
int aliceAge = ageMap["Alice"];  // 访问现有元素

// 使用at()
try {
    int bobAge = ageMap.at("Bob");
    // int unknown = ageMap.at("Unknown"); // 抛出std::out_of_range异常
} catch(const std::out_of_range& e) {
    std::cerr << "Key not found: " << e.what() << '\n';
}

容量查询[编辑 | 编辑源代码]

empty()：检查容器是否为空
size()：返回元素数量
max_size()：返回容器可容纳的最大元素数

修改器[编辑 | 编辑源代码]

insert()：插入元素
emplace()：原位构造元素
erase()：删除元素
clear()：清空容器

示例：

std::unordered_map<int, std::string> idToName;

// 插入元素
idToName.insert({1, "Alice"});
idToName.emplace(2, "Bob");  // 效率更高

// 删除元素
idToName.erase(1);  // 删除键为1的元素

// 清空容器
idToName.clear();

查找操作[编辑 | 编辑源代码]

find()：查找指定键的元素
count()：统计具有指定键的元素数量（0或1）
contains()（C++20）：检查是否包含指定键

示例：

std::unordered_map<std::string, double> priceMap = {{"apple", 1.99}, {"banana", 0.99}};

// 使用find()
auto it = priceMap.find("apple");
if (it != priceMap.end()) {
    std::cout << "Price of apple: " << it->second << '\n';
}

// 使用count()
if (priceMap.count("banana") > 0) {
    std::cout << "Banana exists in the map\n";
}

// C++20的contains()
#if __cplusplus >= 202002L
if (priceMap.contains("orange")) {
    std::cout << "Orange exists in the map\n";
}
#endif

哈希与桶接口[编辑 | 编辑源代码]

unordered_map的性能很大程度上依赖于哈希函数和桶的数量：

桶操作[编辑 | 编辑源代码]

bucket_count()：返回桶的数量
max_bucket_count()：返回容器能拥有的最大桶数
bucket_size(n)：返回第n个桶中的元素数
bucket(key)：返回键所在的桶编号

哈希策略[编辑 | 编辑源代码]

load_factor()：返回负载因子（元素数/桶数）
max_load_factor()：获取或设置最大负载因子
rehash(n)：设置桶数为至少n
reserve(n)：预留至少n个元素的空间

示例：

std::unordered_map<std::string, int> myMap;

// 设置哈希策略
myMap.max_load_factor(0.7);  // 设置最大负载因子
myMap.reserve(100);         // 预留100个元素的空间

// 查看桶信息
std::cout << "Bucket count: " << myMap.bucket_count() << '\n';
std::cout << "Load factor: " << myMap.load_factor() << '\n';

迭代器[编辑 | 编辑源代码]

unordered_map提供前向迭代器：

std::unordered_map<std::string, int> myMap = {{"one", 1}, {"two", 2}, {"three", 3}};

// 使用迭代器遍历
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << it->first << ": " << it->second << '\n';
}

// 使用范围for循环（C++11）
for (const auto& pair : myMap) {
    std::cout << pair.first << ": " << pair.second << '\n';
}

自定义哈希函数[编辑 | 编辑源代码]

对于自定义类型作为键，需要提供哈希函数：

struct Point {
    int x, y;
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

std::unordered_map<Point, std::string, PointHash> pointMap;

性能分析[编辑 | 编辑源代码]

unordered_map在不同操作下的时间复杂度：

操作	平均情况	最坏情况
插入	O(1)	O(n)
删除	O(1)	O(n)
查找	O(1)	O(n)

实际应用案例[编辑 | 编辑源代码]

单词频率统计[编辑 | 编辑源代码]

#include <iostream>
#include <unordered_map>
#include <string>

void countWords(const std::string& text) {
    std::unordered_map<std::string, size_t> wordCount;
    std::string word;
    
    for (char c : text) {
        if (isalpha(c)) {
            word += tolower(c);
        } else if (!word.empty()) {
            ++wordCount[word];
            word.clear();
        }
    }
    
    if (!word.empty()) {
        ++wordCount[word];
    }
    
    // 输出结果
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << '\n';
    }
}

int main() {
    std::string text = "Hello world hello c++ world";
    countWords(text);
    return 0;
}

输出：

hello: 2
world: 2
c: 1

缓存实现[编辑 | 编辑源代码]

#include <unordered_map>
#include <iostream>

template<typename Key, typename Value>
class SimpleCache {
private:
    std::unordered_map<Key, Value> cache;
    size_t maxSize;
    
public:
    SimpleCache(size_t size) : maxSize(size) {}
    
    bool get(const Key& key, Value& value) {
        auto it = cache.find(key);
        if (it != cache.end()) {
            value = it->second;
            return true;
        }
        return false;
    }
    
    void put(const Key& key, const Value& value) {
        if (cache.size() >= maxSize) {
            cache.erase(cache.begin());  // 简单策略：删除第一个元素
        }
        cache[key] = value;
    }
};

int main() {
    SimpleCache<std::string, int> cache(3);
    
    cache.put("one", 1);
    cache.put("two", 2);
    cache.put("three", 3);
    
    int value;
    if (cache.get("two", value)) {
        std::cout << "Found: " << value << '\n';
    }
    
    cache.put("four", 4);  // 这会淘汰"one"
    
    if (!cache.get("one", value)) {
        std::cout << "one was evicted from cache\n";
    }
    
    return 0;
}

输出：

Found: 2
one was evicted from cache

unordered_map vs map[编辑 | 编辑源代码]

特性	unordered_map	map
底层实现	哈希表	红黑树
元素顺序	无序	按键排序
查找时间复杂度	平均O(1)，最坏O(n)	O(log n)
内存使用	通常更高	通常更低
迭代器稳定性	插入/删除可能使所有迭代器失效	除删除元素外，迭代器保持有效

最佳实践[编辑 | 编辑源代码]

1. 当需要快速查找而不关心顺序时，优先使用unordered_map 2. 对于小数据集，map可能更快（哈希计算开销） 3. 对于自定义类型作为键，确保提供良好的哈希函数 4. 预分配足够空间以避免频繁重哈希 5. 考虑负载因子对性能的影响

总结[编辑 | 编辑源代码]

unordered_map是C++中高效的关联容器，特别适合需要快速查找的场景。理解其哈希实现原理和性能特性对于有效使用至关重要。通过合理选择哈希函数和调整哈希策略，可以优化其性能以满足特定应用需求。