如果 {x,y} 和 {y,x} 也被认为是相同的，那么删除 vector<pair<A,A> > 中重复项的最简单方法是什么？

Question

如果 2 对 {x,y} 和 {y,x} 也被认为是重复的，是否有内置方法删除对向量的重复项？

例如，如果我有这样的矢量：

{{1,2},{4,3},{2,1},{5,6},{1,2},{3,4},{0,1}}

我想删除重复项成为：

{{1,2},{4,3},{5,6},{0,1}}

是否有任何内置函数来处理 {x,y} 和 {y,x} 相同的情况？

如果没有，最简单的方法是什么？

我考虑过使用 for 循环类似的东西但不起作用:

vector<int> isRemove;
int count=0;
for(pair<int,int> a : p){
    isRemove.push_back(0);
    for(pair<int,int> b : p){
        if((a.first==b.first && a.second==b.second) || (a.first==b.second && a.second==b.first)){
            isRemove[count]=1;
            break;
        }
    }
    count++;
}
for(int i=isRemove.size()-1;i>=0;i--){
    printf("%d\n",isRemove[i]);
    if(isRemove[i]){
        p.erase(p.begin()+i);
    }
}

还有更简单的方法吗？

Answer 1

std::set holds unique values. Uniqueness is determined by a comparator. You can implement your desired solution as follows (live example):

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

struct custom_comparator {
    bool operator()(const std::pair<int, int>& a,
                    const std::pair<int, int>& b) const
    {
        return less_comparator(std::minmax(a.first, a.second),
                               std::minmax(b.first, b.second));
    }

    std::less<std::pair<int, int>> less_comparator;
};

int main() {
    // Input data including some duplicates
    std::vector<std::pair<int, int>> a = {
        {1, 2}, {4, 3}, {2, 1}, {5, 6}, {5, 6}, {6, 5}, {1, 2}, {3, 4}, {0, 1}
    };

    // Specify custom comparator for the set
    std::set<std::pair<int, int>, custom_comparator> unique;

    // Fill the set
    for (const auto& p : a) {
        unique.insert(p);
    }

    // Demonstrate uniqueness by outputting the elements of the set
    for (const auto& p : unique) {
        std::cout << p.first << ", " << p.second << "\n";
    }

    return 0;
}

输出：

0, 1
1, 2
4, 3
5, 6

您只需定义一个带有自定义比较器的集合，以确保在调用 std::less 时每对中的顺序一致，然后填充该集合。

Answer 2

#include <vector>
#include <algorithm>
#include <iostream>
int main(){
  using namespace std;
  using Intpair = std::pair<int,int>;

  vector<Intpair> v = {{1,2},{4,3},{2,1},{5,6},{1,2},{3,4},{0,1}};
  //Normalize == sort the pair members
  for(auto& p : v){
    int x = max(p.first, p.second), y = min(p.first, p.second);
    p.first = x; p.second = y;
  }
  //Sort the pairs
  sort(v.begin(), v.end(),[](Intpair x, Intpair y){ return (x1 < y1) || (x1==y1 && x2<y2); }  );

  //Print the vector in its normalized and sorted form
  for(auto p : v){ cout<<p.first<<' '<<p.second<<'\n'; }
  cout<<'\n';
  //Unique the vector
  auto last = unique(v.begin(), v.end() );
  v.erase(last, v.end());

  //Print the unique'd vector
  for(auto p : v){ cout<<p.first<<' '<<p.second<<'\n'; }
}

输出：

1 0
2 1
2 1
2 1
4 3
4 3
6 5

1 0
2 1
4 3
6 5

与使用 std::set 相比，对于较小的向量，这应该具有更好的性能，因为后者不像向量那样对缓存友好。

Answer 3

以下程序将完全满足您的需要：

#include <iostream>
#include <vector>


int main () {
  std::vector<std::pair<int, int>> myvector;
  myvector.push_back(std::make_pair(1,2));
  myvector.push_back(std::make_pair(4,3));
  myvector.push_back(std::make_pair(2,1));
  myvector.push_back(std::make_pair(5,6));
  myvector.push_back(std::make_pair(1,2));
  myvector.push_back(std::make_pair(3,4));
  myvector.push_back(std::make_pair(0,1));

  auto it = myvector.begin();
  for (; it != myvector.end(); ++it) {
      auto pit = myvector.begin();
      for (; pit != myvector.end();) {
          if (((it->first == pit->first && it->second == pit->second) || (it->first == pit->second && it->second == pit->first)) && (pit != it)) {
              std::cout << "found pair " << it->first << "," << it->second << " with " << pit->first << "," << pit->second << std::endl;
              pit = myvector.erase(pit);
          } else {
              ++pit;
          }
      }

  }

  std::cout << "myvector contains:";

  for (it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << it->first << "," << it->second;

  std::cout << '\n';

  return 0;
}

输出：

myvector contains: 1,2 4,3 5,6 0,1