如何将不同的对添加到集合中?

Question

我正在尝试将几对int插入到一个集合中，这些对没有任何顺序;也就是说，(1,2) = (2,1)。所以我简单地做如下，

typedef pair<int, int> pairs; 
set<pairs> Set;
pair <int,int> myPair;
// adding pairs:
myPair=pair<int,int>(0,1);
pathSet.insert(myPair);
myPair=pair<int,int>(0,2);
pathSet.insert(myPair);
myPair=pair<int,int>(1,0);
pathSet.insert(myPair);

所以我最终得到了一套这样的

(0,1), (0,2) , (1,0)

我想拥有

(0,1), (0,2)

如何避免重复？有什么办法吗？与"set"相比，在效率方面是否有更好的ADstd::unordered_setT？

Answer 1

您需要一个自定义比较函数。在那里，确保一对元素的顺序在比较时无关紧要。一个简单的方法是让对中的第一个元素始终是较小的元素(否则交换第一个和第二个(。

代码可能如下所示：

int main() {
typedef pair<int, int> pairs;
auto cmp = [](pairs a, pairs b) {
if (a.first > a.second) {
swap(a.first, a.second);
}
if (b.first > b.second) {
swap(b.first, b.second);
}
return a < b;
};
set<pairs, decltype(cmp)> pathSet(cmp);
pairs myPair=pair<int,int>(0,1);
pathSet.insert(myPair);
myPair=pair<int,int>(0,2);
pathSet.insert(myPair);
myPair=pair<int,int>(1,0);
pathSet.insert(myPair);
cout << pathSet.size();
}

输出：

2

Answer 2

您需要一个自定义的比较函数来std::set，因为您使用std::pair作为模板类型。在 C++11 中，您也可以将其制作为 lambda。

compare函数的想法是首先检查Pair是否Pair.first < Pair.second，如果没有，则交换以使它们在compare函数内按顺序排列。这不会更改原始插入的对元素的顺序，但会删除您提到的重复项。

auto compare = [](pairs lhs, pairs rhs) 
{
if(lhs.first > lhs.second ) lhs = pairs{lhs.second, lhs.first };
if(rhs.first > rhs.second ) rhs = pairs{rhs.second, rhs.first };
return lhs< rhs;
};

像这样的东西：在这里查看直播

#include <iostream>
#include <set>
typedef std::pair<int, int> pairs;
int main()
{
auto compare = [](pairs lhs, pairs rhs) //custom compare lambda function
{
if(lhs.first > lhs.second ) lhs = pairs{lhs.second, lhs.first };
if(rhs.first > rhs.second ) rhs = pairs{rhs.second, rhs.first };
return lhs< rhs;
};
std::set<pairs, decltype(compare)> Set(compare);
Set.emplace(std::make_pair(0,1)); // use can also emplace to the Set
Set.emplace(pairs{0,2});
Set.emplace(pairs{1,0});
for(const auto& it: Set)
std::cout << it.first << " " << it.second << std::endl;
}

输出：

0 1
0 2