3

I ベクトルのベクトルで、それぞれが (数学的な意味で) セットを表します。例えば：

{{1, 3}, {4, 9, 14}, {1, 3}, {1, 4, 8, 9, 10, 14, 16}, {1, 3, 9}, {4, 9, 17, 22}}

別のアイテムを含むすべてのアイテムを削除するために、ベクトルをフィルタリングできる最も効率的な C++ 可能な関数を (可能であればその場で) 作成したいと考えています。

たとえば、次のとおりです。

  • {1, 3}{1, 3}とに含まれる{1, 3, 9}
  • {4, 9, 14}に含まれています{1, 4, 8, 9, 10, 14, 16}

結果のベクトルは次のようになります。

{{1, 3}, {4, 9, 14}, {4, 9, 17, 22}}

私は C++ から始めているので、これを効率的に行う方法についてはまったく手がかりがありません。ここでの他の回答で、消去/削除イディオムを見つけましたが、述語としてクロージャーを消去することを除いて、ここではあまり適切ではないようです。これは、C++ ではあまり慣用的ではないようです。

元の順序を維持することは重要ではなく、各セット内の値の順序も重要ではないことに注意してください。

4

1 に答える 1

1

これまでに学んだことを考えると、非常に役立つコメントのおかげで、私が思いついた解決策は次のとおりです。

struct std::vector<size_t> colset;

bool less_colsets(const colset& a, const colset& b) {
  return a.size() < b.size();
}

void sort_colsets(std::list<colset>& l) {
  l.sort(less_colsets);
}

void strip_subsets(std::list<colset>& l) {
  sort_colsets(l);
  for (std::list<colset>::iterator i = l.begin(); i != l.end(); ++i) {
    std::list<colset>::iterator j = next(i, 1);
    while (j != l.end()) {
      if (includes((*j).begin(), (*j).end(), (*i).begin(), (*i).end())) {
        j = l.erase(j);
      }
      else {
        ++j;
      }
    }
  }
}

最も外側の要素を、どこでも要素を削除できるように最適化さstd::vectorれたものに置き換えたことに注意してください。std::list

これは期待どおりに機能するようですが、これを証明するにはさらにテストが必要です。次のステップは、より効率的な比較関数を使用することですincludes。これは、各ベクトルが字句的に順序付けられているという事実を考慮に入れます (プログラムが保証します)。明日これを試してみます。

編集：std::includesすでにこの事実を処理しているようです。わーい！

みんなありがとう。

于 2013-09-24T17:30:07.103 に答える