C++のSTL関数を使ってstd::vector内の重複する文字列を検索・表示する方法

文字列のリストを扱っていると、同じ文字列が複数回出現しているケースによく遭遇します。本記事では、C++のSTL(標準テンプレートライブラリ)を活用して、std::vector内に含まれる重複した文字列を効率的に検索し、画面に表示する方法を解説します。

例として、次のような文字列リストを考えてみましょう。

["Hello", "Kite", "Hello", "C++", "Tom", "C++"]

このリストの場合、「Hello」と「C++」がそれぞれ2回出現しているため、これらを重複として検出する必要があります。

アルゴリズムの考え方:ハッシュを活用した重複検出

ここではハッシュテーブル(std::unordered_set)を使用した手法を採用します。処理の手順は以下の通りです。

1. 空のハッシュセット(unordered_set)を作成する
2. ベクター内の各文字列を先頭から順に走査する
3. 現在の文字列がすでにハッシュセットに存在する場合は、その文字列を重複として表示する
4. 存在しない場合は、その文字列をハッシュセットに挿入する

unordered_setは平均O(1)の時間計算量で要素の検索・挿入が可能なため、このアプローチはデータ量が多くても高速に動作するのが大きなメリットです。

サンプルコード

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

void findDuplicateStrings(vector<string> strings) {
    unordered_set<string> s;
    bool hasDuplicate = false;
    for (int i = 0; i < strings.size(); i++) {
        if (s.find(strings[i]) != s.end()) {
            cout << strings[i] << endl;
            hasDuplicate = true;
        }
        else
            s.insert(strings[i]);
    }
    if (!hasDuplicate)
        cout << "No Duplicate string has found" << endl;
}

int main() {
    vector<string> strings{"Hello", "Kite", "Hello", "C++", "Tom", "C++"};
    findDuplicateStrings(strings);
}

実行結果

Hello
C++

コードのポイント

• s.find(strings[i]) != s.end() によって、文字列がすでにセットに登録済みかどうかを判定しています。
• 初めて出現した文字列のみを s.insert() でセットに追加するため、同じ重複文字列が何度も表示されることはありません。
• hasDuplicate フラグを使用することで、重複が1件も見つからなかった場合に「No Duplicate string has found」というメッセージを表示できるようにしています。

このように、STLの連想コンテナを活用すれば、ループを1回走査するだけで重複要素を簡単かつ高速に検出できます。ぜひ実際のプロジェクトでも活用してみてください。