C++ STL之std::map：红黑树的魔法与性能测试

2023-11-23 微信公众号囧囧妹

最近在使用C++写代码，也是刚接触C++，恰巧碰到一个需要使用map的地方，不知道其查找元素的性能怎么样，所以研究了下，做个记录，目前从x86平台测试map查找一个元素大概需要2us，这里你需要考虑在自身硬件平台比如arm，做一些cpu加压情况下再查看map效率以评估map是否满足业务需求。

在C++编程的世界中，STL（标准模板库）一直以其强大的数据结构和算法而著称。其中，std::map是STL提供的一个关联容器，它的核心是红黑树（Red-Black Tree）数据结构。红黑树是一种自平衡的二叉查找树，以其出色的性能和平衡机制而备受推崇。

本文将深入探讨std::map以及其核心红黑树的原理，解释其关键特性，包括插入、查找和删除操作，以及有序性的优势。我们还将进行性能测试，以展示std::map在实际应用中的卓越性能。

一、红黑树,std::map的核心

std::map的核心数据结构是红黑树（Red-Black Tree）数据结构。红黑树是一种自平衡二叉查找树，它具有以下特性：

每个节点是红色或黑色：每个节点都被标记为红色或黑色，这是红黑树的基本性质之一。
根节点是黑色：树的根节点始终是黑色的。
每个叶子节点（NIL节点，通常表示为黑色）都被认为是黑色的：NIL节点是树的末端节点，它们通常被表示为黑色。
如果一个节点是红色的，那么它的子节点必须是黑色的：这一性质确保没有两个相邻的红色节点。
从任何给定节点到其后代叶子节点的每条路径都包含相同数量的黑色节点：这个性质保证了树的平衡。

这些性质保证了红黑树的平衡性，使得树的高度保持相对较小，从而提供了高效的查找、插入和删除操作。

二、std::map常见操作

1.插入操作：保持平衡

当您向std::map插入新的键值对时，红黑树需要进行一系列旋转和着色操作，以保持树的平衡。这确保了即使在大规模数据集下，插入操作仍然高效。

// 插入操作示例
std::map<int, std::string> myMap;
myMap[42] = "Hello, World!";

在插入操作中，红黑树遵循一些规则，例如：

新插入的节点通常是红色的。
如果插入破坏了红黑树的性质，就需要执行旋转和着色操作来恢复平衡。

2.查找操作：速度与效率

std::map的查找操作非常高效，因为红黑树的结构使得它可以迅速定位到所需的节点。查找操作会从根节点开始，根据键值比较逐步沿树向下移动，直到找到目标节点或确定目标节点不在树中。这个过程的时间复杂度是O(log N)，其中N是树中元素的数量。

// 查找操作示例
auto result = myMap.find(42);
if (result != myMap.end()) {
    std::cout << "Found: " << result->second << std::endl;
} else {
    std::cout << "Not found!" << std.endl;
}

3.删除操作：平衡的维护

删除操作也是相对复杂的，因为它需要保持树的平衡。当删除一个节点时，可能会引起树的不平衡，需要执行旋转和着色操作来修复它。这些操作确保了红黑树的性质仍然得以维持。

// 删除操作示例
myMap.erase(42);

在删除操作中，红黑树也遵循一系列规则，包括：

如果删除的节点是红色的，可能不会破坏树的性质。
如果删除的节点是黑色的，就可能会引发平衡问题，需要执行一系列的操作来修复。

4.有序性：按键排序

std::map中的元素是按键值有序排列的，这意味着您可以使用迭代器来遍历元素，或者进行范围查找。

// 使用迭代器遍历示例
for (const auto& pAIr : myMap) {
    std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}

三、性能测试:查找操作

下面是一个性能测试示例，因为我对查找某个元素的性能是有要求的，所以做了一个简单测试：

#include <IOStream>
#include <map>
#include <random>
#include <chrono>

int main() {
    std::map<int, int> testMap;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dist(1, 1000000);

    // 插入100,000个随机键值对
    for (int i = 0; i < 100000; ++i) {
        int key = dist(gen);
        int value = i;
        testMap[key] = value;
    }

    // 测试查找操作的效率
    int totalIterations = 100000;
    int foundCount = 0;
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < totalIterations; ++i) {
        int key = dist(gen);
        if (testMap.find(key) != testMap.end()) {
            foundCount++;
        }
    }

    std::chrono::high_resolution_clock::time_point end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = std::chrono::duration_cast<std::chrono::duration<double>>(end - start);

    std::cout << "查找 " << totalIterations << " 个元素所用时间: " << duration.count() << " 秒" << std::endl;
    std::cout << "找到 " << foundCount << " 个元素" << std::endl;
    std::cout << "查找单个元素耗时: " << (duration.count()*1000000) / totalIterations << " 微秒" << std::endl;

    return 0;
}

我们首先插入了100,000个随机键值对，然后执行查找操作，并记录查找到的元素数量，并计算时间。

使用g++编译执行结果：

C++ STL之std::map：红黑树的魔法与性能测试

四、总结

std::map是C++编程中的神奇工具，它提供高效的查找、插入和删除操作，并按键排序数据。红黑树的自平衡性确保了它在各种操作下都能保持高效性。无论是实现关键功能还是性能测试，std::map都展现了其出色之处，使其成为处理大规模数据集的理想之选。