c++ - ベクトル内の重複要素を見つける

Question

x 座標と Y 座標と共に要素の識別子を保持するベクトルがあります。私がしたいのは、それらが同じ x 座標と y 座標を持っているかどうかを確認することですか? -そして、それらの1つを削除した場合（別のフィールドに基づいて）。

「一意の」関数についてGoogleで見つけましたが、すべての識別子が一意であるため、これは機能しませんか? 正しい？

ネストされた for ループを使用して、ベクトル比較の各項目を調べることを考えていましたが、より良い方法はありますか?

ありがとうJ

Answer 1

私は先に進んで、いくつかの例を書きました。お役に立てば幸いです。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>


using namespace std;


// Sample coordinate class 
class P {
public:
    int x;
    int y;
    P() : x(0), y(0) {}
    P(int i, int j) : x(i), y(j) {}
};


// Just for printing out
std::ostream& operator<<(ostream& o, const P& p) {
    cout << p.x << " " << p.y << endl;
    return o;
}

// Tells us if one P is less than the other
bool less_comp(const P& p1, const P& p2) {

    if(p1.x > p2.x)
        return false;
    if(p1.x < p2.x)
        return true;

    // x's are equal if we reach here.
    if(p1.y > p2.y)
        return false;
    if(p1.y < p2.y)
        return true;

    // both coordinates equal if we reach here.
    return false;
}


// Self explanatory
bool equal_comp(const P& p1, const P& p2) {

    if(p1.x == p2.x && p1.y == p2.y) 
        return true;

    return false;
}

int main()
{

  vector<P> v;
  v.push_back(P(1,2));
  v.push_back(P(1,3));
  v.push_back(P(1,2));
  v.push_back(P(1,4));

  // Sort the vector. Need for std::unique to work.
  std::sort(v.begin(), v.end(), less_comp);

  // Collect all the unique values to the front.
  std::vector<P>::iterator it;
  it = std::unique(v.begin(), v.end(), equal_comp);
  // Resize the vector. Some elements might have been pushed to the end.
  v.resize( std::distance(v.begin(),it) );

  // Print out.
  std::copy(v.begin(), v.end(), ostream_iterator<P>(cout, "\n"));

}

---

1 2

1 3

1 4

Answer 2

std::uniqueを使用して重複を破棄できます。ただし、これでは、削除された要素に対して何もすることができません。それらはコンテナからドロップされるだけです。これを行う必要がある場合は、次のアプローチを使用できます。

x 座標と y 座標を比較するカスタム比較関数でvector.sortを使用します。次に、各要素を前の要素と比較して、ベクトルを 1 回繰り返します。

ベクトルの順序を変更したくない場合は、ベクトルを最初から最後まで反復し、各要素をより高いインデックスを持つすべての要素と比較することもできます。

for (int i = 0; i < vector.size(); i++) {
    Position current = vector.at(i);
    for (int j = i+1; j < vector.size(); j++) {
         if current.isEqualPosition(vector.at(j)) {
             // found a duplicate
         }
    }
}

ところで: 正確な要件によっては、2d 空間でオブジェクトを処理するより良い方法は、2 次元ツリーのようなカスタム データ構造になる可能性があります。