c++ map find方法源码解析1.背景2.map源码3.结论

93 阅读 0 评论 62 点赞

我是靠谱客的博主典雅果汁，最近开发中收集的这篇文章主要介绍c++ map find方法源码解析1.背景2.map源码3.结论，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.背景

最近，发生了一次奇怪的问题：

用const char*作为map的key，定制比较器（采用strcmp实现），同时用了多线程的技术，在map.find()时候有几率发生死循环，通过windbg调试定位问题，发现是

在map.find()时候发生了死循环，进而导致执行该过程的线程拿到锁了，但无法释放，后续其他线程一直等待该锁，从而发生假的“死锁”（实际为死循环）。

结合map的源码、对应DMP文件的堆栈和相关变量额值（主要为发生死循环的map）以及map的数据结构来分析死循环的原因。

2.map源码

2.1.先看堆栈

在windbg中使用~*kb显示所有线程的堆栈信息，

接下来需要找到源码xtree中的1424/1481/2056位置和1424/1481/2050/2032位置，

tips:

该问题最直观的表现是发生了“死锁”，但通过windbg附加到进程（也可以直接用VS打开DMP文件，VS更香，连局部变量值都给你显示出来了，和在VS中调试代码别无二致！）看堆栈，发现是拿到锁的线程一直卡在map.find中，

导致其他线程一直在等待锁，然后用windbg中的调试命令go、step over、step out等调试命令让程序继续运行，（如果使用了go，需要用break使程序暂停）再输入~*kb输出堆栈信息，发现还是上述位置，那么即可根据源码，分析为什么堆栈会是这样的。

2.2.源码

C:Program Files (x86)Microsoft Visual Studio2017ProfessionalVCToolsMSVC14.16.27023includextree

结合源码和注释可以看到，find的实现思路是从红黑树上找到大于_Keyval且在最左边（也是是大于_Keyval的节点中最小的那个）那个迭代器，

然后判断如果返回的迭代器_Where是end或者大于_Keyval（即_Keyval小于_Where）那么就是没找到等于_Keyval的元素，此时返回end()，否则就是找到了，返回目标迭代器。

接下来我们看看是怎么从红黑树上找到大于_Keyval且在最左边（也是是大于_Keyval的节点中最小的那个）那个迭代器，也就是lower_bound()函数的实现，

发现它仅调用了_Lbound()函数，那么再来看_Lbound()函数的实现，

先取出_Myhead的值赋给_Wherenode作为记录，取_Myhead->_Parent作为当前的_Pnode;
接下来是一个循环，循环条件是当前的_Pnode是否是叶子结点，如果是就执行循环体；
进入循环体，比较当前的_Pnode和目标_Keyval的大小，

如果_Pnode和<_Keyval，_Pnode赋值为_Pnode->_Right；
如果_Pnode和>=_Keyval，更新_Wherenode的值为_Pnode（_Wherenode即为到当前为止符合要求的节点），并对_Pnode赋值为_Pnode->_Left；
不断的执行上述1和2，直到当前的_Pnode是叶子结点，退出循环体

退出循环体后返回记录的_Wherenode，即为最符合要求的节点；

然后执行上述判断，返回end()或目标迭代器。

上图显示了几种情况的执行结果，对于数据正常的map(红黑树)，find()是没有问题的，因为find()依赖的是红黑树的结构，其复杂度为o(logn)；

2.3.map数据结构

当然仅知道find()的源码还是不够的，还需要对照着map的数据结构来理解，map有_Myhead是end()，_Myhead的_Parent是红黑树的根节点，

详细可以参考我的另一篇文章c++ map部分用法关键点的记录

3.结论

3.1.本文所涉及问题结论

本文所涉及问题是map.find()时候发生了死循环，原因是map（红黑树）结构出现了问题：节点的左子树大于该节点了、且出现了循环指向的问题（比如节点3的left指向了节点5，节点5的left指向了节点3，循环指向），从而导致find()时候发生了死循环，一直出不来，由于又用了多线程，表现出来就像线程死锁一样，虽然实际上并不是死锁（windbg通过!locks也可以验证，没有临界区的资源被锁住）。当然再深层次原因及解决方案请参考我的另一篇文章。