C++:在Set或Map中,我可以确定KeyEqual谓词等效于std::memcmp吗



简单示例:

  • 算术标量:KeyEqual的结果相当于比较位模式,因此有效地std::memcmp
  • 指向空终止字符串的指针:KeyEqual的结果不等同于比较指针地址;测试相等性需要应用std::strcmp

KeyEqual是否可以在模板化类中以这种方式进行查询/内省?

基本上std::memcmp从不用于对象的比较。问题是,对象可以包含不影响对象值的填充位,但其本身可以具有随机值。

因此,具有相同值的两个对象可以具有不同的对象表示。此处引用:https://en.cppreference.com/w/cpp/language/object

对于T:类型的对象

  • 对象表示是从与T对象相同的地址开始的类型为unsigned char(或等价地为std::byte)(由于C++17)的sizeof(T)对象的序列
  • 值表示是保持其类型T的值的比特集,并且
  • 填充位是对象表示中不属于值表示的位

此外,C++中的一些对象可能具有不同的";逻辑值";而不是其值表示,在这种情况下,它们重载比较运算符。

这甚至在std:memcmp的描述中提到:https://en.cppreference.com/w/cpp/string/byte/memcmp

此函数读取对象表示,而不是的对象值。它通常只对没有填充的可复制对象有意义。例如,类型为std::stringstd::vector的两个对象之间的memcmp()将不比较它们的内容,并且类型为struct{char c; int n;}的两个物体之间的memcmp()将比较当cn的值相同时其值可能不同的填充字节。

通常情况下,不会。您所要求的内容可能对编译器不可用,或者在其他方面相当于停止问题。

编译器可能只有这个,在另一个翻译单元中实现。

struct KeyEqual {
bool operator()(int lhs, int rhs);
};

您可以测试它是std::equal_to<Key>,并且Key是标量或标量数组。这将错过那些数据成员都是标量的类,但给定struct Padded {char c; int n;}std::equal_to<Padded>不等价于std::memcmp

但你不应该在意。直接使用KeyEqual即可。

正如其他人已经指出的,std::memcmp不能被任何复杂的对象所取代;如果它们不可复制,或者包含填充位,那么std::memcpy将不同意任何合理的逻辑相等比较。

但更糟糕的是:即使在你描述的最基本的情况下,KeyEqual也不等同于std::memcmp,这要归功于IEEE 754二进制浮点的怪异,其中一些具有不同比特模式的浮点值仍然彼此相等(-0.0 == 0.0是真的,但memcmp会认为它们不相等;如果你在一个真正疯狂的系统中,表示相同值的许多数字的规范和非规范表示也可以这样做),而其他浮点值与任何其他浮点值相比都不相等,即使是具有完全相同的比特模式(std::nan("1") == std::nan("1")为假,但memcmp会认为它们相等)。

由于浮点的怪异,使用std::unordered_set<double>:

  1. 您可以重复插入相同的NaN值(例如std::nan("1"))(不断增加unordered_set的大小,即使所有值都具有相同的位模式);这可能并不那么有趣(如果不迭代整个过程并使用std::isnan手动测试以绕过std::unordered_set的本地查找行为,就永远无法对其中任何一个进行成员身份测试或删除它们),但我们已经处于使用std::memcmp的行为会有所不同的位置
  2. 如果同时插入-0.00.0,则常规std::equal_to会将它们视为等效的(保留先插入的那个,所以插入顺序很重要),但std::memcmp会将它们看作不同的(因为位模式不同)

虽然第1项可能不是问题†,但第2项是相关的;任何使用普通==测试的东西都会看到-0.00.0是相同的,但如果您决定在使用普通==时交换std::memcmp,则会更改行为并将它们视为不同的,因此两者可以共存于同一个unordered_set中。

因此,即使在最基本的例子(算术标量)中,认为可以用std::memcmp(&x, &y) == 0比较安全地替换归结为x == y比较的KeyEqual谓词也已经是错误的。基本上,断言有效的唯一情况是纯整数(可以有陷阱表示,可以做各种奇怪的事情,在大多数系统上,它们要么没有陷阱,要么只有一个陷阱位模式;即使它们有陷阱,实际将它们与陷阱表示一起使用也是未定义的行为,因此您不负责处理它们)。

无论如何,在那里使用std::memcmp并不会给你带来任何好处;除非编译器消除你的胡言乱语,否则它会迫使寄存器中的任何值转储到内存中,只是为了使用效率较低的比较方法。两个寄存器(或一个寄存器和一个内存值)的直接比较将更有效。


std::set/std::mapstd::unordered_set/std::unordered_map都没有对NaN和默认比较器/相等测试器做任何类似于正常的事情,事实上,对排序的集合和任何标准比较器使用NaN都违反了严格的弱排序要求,因此在没有自定义比较器的情况下,你在未定义行为之地(或邻近的未指定行为之地和类似的禁区)。除此之外,set/map规范的其余部分,结合NaN比较规则,基本上要求将NaN视为等于(因为x CMP NaNNaN CMP x在任何比较中都必须为false,并且等价性是通过比较返回false,参数按任意顺序排列来定义的,如果涉及NaN,则总是如此),而CCD_ 58/CCD_;通常";对于NaN,并将其视为而不是等于任何东西,甚至不等于具有相同位模式的其他NaN,因此从排序集合切换到基于哈希的集合将完全改变行为。

最新更新