首页 > 编程语言 >C++ map自定义比较函数遵守严格弱序

C++ map自定义比较函数遵守严格弱序

时间:2024-02-14 10:11:19浏览次数:32  
标签:byteArray map const 自定义 ByteArray C++ 弱序

C++ map自定义比较函数遵守严格弱序

问题背景及定位

背景:这个问题是在将tablesaw(一个Java的数据处理项目)迁移到C++时出现的。

问题位置:SplitOn()函数,在数据流水线中的aggregate阶段。

问题描述:使用google/benchmark进行了批量化的性能测试,在测试中出现偶发性段错误,几率大约在万分之一到十万分之一之间。

问题定位:由于开发环境为受限环境,无法使用GDB调试查看堆栈定位,只能使用打印日志的方式处理

定位问题出现在如下代码处:

struct ByteArrayCompare {
    bool operator()(const ByteArray &a, const ByteArray &b) const {
        for (int i = 0; i < min(a.byteArray.size(), b.byteArray.size()); i++)
		{
			if (a.byteArray[i] != b.byteArray[i])
				return a.byteArray[i] < b.byteArray[i];
		}
		return true;
    }
    typedef ByteArray value_type;
};

......

map<ByteArray, Selection, ByteArrayCompare> selectionMap;

......

selectionMap[instanceByteArray] = std::move(selection); # crash here

至此,我个人百思不得其解,按照常理来说,应该是没有问题的。在没有段错误的情况下,测试用例能够顺利通过。

刚开始以为是class Selection的右值引用问题,有内存分配/释放没有构造/析构好,或者是移动构造出现问题,经过思考和检查排除以上问题。

因此定位问题出现在map自定义的ByteArrayCompare函数上。

map定义参见文档:https://cplusplus.com/reference/map/map/

template < class Key,                                   //map::key_tpe
           class T,                                     //map::mapped_type
           class Compare = less<Key>,                   //map::key_compare
           class Alloc = allocator<pair<const Key, T>>  //map::allocator_type
           > class map;

由以上代码可见,map是可以自定义Compare比较函数和Alloc分配器的,此处就使用了自定义的Compare比较函数,应用于ByteArray数据类型。

题外话:unordered_map可以自定义hash和equal函数,这也体现了STL对于两种数据结构的不同实现方式,此处不再展开。

问题原因及解决方案

这里我们需要一个概念strict_weak_order(严格弱序)

本篇文章在数学和语义上阐述了严格弱序的意义,值得一看:https://zhuanlan.zhihu.com/p/378294506

抛开复杂的逻辑不谈,简单来说,该性质要求比较函数对于两个不同的key,改变输入顺序不会改变比较结果。

例:(a, b)形式输入,输出结果为a < b(假设为false),(b, a)形式输入,输出结果应该为true,若为仍false则会出现问题。

具体到我们此处的代码:此时我们已经遍历完成了a和b中较短的那个,但是对于剩余长度,没有进行比较,而是直接返回true,因此出现了上述的非严格弱序问题。

修改后代码:

struct ByteArrayCompare {
    bool operator()(const ByteArray &a, const ByteArray &b) const {
        for (int i = 0; i < min(a.byteArray.size(), b.byteArray.size()); i++)
		{
			if (a.byteArray[i] != b.byteArray[i])
				return a.byteArray[i] < b.byteArray[i];
		}
		return a.byteArray.size() < b.byteArray.size();
    }
    typedef ByteArray value_type;
};

......

map<ByteArray, Selection, ByteArrayCompare> selectionMap;

......

selectionMap[instanceByteArray] = std::move(selection); # crash here

至此,再进行测试后不会出现上述段错误问题,问题解决。

标签:byteArray,map,const,自定义,ByteArray,C++,弱序
From: https://www.cnblogs.com/kazusarua/p/18015058

相关文章

  • jvm shutdownHook + spring 自定义事件实现业务处理
    jvm的shutdownHook可以实现对于jvm退出的一些处理,比如资源清理,异常事件通知,spring自定义事件(或者使用内部的)可以实现bean的一些事件驱动处理,两个结合起来可以方便我们进行一些业务处理一些业务场景资源清理服务停止业务状态一致性补偿服务注册场景中的取消注册服务停......
  • C++——编译和链接原理笔记
    我们在学习和开发C++程序中,理解编译和链接的原理至关重要。下面将学习一下C++程序是如何从源代码转换为可执行文件的过程,并结合示例代码进行说明。也是为了解开自己在刚学习C++的时候,编译时间长的疑惑。为了不让自己的学习之路这么枯燥,我按照一个正常的开发流程梳理一下......
  • c++定义类的时候,只提供拷贝构造函数而不提供默认(无参)构造函数和有参构造函数会怎样?
    4.2.4构造函数调用规则默认情况下,c++编译器至少给一个类添加三个函数:默认构造函数(无参,函数体为空)默认析构函数(无参,函数体为空)默认拷贝构造函数(对属性进行值拷贝)构造函数调用规则:如果用户定义有参构造函数,编译器不会提供默认(无参)构造,但是会提供默认拷贝构造函数如果用户......
  • defer slice 和 map 面向对象的特征
    5、deferdefer语句被用于预定对一个函数的调用。可以把这类被defer语句调用的函数称为延迟函数。defer作用:●释放占用的资源●捕捉处理异常●输出日志结果如果一个函数中有多个defer语句,它们会以LIFO(后进先出)的顺序执行。  recover错误拦截运行时panic异常......
  • springboot自定义starter 版本大于2.7
    相关jar包<!--提示配置--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-configuration-processor</artifactId><version>3.2.1</versi......
  • C++——异常处理模块笔记
    异常处理是C++中的重要概念之一,用于处理在程序执行过程中可能发生的错误或异常情况。异常是指在程序执行过程中发生的一些不寻常的事件,例如除零错误、访问无效内存等。C++提供了一套异常处理机制,使得程序可以优雅地处理这些异常,提高程序的可靠性和健壮性。异常是一种程序......
  • 【C++】两两交换链表中的节点
    #include<iostream>#include<stack>usingnamespacestd;structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};ListNode*swapPairs1(ListNode*head){ListNode*dummyHead=newListNode(0);dummyHead......
  • 【C++】给定两个增序的链表,试将其合并成一个增序的链表。
    给定两个增序的链表,试将其合并成一个增序的链表。#include<iostream>#include<stack>usingnamespacestd;structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};voidprintList(ListNode*head){while(head){std:......
  • 【C++】假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
    题目:假设链表中每一个节点的值都在0-9之间,那么链表整体就可以代表一个整数。给定两个这种链表,请生成代表两个整数相加值的结果链表。数据范围:0≤n,m≤1000000,链表任意值0≤val≤9要求:空间复杂度O(n),时间复杂度O(n)例如:链表1为9->3->7,链表2为6->3,最后生成新的结果链表......
  • qt自定义标题栏,纯代码实现,拿来即用,初始化列表时传入父窗口的this指针
    //头文件#ifndefTITLEBAR_H#defineTITLEBAR_H#include<QWidget>#include<QPoint>//坐标点#include<QMouseEvent>//鼠标事件classTitleBar:publicQWidget{Q_OBJECTpublic:explicitTitleBar(QWidget*parent=nullptr);//移动窗口......