您当前的位置:首页 > 电脑百科 > 程序开发 > 语言 > C/C++/C#

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

时间:2023-11-23 13:40:04  来源:微信公众号  作者:囧囧妹

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

C++ STL之std::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都展现了其出色之处,使其成为处理大规模数据集的理想之选。



Tags:C++   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
C++常见避坑指南
C++ 从入门到放弃?本文主要总结了在C++开发或review过程中常见易出错点做了归纳总结,希望借此能增进大家对C++的了解,减少编程出错,提升工作效率,也可以作为C++开发的避坑攻略。...【详细内容】
2024-04-03  Search: C++  点击:(4)  评论:(0)  加入收藏
C++ 之父反驳白宫警告:自诞生第一天起,C++ 的目标就一直是提高安全性
整理 | 郑丽媛上个月,美国白宫国家网络主任办公室(ONCD)在一份主题为《回到基础构件:通往安全软件之路》的 19 页 PDF 报告中,呼吁开发人员停止使用容易出现内存安全漏洞的编程语...【详细内容】
2024-03-25  Search: C++  点击:(4)  评论:(0)  加入收藏
八个 C++ 开源项目,帮助初学者进阶成长
通过参与或阅读开源项目的源代码,你可以获得丰富的实践机会。实际的项目代码比简单的教程更具挑战性,可以帮助你深入理解 C++ 的各种概念和技术。1.ThreadPool一个简单的 C++1...【详细内容】
2024-03-22  Search: C++  点击:(21)  评论:(0)  加入收藏
C++多线程编程:解锁性能与并发的奥秘
今天我们将深入探讨C++中的多线程编程,揭示多线程如何解锁性能潜力,提高程序的并发性能。什么是多线程?在计算机科学中,多线程是指一个进程(程序的执行实例)中的多个线程同时执行...【详细内容】
2024-02-03  Search: C++  点击:(68)  评论:(0)  加入收藏
C++代码优化攻略
今天我们将深入探讨C++性能优化的世界。在当今软件开发的浪潮中,高性能的代码是必不可少的。无论是开发桌面应用、移动应用,还是嵌入式系统,性能都是关键。1. 选择合适的数据结...【详细内容】
2024-01-26  Search: C++  点击:(113)  评论:(0)  加入收藏
C++质数检测器的设计与实现​
质数,作为数学中的一个基本概念,一直以其独特的性质吸引着众多研究者和爱好者。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。在实际应用中,质数检测也扮演着...【详细内容】
2024-01-15  Search: C++  点击:(110)  评论:(0)  加入收藏
指针变量在C/C++中的内存占用
在编程领域,尤其是C和C++这类底层语言中,指针是一个核心概念,它允许程序直接操作内存地址。然而,关于指针本身在内存中占用的空间大小,却常常让初学者感到困惑。本文将深入探讨这...【详细内容】
2024-01-09  Search: C++  点击:(94)  评论:(0)  加入收藏
C++的面向对象编程:深入解析与理解
当我们谈论C++时,面向对象编程(OOP)是一个无法回避的话题。那么,C++的面向对象究竟是什么?为什么它如此重要?本文将从基本概念到实际应用,为您详细解析C++中的面向对象编程。一、面...【详细内容】
2024-01-03  Search: C++  点击:(95)  评论:(0)  加入收藏
有什么好用的C/C++源代码混淆工具?
开始使用ipaguard前言iOS加固保护是直接针对ios ipa二进制文件的保护技术,可以对iOS APP中的可执行文件进行深度混淆、加密。使用任何工具都无法逆向、破解还原源文件。对APP...【详细内容】
2023-12-29  Search: C++  点击:(117)  评论:(0)  加入收藏
C++中new与malloc:内存分配机制深度解析
本文旨在深入探讨C++中new和malloc两种内存分配机制的区别。通过对比它们在内存分配、初始化、错误处理、调用构造函数/析构函数、类型转换和使用便捷性等方面的不同,我们将...【详细内容】
2023-12-27  Search: C++  点击:(126)  评论:(0)  加入收藏
▌简易百科推荐
C++常见避坑指南
C++ 从入门到放弃?本文主要总结了在C++开发或review过程中常见易出错点做了归纳总结,希望借此能增进大家对C++的了解,减少编程出错,提升工作效率,也可以作为C++开发的避坑攻略。...【详细内容】
2024-04-03  腾讯技术工程    Tags:C++   点击:(4)  评论:(0)  加入收藏
C++ 之父反驳白宫警告:自诞生第一天起,C++ 的目标就一直是提高安全性
整理 | 郑丽媛上个月,美国白宫国家网络主任办公室(ONCD)在一份主题为《回到基础构件:通往安全软件之路》的 19 页 PDF 报告中,呼吁开发人员停止使用容易出现内存安全漏洞的编程语...【详细内容】
2024-03-25    CSDN  Tags:C++   点击:(4)  评论:(0)  加入收藏
八个 C++ 开源项目,帮助初学者进阶成长
通过参与或阅读开源项目的源代码,你可以获得丰富的实践机会。实际的项目代码比简单的教程更具挑战性,可以帮助你深入理解 C++ 的各种概念和技术。1.ThreadPool一个简单的 C++1...【详细内容】
2024-03-22  AI让生活更美好  微信公众号  Tags:C++   点击:(21)  评论:(0)  加入收藏
C# 中15个值得收藏的开源项目推荐
在开源的世界里,C# 编程语言也占有一席之地。这些开源项目涵盖了多个领域,从框架、库到工具,它们为C#开发者提供了丰富的资源和工具,帮助他们更高效地开发、测试和部署应用程序...【详细内容】
2024-03-20  程序员编程日记  微信公众号  Tags:C#   点击:(29)  评论:(0)  加入收藏
C#异步编程:Task.Run vs. async-await,掌握基础与高级用法
概述:C#中的异步编程有两主要方式:Task.Run用于在后台线程执行同步操作,而async-await更适用于清晰表达异步流程。基础用法展示了它们的简单应用,高级用法则演示了它们的结合使...【详细内容】
2024-03-09  架构师老卢  今日头条  Tags:C#   点击:(22)  评论:(0)  加入收藏
C++多线程编程:解锁性能与并发的奥秘
今天我们将深入探讨C++中的多线程编程,揭示多线程如何解锁性能潜力,提高程序的并发性能。什么是多线程?在计算机科学中,多线程是指一个进程(程序的执行实例)中的多个线程同时执行...【详细内容】
2024-02-03     AI让生活更美好  Tags:C++   点击:(68)  评论:(0)  加入收藏
C++代码优化攻略
今天我们将深入探讨C++性能优化的世界。在当今软件开发的浪潮中,高性能的代码是必不可少的。无论是开发桌面应用、移动应用,还是嵌入式系统,性能都是关键。1. 选择合适的数据结...【详细内容】
2024-01-26  AI让生活更美好  微信公众号  Tags:C++   点击:(113)  评论:(0)  加入收藏
C# 线程本地存储为什么线程间值不一样
为什么用 ThreadStatic 标记的字段,只有第一个线程拿到了初始值,其他线程都是默认值,让我能不能帮他解答一下,尼玛,我也不是神仙什么都懂,既然问了,那我试着帮他解答一下,也给后面类...【详细内容】
2024-01-26  一线码农聊技术  微信公众号  Tags:C#   点击:(66)  评论:(0)  加入收藏
C++质数检测器的设计与实现​
质数,作为数学中的一个基本概念,一直以其独特的性质吸引着众多研究者和爱好者。质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的数。在实际应用中,质数检测也扮演着...【详细内容】
2024-01-15  鲨鱼编程  微信公众号  Tags:C++   点击:(110)  评论:(0)  加入收藏
C# 登顶!超越Java或非空想
整理丨诺亚出品 | 51CTO技术栈(微信号:blog51cto)近日,TIOBE编程社区公布年度编程语言,此次摘得这一桂冠的是C#。这也是C#在TIOBE二十多年评选历史中首次赢得这一年度大奖。C#虽...【详细内容】
2024-01-15    51CTO  Tags:C#   点击:(112)  评论:(0)  加入收藏
站内最新
站内热门
站内头条