このコードは一種の「セット等価性」チェックのみを行うことに気付きました (そして今、あなたが実際にそう言っていることがわかりました。私はなんてお粗末な読者なのでしょう!)。これははるかに簡単に実現できます
template <class T>
static bool compareVectors(vector<T> a, vector<T> b)
{
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
return (a == b);
}
ヘッダーを含める必要がありますalgorithm。
ベクトルが常に同じサイズである場合は、メソッドの先頭にアサーションを追加することをお勧めします。
assert(a.size() == b.size());
これは、この操作を誤って長さが等しくない場合に、プログラムのデバッグに役立ちます。
それ以外の場合、長さが等しくない場合、ベクトルを同じにすることはできないため、追加するだけです
if ( a.size() != b.size() )
{
return false;
}
ソート指示の前。これにより、多くの時間を節約できます。
これの技術的な複雑さは、O(n*log(n))(通常) その複雑さのソートに主に依存しているためです。これはあなたのO(n^2)アプローチよりも優れていますが、必要なコピーのために悪化する可能性があります. 元のベクトルがソートされている可能性がある場合、これは関係ありません。
あなたのアプローチに固執したいが、微調整したい場合は、これに関する私の考えを次に示します。
これに使用できますstd::find：
template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
const size_t n = a.size(); // make it const and unsigned!
std::vector<bool> free(n, true);
for ( size_t i = 0; i < n; ++i )
{
bool matchFound = false;
auto start = b.cbegin();
while ( true )
{
const auto position = std::find(start, b.cend(), a[i]);
if ( position == b.cend() )
{
break; // nothing found
}
const auto index = position - b.cbegin();
if ( free[index] )
{
// free pair found
free[index] = false;
matchFound = true;
break;
}
else
{
start = position + 1; // search in the rest
}
}
if ( !matchFound )
{
return false;
}
}
return true;
}
もう 1 つの可能性は、自由な位置を格納する構造を置き換えることです。使用したインデックスをベクターに保存するstd::bitsetか、単に保存して、そのインデックスベクターに一致がないかどうかを確認することができます。この関数の結果が非常に頻繁に同じである場合 (つまり、ほぼ true またはほぼ false)、それを反映するようにデータ構造を最適化できます。たとえば、ほんの一握りのインデックスのみを保存する必要があるため、結果が通常 false の場合は、使用済みインデックスのリストを使用します。
この方法の複雑さは、アプローチと同じです。std::find を使用して物事を検索すると、手動で検索するよりも優れている場合があります。(たとえば、データがソートされていて、コンパイラがそれを認識している場合、これはバイナリ検索になります)。