c++ - 如果 C++ 中的 std::map 中的比较函数自反为真，它如何工作？

Question

我的项目中有一张 map 。 每次我插入一个新元素时，我都想确保我插入的新元素的键至少与 map 中的其他元素相距一个最小宽度。为此，我编写了一个自定义比较类，如下所示:

class PulseCompare
{
public:
    PulseCompare(int minwidth_):minwidth(minwidth_){};
    bool operator()(const int x, const int y) const {
        if(abs(x-y)>minwidth) return false;
        else return true;
    }
private:
    int minwidth;
};

并创建了这样的 map :

std::map<int,float,PulseCompare> pulsemap(PulseCompare(256));

在插入元素之前，我使用 map.find像这样的方法:

if ( pulsemap.find(1600) == pulsemap.end() ) {
  // not found so I can insert
} else {
  // found
}

但问题是，当 map 尝试通过交换 x 的值来使用上述比较函数进行自反比较时和 y , 它会得到一个 true对于这两种情况，通常不是像 < 这样的普通比较运算符的情况。和 >

在 std::map::key_comp 上的 cplusplus 文档页面上here它说，我引用

The comparison object of a map object is set on construction. Its type (member key_compare) is the third template parameter of the map template. By default, this is a less object, which returns the same as operator "<".

This object determines the order of the elements in the container: it is a function pointer or a function object that takes two arguments of the same type as the element keys, and returns true if the first argument is considered to go before the second in the strict weak ordering it defines, and false otherwise.

Two keys are considered equivalent if key_comp returns false reflexively (i.e., no matter the order in which the keys are passed as arguments).

但这并没有说明它是自反的情况 true .谁能告诉我它的行为是什么？或者我应该只通过遍历整个 map 来进行这种区间比较吗？

Answer 1

1. 用于 std::map 的比较器必须提供 strict weak ordering的对象。
2. 你的比较者没有。
3. 因此，您的 std::map 实例将产生未定义的行为。

注意:让比较器提供总排序通常更容易。

此外，让我们描述一下严格弱排序的要求。在这里，我摘自 C++ 2011，第 25.4 节。

• 你要创建一个仿函数 Compator comp;我要引用 comp(lhs, rhs)作为返回 bool 值的函数。将其视为 lhs < rhs 会很有帮助.
• 我们要创建一个函数 equiv(lhs, rhs) .这被定义为 (!comp(lhs, rhs) && !comp(rhs, lhs)) .所以，!(lhs < rhs) && !(rhs < lhs) .

我们需要遵守以下规则:

comp(a, b) && comp(b, c) implies comp(a, c)
equiv(a, b) && equiv(b, c) implies equiv(a, c)