3

私が提供する rect のリストの中にあるすべての要素をベクトル内に格納されたポイントのセットから削除することになっているアルゴリズムを書いています。

私は C++11 のテストの場としても使用しているので、まだ新しい機能に慣れているので、これが効率的なアプローチなのか、それとも特定の欠陥があるのか​​ を知りたいです。取得していません。

vector<tuple<u16, u16, u16, u16>> limits;

FOR_EACH_AREA_TO_REMOVE
   limits.push_back(make_tuple(
       area->x - VIEWPORT_SIZE_X/2, 
       area->x + VIEWPORT_SIZE_X/2, 
       area->y - VIEWPORT_SIZE_Y/2, 
       area->y + VIEWPORT_SIZE_Y/2));
FOR_EACH_AREA_TO_REMOVE_END

vector<Point2D> points;

remove_copy_if(suitablePoints.begin(), suitablePoints.end(), 
               points.begin(), [&](const Point2D &point) {
  for (auto limit : limits)
    if (point->x > get<0>(limit) && 
        point->x < get<1>(limit) && 
        point->y > get<2>(limit) && 
        point->y < get<3>(limit))
      return true;

  return false;
  }
);

これは、問題に対するより単純な解決策のようです。ポイントセットから除外する必要がある境界のベクトルを作成し、セットポイントを反復処理します。問題へのより良いアプローチがあるかどうか疑問に思います。四角形のセットは実際には十分に制限されていますが、ポイントのセットは巨大になる可能性があることを指摘したいと思います。

4

1 に答える 1

4

コレクションを反復処理するときに各長方形のコピーを作成する必要がないため、 にauto変更できます。auto const&limits

for (auto const& limit : limits)
//        ^^^^^^

これにより、パフォーマンスがいくらか向上するはずです (ただし、パフォーマンスが懸念される場合は、結論を出す前にパフォーマンスを測定してください)。

また、ベクターから削除する要素のコピーを作成する必要がない限り (質問のテキストではこれについて言及されていません)、std::remove_if()代わりにstd::remove_copy_if().

std::remove_if()削除された要素を後続の要素で上書きすることで機能し、ベクトル自体のサイズを実際に変更せずに、ベクトルの新しい論理端を返します (これは、必要がない場合は望ましい動作です)。

std::vector::erase()したがって、 afterを呼び出してこれを行うかどうかはあなた次第ですstd::remove_if()。これは、名前もある非常に一般的な方法です。

于 2013-05-21T17:30:58.837 に答える