提问人：TheMemeMachine 提问时间：8/23/2023 最后编辑：Some programmer dudeTheMemeMachine 更新时间：8/23/2023 访问量：41
如何为 std：：set<std：:p air<int，int 编写自定义比较器>>其中 pair 的第一个元素必须是唯一的
How to write custom comparator for std::set<std::pair<int,int>> where first element of pair must be unique
问：
我在编写严格的弱排序比较器时遇到了麻烦，以便插入对的第一个元素在集合中必须是唯一的，并且对的第二个元素必须按降序排列。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
如何强制执行对中第一个元素的唯一性？
答：
1赞
Yakk - Adam Nevraumont
8/23/2023
#1
std::set假设键是根据一组称为严格弱排序的公理进行排序的。在 cppreference 上，它们给出了一套对程序员友好的规则。
它需要：
非反射性：
!( a < a )
及物：
(a < b) and (b < c) means (a < c)
然后，定义为 -- 即，任何一个元素都不小于彼此，因此在 we 下是“等价的”。那么这个等价关系是传递的（显然是反身的）：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）<（2,3）和（2,3）<（1,1），这意味着（1,5）<（1,1）通过传递要求。
这与您的要求不一致，即 （1,5） 和 （1,1） 是等效的。
所以不能支持这个排序。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
评论
0赞
TheMemeMachine
8/24/2023
std：：multiset 是否支持这样的排序？
0赞
Yakk - Adam Nevraumont
8/24/2023
@TheMemeMachine多集也需要严格的弱排序，所以不需要。multi 的唯一区别是它如何处理等效元素。
评论