最近在使用C++写代码，也是刚接触C++，恰巧碰到一个需要使用map的地方，不知道其查找元素的性能怎么样，所以研究了下，做个记录，目前从x86平台测试map查找一个元素大概需要2us，这里你需要考虑在自身硬件平台比如arm，做一些cpu加压情况下再查看map效率以评估map是否满足业务需求。
在C++编程的世界中，STL（标准模板库）一直以其强大的数据结构和算法而著称。其中，std::map是STL提供的一个关联容器，它的核心是红黑树（Red-Black Tree）数据结构。红黑树是一种自平衡的二叉查找树，以其出色的性能和平衡机制而备受推崇。
本文将深入探讨std::map以及其核心红黑树的原理，解释其关键特性，包括插入、查找和删除操作，以及有序性的优势。我们还将进行性能测试，以展示std::map在实际应用中的卓越性能。
std::map的核心数据结构是红黑树（Red-Black Tree）数据结构。红黑树是一种自平衡二叉查找树，它具有以下特性：
这些性质保证了红黑树的平衡性，使得树的高度保持相对较小，从而提供了高效的查找、插入和删除操作。
当您向std::map插入新的键值对时，红黑树需要进行一系列旋转和着色操作，以保持树的平衡。这确保了即使在大规模数据集下，插入操作仍然高效。
// 插入操作示例std::map<int, std::string> myMap;myMap[42] = "Hello, World!";在插入操作中，红黑树遵循一些规则，例如：
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;}删除操作也是相对复杂的，因为它需要保持树的平衡。当删除一个节点时，可能会引起树的不平衡，需要执行旋转和着色操作来修复它。这些操作确保了红黑树的性质仍然得以维持。
// 删除操作示例myMap.erase(42);在删除操作中，红黑树也遵循一系列规则，包括：
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++编译执行结果：
std::map是C++编程中的神奇工具，它提供高效的查找、插入和删除操作，并按键排序数据。红黑树的自平衡性确保了它在各种操作下都能保持高效性。无论是实现关键功能还是性能测试，std::map都展现了其出色之处，使其成为处理大规模数据集的理想之选。
本文链接：http://www.28at.com/showinfo-26-32434-0.htmlC++ STL之std::map：红黑树的魔法与性能测试
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
上一篇： 21个优秀开源网络爬虫库，适合Python、Java、Go、JavaScript开发语言
下一篇： C语言代码：数字雨
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号