MENU
  1. ホーム
  2. C++
  3. C++のstd::setとstd::unordered_setの使い方と利点を徹底解説

C++のstd::setとstd::unordered_setの使い方と利点を徹底解説

C++

C++の標準ライブラリには、データの集合を管理するためのデータ構造としてstd::setとstd::unordered_setが用意されています。これらはどちらも一意な要素を格納するために使用されますが、内部的な実装や特性には大きな違いがあります。本記事では、std::setとstd::unordered_setの基本的な使い方から、それぞれの利点や注意点、具体的な応用例、パフォーマンスの比較までを詳しく解説します。これにより、適切な場面でどちらを使用すべきかの判断材料を提供します。

目次

std::setの基本的な使い方

C++のstd::setは、要素が自動的にソートされ、重複が許されない集合を表します。これは通常、二分探索木を基盤として実装されています。以下に基本的な使い方を示します。

std::setの定義と初期化

std::setは、ヘッダーファイルをインクルードすることで使用できます。基本的な定義と初期化の例を以下に示します。

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};
    for (int elem : mySet) {
        std::cout << elem << " ";
    }
    return 0;
}

上記のコードは、整数のセットを作成し、その要素を出力します。

要素の追加

std::setに要素を追加するには、insertメソッドを使用します。重複する要素は自動的に無視されます。

mySet.insert(6); // 6を追加
mySet.insert(3); // 既に存在するため無視される

要素の削除

要素を削除するには、eraseメソッドを使用します。

mySet.erase(2); // 2を削除

要素の検索

特定の要素が存在するかを確認するには、findメソッドを使用します。

if (mySet.find(3) != mySet.end()) {
    std::cout << "Element found" << std::endl;
} else {
    std::cout << "Element not found" << std::endl;
}

サイズとクリア

集合のサイズを取得するにはsizeメソッドを、全ての要素を削除するにはclearメソッドを使用します。

std::cout << "Size: " << mySet.size() << std::endl;
mySet.clear(); // 全要素を削除

これらの基本操作を理解することで、std::setを効果的に活用することができます。

std::setの利点と注意点

std::setにはいくつかの利点がありますが、使用する際には注意すべき点も存在します。以下にそれらを詳しく説明します。

利点

自動的なソート

std::setは要素を自動的にソートして格納します。これにより、ソートされた順序で要素を扱いたい場合に非常に便利です。

重複の排除

std::setは一意の要素のみを格納します。重複する要素を自動的に排除するため、データの一意性を保証する必要がある場合に有用です。

効率的な検索と削除

std::setは内部的にバランスの取れた二分探索木（通常は赤黒木）を使用しており、要素の検索、追加、削除操作が平均してO(log n)の時間で実行されます。

注意点

挿入順序の維持ができない

std::setは要素をソート順に保持するため、挿入した順序を維持したい場合には適していません。挿入順序を維持する必要がある場合は、std::setではなくstd::vectorやstd::listの使用を検討してください。

比較関数のカスタマイズ

std::setはデフォルトで要素を昇順にソートしますが、独自のソート順を設定するために比較関数を指定することも可能です。この場合、比較関数が正しく定義されていないと、正しく動作しない可能性があります。

struct CustomCompare {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs > rhs; // 降順にソート
    }
};

std::set<int, CustomCompare> mySet = {1, 2, 3, 4, 5};

メモリ消費

std::setはバランスの取れた二分探索木を使用するため、データの格納に必要なメモリ量が他のコンテナ（例えば、std::vectorやstd::array）に比べて多くなることがあります。

使用例と考慮点

std::setは、以下のような状況で特に有効です。

  • データの一意性が重要である場合
  • データのソートが必要な場合
  • 頻繁な検索や削除操作が発生する場合

これらの特性を理解して、適切な場面でstd::setを活用することが重要です。

std::unordered_setの基本的な使い方

C++のstd::unordered_setは、ハッシュテーブルを基盤とした集合で、要素の順序は保証されませんが、高速な操作が可能です。以下に基本的な使い方を示します。

std::unordered_setの定義と初期化

std::unordered_setは、ヘッダーファイルをインクルードすることで使用できます。基本的な定義と初期化の例を以下に示します。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet = {1, 2, 3, 4, 5};
    for (int elem : myUnorderedSet) {
        std::cout << elem << " ";
    }
    return 0;
}

上記のコードは、整数のunordered_setを作成し、その要素を出力します。

要素の追加

std::unordered_setに要素を追加するには、insertメソッドを使用します。重複する要素は自動的に無視されます。

myUnorderedSet.insert(6); // 6を追加
myUnorderedSet.insert(3); // 既に存在するため無視される

要素の削除

要素を削除するには、eraseメソッドを使用します。

myUnorderedSet.erase(2); // 2を削除

要素の検索

特定の要素が存在するかを確認するには、findメソッドを使用します。

if (myUnorderedSet.find(3) != myUnorderedSet.end()) {
    std::cout << "Element found" << std::endl;
} else {
    std::cout << "Element not found" << std::endl;
}

サイズとクリア

集合のサイズを取得するにはsizeメソッドを、全ての要素を削除するにはclearメソッドを使用します。

std::cout << "Size: " << myUnorderedSet.size() << std::endl;
myUnorderedSet.clear(); // 全要素を削除

これらの基本操作を理解することで、std::unordered_setを効果的に活用することができます。

std::unordered_setの利点と注意点

std::unordered_setは、ハッシュテーブルを基盤とした集合データ構造で、特定の利点と注意点があります。以下にそれらを詳しく説明します。

利点

高速な操作

std::unordered_setはハッシュテーブルを使用しているため、要素の追加、削除、検索操作が平均してO(1)の時間で実行されます。大量のデータを高速に処理する場合に非常に有効です。

重複の排除

std::unordered_setもstd::setと同様に、一意の要素のみを格納します。重複する要素は自動的に排除されるため、データの一意性を保証する必要がある場合に便利です。

注意点

要素の順序が保証されない

std::unordered_setは要素の順序を保証しません。挿入した順序やソートされた順序で要素を扱いたい場合には適していません。要素の順序が重要な場合はstd::setを使用してください。

ハッシュ関数の選択

std::unordered_setはハッシュ関数に依存して動作します。デフォルトのハッシュ関数は多くの場合で適切に動作しますが、特定のデータ型や用途においてはカスタムのハッシュ関数を定義する必要がある場合があります。ハッシュ関数が適切に定義されていないと、性能が低下する可能性があります。

struct CustomHash {
    std::size_t operator()(int const& key) const {
        return std::hash<int>()(key) ^ (key << 1);
    }
};

std::unordered_set<int, CustomHash> myUnorderedSet;

メモリ消費

std::unordered_setはハッシュテーブルを使用するため、メモリ消費量がstd::setや他のコンテナと比較して多くなることがあります。メモリの使用量が制約となる場合は注意が必要です。

使用例と考慮点

std::unordered_setは、以下のような状況で特に有効です。

  • データの一意性が重要であり、要素の順序が不要な場合
  • 大量のデータに対して高速な追加、削除、検索操作が必要な場合

これらの特性を理解して、適切な場面でstd::unordered_setを活用することが重要です。

両者の違いと選択基準

std::setとstd::unordered_setは、どちらも一意な要素を格納する集合データ構造ですが、それぞれの内部実装と特性に大きな違いがあります。以下にそれらの違いと、使用シーンに応じた選択基準を解説します。

内部構造の違い

std::set

std::setはバランスの取れた二分探索木（通常は赤黒木）を内部的に使用しています。このため、要素は常にソートされた順序で格納されます。検索、追加、削除操作はすべてO(log n)の時間で実行されます。

std::unordered_set

std::unordered_setはハッシュテーブルを使用しています。このため、要素の順序は保証されませんが、検索、追加、削除操作は平均してO(1)の時間で実行されます。ただし、最悪の場合はO(n)になることもあります。

パフォーマンスの違い

検索・追加・削除の速度

  • std::set: O(log n)
  • std::unordered_set: 平均O(1)、最悪O(n)

std::unordered_setは、一般的にstd::setよりも高速な操作が可能です。しかし、ハッシュ関数の品質やデータの性質によってはパフォーマンスが低下する場合があります。

メモリ消費

std::setはバランスの取れた木構造を使用するため、メモリ効率が比較的高いです。一方、std::unordered_setはハッシュテーブルを使用するため、メモリ消費量が多くなる傾向があります。

要素の順序

  • std::set: 要素は常にソートされた順序で格納されます。
  • std::unordered_set: 要素の順序は保証されません。

使用シーンに応じた選択基準

std::setを選ぶべき場合

  • 要素をソートされた順序で保持する必要がある場合。
  • 頻繁に要素を追加・削除し、そのたびにソートされたデータを利用したい場合。
  • データの一意性とともに、順序が重要な場合。

std::unordered_setを選ぶべき場合

  • 高速な検索・追加・削除操作が求められる場合。
  • 要素の順序が不要な場合。
  • ハッシュ関数が適切に定義されており、ハッシュテーブルの性能が発揮できる場合。

具体的な選択例

  • 小規模なデータ集合や、順序が重要な場合はstd::setを使用。
  • 大規模なデータ集合や、順序が不要でパフォーマンスが重要な場合はstd::unordered_setを使用。

これらの基準をもとに、適切なデータ構造を選択することで、効率的なプログラムを実現することができます。

std::setの応用例

std::setは一意な要素をソートされた順序で管理するため、特定の用途に非常に適しています。以下にいくつかの応用例を紹介します。

ユニークな要素の収集とソート

std::setを使用することで、重複を排除しつつソートされた順序で要素を管理できます。例えば、ユーザーからの入力を一意かつソートされた形で収集する場合に便利です。

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> uniqueWords;
    std::string word;
    while (std::cin >> word) {
        uniqueWords.insert(word);
    }

    for (const auto& w : uniqueWords) {
        std::cout << w << " ";
    }
    return 0;
}

上記のコードでは、ユーザーからの入力を収集し、一意かつアルファベット順にソートされた形で出力します。

重複のないランダム抽選

std::setを利用して、重複のないランダムな抽選を行うことができます。

#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>

int main() {
    std::set<int> lotteryNumbers;
    std::srand(std::time(nullptr));

    while (lotteryNumbers.size() < 5) {
        int num = std::rand() % 50 + 1; // 1から50までのランダムな数
        lotteryNumbers.insert(num);
    }

    for (const auto& num : lotteryNumbers) {
        std::cout << num << " ";
    }
    return 0;
}

この例では、1から50までの範囲で重複のない5つのランダムな数字を生成し、出力します。

インターバルの管理

std::setは、インターバルや範囲を管理するのにも役立ちます。例えば、予約システムで重複しない時間帯を管理する場合に有効です。

#include <iostream>
#include <set>
#include <utility> // std::pair

int main() {
    std::set<std::pair<int, int>> timeIntervals;
    timeIntervals.insert({9, 10});
    timeIntervals.insert({11, 12});
    timeIntervals.insert({14, 15});

    for (const auto& interval : timeIntervals) {
        std::cout << "Start: " << interval.first << ", End: " << interval.second << std::endl;
    }
    return 0;
}

このコードは、予約の時間帯を管理し、開始時間と終了時間のペアをソートされた順序で出力します。

重複の排除とソートされた出力の組み合わせ

std::setは重複の排除と自動ソートの両方を提供するため、これらの特性を組み合わせてデータ処理を効率化することができます。例えば、大量のログデータから一意のイベントをソートされた形で抽出する場合などに活用できます。

これらの応用例を通じて、std::setの実践的な利用方法を理解し、適切な場面で効果的に使用することが可能になります。

std::unordered_setの応用例

std::unordered_setは、ハッシュテーブルを基盤とした集合データ構造で、要素の順序を保証しない代わりに高速な操作が可能です。以下にいくつかの応用例を紹介します。

高速な要素の存在確認

std::unordered_setは、要素の存在確認が平均O(1)の時間で行えるため、大量のデータに対して頻繁に検索操作を行う場合に非常に有効です。

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::unordered_set<int> dataSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> searchValues = {3, 7, 10, 15};

    for (int value : searchValues) {
        if (dataSet.find(value) != dataSet.end()) {
            std::cout << value << " is found in the set." << std::endl;
        } else {
            std::cout << value << " is not found in the set." << std::endl;
        }
    }
    return 0;
}

このコードは、データセット内に特定の値が存在するかを高速に確認します。

ユニークなIDの管理

std::unordered_setは、一意のIDの集合を管理するのに適しています。例えば、ユーザーIDや商品IDなどの管理に利用できます。

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> userIDs = {"user1", "user2", "user3"};

    // 新しいユーザーIDを追加
    userIDs.insert("user4");

    // 既存のユーザーIDをチェック
    std::string newID = "user2";
    if (userIDs.find(newID) != userIDs.end()) {
        std::cout << newID << " already exists." << std::endl;
    } else {
        std::cout << newID << " is available." << std::endl;
    }

    return 0;
}

この例では、ユーザーIDの重複を防ぎつつ新しいIDを追加しています。

デュープリケートの検出

大量のデータセットにおいて重複する要素を検出する際に、std::unordered_setは効率的です。

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 3, 7, 8, 9, 10, 1};
    std::unordered_set<int> uniqueNumbers;
    std::unordered_set<int> duplicates;

    for (int number : numbers) {
        if (!uniqueNumbers.insert(number).second) {
            duplicates.insert(number);
        }
    }

    std::cout << "Duplicate numbers: ";
    for (int dup : duplicates) {
        std::cout << dup << " ";
    }
    std::cout << std::endl;

    return 0;
}

このコードは、与えられたリストの中から重複する数値を検出して出力します。

ユニークな要素のカウント

std::unordered_setを利用して、リスト内のユニークな要素の数を効率的にカウントすることができます。

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<int> items = {1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 10, 10};
    std::unordered_set<int> uniqueItems(items.begin(), items.end());

    std::cout << "Number of unique items: " << uniqueItems.size() << std::endl;

    return 0;
}

このコードは、与えられたリストからユニークな要素の数をカウントして出力します。

これらの応用例を通じて、std::unordered_setの実践的な利用方法を理解し、適切な場面で効果的に使用することが可能になります。

パフォーマンス比較

std::setとstd::unordered_setのパフォーマンスは、内部実装が異なるため、それぞれの使用ケースによって大きく異なります。以下に、両者のパフォーマンスを比較し、具体的なケースでの違いを説明します。

挿入操作のパフォーマンス

std::set

std::setは、バランスの取れた二分探索木（通常は赤黒木）を使用しているため、要素の挿入にはO(log n)の時間がかかります。

std::unordered_set

std::unordered_setは、ハッシュテーブルを使用しているため、要素の挿入は平均O(1)の時間で行えます。ただし、ハッシュの衝突が発生する場合は、最悪O(n)の時間がかかることもあります。

#include <iostream>
#include <set>
#include <unordered_set>
#include <chrono>

int main() {
    std::set<int> orderedSet;
    std::unordered_set<int> unorderedSet;

    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        orderedSet.insert(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;
    std::cout << "std::set insert time: " << duration.count() << " seconds" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        unorderedSet.insert(i);
    }
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::unordered_set insert time: " << duration.count() << " seconds" << std::endl;

    return 0;
}

このコードでは、std::setとstd::unordered_setに対する挿入操作の時間を計測しています。一般的に、std::unordered_setの方が高速です。

検索操作のパフォーマンス

std::set

std::setは、二分探索木を使用しているため、要素の検索にはO(log n)の時間がかかります。

std::unordered_set

std::unordered_setは、ハッシュテーブルを使用しているため、要素の検索は平均O(1)の時間で行えます。ただし、最悪の場合はO(n)になることもあります。

#include <iostream>
#include <set>
#include <unordered_set>
#include <chrono>

int main() {
    std::set<int> orderedSet;
    std::unordered_set<int> unorderedSet;
    for (int i = 0; i < 100000; ++i) {
        orderedSet.insert(i);
        unorderedSet.insert(i);
    }

    auto start = std::chrono::high_resolution_clock::now();
    orderedSet.find(50000);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;
    std::cout << "std::set find time: " << duration.count() << " seconds" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    unorderedSet.find(50000);
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::unordered_set find time: " << duration.count() << " seconds" << std::endl;

    return 0;
}

このコードでは、std::setとstd::unordered_setに対する検索操作の時間を計測しています。std::unordered_setの方が一般的に高速です。

削除操作のパフォーマンス

std::set

std::setは、要素の削除にO(log n)の時間がかかります。

std::unordered_set

std::unordered_setは、要素の削除に平均O(1)の時間がかかります。ただし、最悪の場合はO(n)になることもあります。

メモリ使用量

std::setは、二分探索木を使用しているため、比較的メモリ使用量が少ないです。一方、std::unordered_setは、ハッシュテーブルを使用しているため、メモリ使用量が多くなる傾向があります。

選択基準のまとめ

  • 高速な挿入・検索・削除操作が必要な場合は、std::unordered_setを使用する。
  • 要素の順序が重要で、ソートされた状態で要素を保持したい場合は、std::setを使用する。
  • メモリ使用量が制約となる場合は、std::setを検討する。

これらのパフォーマンス特性を理解して、適切なデータ構造を選択することで、プログラムの効率性を向上させることができます。

エラーハンドリング

std::setとstd::unordered_setを使用する際には、いくつかのエラーハンドリングを考慮する必要があります。これにより、コードの堅牢性と信頼性を高めることができます。

std::setのエラーハンドリング

std::setに関連する一般的なエラーは、操作が失敗した場合や無効な操作を試みた場合に発生します。

要素の挿入時のエラーハンドリング

挿入操作は通常成功するため、特にエラーハンドリングは不要ですが、例えば、要素が既に存在する場合に対応することも可能です。

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};
    auto result = mySet.insert(3);

    if (!result.second) {
        std::cerr << "Error: Element 3 already exists in the set." << std::endl;
    } else {
        std::cout << "Element 3 was successfully inserted." << std::endl;
    }

    return 0;
}

要素の削除時のエラーハンドリング

削除操作は、要素が存在しない場合に対応する必要があります。

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};
    size_t numErased = mySet.erase(6);

    if (numErased == 0) {
        std::cerr << "Error: Element 6 not found in the set." << std::endl;
    } else {
        std::cout << "Element 6 was successfully erased." << std::endl;
    }

    return 0;
}

要素の検索時のエラーハンドリング

要素が見つからない場合の処理を考慮します。

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};
    auto it = mySet.find(7);

    if (it == mySet.end()) {
        std::cerr << "Error: Element 7 not found in the set." << std::endl;
    } else {
        std::cout << "Element 7 found in the set." << std::endl;
    }

    return 0;
}

std::unordered_setのエラーハンドリング

std::unordered_setに関連する一般的なエラーは、主にハッシュ関数の問題やハッシュの衝突に関係しています。

ハッシュ関数のエラーハンドリング

独自のハッシュ関数を定義する場合、そのハッシュ関数が正しく動作することを確認する必要があります。例えば、ハッシュ関数が全ての入力に対して同じ値を返す場合、性能が著しく低下します。

#include <iostream>
#include <unordered_set>

struct BadHash {
    size_t operator()(int x) const {
        return 1; // すべての入力に対して同じ値を返す
    }
};

int main() {
    std::unordered_set<int, BadHash> myUnorderedSet = {1, 2, 3, 4, 5};

    // ハッシュ衝突をチェックする
    for (int i = 1; i <= 5; ++i) {
        if (myUnorderedSet.find(i) == myUnorderedSet.end()) {
            std::cerr << "Error: Element " << i << " not found in the set." << std::endl;
        }
    }

    return 0;
}

要素の挿入時のエラーハンドリング

std::unordered_setも、要素の挿入時にエラーが発生する可能性があります。例えば、メモリ不足など。

#include <iostream>
#include <unordered_set>
#include <new> // std::bad_alloc

int main() {
    try {
        std::unordered_set<int> myUnorderedSet;
        for (int i = 0; i < 1000000; ++i) {
            myUnorderedSet.insert(i);
        }
    } catch (const std::bad_alloc& e) {
        std::cerr << "Error: Memory allocation failed - " << e.what() << std::endl;
    }

    return 0;
}

要素の削除時のエラーハンドリング

std::unordered_setも、要素が存在しない場合にエラーを処理する必要があります。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet = {1, 2, 3, 4, 5};
    size_t numErased = myUnorderedSet.erase(6);

    if (numErased == 0) {
        std::cerr << "Error: Element 6 not found in the set." << std::endl;
    } else {
        std::cout << "Element 6 was successfully erased." << std::endl;
    }

    return 0;
}

これらのエラーハンドリングを考慮することで、std::setおよびstd::unordered_setをより堅牢に使用することができます。

練習問題

以下の練習問題を通じて、std::setとstd::unordered_setの理解を深め、実践的なスキルを習得しましょう。

問題1: std::setの基本操作

次の操作を行うプログラムを作成してください。

  1. 整数のstd::setを定義し、1から10までの数を挿入します。
  2. すべての要素を昇順に表示します。
  3. 要素5を削除します。
  4. 7がセットに含まれているかをチェックし、結果を表示します。
#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // 1. 1から10までの数を挿入
    for (int i = 1; i <= 10; ++i) {
        mySet.insert(i);
    }

    // 2. すべての要素を昇順に表示
    std::cout << "Elements in set: ";
    for (const int& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 3. 要素5を削除
    mySet.erase(5);

    // 4. 7がセットに含まれているかチェック
    if (mySet.find(7) != mySet.end()) {
        std::cout << "Element 7 is in the set." << std::endl;
    } else {
        std::cout << "Element 7 is not in the set." << std::endl;
    }

    return 0;
}

問題2: std::unordered_setの基本操作

次の操作を行うプログラムを作成してください。

  1. 文字列のstd::unordered_setを定義し、”apple”, “banana”, “cherry”を挿入します。
  2. すべての要素を表示します。
  3. “banana”を削除します。
  4. “grape”がセットに含まれているかをチェックし、結果を表示します。
#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<std::string> myUnorderedSet;

    // 1. "apple", "banana", "cherry"を挿入
    myUnorderedSet.insert("apple");
    myUnorderedSet.insert("banana");
    myUnorderedSet.insert("cherry");

    // 2. すべての要素を表示
    std::cout << "Elements in unordered set: ";
    for (const std::string& elem : myUnorderedSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 3. "banana"を削除
    myUnorderedSet.erase("banana");

    // 4. "grape"がセットに含まれているかチェック
    if (myUnorderedSet.find("grape") != myUnorderedSet.end()) {
        std::cout << "Element grape is in the set." << std::endl;
    } else {
        std::cout << "Element grape is not in the set." << std::endl;
    }

    return 0;
}

問題3: カスタムハッシュ関数の使用

カスタムハッシュ関数を使用して、std::unordered_setに複数のカスタムオブジェクトを挿入し、特定のオブジェクトを検索するプログラムを作成してください。

#include <iostream>
#include <unordered_set>
#include <string>

struct Person {
    std::string name;
    int age;

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

struct PersonHash {
    std::size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
    }
};

int main() {
    std::unordered_set<Person, PersonHash> persons;

    // カスタムオブジェクトを挿入
    persons.insert({"Alice", 30});
    persons.insert({"Bob", 25});
    persons.insert({"Charlie", 35});

    // 特定のオブジェクトを検索
    Person searchPerson = {"Bob", 25};
    if (persons.find(searchPerson) != persons.end()) {
        std::cout << "Person found: " << searchPerson.name << ", " << searchPerson.age << std::endl;
    } else {
        std::cout << "Person not found" << std::endl;
    }

    return 0;
}

問題4: パフォーマンスの比較

std::setとstd::unordered_setの挿入、検索、削除操作のパフォーマンスを比較するプログラムを作成し、結果を表示してください。

#include <iostream>
#include <set>
#include <unordered_set>
#include <chrono>

int main() {
    std::set<int> orderedSet;
    std::unordered_set<int> unorderedSet;
    const int numElements = 100000;

    // 挿入のパフォーマンス比較
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numElements; ++i) {
        orderedSet.insert(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;
    std::cout << "std::set insert time: " << duration.count() << " seconds" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numElements; ++i) {
        unorderedSet.insert(i);
    }
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::unordered_set insert time: " << duration.count() << " seconds" << std::endl;

    // 検索のパフォーマンス比較
    start = std::chrono::high_resolution_clock::now();
    orderedSet.find(numElements / 2);
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::set find time: " << duration.count() << " seconds" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    unorderedSet.find(numElements / 2);
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::unordered_set find time: " << duration.count() << " seconds" << std::endl;

    // 削除のパフォーマンス比較
    start = std::chrono::high_resolution_clock::now();
    orderedSet.erase(numElements / 2);
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::set erase time: " << duration.count() << " seconds" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    unorderedSet.erase(numElements / 2);
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::unordered_set erase time: " << duration.count() << " seconds" << std::endl;

    return 0;
}

これらの練習問題を通じて、std::setおよびstd::unordered_setの基本操作、カスタムハッシュ関数の利用方法、およびパフォーマンスの比較に関する理解を深めることができます。

まとめ

本記事では、C++の標準ライブラリであるstd::setとstd::unordered_setについて、基本的な使い方から利点と注意点、応用例、パフォーマンス比較、エラーハンドリング、そして理解を深めるための練習問題までを包括的に解説しました。

  • std::setは、要素を自動的にソートし、一意性を保証するデータ構造であり、検索や挿入、削除がO(log n)の時間で行えます。要素の順序が重要な場合や、挿入順序を維持する必要がある場合に適しています。
  • std::unordered_setは、ハッシュテーブルを基盤としており、要素の順序を保証しない代わりに、平均してO(1)の高速な操作が可能です。大量のデータを高速に処理する必要がある場合や、要素の順序が不要な場合に適しています。

それぞれのデータ構造の特性を理解し、適切な場面で選択することが、効率的なプログラムの作成に繋がります。練習問題を通じて実践的なスキルを磨き、std::setとstd::unordered_setの効果的な活用法を身に付けてください。

これで本記事の内容を締めくくります。ぜひ、実際のコードで試してみて、理解を深めてください。

C++
C++ std::set std::unordered_set

コメント

コメントする

目次