set

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

2025-01-18更新日: 2025-01-18

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は、重複を許さない要素の集合を管理するためのコンテナです。

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

以下は、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;
}