基本标准集逻辑

Question

这可能是个无聊的问题，但我想确定一下。假设我有一个结构：

struct A
{
    int number;
    bool flag;

    bool operator<(const A& other) const
    {
        return number < other.number;
    }
};

代码中某处：

A a1, a2, a3;
std::set<A> set;

a1.flag = true;
a1.number = 0;

a2.flag = false;
a2.number = 10;

a3 = a1;

set.insert(a1);
set.insert(a2);

if(set.find(a3) == set.end())
{
    printf("NOT FOUND");
}
else
{
    printf("FOUND");
}

我得到的输出是"FOUND"。我明白，因为我正在传递值，所以集合中的元素按值进行比较。但是，既然等于运算符没有被覆盖，对象 A 如何通过它们的值进行比较呢？我不明白覆盖运算符“<”如何足以满足集合查找功能。

Answer 1

flag 成员在这里完全不相关。 set 找到了一个与搜索值等价的元素，相对于 <。

也就是说，如果a不小于b，b不小于a，那么a和b一定是相等的。这就是它处理普通整数的方式。这就是如何决定 2 个值在 std::set.

中是等价的

std::set 根本不使用 ==。（unordered_set，这是一个哈希集，确实使用它，因为它是区分哈希冲突的唯一方法）。

您也可以提供一个函数来完成 < 的工作，但它的行为必须与 strict weak ordering. Which is a bit heavy on the maths, but basically you could use > instead, via std::greater 相同，或者定义您自己的命名函数而不是定义 operator<。

因此，从技术上讲，没有什么可以阻止您定义一个 operator==，它的行为不同于来自您的 operator< 的等价概念，但 std::set 不会使用它，这可能会让人们感到困惑。

Answer 2

有序容器（set、multiset、map、multimap）使用一个单独的谓词来建立元素顺序和查找值，小于谓词。

如果两个元素都不小于另一个，则认为两个元素相等。

这个概念 if "equality" 可能与您可能拥有的其他一些平等概念不同。有时，术语 "equivalent" 更适用于区分由小于顺序引起的概念与可能同时存在的其他临时平等概念（例如，超载的 operator==）。

对于"sane"值类型（也称为常规类型），ad-hoc相等和小于诱导等价必须相同；许多自然发生的类型是规则的（例如算术类型（如果 NaN 被移除））。在其他情况下，特别是如果小于谓词是外部提供的，而不是由类型本身提供的，小于等价类完全有可能包含许多非 "equal" 值。

Answer 3

来自集合的文档

two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a)

http://en.cppreference.com/w/cpp/container/set

在模板中可以看到

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

std::less

将调用 operator<，这就是它起作用的原因。

基本标准集逻辑

Basic std set logic

c++

std