发布于 由admin

实战：利用 `std::map` 与 `std::unordered_map` 实现高效的键值对存储

引言：高效键值对存储的艺术

在现代软件开发中，我们经常面临需要将数据以“键-值”对的形式进行存储和检索的挑战。想象一下，你正在构建一个系统，需要根据用户的ID迅速找到其详细信息，或者根据商品的SKU码获取其库存量。在这种场景下，一个能够高效地将一个值（Value）与一个唯一的标识符（Key）关联起来，并支持快速查找、插入和删除操作的数据结构就显得至关重要。

C++标准库为我们提供了两种强大的关联容器来解决这类问题：std::map 和 std::unordered_map。它们各自拥有独特的底层实现机制和性能特性，适用于不同的应用场景。作为一名资深编程专家，我将带领大家深入探讨这两种容器的内部工作原理、使用方法、性能特点以及在实际项目中的最佳实践，帮助您在面对多样化的键值对存储需求时，做出最明智的选择。

本次讲座的目标是：

  1. 理解 std::map 和 std::unordered_map 的核心概念和底层实现。
  2. 掌握 它们的常用操作和时间复杂度。
  3. 洞察 它们在性能、内存和适用场景上的差异。
  4. 学习 如何根据实际需求选择最合适的容器，并进行优化。
  5. 掌握 处理自定义键类型以及一些高级使用技巧。

让我们从 std::map 开始，揭开它有序之美的面纱。

std::map：有序之美与平衡树的智慧

std::map 是 C++ 标准库提供的一个关联容器，它能够存储键值对，并按照键的严格弱序进行排序。这意味着无论你以何种顺序插入元素，它们在 std::map 中总是保持着键的升序排列。这种有序性是 std::map 最核心的特征之一。

2.1 底层实现：红黑树的奥秘

std::map 的底层数据结构通常实现为一棵红黑树（Red-Black Tree）。红黑树是一种自平衡二叉搜索树，它通过对每个节点着色（红色或黑色）并遵循一系列规则来确保树的高度始终保持在对数级别。这些规则包括：

  • 每个节点要么是红色，要么是黑色。
  • 根节点是黑色的。
  • 所有叶子节点（NIL节点，通常不存储数据但用于终止路径）是黑色的。
  • 如果一个节点是红色的，则它的子节点必须是黑色的。
  • 从任意节点到其每个叶子节点的所有简单路径都包含相同数量的黑色节点。

红黑树的自平衡特性保证了在插入、删除和查找操作时，树的高度不会失衡，从而确保了操作的对数时间复杂度。这意味着即使在最坏情况下，std::map 的性能也能维持在可预测的水平。

2.2 核心特性

  • 键唯一性：std::map 中的键是唯一的。如果你尝试插入一个已经存在的键，插入操作将不会成功（或者会更新对应的值，取决于使用的插入方法）。
  • 有序性：元素总是按照键的升序排列。这使得 std::map 非常适合需要范围查询或有序遍历的场景。
  • 双向迭代器：std::map 提供了双向迭代器，可以向前或向后遍历元素，并且遍历结果始终是有序的。
  • 动态大小：容器大小可以根据需要动态增长或收缩。

2.3 时间复杂度分析

理解操作的时间复杂度是选择容器的关键。对于 std::map，其主要操作的时间复杂度如下：

操作类型 平均时间复杂度 最坏时间复杂度 备注
插入 (insert) O(log N) O(log N) 涉及查找插入位置和可能的树旋转
查找 (find) O(log N) O(log N) 沿着树路径进行比较
删除 (erase) O(log N) O(log N) 涉及查找节点和可能的树旋转
访问 (at, []) O(log N) O(log N) at() 检查键是否存在，[] 不存在则插入
迭代 (traverse) O(N) O(N) 遍历所有 N 个元素
构造 (copy) O(N log N) O(N log N) 复制 N 个元素

这里的 N 是 std::map 中元素的数量。对数时间复杂度意味着即使 N 变得非常大，操作时间也只会缓慢增长，这对于大多数应用来说是高效且可预测的。

2.4 实际应用示例

2.4.1 声明与初始化

std::map 的声明需要指定键类型和值类型。

#include <iostream>
#include <map>
#include <string>

// 声明一个键为string，值为int的map
std::map<std::string, int> cityPopulation;

// 声明并初始化
std::map<std::string, double> productPrices = {
    {"Laptop", 1200.50},
    {"Mouse", 25.99},
    {"Keyboard", 75.00}
};

void printMap(const std::string& title, const std::map<std::string, int>& m) {
    std::cout << title << ":n";
    for (const auto& pair : m) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;
}

void printDoubleMap(const std::string& title, const std::map<std::string, double>& m) {
    std::cout << title << ":n";
    for (const auto& pair : m) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    // 示例1: 声明与初始化
    std::map<std::string, int> studentScores = {
        {"Alice", 95},
        {"Bob", 88},
        {"Charlie", 92}
    };
    printMap("Initial Student Scores", studentScores);

    // ... 其他操作将在后续示例中展示
    return 0;
}

2.4.2 插入元素

有几种方式可以向 std::map 中插入元素：

#include <iostream>
#include <map>
#include <string>
#include <utility> // For std::make_pair

// (printMap function from previous example)

int main() {
    std::map<std::string, int> studentScores;

    // 1. 使用 operator[]
    // 如果键不存在，则插入新元素并返回其引用；如果存在，则修改其值。
    studentScores["Alice"] = 95;
    studentScores["Bob"] = 88;
    printMap("After inserting Alice and Bob (using operator[])", studentScores);

    // 2. 使用 insert() 方法 - 接受 std::pair 或 value_type
    // 如果键已存在，insert() 不会修改值，并返回一个pair，其bool成员为false。
    studentScores.insert(std::pair<std::string, int>("Charlie", 92));
    studentScores.insert({"David", 78}); // C++11 列表初始化
    studentScores.insert(std::make_pair("Eve", 100));
    printMap("After inserting Charlie, David, Eve (using insert)", studentScores);

    // 尝试插入已存在的键，观察返回结果
    auto result = studentScores.insert({"Alice", 99}); // Alice已存在
    if (result.second) {
        std::cout << "Successfully inserted new entry for Alice.n";
    } else {
        std::cout << "Failed to insert new entry for Alice, key already exists. Value: "
                  << result.first->second << std::endl; // result.first 是指向现有元素的迭代器
    }
    printMap("After attempting to insert Alice again", studentScores);

    // 3. 使用 emplace() 方法 (C++11) - 原位构造，避免拷贝/移动
    // 类似于 insert()，如果键已存在则不插入。
    studentScores.emplace("Frank", 85);
    printMap("After emplace Frank", studentScores);

    // 4. C++17 新特性：insert_or_assign() 和 try_emplace()
    // insert_or_assign(): 如果键存在，则更新值；如果不存在，则插入。
    studentScores.insert_or_assign("Alice", 99); // 更新Alice的分数
    std::cout << "After insert_or_assign Alice to 99.n";
    printMap("Current Scores", studentScores);

    // try_emplace(): 仅当键不存在时才插入。如果键存在，则什么也不做。
    studentScores.try_emplace("Alice", 100); // Alice已存在，不会改变
    std::cout << "After try_emplace Alice to 100 (should not change).n";
    printMap("Current Scores", studentScores);

    studentScores.try_emplace("Grace", 70); // Grace不存在，会插入
    std::cout << "After try_emplace Grace to 70.n";
    printMap("Current Scores", studentScores);

    return 0;
}

2.4.3 访问元素

#include <iostream>
#include <map>
#include <string>
#include <stdexcept> // For std::out_of_range

// (printMap function from previous example)

int main() {
    std::map<std::string, int> studentScores = {
        {"Alice", 95},
        {"Bob", 88},
        {"Charlie", 92}
    };

    // 1. 使用 operator[] 访问
    std::cout << "Bob's score: " << studentScores["Bob"] << std::endl;
    // 注意：如果键不存在，operator[] 会插入一个新元素，并用默认构造函数初始化值 (int为0)。
    std::cout << "NonExistentStudent's score (accessing with []): " << studentScores["NonExistentStudent"] << std::endl;
    printMap("After accessing NonExistentStudent with []", studentScores);

    // 2. 使用 at() 方法访问
    // at() 会检查键是否存在，如果不存在则抛出 std::out_of_range 异常。
    try {
        std::cout << "Charlie's score (using at()): " << studentScores.at("Charlie") << std::endl;
        std::cout << "AnotherNonExistentStudent's score (using at()): " << studentScores.at("AnotherNonExistentStudent") << std::endl;
    } catch (const std::out_of_range& e) {
        std::cerr << "Error accessing: " << e.what() << std::endl;
    }
    printMap("After attempting to access NonExistentStudent with at()", studentScores);

    // 3. 使用 find() 方法查找
    // find() 返回一个迭代器，如果找到键则指向对应元素，否则返回 end() 迭代器。
    auto it = studentScores.find("Bob");
    if (it != studentScores.end()) {
        std::cout << "Found Bob: " << it->first << " -> " << it->second << std::endl;
        // 可以修改找到元素的值
        it->second = 90;
        std::cout << "Bob's new score: " << studentScores["Bob"] << std::endl;
    } else {
        std::cout << "Bob not found." << std::endl;
    }

    auto it_not_found = studentScores.find("Zoe");
    if (it_not_found == studentScores.end()) {
        std::cout << "Zoe not found." << std::endl;
    }
    printMap("After searching and modifying Bob's score", studentScores);

    return 0;
}

2.4.4 遍历元素

std::map 的遍历始终是按照键的有序性进行的。

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> studentScores = {
        {"Alice", 95},
        {"Bob", 88},
        {"Charlie", 92},
        {"David", 78},
        {"Eve", 100}
    };

    std::cout << "Iterating through studentScores (range-based for loop):n";
    for (const auto& pair : studentScores) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;

    std::cout << "Iterating through studentScores (using explicit iterators):n";
    for (std::map<std::string, int>::iterator it = studentScores.begin();
         it != studentScores.end(); ++it) {
        std::cout << "  " << it->first << ": " << it->second << std::endl;
    }
    std::cout << std::endl;

    std::cout << "Iterating in reverse (using reverse iterators):n";
    for (std::map<std::string, int>::reverse_iterator rit = studentScores.rbegin();
         rit != studentScores.rend(); ++rit) {
        std::cout << "  " << rit->first << ": " << rit->second << std::endl;
    }
    std::cout << std::endl;

    return 0;
}

2.4.5 删除元素

#include <iostream>
#include <map>
#include <string>

// (printMap function from previous example)

int main() {
    std::map<std::string, int> studentScores = {
        {"Alice", 95},
        {"Bob", 88},
        {"Charlie", 92},
        {"David", 78},
        {"Eve", 100}
    };
    printMap("Initial Scores", studentScores);

    // 1. 根据键删除
    size_t erased_count = studentScores.erase("Bob"); // erase() 返回被删除元素的数量 (0或1)
    if (erased_count > 0) {
        std::cout << "Successfully erased Bob.n";
    } else {
        std::cout << "Bob not found for erase.n";
    }
    printMap("After erasing Bob", studentScores);

    erased_count = studentScores.erase("NonExistent"); // 尝试删除不存在的键
    if (erased_count == 0) {
        std::cout << "NonExistent not found for erase.n";
    }
    printMap("After attempting to erase NonExistent", studentScores);

    // 2. 根据迭代器删除
    auto it = studentScores.find("Charlie");
    if (it != studentScores.end()) {
        studentScores.erase(it);
        std::cout << "Successfully erased Charlie using iterator.n";
    }
    printMap("After erasing Charlie by iterator", studentScores);

    // 3. 范围删除 (C++11)
    // 删除从 begin() 到 end() 之间的所有元素，即清空map
    // studentScores.erase(studentScores.begin(), studentScores.end());
    // std::cout << "After erasing a range (all elements):n";
    // printMap("Current Scores", studentScores);

    studentScores.clear(); // 清空所有元素
    std::cout << "After clearing all elements.n";
    printMap("Current Scores", studentScores);

    return 0;
}

2.4.6 自定义比较器

std::map 默认使用 std::less<Key> 进行键的比较，从而实现升序排列。我们可以通过提供自定义的比较器来改变排序规则。这可以是函数对象（仿函数）或 Lambda 表达式。

#include <iostream>
#include <map>
#include <string>
#include <functional> // For std::greater

// 自定义比较器（仿函数），实现降序排列
struct DescendingStringCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return a > b; // 从大到小排序
    }
};

int main() {
    // 默认升序 map
    std::map<std::string, int> defaultMap = {
        {"apple", 1}, {"banana", 2}, {"cherry", 3}
    };
    std::cout << "Default (ascending) map:n";
    for (const auto& pair : defaultMap) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 使用自定义仿函数实现降序 map
    std::map<std::string, int, DescendingStringCompare> descendingMap = {
        {"apple", 1}, {"banana", 2}, {"cherry", 3}
    };
    std::cout << "Descending map (using custom functor):n";
    for (const auto& pair : descendingMap) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 使用 std::greater 实现降序 map (对于标准类型更简洁)
    std::map<std::string, int, std::greater<std::string>> anotherDescendingMap = {
        {"apple", 1}, {"banana", 2}, {"cherry", 3}
    };
    std::cout << "Descending map (using std::greater):n";
    for (const auto& pair : anotherDescendingMap) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 使用 Lambda 表达式作为比较器
    auto lambda_compare = [](const std::string& a, const std::string& b) {
        return a.length() < b.length(); // 按字符串长度升序排列
    };
    std::map<std::string, int, decltype(lambda_compare)> lengthSortedMap(lambda_compare);
    lengthSortedMap["apple"] = 1;
    lengthSortedMap["banana"] = 2;
    lengthSortedMap["kiwi"] = 3;
    lengthSortedMap["strawberry"] = 4;
    std::cout << "Length sorted map (using lambda):n";
    for (const auto& pair : lengthSortedMap) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;

    return 0;
}

2.5 内存开销

std::map 的每个节点都包含键、值、颜色信息，以及指向父节点、左子节点和右子节点的指针。这意味着每个元素会带来额外的指针开销，通常是 3 个指针（父、左、右）加上颜色字节。对于 64 位系统，一个指针通常是 8 字节，所以额外开销至少是 24 字节，再加上键和值本身的存储，以及可能的内存对齐填充。因此，当存储大量小对象时，std::map 的内存效率可能不如其他容器。

2.6 适用场景总结

std::map 是一个非常可靠和多功能的容器，尤其适用于以下场景：

  • 需要保持键的有序性：当你需要按照键的顺序遍历元素，或者进行范围查询时，std::map 是理想选择。
  • 对最坏情况性能有严格要求：std::map 提供了 O(log N) 的最坏情况性能保证，这在实时系统或对性能稳定性有高要求的场景中非常重要。
  • 键类型可比较但难以哈希：如果你的键类型很复杂，或者很难设计一个高效且冲突少的哈希函数，但很容易进行比较（例如，通过 operator<），那么 std::map 是一个更好的选择。
  • 数据量不是极其庞大：虽然 O(log N) 效率很高，但对于千万亿级别的数据，O(1) 的常数时间会更有优势。

std::unordered_map：哈希的艺术与平均常数时间的魅力

与 std::map 形成鲜明对比的是 std::unordered_map。它牺牲了键的有序性，以换取在平均情况下的常数时间复杂度。这种性能上的飞跃使其成为许多高性能应用的首选。

3.1 底层实现：哈希表的秘密

std::unordered_map 的底层数据结构是哈希表（Hash Table）。哈希表通过一个哈希函数将键映射到一个数组的索引（通常称为“桶”或“槽”）。理想情况下，每个键都会被映射到不同的桶，从而实现 O(1) 的查找和插入。然而，不同的键可能会被哈希到同一个桶，这被称为哈希冲突（Hash Collision）。

std::unordered_map 通常采用链地址法（Separate Chaining）来解决哈希冲突。每个桶不是直接存储元素，而是存储一个链表（或类似的动态结构，如 std::forward_list 或 std::vector）的头部。当多个键哈希到同一个桶时，它们会被添加到该桶对应的链表中。

哈希表的性能高度依赖于：

  • 哈希函数的质量：一个好的哈希函数应该能够将键均匀地分布到各个桶中，减少冲突。
  • 桶的数量：足够的桶可以降低每个桶中链表的平均长度。
  • 负载因子：元素数量与桶数量的比值。

3.2 核心特性

  • 键唯一性：与 std::map 相同，键是唯一的。
  • 无序性：元素的存储顺序与键的大小无关，而是取决于哈希函数和内部桶的组织方式。
  • 前向迭代器：std::unordered_map 只提供前向迭代器，只能单向遍历元素。遍历顺序是不确定的，且通常与插入顺序也无关。
  • 动态大小：容器大小可以动态调整。当负载因子超过预设阈值时，std::unordered_map 会进行再哈希（Rehashing），即创建一个更大的桶数组，并将所有现有元素重新插入到新的桶中。

3.3 时间复杂度分析

std::unordered_map 的时间复杂度分为平均情况和最坏情况。

操作类型 平均时间复杂度 最坏时间复杂度 备注
插入 (insert) O(1) O(N) 最坏情况发生于所有元素哈希到同一个桶，或再哈希操作
查找 (find) O(1) O(N) 最坏情况同上
删除 (erase) O(1) O(N) 最坏情况同上
访问 (at, []) O(1) O(N) at() 检查键是否存在，[] 不存在则插入
迭代 (traverse) O(N) O(N) 遍历所有 N 个元素
构造 (copy) O(N) O(N^2) 复制 N 个元素，最坏情况是所有键哈希冲突，导致链表非常长

这里的 N 是 std::unordered_map 中元素的数量。平均 O(1) 的性能是其最大的吸引力，但在最坏情况下（例如，一个设计不佳的哈希函数导致大量冲突，或者恶意输入专门制造冲突），性能可能会退化到 O(N)。

3.4 关键概念详解

3.4.1 哈希函数与相等比较器

std::unordered_map 要求键类型满足两个条件：

  1. 可哈希（Hashable）：必须能够通过一个哈希函数将其转换为一个 size_t 类型的值。对于基本类型（如 int, string 等），std::hash 已经提供了默认实现。
  2. 可相等比较（Equality Comparable）：必须能够通过 operator== 判断两个键是否相等。这是为了在哈希冲突时，能够区分同一个桶中的不同键。

3.4.2 负载因子与再哈希

  • 负载因子 (Load Factor)：当前元素数量 (size()) 与桶数量 (bucket_count()) 的比值。load_factor() = size() / bucket_count()。
  • 最大负载因子 (Max Load Factor)：一个阈值，当当前负载因子超过这个阈值时，std::unordered_map 会自动触发再哈希操作。默认值通常是 1.0。
  • 再哈希 (Rehashing)：当负载因子过高时，容器会分配一个更大的桶数组，并重新计算所有现有元素的哈希值，将它们移动到新的桶中。这是一个开销较大的操作，时间复杂度为 O(N)。虽然再哈希是自动进行的，但它会导致性能的瞬时下降。可以通过 reserve() 方法预先分配足够的桶来减少再哈希的次数。

3.5 实际应用示例

3.5.1 声明与初始化

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

// 声明一个键为string，值为int的unordered_map
std::unordered_map<std::string, int> userSessions;

// 声明并初始化
std::unordered_map<int, std::string> errorCodes = {
    {404, "Not Found"},
    {500, "Internal Server Error"},
    {200, "OK"}
};

void printUnorderedMap(const std::string& title, const std::unordered_map<std::string, int>& m) {
    std::cout << title << ":n";
    for (const auto& pair : m) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    std::unordered_map<std::string, int> wordCounts = {
        {"hello", 2},
        {"world", 1},
        {"cplusplus", 3}
    };
    printUnorderedMap("Initial Word Counts", wordCounts);
    // 注意：输出顺序可能与插入顺序不同，因为它是无序的。

    return 0;
}

3.5.2 插入、访问、删除元素

这些操作的语法与 std::map 非常相似，只是底层实现和性能特性不同。

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

// (printUnorderedMap function from previous example)

int main() {
    std::unordered_map<std::string, int> inventory;

    // 插入元素
    inventory["Apple"] = 100; // 使用 operator[]
    inventory.insert({"Banana", 150}); // 使用 insert()
    inventory.emplace("Orange", 80); // 使用 emplace()
    printUnorderedMap("Current Inventory", inventory);

    // 访问元素
    std::cout << "Quantity of Apple: " << inventory["Apple"] << std::endl;
    try {
        std::cout << "Quantity of Orange (at()): " << inventory.at("Orange") << std::endl;
        std::cout << "Quantity of Grape (at()): " << inventory.at("Grape") << std::endl;
    } catch (const std::out_of_range& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }

    // 查找元素
    auto it = inventory.find("Banana");
    if (it != inventory.end()) {
        std::cout << "Found Banana: " << it->second << " units." << std::endl;
        it->second += 50; // 修改数量
    } else {
        std::cout << "Banana not found." << std::endl;
    }
    printUnorderedMap("Inventory after finding and modifying Banana", inventory);

    // 删除元素
    inventory.erase("Apple");
    std::cout << "After erasing Apple:n";
    printUnorderedMap("Current Inventory", inventory);

    // 尝试删除不存在的元素
    size_t erased_count = inventory.erase("Mango");
    if (erased_count == 0) {
        std::cout << "Mango not found for deletion.n";
    }
    printUnorderedMap("Current Inventory (after attempting to erase Mango)", inventory);

    inventory.clear();
    std::cout << "After clearing all items:n";
    printUnorderedMap("Current Inventory", inventory);

    return 0;
}

3.5.3 遍历元素

std::unordered_map 的遍历顺序是不确定的。

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

int main() {
    std::unordered_map<std::string, int> ages = {
        {"Alice", 30}, {"Bob", 25}, {"Charlie", 35}, {"David", 28}
    };

    std::cout << "Iterating through ages (range-based for loop):n";
    for (const auto& pair : ages) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 也可以使用显式迭代器
    std::cout << "Iterating through ages (explicit iterators):n";
    for (auto it = ages.begin(); it != ages.end(); ++it) {
        std::cout << "  " << it->first << ": " << it->second << std::endl;
    }
    std::cout << std::endl;

    // 访问桶信息
    std::cout << "Bucket information:n";
    std::cout << "  Total buckets: " << ages.bucket_count() << std::endl;
    std::cout << "  Load factor: " << ages.load_factor() << std::endl;
    std::cout << "  Max load factor: " << ages.max_load_factor() << std::endl;

    for (size_t i = 0; i < ages.bucket_count(); ++i) {
        std::cout << "  Bucket " << i << " has " << ages.bucket_size(i) << " elements: ";
        for (auto local_it = ages.begin(i); local_it != ages.end(i); ++local_it) {
            std::cout << "(" << local_it->first << ", " << local_it->second << ") ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;

    return 0;
}

3.5.4 自定义哈希函数与相等比较器

当键类型是自定义类时，需要为其提供哈希函数和相等比较器。

#include <iostream>
#include <unordered_map>
#include <string>
#include <functional> // For std::hash

// 自定义键类型：Point
struct Point {
    int x;
    int y;

    // 必须提供相等比较运算符
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 为 Point 类型特化 std::hash
// 方式1: 在 std 命名空间内特化 (推荐用于自定义类型)
namespace std {
    template <>
    struct hash<Point> {
        size_t operator()(const Point& p) const {
            // 简单哈希组合，通常使用 boost::hash_combine 等更复杂的算法
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

// 方式2: 自定义哈希函数对象 (如果不想特化 std::hash)
struct PointHasher {
    size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    // 使用特化的 std::hash
    std::unordered_map<Point, std::string> pointNames1;
    pointNames1[{1, 2}] = "Origin";
    pointNames1[{3, 4}] = "Destination";
    pointNames1[{1, 2}] = "New Origin"; // 更新值

    std::cout << "Using std::hash specialization:n";
    for (const auto& pair : pointNames1) {
        std::cout << "  (" << pair.first.x << ", " << pair.first.y << "): " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 使用自定义哈希函数对象
    std::unordered_map<Point, std::string, PointHasher> pointNames2;
    pointNames2[{5, 6}] = "Waypoint A";
    pointNames2[{7, 8}] = "Waypoint B";

    std::cout << "Using custom hasher object:n";
    for (const auto& pair : pointNames2) {
        std::cout << "  (" << pair.first.x << ", " << pair.first.y << "): " << pair.second << std::endl;
    }
    std::cout << std::endl;

    // 查找
    Point p_to_find = {1, 2};
    auto it = pointNames1.find(p_to_find);
    if (it != pointNames1.end()) {
        std::cout << "Found Point (" << p_to_find.x << ", " << p_to_find.y << "): " << it->second << std::endl;
    } else {
        std::cout << "Point (" << p_to_find.x << ", " << p_to_find.y << ") not found.n";
    }

    return 0;
}

注意：在 std 命名空间中特化模板是 C++ 标准允许的，但仅限于为用户自定义类型特化标准库模板。对于自定义哈希函数，通常更推荐提供一个自定义的哈希函数对象，并将其作为 std::unordered_map 的第三个模板参数。

3.6 内存开销

std::unordered_map 的内存开销包括：

  • 桶数组：一个 std::vector 或动态数组，存储指向链表头部的指针。即使没有元素，也需要占据一定的空间。
  • 元素节点：每个元素存储键、值，以及一个指向链表中下一个元素的指针。
  • 负载因子管理：当需要再哈希时，会额外分配一个更大的桶数组，并复制所有元素，这会带来临时的内存峰值。

由于哈希表的设计，桶数组的大小通常是素数，或者以 2 的幂次增长。虽然平均查找效率高，但为了减少冲突，通常会预留比实际元素数量更多的桶，这可能导致比 std::map 更多的内存占用，尤其是在元素数量较少时。

3.7 适用场景总结

std::unordered_map 是追求极致性能的首选，特别适合以下场景：

  • 需要最快的平均查找、插入和删除性能：O(1) 的平均时间复杂度在处理大量数据时具有压倒性优势。
  • 不需要元素有序性：如果键的顺序无关紧要，那么 std::unordered_map 是一个更高效的选择。
  • 键类型具有高效且分布良好的哈希函数：高质量的哈希函数是 std::unordered_map 性能的关键。
  • 可以接受偶尔的再哈希开销：再哈希操作会带来短暂的性能停顿和内存峰值，但在大多数情况下，其平均性能的优势足以弥补这一点。

性能对决与选择智慧：std::map 与 std::unordered_map 的深度比较

理解了 std::map 和 std::unordered_map 的基本原理和特性后，我们现在可以进行一次全面的对比，并探讨在实际项目中如何做出明智的选择。

4.1 核心特性对比

特性/操作 std::map std::unordered_map
底层数据结构 红黑树 (自平衡二叉搜索树) 哈希表 (通常是链地址法)
元素顺序 按键有序 (升序，可自定义比较器) 无序 (取决于哈希函数和内部实现)
键的唯一性 是 是
插入/查找/删除 O(log N) 平均 O(1), 最坏 O(N)
最坏情况性能 O(log N) O(N)
迭代器类型 双向迭代器 (支持 ++, --) 前向迭代器 (仅支持 ++)
迭代器有效性 删除元素可能使指向该元素的迭代器失效；插入不会使现有迭代器失效。 删除元素可能使指向该元素的迭代器失效；再哈希操作会使所有迭代器失效。
键类型要求 必须可比较 (operator< 或自定义比较器) 必须可哈希 (std::hash 特化或自定义哈希函数) 和 可相等比较 (operator==)
内存开销 每个节点包含键、值、3个指针、颜色信息，相对固定。 桶数组开销，每个元素包含键、值、1个指针，可能因负载因子再哈希。整体内存占用可能更高。
缓存局部性 较差。树结构节点在内存中可能分散。 较好。桶内元素通常在内存中相对连续，但不同桶可能分散。
适用场景 需要有序性、稳定最坏情况性能、复杂键比较。 追求平均极致性能、键可高效哈希、不需要有序性。

4.2 性能基准测试（概念性）

为了直观感受两者的性能差异，我们可以设计一个简单的基准测试。这个测试将模拟插入大量数据，然后进行查找和删除操作。

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
#include <chrono>
#include <vector>
#include <random>
#include <algorithm> // For std::shuffle

// Helper to generate random strings
std::string generate_random_string(size_t length) {
    const std::string CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    std::string s(length, ' ');
    std::random_device rd;
    std::mt19937 generator(rd());
    std::uniform_int_distribution<> distribution(0, CHARACTERS.size() - 1);

    for (size_t i = 0; i < length; ++i) {
        s[i] = CHARACTERS[distribution(generator)];
    }
    return s;
}

const int NUM_ELEMENTS = 1000000; // 100万元素
const int KEY_LENGTH = 10;

int main() {
    std::cout << "Benchmarking std::map vs std::unordered_map with " << NUM_ELEMENTS << " elements.n";
    std::cout << "Key length: " << KEY_LENGTH << "nn";

    std::vector<std::string> keys_to_insert(NUM_ELEMENTS);
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        keys_to_insert[i] = generate_random_string(KEY_LENGTH);
    }

    // --- std::map benchmark ---
    std::map<std::string, int> my_map;
    auto start = std::chrono::high_resolution_clock::now();

    // Insertion
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        my_map[keys_to_insert[i]] = i;
    }
    auto end_insert = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> insert_duration_map = end_insert - start;
    std::cout << "std::map - Insertion time: " << insert_duration_map.count() << " secondsn";

    // Lookup
    std::vector<std::string> keys_to_lookup = keys_to_insert;
    std::shuffle(keys_to_lookup.begin(), keys_to_lookup.end(), std::mt19937(std::random_device()())); // Shuffle for random lookup
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        volatile int val = my_map[keys_to_lookup[i]]; // Use volatile to prevent optimization
    }
    auto end_lookup = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> lookup_duration_map = end_lookup - start;
    std::cout << "std::map - Lookup time:    " << lookup_duration_map.count() << " secondsn";

    // Deletion
    std::shuffle(keys_to_lookup.begin(), keys_to_lookup.end(), std::mt19937(std::random_device()())); // Shuffle for random deletion
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        my_map.erase(keys_to_lookup[i]);
    }
    auto end_erase = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> erase_duration_map = end_erase - start;
    std::cout << "std::map - Deletion time:  " << erase_duration_map.count() << " secondsn";
    std::cout << "------------------------------------------n";

    // --- std::unordered_map benchmark ---
    std::unordered_map<std::string, int> my_unordered_map;
    start = std::chrono::high_resolution_clock::now();

    // Insertion
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        my_unordered_map[keys_to_insert[i]] = i;
    }
    end_insert = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> insert_duration_unordered_map = end_insert - start;
    std::cout << "std::unordered_map - Insertion time: " << insert_duration_unordered_map.count() << " secondsn";

    // Lookup
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        volatile int val = my_unordered_map[keys_to_lookup[i]];
    }
    end_lookup = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> lookup_duration_unordered_map = end_lookup - start;
    std::cout << "std::unordered_map - Lookup time:    " << lookup_duration_unordered_map.count() << " secondsn";

    // Deletion
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        my_unordered_map.erase(keys_to_lookup[i]);
    }
    end_erase = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> erase_duration_unordered_map = end_erase - start;
    std::cout << "std::unordered_map - Deletion time:  " << erase_duration_unordered_map.count() << " secondsn";
    std::cout << "------------------------------------------n";

    return 0;
}

运行结果分析（示例，实际结果会因机器、编译器、哈希函数质量而异）：
在我的机器上运行上述代码，对于 100 万个随机字符串键：

Benchmarking std::map vs std::unordered_map with 1000000 elements.
Key length: 10

std::map - Insertion time: 1.6345 seconds
std::map - Lookup time:    1.9872 seconds
std::map - Deletion time:  1.9901 seconds
------------------------------------------
std::unordered_map - Insertion time: 0.5218 seconds
std::unordered_map - Lookup time:    0.3876 seconds
std::unordered_map - Deletion time:  0.4211 seconds
------------------------------------------

从这个简化的基准测试可以看出，std::unordered_map 在插入、查找和删除操作上通常比 std::map 快数倍。这是 O(1) 平均时间复杂度对 O(log N) 的典型优势体现。然而，请注意，这只是一个宏观的性能对比，实际应用中的性能会受到多种因素的影响，包括键的复杂性、哈希函数的质量、数据分布以及缓存行为等。

4.3 决策矩阵：何时选择哪个容器？

选择 std::map 还是 std::unordered_map，取决于你的具体需求和权衡：

选择 std::map 的理由：

  • 需要键的有序性：如果你需要按键进行范围查询、有序遍历或保持键的排序，std::map 是唯一的选择。例如，存储用户最近登录时间，需要按时间顺序查看。
  • 对最坏情况性能有严格要求：std::map 的 O(log N) 性能是稳定的，没有哈希冲突导致的性能退化风险。这在对延迟敏感的系统中非常重要。
  • 键类型难以高效哈希：如果你的键类型很复杂，或者 std::hash 无法为其提供一个均匀分布的哈希函数，那么 std::map 的基于比较的机制可能更鲁棒。
  • 迭代器稳定性：除了被删除的元素，std::map 的迭代器在插入或删除其他元素时不会失效，这在某些复杂算法中可能是一个优势。
  • 内存使用模式：虽然单个节点开销大，但 std::map 的内存分配是渐进的，没有 std::unordered_map 那样的再哈希峰值。

选择 std::unordered_map 的理由：

  • 追求平均极致性能：如果你最关心平均情况下的查找、插入和删除速度，并且不需要键的有序性，那么 std::unordered_map 是首选。例如，构建一个单词计数器或缓存系统。
  • 键类型易于哈希且 operator== 高效：对于 int, string 等内置类型或自定义类型，如果可以提供一个高质量的哈希函数和高效的相等比较，unordered_map 将发挥其最大优势。
  • 数据量非常庞大：在 N 很大时，O(1) 和 O(log N) 的差距会变得非常显著。
  • 可接受再哈希开销：如果你的应用能够容忍偶尔的性能波动（再哈希），那么 unordered_map 的平均性能将带来巨大的收益。可以通过 reserve() 预分配桶来缓解这个问题。

4.4 混合使用场景

在某些复杂的应用中，你可能需要结合两者的优势。例如：

  • 场景：你需要快速查找元素，但有时也需要按键的范围进行有序查询。
  • 方案：你可以主要使用 std::unordered_map 进行快速查找，并维护一个辅助的 std::map 或 std::vector (在每次需要有序性时排序) 来处理有序操作。当然，这种方式会增加内存和同步的复杂性。更常见的是，如果有序操作不频繁，可以从 unordered_map 中提取键值对到 std::vector<std::pair<Key, Value>> 中，然后进行排序。

进阶实践与优化技巧

掌握了 std::map 和 std::unordered_map 的基本用法和选择原则后，我们来看一些更高级的实践技巧，以进一步提升代码的效率和健壮性。

5.1 元素插入与更新的精细控制

C++11 引入的 emplace 系列函数以及 C++17 引入的 insert_or_assign 和 try_emplace 提供了更高效和语义更清晰的插入/更新方式。

  • insert()：接受 std::pair 或 value_type 对象。如果键已存在，不插入新元素，返回指向现有元素的迭代器和 false。
  • operator[]：如果键不存在，会先默认构造一个值类型对象，然后插入到容器中。这可能导致不必要的默认构造和赋值操作。
  • emplace()：在容器内部直接构造元素，避免了不必要的拷贝或移动。它接受与键值对构造函数相同的参数。如果键已存在，它不会插入新元素。 
    std::map<int, std::string> myMap;
myMap.emplace(1, "one"); // 直接构造 pair<const int, string>
myMap.emplace(std::piecewise_construct,
              std::forward_as_tuple(2), // 构造键
              std::forward_as_tuple(5, 'a')); // 构造值 (string(5, 'a'))
  • insert_or_assign() (C++17)：提供“如果键存在则更新，不存在则插入”的原子操作。 
    std::map<int, std::string> myMap;
myMap.insert_or_assign(1, "new_one"); // 如果1不存在则插入，如果存在则更新为"new_one"
  • try_emplace() (C++17)：提供“如果键不存在则插入，如果存在则不作任何操作”的语义。 
    std::map<int, std::string> myMap;
myMap.try_emplace(1, "original_one"); // 1不存在，插入
myMap.try_emplace(1, "another_one"); // 1已存在，不作任何操作

    在需要精确控制插入行为和追求性能时，优先考虑 emplace、insert_or_assign 和 try_emplace。

5.2 自定义键类型的高级处理

当使用自定义类作为键时，需要确保它满足容器的要求。

  • std::map (基于比较)：

    • 键类型必须定义 operator<，或者提供一个自定义的比较器。
    • operator< 必须满足严格弱序（Strict Weak Ordering）原则：
      • 反自反性：!(a < a) 永远为真。
      • 非对称性：如果 a < b 为真，则 b < a 必须为假。
      • 传递性：如果 a < b 且 b < c 为真，则 a < c 必须为真。
      • 不可比性传递性：如果 a 不小于 b 且 b 不小于 a 为真（即 a 和 b 等价），并且 b 不小于 c 且 c 不小于 b 为真（即 b 和 c 等价），则 a 不小于 c 且 c 不小于 a 必须为真（即 a 和 c 等价）。

  • std::unordered_map (基于哈希)：

    • 键类型必须定义 operator==。
    • 键类型必须提供一个哈希函数。可以通过以下两种方式之一实现：
      1. 特化 std::hash<KeyType>：在 std 命名空间中为你的自定义类型特化 std::hash 模板。 
        namespace std {
    template <>
    struct hash<MyCustomKey> {
        size_t operator()(const MyCustomKey& k) const {
            // 实现高效且冲突少的哈希算法
            size_t h1 = std::hash<int>()(k.member1);
            size_t h2 = std::hash<std::string>()(k.member2);
            return h1 ^ (h2 << 1); // 简单组合
        }
    };
}
      2. 提供自定义哈希函数对象：创建一个仿函数作为 std::unordered_map 的第三个模板参数。 
        struct MyCustomKeyHasher {
    size_t operator()(const MyCustomKey& k) const {
        size_t h1 = std::hash<int>()(k.member1);
        size_t h2 = std::hash<std::string>()(k.member2);
        return h1 ^ (h2 << 1);
    }
};
std::unordered_map<MyCustomKey, ValueType, MyCustomKeyHasher> myMap;
    • 重要原则：如果 key1 == key2 为真，那么 hash(key1) 必须等于 hash(key2)。反之不成立（哈希冲突）。

5.3 std::unordered_map 的负载因子与桶管理

优化 std::unordered_map 性能的关键在于有效管理其底层哈希表。

  • max_load_factor(): 获取或设置最大负载因子。将其设置得较低可以减少冲突，但会增加内存使用和再哈希频率。将其设置得较高可以节省内存，但可能导致链表过长，降低 O(1) 性能。默认值通常是 1.0。
  • reserve(count): 预留至少能容纳 count 个元素的桶空间。如果你知道大致的元素数量，在插入前调用 reserve() 可以避免多次再哈希操作，从而提高插入效率。
  • rehash(count): 强制容器重新哈希到至少 count 个桶。
#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> myMap;

    std::cout << "Initial bucket count: " << myMap.bucket_count() << std::endl;
    std::cout << "Initial load factor: " << myMap.load_factor() << std::endl;
    std::cout << "Max load factor: " << myMap.max_load_factor() << std::endl;

    // 预留空间，避免多次再哈希
    myMap.reserve(100); // 预留足够容纳100个元素的桶
    std::cout << "After reserve(100), bucket count: " << myMap.bucket_count() << std::endl;

    for (int i = 0; i < 50; ++i) {
        myMap[i] = std::to_string(i);
    }
    std::cout << "After inserting 50 elements, load factor: " << myMap.load_factor() << std::endl;

    // 尝试降低最大负载因子，可能触发再哈希
    myMap.max_load_factor(0.7f);
    std::cout << "After setting max_load_factor(0.7f), current load factor: " << myMap.load_factor() << std::endl;
    std::cout << "Bucket count: " << myMap.bucket_count() << std::endl;

    // 强制再哈希到更多桶
    myMap.rehash(200);
    std::cout << "After rehash(200), bucket count: " << myMap.bucket_count() << std::endl;
    std::cout << "Load factor: " << myMap.load_factor() << std::endl;

    return 0;
}

5.4 异常安全与错误处理

  • at() vs operator[]:
    • at(key)：如果键不存在，会抛出 std::out_of_range 异常。适用于你确定键应该存在，或者需要明确区分“键不存在”和“值是默认值”的情况。
    • operator[](key)：如果键不存在，会插入一个新元素（默认构造值），并返回其引用。如果键存在，则返回其引用。适合于“如果存在则访问，不存在则插入”的语义，但要注意可能意外地插入元素。
  • find(): find(key) 返回一个迭代器。如果键不存在，返回 end() 迭代器。这是查找元素最安全且高效的方式，不会修改容器。

5.5 键类型选择

  • 基本类型 (int, char, float 等)：效率最高，无需特殊处理。
  • std::string: 效率也很高，std::hash<std::string> 通常表现良好。
  • 指针：除非你确实想比较指针地址，否则通常不是一个好主意。如果你想比较指针指向的内容，应该使用内容作为键。
  • 自定义结构/类：如前所述，需要提供 operator< (for map) 或 operator== 和 std::hash 特化 (for unordered_map)。
  • std::string_view (C++17)：对于 std::unordered_map，如果你的键是字符串字面量或已知生命周期的字符串片段，使用 std::string_view 可以避免字符串拷贝，提升性能。但需要注意 std::string_view 的生命周期管理。

实战案例分析

现在我们将通过一些具体的实战场景，来展示 std::map 和 std::unordered_map 各自的优势和典型应用。

6.1 std::map 的适用场景

6.1.1 配置管理与字典

场景：你需要读取一个配置文件，其中包含键值对，并且希望这些配置项能够按照名称（键）的字母顺序进行存储和查找。当展示给用户或进行调试时，有序的配置列表会更清晰。

实现：

#include <iostream>
#include <map>
#include <string>
#include <fstream>
#include <sstream>

class ConfigurationManager {
public:
    std::map<std::string, std::string> config;

    void loadConfig(const std::string& filename) {
        std::ifstream file(filename);
        if (!file.is_open()) {
            std::cerr << "Error: Could not open config file " << filename << std::endl;
            return;
        }

        std::string line;
        while (std::getline(file, line)) {
            // 忽略空行和注释
            if (line.empty() || line[0] == '#') {
                continue;
            }

            size_t delimiterPos = line.find('=');
            if (delimiterPos != std::string::npos) {
                std::string key = line.substr(0, delimiterPos);
                std::string value = line.substr(delimiterPos + 1);
                // 移除键和值可能存在的首尾空格
                key.erase(0, key.find_first_not_of(" t"));
                key.erase(key.find_last_not_of(" t") + 1);
                value.erase(0, value.find_first_not_of(" t"));
                value.erase(value.find_last_not_of(" t") + 1);
                config[key] = value;
            }
        }
        file.close();
    }

    std::string getValue(const std::string& key, const std::string& defaultValue = "") const {
        auto it = config.find(key);
        if (it != config.end()) {
            return it->second;
        }
        return defaultValue;
    }

    void printConfig() const {
        std::cout << "--- Current Configuration (Sorted by Key) ---n";
        for (const auto& pair : config) {
            std::cout << pair.first << " = " << pair.second << std::endl;
        }
        std::cout << "---------------------------------------------n";
    }
};

int main() {
    // 创建一个示例配置文件
    std::ofstream("app.conf") <<
        "# Application Configurationn"
        "DATABASE_HOST = localhostn"
        "DATABASE_PORT = 5432n"
        "DEBUG_MODE = truen"
        "LOG_LEVEL = INFOn";

    ConfigurationManager mgr;
    mgr.loadConfig("app.conf");
    mgr.printConfig();

    std::cout << "Database Host: " << mgr.getValue("DATABASE_HOST") << std::endl;
    std::cout << "Non-existent Key: " << mgr.getValue("API_KEY", "NOT_SET") << std::endl;

    return 0;
}

分析：std::map 确保了配置项总是按照键的字母顺序排列，这对于人类阅读和调试非常方便。查找单个配置项的 O(log N) 性能对于配置这种通常数量不大的数据来说是完全足够的。

6.1.2 有序日志索引

场景：你需要根据时间戳或事件ID（这些ID通常是递增的）存储日志条目，并且能够快速检索特定范围的日志，或者按时间顺序遍历所有日志。

实现：

#include <iostream>
#include <map>
#include <string>
#include <chrono>
#include <iomanip> // For std::put_time

// 模拟日志条目
struct LogEntry {
    std::string message;
    std::string level;
    // ... 其他字段

    std::string toString() const {
        return "[" + level + "] " + message;
    }
};

// 使用时间戳作为键
using Timestamp = std::chrono::time_point<std::chrono::system_clock>;
std::map<Timestamp, LogEntry> logStore;

// 辅助函数：获取当前时间戳
Timestamp now() {
    return std::chrono::system_clock::now();
}

// 辅助函数：将时间戳格式化为字符串
std::string formatTimestamp(Timestamp ts) {
    auto time_t_val = std::chrono::system_clock::to_time_t(ts);
    std::tm tm_buf;
#ifdef _WIN32
    localtime_s(&tm_buf, &time_t_val);
#else
    localtime_r(&time_t_val, &tm_buf);
#endif
    std::stringstream ss;
    ss << std::put_time(&tm_buf, "%Y-%m-%d %H:%M:%S");
    return ss.str();
}

void addLog(const std::string& message, const std::string& level) {
    logStore[now()] = {message, level};
}

void printLogsInRange(Timestamp start, Timestamp end) {
    std::cout << "n--- Logs from " << formatTimestamp(start) << " to " << formatTimestamp(end) << " ---n";
    // lower_bound 返回第一个键 >= start 的迭代器
    // upper_bound 返回第一个键 > end 的迭代器
    for (auto it = logStore.lower_bound(start); it != logStore.upper_bound(end); ++it) {
        std::cout << "[" << formatTimestamp(it->first) << "] " << it->second.toString() << std::endl;
    }
    std::cout << "---------------------------------------------------------n";
}

int main() {
    addLog("Application started.", "INFO");
    std::this_thread::sleep_for(std::chrono::milliseconds(100)); // 模拟时间流逝
    Timestamp t1 = now();
    addLog("User 'Alice' logged in.", "INFO");
    std::this_thread::sleep_for(std::chrono::milliseconds(200));
    addLog("Failed to connect to database.", "ERROR");
    Timestamp t2 = now();
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
    addLog("Processing request for report.", "DEBUG");
    std::this_thread::sleep_for(std::chrono::milliseconds(150));
    addLog("Report generated successfully.", "INFO");

    std::cout << "--- All Logs (Sorted by Timestamp) ---n";
    for (const auto& pair : logStore) {
        std::cout << "[" << formatTimestamp(pair.first) << "] " << pair.second.toString() << std::endl;
    }

    // 查询特定时间范围内的日志
    printLogsInRange(t1, t2);

    return 0;
}

分析：std::map 能够自然地根据时间戳对日志进行排序。lower_bound() 和 upper_bound() 方法可以高效地进行范围查询，这对于日志分析和筛选非常有用。

6.2 std::unordered_map 的适用场景

6.2.1 缓存系统

场景：构建一个网页内容缓存，其中 URL 是键，网页内容是值。需要以最快的速度存取数据。

实现：

#include <iostream>
#include <unordered_map>
#include <string>
#include <chrono>
#include <thread> // For std::this_thread::sleep_for

class WebCache {
public:
    std::unordered_map<std::string, std::string> cache;

    std::string getPageContent(const std::string& url) {
        auto it = cache.find(url);
        if (it != cache.end()) {
            std::cout << "Cache hit for: " << url << std::endl;
            return it->second;
        } else {
            std::cout << "Cache miss for: " << url << ". Fetching...n";
            // 模拟从网络获取数据
            std::this_thread::sleep_for(std::chrono::milliseconds(500));
            std::string content = "<html><body>Content of " + url + "</body></html>";
            cache[url] = content; // 存入缓存
            std::cout << "Fetched and cached: " << url << std::endl;
            return content;
        }
    }

    void clearCache() {
        cache.clear();
        std::cout << "Cache cleared.n";
    }

    void printCacheStatus() const {
        std::cout << "n--- Cache Status ---n";
        std::cout << "Size: " << cache.size() << std::endl;
        std::cout << "Bucket count: " << cache.bucket_count() << std::endl;
        std::cout << "Load factor: " << cache.load_factor() << std::endl;
        std::cout << "---------------------n";
    }
};

int main() {
    WebCache myCache;
    myCache.printCacheStatus();

    std::cout << myCache.getPageContent("https://example.com/page1") << std::endl;
    std::cout << myCache.getPageContent("https://example.com/page2") << std::endl;
    std::cout << myCache.getPageContent("https://example.com/page1") << std::endl; // Cache hit

    myCache.printCacheStatus();

    // 假设有大量URL需要缓存，可以预先保留桶
    myCache.cache.reserve(1000); // 预留1000个元素的空间
    std::cout << "nAfter reserving 1000 buckets:n";
    myCache.printCacheStatus();

    std::cout << myCache.getPageContent("https://example.com/page3") << std::endl;

    return 0;
}

分析：缓存系统最核心的需求是快速查找。std::unordered_map 的平均 O(1) 查找性能完美契合这一需求。预先调用 reserve() 可以优化大规模插入时的性能，避免频繁的再哈希。

6.2.2 单词计数器

场景：统计一个文本文件中每个单词出现的频率。单词的顺序不重要，只关心最终的计数。

实现：

#include <iostream>
#include <unordered_map>
#include <string>
#include <fstream>
#include <sstream>
#include <algorithm> // For std::transform

// 辅助函数：将字符串转换为小写并移除标点
std::string cleanWord(std::string word) {
    // 移除标点
    word.erase(std::remove_if(word.begin(), word.end(), ::ispunct), word.end());
    // 转换为小写
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);
    return word;
}

int main() {
    std::unordered_map<std::string, int> wordCounts;
    std::ifstream file("sample.txt");

    if (!file.is_open()) {
        std::cerr << "Error: Could not open sample.txt" << std::endl;
        // 创建一个示例文件
        std::ofstream("sample.txt") <<
            "Hello world! This is a sample text file.n"
            "World is great. Hello C++.n"
            "C++ programming is fun and challenging.n";
        file.open("sample.txt");
        if (!file.is_open()) {
            std::cerr << "Error: Failed to create and open sample.txt" << std::endl;
            return 1;
        }
    }

    std::string word;
    while (file >> word) {
        word = cleanWord(word);
        if (!word.empty()) {
            wordCounts[word]++;
        }
    }
    file.close();

    std::cout << "--- Word Counts ---n";
    for (const auto& pair : wordCounts) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << "--------------------n";

    // 查找特定单词的计数
    std::string searchWord = "hello";
    auto it = wordCounts.find(searchWord);
    if (it != wordCounts.end()) {
        std::cout << "Count of '" << searchWord << "': " << it->second << std::endl;
    } else {
        std::cout << "'" << searchWord << "' not found.n";
    }

    return 0;
}

分析：在单词计数器中，我们频繁地执行查找和更新操作 (wordCounts[word]++)。std::unordered_map 的平均 O(1) 性能使得这个过程非常高效，即使处理大型文本文件也能表现出色。单词的最终输出顺序并不重要，

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注