是否可以使用 std::pair 作为 std::set 的键而每个元素都没有重复？

Question

我正在尝试使用结构中的两个整数作为键将结构存储在 std::set 中。我知道可以使用 std::pair 作为 std::set.

的键

struct TYPE{
  pair<int, int> nums;
  ... // some other things

  TYPE(){}
  TYPE(int first, int second) { nums = make_pair(first, second); }
  bool operator<(const TYPE &rhs) const{
    return nums < rhs.nums;
  }
};
set<TYPE> nums_set;
nums_set.insert(TYPE(1, 2));
nums_set.insert(TYPE(1, 4));
nums_set.insert(TYPE(5, 2));
// size of set : 3, (1,2)(1,4)(5,2)
auto it = nums_set.find(TYPE(1, 2)); // find return (1,2)

但是，我想要可搜索且没有重复项 std::set，而不管 std::pair 中元素的顺序如何。像这样：

nums_set.insert(TYPE(1, 2));
nums_set.insert(TYPE(1, 4)); // failed. duplicate 1
nums_set.insert(TYPE(4, 2)); // failed. duplicate 2
nums_set.insert(TYPE(4, 1)); // failed. duplicate 1
nums_set.insert(TYPE(3, 4));
// size of set : 2, (1,2)(3,4)
auto it = nums_set.find(TYPE(2, 7));  // find return (1,2).

到目前为止最简单的解决方案是使用 std::vector 代替并在插入向量之前进行重复检查，如下所示：

auto fn = [](const TYPE& e, const TYPE&& t){
    return e.nums.first == t.nums.first ||
            e.nums.first == t.nums.second ||
            e.nums.second == t.nums.first ||
            e.nums.second == t.nums.second;
};
vector<TYPE> nums_vec;
nums_vec.push_back(TYPE(1, 2));
if(nums_vec.end() == find_if(nums_vec.begin(), nums_vec.end(), 
  bind(fn, placeholders::_1, TYPE(1,4))))
{  nums_vec.push_back(TYPE(1,4)); }

但是，我觉得每次插入都这样做以避免重复并不是一个好主意。所以，我的问题是，是否也可以使用 std::set 来实现这些功能？

Answer 1

用于集合的比较必须满足 Compare 命名要求。这些要求中包括导出等价关系的传递性：

If equivalent(a,b) and equivalent(b,c) then equivalent(a,c).

具体案例：

设a为{1,2}，b为{1,4}，c为{3,4}。
传递性：如果{1,2}等价于{1,4}并且{1,4}等价于{3,4}则{1,2} 等同于 {3,4}.

另一种表示 X 等同于 Y 的方式是，X 在您的集合中的存在阻止添加 Y。您希望 {1,2} 阻止 {1,4} 被添加到集合中。您希望 {1,4} 阻止 {3,4} 被添加到集合中。要获得所需的传递性，需要 {1,2} 阻止 {3,4} 被添加到集合中，这是你做的事情 而不是想要。

不，您的目标不能仅仅通过集合使用的顺序来实现。

Answer 2

没有可以使用的严格弱排序，因此不能使用 std::set。

但是，您可以使用 std::unordered_set，它只需要提供相等性。

是否可以使用 std::pair 作为 std::set 的键而每个元素都没有重复？

is it possible to using std::pair as key of std::set without any duplicates each element?

c++

stl

c++11