MENU
  1. ホーム
  2. C++
  3. STL
  4. set
  5. [C++] setで配列を二部探索するプログラムの書き方

[C++] setで配列を二部探索するプログラムの書き方

C++のstd::setは内部的に要素をソートされた状態で保持するため、二分探索を効率的に行うことができます。

std::set自体は二分木を基にしているため、要素の挿入や検索は平均で\(O(\log n)\)の時間で行われます。

std::setで二分探索を行うには、find関数やlower_bound関数を使用します。

findは特定の要素が存在するかを確認し、lower_boundは指定した値以上の最小の要素を返します。

この記事でわかること
  • std::setの基本的な使い方
  • 二分探索の実装方法
  • 配列からの変換手法
  • 重複要素の管理方法
  • 効率的なデータ検索の技術

目次から探す

std::setを使った二分探索の実装

std::setの初期化と要素の挿入

std::setは、重複を許さない要素の集合を管理するためのコンテナです。

初期化は簡単で、要素を挿入することで自動的にソートされます。

以下は、std::setの初期化と要素の挿入の例です。

#include <iostream>
#include <set>
int main() {
    // std::setの初期化
    std::set<int> mySet;
    // 要素の挿入
    mySet.insert(5);  // 5を挿入
    mySet.insert(3);  // 3を挿入
    mySet.insert(8);  // 8を挿入
    mySet.insert(1);  // 1を挿入
    // 要素の表示
    for (const auto& element : mySet) {
        std::cout << element << " ";  // 要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
1 3 5 8

std::setは自動的に要素をソートして保持します。

これにより、探索が効率的に行えるようになります。

find関数を使った探索

std::setには、特定の要素を探すためのfind関数があります。

この関数は、要素が見つかった場合はそのイテレータを、見つからなかった場合はend()を返します。

以下は、find関数を使った探索の例です。

#include <iostream>
#include <set>
int main() {
    std::set<int> mySet = {1, 3, 5, 8};
    // 探索する要素
    int target = 3;
    auto it = mySet.find(target);  // find関数で探索
    if (it != mySet.end()) {
        std::cout << target << "はセットに存在します。" << std::endl;  // 存在する場合
    } else {
        std::cout << target << "はセットに存在しません。" << std::endl;  // 存在しない場合
    }
    return 0;
}
3はセットに存在します。

find関数は、要素の存在確認に便利です。

lower_bound関数を使った探索

lower_bound関数は、指定した値以上の最初の要素の位置を返します。

この関数を使うことで、特定の値がどこに挿入されるかを知ることができます。

以下は、lower_bound関数を使った探索の例です。

#include <iostream>
#include <set>
int main() {
    std::set<int> mySet = {1, 3, 5, 8};
    // 探索する要素
    int target = 4;
    auto it = mySet.lower_bound(target);  // lower_bound関数で探索
    if (it != mySet.end()) {
        std::cout << target << "以上の最初の要素は" << *it << "です。" << std::endl;  // 結果表示
    } else {
        std::cout << target << "以上の要素は存在しません。" << std::endl;  // 存在しない場合
    }
    return 0;
}
4以上の最初の要素は5です。

lower_bound関数は、挿入位置を知るのに役立ちます。

upper_bound関数を使った探索

upper_bound関数は、指定した値より大きい最初の要素の位置を返します。

この関数を使うことで、特定の値より大きい要素を見つけることができます。

以下は、upper_bound関数を使った探索の例です。

#include <iostream>
#include <set>
int main() {
    std::set<int> mySet = {1, 3, 5, 8};
    // 探索する要素
    int target = 5;
    auto it = mySet.upper_bound(target);  // upper_bound関数で探索
    if (it != mySet.end()) {
        std::cout << target << "より大きい最初の要素は" << *it << "です。" << std::endl;  // 結果表示
    } else {
        std::cout << target << "より大きい要素は存在しません。" << std::endl;  // 存在しない場合
    }
    return 0;
}
5より大きい最初の要素は8です。

upper_bound関数は、特定の条件に合った要素を見つけるのに便利です。

二分探索の実行時間とパフォーマンス

std::setは、内部的に平衡二分探索木(通常は赤黒木)を使用しており、要素の挿入、削除、探索の平均時間計算量はO(log n)です。

これにより、大量のデータを扱う際でも効率的に操作が可能です。

特に、要素がソートされた状態で保持されるため、探索が迅速に行えます。

このように、std::setを使用することで、効率的な二分探索が実現でき、プログラムのパフォーマンスを向上させることができます。

std::setを使った配列の二分探索

配列をstd::setに変換する方法

配列をstd::setに変換するには、配列の要素をstd::setに挿入する必要があります。

以下は、配列をstd::setに変換する例です。

#include <iostream>
#include <set>
int main() {
    // 配列の定義
    int arr[] = {5, 3, 8, 1, 3, 5};
    int size = sizeof(arr) / sizeof(arr[0]);  // 配列のサイズ
    // std::setの初期化
    std::set<int> mySet(arr, arr + size);  // 配列をstd::setに変換
    // 要素の表示
    for (const auto& element : mySet) {
        std::cout << element << " ";  // 要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
1 3 5 8

このように、配列をstd::setに変換することで、重複を排除しつつ自動的にソートされた状態で要素を保持できます。

配列の要素をstd::setに挿入する際の注意点

配列の要素をstd::setに挿入する際には、重複要素が自動的に排除されることに注意が必要です。

以下は、重複要素を持つ配列をstd::setに挿入する例です。

#include <iostream>
#include <set>
int main() {
    // 重複要素を持つ配列の定義
    int arr[] = {2, 4, 4, 6, 2, 8};
    int size = sizeof(arr) / sizeof(arr[0]);  // 配列のサイズ
    // std::setの初期化
    std::set<int> mySet(arr, arr + size);  // 配列をstd::setに変換
    // 要素の表示
    for (const auto& element : mySet) {
        std::cout << element << " ";  // 要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
2 4 6 8

この例では、std::setに挿入された際に重複した要素(2と4)が自動的に排除されていることがわかります。

配列の要素を二分探索する方法

配列の要素をstd::setに変換した後、find関数やlower_bound関数を使って二分探索を行うことができます。

以下は、配列の要素を二分探索する例です。

#include <iostream>
#include <set>
int main() {
    // 配列の定義
    int arr[] = {5, 3, 8, 1, 3, 5};
    int size = sizeof(arr) / sizeof(arr[0]);  // 配列のサイズ
    // std::setの初期化
    std::set<int> mySet(arr, arr + size);  // 配列をstd::setに変換
    // 探索する要素
    int target = 3;
    auto it = mySet.find(target);  // find関数で探索
    if (it != mySet.end()) {
        std::cout << target << "はセットに存在します。" << std::endl;  // 存在する場合
    } else {
        std::cout << target << "はセットに存在しません。" << std::endl;  // 存在しない場合
    }
    return 0;
}
3はセットに存在します。

このように、std::setを使うことで、配列の要素に対して効率的に二分探索を行うことができます。

配列の重複要素に対するstd::setの挙動

std::setは重複を許さないため、配列に重複要素が含まれている場合、挿入時に自動的に排除されます。

以下は、重複要素を持つ配列をstd::setに挿入した際の挙動を示す例です。

#include <iostream>
#include <set>
int main() {
    // 重複要素を持つ配列の定義
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);  // 配列のサイズ
    // std::setの初期化
    std::set<int> mySet(arr, arr + size);  // 配列をstd::setに変換
    // 要素の表示
    for (const auto& element : mySet) {
        std::cout << element << " ";  // 要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
1 2 3 4 5

この例では、重複した要素(2と4)が自動的に排除され、std::setには一意の要素のみが保持されていることが確認できます。

std::setを使用することで、重複要素の管理が容易になります。

応用例

std::setを使った範囲検索

std::setを使用すると、特定の範囲内の要素を簡単に検索できます。

lower_boundとupper_boundを組み合わせることで、指定した範囲の要素を取得することができます。

以下は、範囲検索の例です。

#include <iostream>
#include <set>
int main() {
    std::set<int> mySet = {1, 3, 5, 7, 9, 11, 13};
    // 範囲検索のための境界値
    int lower = 4;
    int upper = 10;
    // lower_boundとupper_boundを使った範囲検索
    auto itLow = mySet.lower_bound(lower);
    auto itUp = mySet.upper_bound(upper);
    std::cout << "範囲内の要素: ";
    for (auto it = itLow; it != itUp; ++it) {
        std::cout << *it << " ";  // 範囲内の要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
範囲内の要素: 5 7 9

このように、std::setを使うことで、特定の範囲に含まれる要素を効率的に取得できます。

std::setを使った重複排除

std::setは、重複を許さない特性を持っているため、データの重複を自動的に排除するのに非常に便利です。

以下は、重複排除の例です。

#include <iostream>
#include <set>
int main() {
    // 重複要素を持つ配列の定義
    int arr[] = {2, 4, 4, 6, 2, 8};
    int size = sizeof(arr) / sizeof(arr[0]);  // 配列のサイズ
    // std::setの初期化
    std::set<int> mySet(arr, arr + size);  // 配列をstd::setに変換
    // 要素の表示
    std::cout << "重複排除後の要素: ";
    for (const auto& element : mySet) {
        std::cout << element << " ";  // 要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
重複排除後の要素: 2 4 6 8

このように、std::setを使用することで、重複したデータを簡単に排除できます。

std::setを使ったソート済みデータの管理

std::setは、要素を自動的にソートして保持するため、ソート済みデータの管理に非常に適しています。

以下は、ソート済みデータの管理の例です。

#include <iostream>
#include <set>
int main() {
    // std::setの初期化
    std::set<int> mySet = {5, 1, 3, 8, 2};
    // 要素の表示
    std::cout << "ソート済みデータ: ";
    for (const auto& element : mySet) {
        std::cout << element << " ";  // 要素を表示
    }
    std::cout << std::endl;  // 改行
    return 0;
}
ソート済みデータ: 1 2 3 5 8

このように、std::setを使用することで、要素が自動的にソートされ、常に整然とした状態でデータを管理できます。

std::setを使った効率的なデータ検索

std::setは、内部的に平衡二分探索木を使用しているため、データの検索が非常に効率的です。

以下は、効率的なデータ検索の例です。

#include <iostream>
#include <set>
int main() {
    std::set<int> mySet = {10, 20, 30, 40, 50};
    // 探索する要素
    int target = 30;
    auto it = mySet.find(target);  // find関数で探索
    if (it != mySet.end()) {
        std::cout << target << "はセットに存在します。" << std::endl;  // 存在する場合
    } else {
        std::cout << target << "はセットに存在しません。" << std::endl;  // 存在しない場合
    }
    return 0;
}
30はセットに存在します。

このように、std::setを使用することで、データの検索が迅速に行え、効率的なプログラムを実現できます。

よくある質問

std::setとstd::vectorの違いは何ですか？

std::setとstd::vectorは、どちらもC++の標準ライブラリに含まれるコンテナですが、いくつかの重要な違いがあります。

以下に主な違いを示します。

  • 重複の扱い: std::setは重複を許さず、一意の要素のみを保持します。

一方、std::vectorは重複を許可し、同じ要素を複数回格納できます。

  • 要素の順序: std::setは要素を自動的にソートして保持しますが、std::vectorは挿入順序を保持します。
  • 検索の効率: std::setは内部的に平衡二分探索木を使用しているため、要素の検索がO(log n)の時間計算量で行えます。

std::vectorは線形探索が必要なため、最悪の場合O(n)の時間計算量になります。

  • メモリの使用: std::setは要素をソートして保持するため、std::vectorよりもメモリのオーバーヘッドが大きくなることがあります。

std::setで二分探索を行う際の注意点は？

std::setで二分探索を行う際には、以下の点に注意が必要です。

  • 要素の存在確認: std::setのfind関数を使用して要素を探索する場合、要素が存在しない場合はend()を返すため、必ずその確認を行う必要があります。
  • 重複要素の扱い: std::setは重複を許さないため、同じ要素を挿入しようとすると、既存の要素はそのまま残ります。

探索時には、重複がないことを前提にする必要があります。

  • イテレータの使用: std::setのイテレータは、要素の順序が保証されているため、範囲検索や順序付きの操作を行う際に便利ですが、イテレータの無効化に注意が必要です。

要素の削除や挿入によってイテレータが無効になることがあります。

std::setのパフォーマンスを向上させる方法は？

std::setのパフォーマンスを向上させるためには、以下の方法を考慮することができます。

  • 適切なデータ型の選択: std::setに格納するデータ型を選ぶ際、比較演算が効率的に行える型を選ぶことで、パフォーマンスが向上します。
  • カスタム比較関数の使用: デフォルトの比較関数ではなく、特定の条件に基づいたカスタム比較関数を使用することで、特定のデータに対する探索効率を向上させることができます。
  • データの事前ソート: 大量のデータを挿入する場合、最初にデータをソートしてからstd::setに挿入することで、挿入時のパフォーマンスを向上させることができます。
  • 適切なメモリ管理: std::setのサイズが大きくなる場合、メモリの再割り当てが発生することがあります。

必要に応じて、reserve関数を使用してメモリを事前に確保することが有効です。

まとめ

この記事では、C++のstd::setを使用した二分探索の実装方法や、配列との連携、応用例について詳しく解説しました。

std::setは、重複を排除しつつ自動的にソートされたデータを管理できるため、効率的なデータ検索や範囲検索が可能です。

これを活用することで、プログラムのパフォーマンスを向上させることができるため、ぜひ実際のプロジェクトに取り入れてみてください。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

set
  • URLをコピーしました！

関連記事

目次から探す