引言
最近在使用C++写代码，也是刚接触C++，恰巧碰到一个需要使用map的地方，不知道其查找元素的性能怎么样，所以研究了下，做个记录，目前从x86平台测试map查找一个元素大概需要2us，这里你需要考虑在自身硬件平台比如arm，做一些cpu加压情况下再查看map效率以评估map是否满足业务需求。
红黑树,std::map的核心
std::map的核心数据结构是红黑树（Red-Black Tree）数据结构。红黑树是一种自平衡二叉查找树，它具有以下特性：
每个节点是红色或黑色：每个节点都被标记为红色或黑色，这是红黑树的基本性质之一。
根节点是黑色：树的根节点始终是黑色的。
每个叶子节点（NIL节点，通常表示为黑色）都被认为是黑色的：NIL节点是树的末端节点，它们通常被表示为黑色。
如果一个节点是红色的，那么它的子节点必须是黑色的：这一性质确保没有两个相邻的红色节点。
从任何给定节点到其后代叶子节点的每条路径都包含相同数量的黑色节点：这个性质保证了树的平衡。
std::map常见操作
当您向std::map插入新的键值对时，红黑树需要进行一系列旋转和着色操作，以保持树的平衡。这确保了即使在大规模数据集下，插入操作仍然高效。
// 插入操作示例std::map<int, std::string> myMap;myMap[42] = "Hello, World!";
在插入操作中，红黑树遵循一些规则，例如：
// 查找操作示例auto result = myMap.find(42);if (result != myMap.end()) {std::cout << "Found: " << result->second << std::endl;} else {std::cout << "Not found!" << std.endl;}
// 删除操作示例myMap.erase(42);
在删除操作中，红黑树也遵循一系列规则，包括：
如果删除的节点是红色的，可能不会破坏树的性质。
如果删除的节点是黑色的，就可能会引发平衡问题，需要执行一系列的操作来修复。
// 使用迭代器遍历示例for (const auto& pair : myMap) {std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;}
性能测试:查找操作
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;}
总结
觉得文章不错，点击“分享”、“赞”、“在看” 呗！
