时间戳

首页 > 解决方案 > 是否可以使用 std::pair 作为 std::set 的键而每个元素没有任何重复？

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

问题描述

我正在尝试使用 struct 中的std::set两个整数作为键来存储 struct。我知道可以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？

标签： c++c++11stl

解决方案

用于集合的比较必须满足比较命名要求。在这些要求中，有诱导等价关系的传递性：

如果equivalent(a,b)然后。equivalent(b,c)_equivalent(a,c)

具体案例：

  • 让我们a成为{1,2}，b成为{1,4}，c成为{3,4}。
  • 传递性： if{1,2}等价于{1,4}and{1,4}等价于{3,4}then{1,2}等价于{3,4}.

另一种表达方式X等同于您的集合Y中的存在X防止Y被添加。您想{1,2}防止{1,4}被添加到集合中。您想{1,4}防止{3,4}被添加到集合中。为了具有所需的传递性，需要防止被添加到集合中，这是您不想要的。{1,2}{3,4}

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

推荐阅读