如何为 std::set<std::pair<int,int>> 编写自定义比较器，其中对的第一个元素必须是唯一的

Question

我在为

std::set<std::pair<int,int>>

编写严格的弱排序比较器时遇到困难，使得插入对的第一个元素在集合中必须是唯一的，并且对的第二个元素必须按降序排列。

这是我的实现：

#include <set>
#include <iostream>

struct Comparator {
    bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
        if (lhs.first == rhs.first) {
            return false;
        }
        
        return lhs.second > rhs.second;
    }
};


int main() {
    std::set<std::pair<int, int>, Comparator> s;
    
    s.emplace(1, 1);
    s.emplace(2, 0);
    s.emplace(2, 2);

    for (auto e : s) {
        std::cout << e.first << " " << e.second << std::endl;
    }

    return 0;
};

预期输出：

1 1
2 0

实际产量：

2 2
1 1
2 0

如何强制该对中第一个元素的唯一性？

Answer 1

std::set

假设键是根据一组称为“严格弱排序”的公理进行排序的。在 cppreference 上，他们给出了一套对程序员友好的规则。 需要：

非反身：

!( a < a )

传递：

(a < b) and (b < c) means (a < c)

然后，将 

weak_equivalent(a,b)

定义为

!(a<b) and !(b<a)

—— 即，两个元素都不小于彼此，因此在

<

下我们是“等价的”。那么这个等价关系是传递的（并且显然是自反的）：weak_equivalent(a,b) and weak_equivalent(b,c) means weak_equivalent(a,c)

即，

weak_equivalent

描述了一组彼此相等的元素。

在您的情况下，您似乎希望所有元素 (x,_) 在您的

<

下等效。

并且您希望它按第二个元素排序（向后，但这对我来说并不重要）。

但是 (1,5)

这不符合你的要求（1,5）和（1,1）是等价的。< (2,3) and (2,3) < (1,1), which means (1,5) < (1,1) by the transitive requirement.

所以

std::set

不支持此订购。

一般来说，当你不是严格的弱排序时排序是很困难的，因为你的元素没有一致的顺序。

就您而言，您可能应该直接停止使用

std::set

。

struct my_special_container {
  std::map<int, int> m_s;

  void emplace_if_not_exist( int a, int b ) {
    auto it = m_s.find(b);
    if (it != m_s.end()) {
      m_s[b] = a;
    }
  }
};

现在您只需编写一个返回元素的迭代器即可；与您的要求相比，

map

迭代器会向后执行。