アルゴリズム

[C++] unique()の使い方 – 重複要素の削除

C++のstd::uniqueは、連続する重複要素を削除するためのアルゴリズムです。

ただし、完全に削除するわけではなく、重複しない要素を先頭に移動し、その後ろに不要な要素が残る形になります。

使用するには、ソート済みの範囲に適用する必要があります。

戻り値は新しい末尾のイテレータで、これを使って不要な要素を削除するにはeraseと組み合わせます。

目次から探す

unique()の使い方

C++のunique()関数は、指定した範囲内の重複した要素を削除するために使用されます。

この関数は、<algorithm>ヘッダに含まれており、通常はstd::vectorやstd::listなどのコンテナと組み合わせて使用されます。

unique()は、重複を削除した後の新しい範囲の終端を返しますが、実際には元のコンテナのサイズは変わりません。

重複を削除した後は、通常、erase()メソッドを使ってコンテナのサイズを調整します。

以下に、unique()の基本的な使い方を示すサンプルコードを示します。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    // 重複した要素を含むベクターを作成
    std::vector<int> numbers = {1, 2, 2, 3, 4, 4, 4, 5};
    // unique()を使用して重複を削除
    auto last = std::unique(numbers.begin(), numbers.end());
    // unique()の結果を表示
    numbers.erase(last, numbers.end()); // 実際にサイズを調整
    // 結果を出力
    for (int number : numbers) {
        std::cout << number << " "; // 重複を削除した結果を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

1 2 3 4 5

このコードでは、std::vectorに重複した整数を格納し、unique()を使って重複を削除しています。

unique()は重複を削除した後の新しい終端を返し、その後erase()を使って実際にコンテナのサイズを調整しています。

最終的に、重複のない要素が出力されます。

unique()を使用する際の注意点

unique()関数を使用する際には、いくつかの注意点があります。

これらを理解しておくことで、意図した通りに重複要素を削除し、プログラムの動作を正しく保つことができます。

以下に、主な注意点を示します。

注意点	説明
ソートが必要	`unique()`は隣接する重複要素を削除するため、事前にソートが必要です。
元のコンテナのサイズは変わらない	`unique()`は重複を削除した後の新しい終端を返しますが、元のコンテナのサイズは変わりません。
erase()の使用	`unique()`の後に`erase()`を使って、実際にコンテナのサイズを調整する必要があります。
カスタム比較関数	デフォルトでは`operator==`が使用されますが、カスタム比較関数を指定することも可能です。

ソートが必要

unique()は、隣接する重複要素を削除するため、使用する前にコンテナをソートしておく必要があります。

ソートされていない場合、意図しない結果が得られることがあります。

元のコンテナのサイズは変わらない

unique()は、重複を削除した後の新しい終端を返しますが、元のコンテナのサイズはそのままです。

したがって、erase()を使って実際にサイズを調整する必要があります。

erase()の使用

unique()の結果を反映させるためには、erase()メソッドを使用して、削除された要素をコンテナから取り除く必要があります。

これを行わないと、元のコンテナには依然として重複した要素が残ります。

カスタム比較関数

デフォルトでは、unique()はoperator==を使用して重複を判断しますが、必要に応じてカスタム比較関数を指定することもできます。

これにより、特定の条件に基づいて重複を削除することが可能です。

これらの注意点を理解し、適切に対処することで、unique()を効果的に活用することができます。

unique()の応用例

unique()関数は、重複要素の削除だけでなく、さまざまな場面で応用することができます。

以下に、いくつかの具体的な応用例を示します。

1. 重複した文字列の削除

文字列のリストから重複を削除する場合にもunique()を使用できます。

以下のサンプルコードでは、文字列のベクターから重複を削除しています。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main() {
    // 重複した文字列を含むベクターを作成
    std::vector<std::string> fruits = {"apple", "banana", "apple", "orange", "banana", "grape"};
    // ソートしてからunique()を使用
    std::sort(fruits.begin(), fruits.end());
    auto last = std::unique(fruits.begin(), fruits.end());
    // unique()の結果を表示
    fruits.erase(last, fruits.end()); // 実際にサイズを調整
    // 結果を出力
    for (const auto& fruit : fruits) {
        std::cout << fruit << " "; // 重複を削除した結果を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

apple banana grape orange

2. ユーザー定義型の重複削除

ユーザー定義型のオブジェクトに対しても、unique()を使用することができます。

以下の例では、Personクラスのオブジェクトから重複を削除しています。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
class Person {
public:
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
    // 同一性を比較するための演算子オーバーロード
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};
int main() {
    // 重複したPersonオブジェクトを含むベクターを作成
    std::vector<Person> people = {
        Person("Alice", 30),
        Person("Bob", 25),
        Person("Alice", 30),
        Person("Charlie", 35),
        Person("Bob", 25)
    };
    // unique()を使用して重複を削除
    auto last = std::unique(people.begin(), people.end());
    // unique()の結果を表示
    people.erase(last, people.end()); // 実際にサイズを調整
    // 結果を出力
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ") "; // 重複を削除した結果を表示
    }
    std::cout << std::endl; // 改行
    return 0;
}

Alice (30) Bob (25) Charlie (35)

std::uniqueは連続した重複要素しか削除しません。そのため、std::sortを使用してベクターをソートしてからstd::uniqueを適用する必要があります。

3. 複雑な条件での重複削除

カスタム比較関数を使用することで、特定の条件に基づいて重複を削除することも可能です。

以下の例では、年齢が同じであれば重複とみなす条件でunique()を使用しています。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

class Person {
   public:
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
};

// 年齢でソートするための比較関数
bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age;
}

int main() {
    // 重複したPersonオブジェクトを含むベクターを作成
    std::vector<Person> people = {Person("Alice", 30), Person("Bob", 25),
                                  Person("Charlie", 30), Person("David", 25)};
    
    // 年齢でベクターをソート
    std::sort(people.begin(), people.end(), compareByAge);
    
    // unique()を使用して年齢が同じ要素を削除
    auto last = std::unique(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age == b.age;
    });
    
    // unique()の結果を反映してサイズを調整
    people.erase(last, people.end());
    
    // 結果を出力
    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ") ";
    }
    std::cout << std::endl; // 改行
    return 0;
}

Alice (30) Bob (25)

これらの応用例から、unique()関数がさまざまなデータ型や条件に対して柔軟に使用できることがわかります。

重複要素の削除に役立つ強力なツールです。

unique()と他のアルゴリズムとの比較

C++のunique()関数は、重複要素の削除に特化したアルゴリズムですが、他のアルゴリズムと組み合わせて使用することで、より効果的にデータを処理することができます。

以下に、unique()と他の関連するアルゴリズムとの比較を示します。

1. sort()との組み合わせ

unique()は、隣接する重複要素を削除するため、通常はsort()と組み合わせて使用されます。

sort()を使用することで、重複要素が隣接するように整列され、unique()が正しく機能します。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {4, 1, 2, 2, 3, 4, 1};
    // ソートしてからunique()を使用
    std::sort(numbers.begin(), numbers.end());
    auto last = std::unique(numbers.begin(), numbers.end());
    numbers.erase(last, numbers.end());
    for (int number : numbers) {
        std::cout << number << " "; // 重複を削除した結果を表示
    }
    std::cout << std::endl;
    return 0;
}

1 2 3 4

2. remove_if()との比較

remove_if()は、条件に基づいて要素を削除するためのアルゴリズムです。

remove_if()は、指定した条件に一致する要素を削除し、残りの要素を前方に移動します。

unique()は隣接する重複要素を削除するのに対し、remove_if()は任意の条件に基づいて要素を削除できます。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    // 偶数を削除するためにremove_if()を使用
    auto last = std::remove_if(numbers.begin(), numbers.end(), [](int n) {
        return n % 2 == 0; // 偶数を条件に
    });
    numbers.erase(last, numbers.end());
    for (int number : numbers) {
        std::cout << number << " "; // 偶数を削除した結果を表示
    }
    std::cout << std::endl;
    return 0;
}

1 3 5 7 9

3. setとの比較

std::setは、重複を自動的に排除するデータ構造です。

setを使用することで、要素を追加する際に重複が自動的に排除されるため、unique()を使用する必要がありません。

ただし、setは要素の順序を保持しないため、順序が重要な場合にはvectorとunique()の組み合わせが適しています。

#include <iostream>
#include <set>
int main() {
    std::set<int> numbers = {4, 1, 2, 2, 3, 4, 1}; // 重複を自動的に排除
    for (int number : numbers) {
        std::cout << number << " "; // 重複を排除した結果を表示
    }
    std::cout << std::endl;
    return 0;
}

1 2 3 4

4. distinct()との比較

C++20以降では、std::ranges::uniqueが導入され、より直感的に重複を削除することが可能になりました。

rangesライブラリを使用することで、より簡潔なコードで重複を削除できます。

#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
int main() {
    std::vector<int> numbers = {4, 1, 2, 2, 3, 4, 1};
    // ranges::unique()を使用して重複を削除
    auto unique_numbers = numbers | std::views::unique;
    for (int number : unique_numbers) {
        std::cout << number << " "; // 重複を削除した結果を表示
    }
    std::cout << std::endl;
    return 0;
}

4 1 2 3

unique()は、重複要素の削除に特化したアルゴリズムですが、他のアルゴリズムやデータ構造と組み合わせることで、より効果的にデータを処理することができます。

sort()やremove_if()、set、rangesなど、用途に応じて適切な方法を選択することが重要です。

unique()のパフォーマンス

unique()関数のパフォーマンスは、主に入力データのサイズや特性、使用するコンテナの種類によって異なります。

以下に、unique()のパフォーマンスに影響を与える要因や、実際の計算量について詳しく説明します。

1. 計算量

unique()の計算量は、O(n)です。

ここで、nはコンテナ内の要素数を表します。

unique()は、隣接する重複要素を削除するために、コンテナ内の要素を1回スキャンするだけで済むため、効率的です。

ただし、unique()を使用する前にsort()を行う場合、sort()の計算量はO(n log n)となるため、全体の計算量はO(n log n)になります。

2. コンテナの種類

unique()は、std::vectorやstd::dequeなどのランダムアクセス可能なコンテナで特に効果的です。

これらのコンテナでは、要素へのアクセスが高速であるため、unique()のパフォーマンスが向上します。

一方、std::listのような双方向リストでは、要素へのアクセスが遅くなるため、パフォーマンスが低下する可能性があります。

3. データの特性

データの特性もunique()のパフォーマンスに影響を与えます。

例えば、重複要素が少ない場合、unique()は効率的に動作しますが、重複要素が多い場合、結果として多くの要素が残るため、erase()を使用する際に余分なコストがかかることがあります。

4. メモリ使用量

unique()は、元のコンテナのサイズを変更しないため、メモリ使用量は元のコンテナのサイズに依存します。

erase()を使用してサイズを調整する際に、メモリの再割り当てが発生することがありますが、これもコンテナの種類によって異なります。

std::vectorでは、メモリの再割り当てが発生する可能性がありますが、std::listでは発生しません。

5. 実際のパフォーマンス測定

実際のパフォーマンスを測定するためには、異なるサイズや特性のデータセットを用意し、unique()の実行時間を計測することが重要です。

以下は、簡単なパフォーマンステストのサンプルコードです。

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
int main() {
    // 大きなデータセットを作成
    std::vector<int> numbers(1000000);
    std::generate(numbers.begin(), numbers.end(), []() { return rand() % 100; }); // 0-99の乱数
    // ソートしてからunique()を使用
    std::sort(numbers.begin(), numbers.end());
    // パフォーマンス測定開始
    auto start = std::chrono::high_resolution_clock::now();
    auto last = std::unique(numbers.begin(), numbers.end());
    numbers.erase(last, numbers.end()); // サイズを調整
    auto end = std::chrono::high_resolution_clock::now();
    // 実行時間を表示
    std::chrono::duration<double> duration = end - start;
    std::cout << "unique()の実行時間: " << duration.count() << "秒" << std::endl;
    return 0;
}

このコードでは、100万個の乱数を生成し、unique()の実行時間を測定しています。

実際のパフォーマンスは、データの特性やコンピュータの性能によって異なるため、複数回実行して平均値を取ることが推奨されます。

unique()は、重複要素の削除において非常に効率的なアルゴリズムですが、計算量やコンテナの種類、データの特性によってパフォーマンスが変わることがあります。

これらの要因を考慮し、適切に使用することで、プログラムの効率を最大限に引き出すことができます。