C++ベクトルから重複を削除する方法

重複とは、同じものが2つ以上あることの1つを意味します。 次のベクトルを考えてみましょう。

「E」は、異なる位置で3回発生します。 「A」は異なる位置で2回発生します。 「C」は、異なる位置で2回発生します。 したがって、「E」、「A」、および「C」には重複があります。 他の各文字は1回出現します。

このベクトルの重複を削除するということは、「E」、「A」、および「C」の重複を削除し、その位置で各文字が最初に出現することを許可することを意味します。 結果は次のようになります。

ベクトルから重複を削除するには、主に2つの方法があります。 1つの方法は、直接またはブルートフォースの方法です。 このようにして、最初の要素が残りの要素と照合され、重複があれば削除されます。 2番目の要素は、右側の他の要素と照合され、重複が削除されます。 3番目の要素と残りの要素についても同じ手順が実行されます。 この方法は通常、時間がかかりすぎます。 もう1つの方法は、元のベクトルを維持し、そのコピーを並べ替えることです。 マップのキーとして、重複した要素のコピーを作成しながら、ソートされたベクトルから重複を削除します。 最後に、マップを使用して元のベクトルを最初から最後までスキャンし、重複を消去します。

これらの2つの方法は、それぞれブルートフォース方式とソートアンドコンペア方式と呼ばれます。 この記事では、両方の方法について説明します。 プログラムの最初にベクターライブラリを含めることを忘れないでください。

ベクトル要素の削除

ベクトル要素は、ベクトル消去メンバー関数で削除されます。 構文は次のとおりです。

引数は、削除する要素を指すイテレータです。

ブルートフォースによる重複の削除

このアプローチでは、最初の要素が右側の残りの要素と1つずつ比較され、重複があれば消去されます。 2番目の要素は、消去されていない場合は、右側の他の要素と1つずつ比較され、重複が消去されます。 3番目の要素と残りの要素についても同じ手順が実行されます。 このアプローチは通常、時間がかかりすぎます。 次のコードは、イテレータを使用してそれを示しています。

これらは、1つのループがネストされたイテレータforループです。 2番目の個別のforループは、プロセスの一部ではありません。 結果を印刷するためのものです。 プロセスには2つのforループがあります。 内側のforループはベクトルの残りの部分をスキャンし、各要素を外側のforループが指す要素と比較します。 ステートメントに注意してください、

内側のforループの括弧内。

並べ替えと比較による重複の削除

上記の方法から、1つのベクトルの要素の大きなシーケンスから小さなシーケンスへの再スキャン（再読み取りと比較）がたくさんあることに注意してください。 ベクトル全体が1回、2回、または3回スキャンされる場合、これはおそらく、上記のアプローチと比較して要素へのアクセスが少ないことを意味します。 ええと、ベクトル全体を4回以上スキャンすることもできますが、何度もスキャンすることはできません。 これは、必ずしも同じベクトルで実行する必要はありません。 これは、ベクターのコピーを使用して実行できます。

2番目のアプローチでは、ソートされたコピーが作成されている間、元のベクトルが維持されます。 ソートされたベクトルが読み取られ（スキャンされ）、複数回発生した連続する要素の重複が消去されます。 1つのイテレータforループは、ソートされたベクトルの最初から最後まで、これを1回実行できます。 この読み取りといくつかの消去が行われている間、複数回発生する要素については、要素のコピーがマップ内のキーになり、このキーに対応する値に値-1が与えられます。 この値-1は、重複を示すために1に変更されます。 マップ内の各値は、元のベクトルで2回以上発生する可能性のあるキーの重複を示すインジケーターです。

重複を削除したソート済みベクトルが必要な場合は、ソート済みベクトルが返され、作業が完了します。 ベクトル要素の最初の出現順序を維持する必要がある場合は、次のサブ手順を実行する必要があります（続行）。

元のベクトルを最初から読み直します。 読み取り中に、マップでキーが発生しない場合（マップは0を返す）、元のベクトルでそのキーを許可します。 これは、キーに重複がないことを意味します。 元のベクトルのキーがマップ内にある場合、それはベクトル内のその要素の重複が最初に発生したことを意味します。 マップ内のキーのインジケーター値を作成します。1。そのインジケーター値の値は1になります。元のベクトルの残りの要素の読み取りを続行し、マップで重複する要素をチェックします。 キーが見つかり、マップキー値が1の場合、現在の要素は重複しています。 現在の要素を削除します。 （重複キーが最初に発生すると、マップ内の対応するインジケーター値が-1から1に変わったことを思い出してください。）マップキーインジケーターに値1を指定し続け、対応する1がすでにある元の現在のベクトル要素を削除します。元のベクトルからのマップ。 元のベクトルの終わりに達するまで。 結果として得られる元のベクトルは、重複する要素がなく、最初に出現した順序のベクトルです。

マップをC++でコーディングするには、マップ（unordered_map）ライブラリを含める必要があります。 アルゴリズムライブラリのsort（）関数が使用されるため、アルゴリズムライブラリもプログラムに含める必要があります。 このアプローチのプログラムの見出しは、次のようになります。

C++メイン関数の最初のコードセグメントは次のようになります。

最初のステートメントは、元のベクトルを定義します。 2番目のステートメントは、元のベクトルのコピーを作成します。 3番目のステートメントは、コピーされたベクトルをソートします。 4番目のステートメントは、初期化せずにマップを宣言します。 C++メイン関数の次のコードセグメントは次のようになります。

このコードセグメントは、ソートされたコピーされたベクトルから重複を消去します。 その間、マップエントリを作成します。 forループの括弧内では、反復は（最後の要素ではなく）最後の1つの要素に到達することに注意してください。 これは、現在の要素と次の要素がコードに含まれているためです。 また、要素を消去する場合、イテレータは1ステップ遅延（デクリメント）されることに注意してください。

重複のないソートされたベクトルが必要なものである場合、次のコードは結果を表示します。

次のコードセグメントは、元のベクトルとマップを使用して、元のベクトルの重複を消去します。

0と1ではなく-1と1を選択する理由は、このマップのデフォルト（不在）値が0であるためです。これにより、重複がまったくない要素との混同を回避できます。 次のような通常のforループは、最終的な（縮小された）元のベクトルを出力できます。

プログラムへの入力は次のとおりです。

プログラムの出力は次のとおりです。

出力の最初の行は、重複のないソートされた入力です。 2行目は、重複が削除された、指定された順序での入力です。

結論

C ++ベクトルから重複を削除するために、力ずくの方法を使用できます。 この方法は通常遅いです。 読者は、彼/彼女の商業的な仕事のために、通常は速いソートアンドコンペア法を使用することをお勧めします。 両方の方法は上で説明されています。