[C++] 二次元のvectorから要素を検索する方法

2024-08-202024-08-25

C++で二次元のvectorから要素を検索するには、ネストされたループを使用します。外側のループで行を、内側のループで列を走査し、各要素をチェックします。

見つけたい要素と一致するかをif文で確認し、一致した場合にその位置を記録することが一般的です。

STLのfind関数を使用することも可能ですが、二次元vectorでは手動でループを回す方法が一般的です。

この記事でわかること

二次元vectorでの線形探索とその実装方法
二分探索を用いた効率的な要素検索の手法
カスタム検索における条件付き検索やラムダ式の活用法
マトリックスや文字列、座標データを扱う応用例

目次から探す

二次元vectorでの要素検索の基本

二次元vectorは、C++で多次元データを扱う際に非常に便利なデータ構造です。

ここでは、二次元vectorから特定の要素を検索する基本的な方法について解説します。

線形探索の概要

線形探索は、データ構造内の要素を順番に確認し、目的の要素を見つける最も基本的な検索方法です。

二次元vectorの場合、各行と列を順に確認していきます。

この方法は、データが整列されていない場合でも使用できるため、汎用性が高いです。

線形探索の実装方法

以下に、二次元vectorで線形探索を行うサンプルコードを示します。

#include <iostream>
#include <vector>
int main() {
    // 二次元vectorの定義
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int target = 5; // 検索したい要素
    bool found = false;
    // 線形探索の実装
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); ++j) {
            if (matrix[i][j] == target) {
                std::cout << "要素 " << target << " は位置 (" << i << ", " << j << ") にあります。" << std::endl;
                found = true;
                break;
            }
        }
        if (found) break;
    }
    if (!found) {
        std::cout << "要素 " << target << " は見つかりませんでした。" << std::endl;
    }
    return 0;
}

要素 5 は位置 (1, 1) にあります。

このコードは、二次元vector内の要素を順に確認し、目的の要素が見つかった場合にその位置を出力します。

見つからなかった場合は、その旨を出力します。

線形探索の時間計算量

線形探索の時間計算量はO(n*m)です。

ここで、nは行数、mは列数を表します。

すべての要素を確認する必要があるため、データ量が増えると処理時間も増加します。

線形探索の利点と欠点

スクロールできます

利点	欠点
データが整列されていなくても使用可能	時間計算量が高く、効率が悪い
実装が簡単で理解しやすい	大規模データには不向き

線形探索は、データが少ない場合や、データが整列されていない場合に有効です。

しかし、データ量が多い場合は、他の効率的な検索アルゴリズムを検討する必要があります。

効率的な要素検索方法

二次元vectorでの要素検索を効率的に行うためには、データの特性を活かしたアルゴリズムを使用することが重要です。

ここでは、効率的な検索方法の一つである二分探索について解説します。

二分探索の概要

二分探索は、データが整列されている場合に使用できる効率的な検索アルゴリズムです。

データを半分に分割し、目的の要素がどちらの半分にあるかを判断しながら探索を進めます。

この方法により、探索範囲を急速に狭めることができます。

二分探索の前提条件

二分探索を使用するためには、データが整列されている必要があります。

二次元vectorの場合、各行が整列されていることが前提となります。

また、行ごとに独立して二分探索を行うことが一般的です。

二分探索の実装方法

以下に、二次元vectorで二分探索を行うサンプルコードを示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::binary_searchを使用するために必要
int main() {
    // 整列された二次元vectorの定義
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int target = 5; // 検索したい要素
    bool found = false;
    // 各行に対して二分探索を実行
    for (size_t i = 0; i < matrix.size(); ++i) {
        if (std::binary_search(matrix[i].begin(), matrix[i].end(), target)) {
            std::cout << "要素 " << target << " は行 " << i << " に存在します。" << std::endl;
            found = true;
            break;
        }
    }
    if (!found) {
        std::cout << "要素 " << target << " は見つかりませんでした。" << std::endl;
    }
    return 0;
}

要素 5 は行 1 に存在します。

このコードは、各行が整列されている二次元vectorに対して、std::binary_searchを用いて効率的に要素を検索します。

二分探索の時間計算量

二分探索の時間計算量はO(log m)です。

ここで、mは各行の要素数を表します。

行ごとに探索を行うため、全体の時間計算量はO(n log m)となります。

nは行数です。

二分探索の利点と欠点

スクロールできます

利点	欠点
時間計算量が低く、効率的	データが整列されている必要がある
大規模データに対しても高速	二次元vector全体の整列は難しい

二分探索は、データが整列されている場合に非常に効率的です。

しかし、整列されていないデータに対しては使用できないため、データの特性に応じて適切なアルゴリズムを選択することが重要です。

二次元vectorでのカスタム検索

二次元vectorでのカスタム検索は、特定の条件に基づいて要素を検索する方法です。

標準的な検索方法では対応できない複雑な条件を扱う際に有効です。

条件付き検索の実装

条件付き検索では、特定の条件を満たす要素を見つけるために、カスタムロジックを実装します。

以下に、条件付き検索の基本的な実装例を示します。

#include <iostream>
#include <vector>
int main() {
    // 二次元vectorの定義
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int threshold = 5; // 条件としての閾値
    bool found = false;
    // 条件付き検索の実装
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); ++j) {
            if (matrix[i][j] > threshold) {
                std::cout << "要素 " << matrix[i][j] << " は閾値 " << threshold << " を超えています。" << std::endl;
                found = true;
            }
        }
    }
    if (!found) {
        std::cout << "閾値 " << threshold << " を超える要素は見つかりませんでした。" << std::endl;
    }
    return 0;
}

要素 6 は閾値 5 を超えています。
要素 7 は閾値 5 を超えています。
要素 8 は閾値 5 を超えています。
要素 9 は閾値 5 を超えています。

このコードは、二次元vector内の要素が特定の閾値を超えるかどうかを確認し、条件を満たす要素を出力します。

ラムダ式を用いた検索

ラムダ式を用いることで、より柔軟な条件を簡潔に記述できます。

以下に、ラムダ式を用いた検索の例を示します。

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    // 二次元vectorの定義
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int target = 5; // 検索したい要素
    bool found = false;
    // ラムダ式を用いた検索
    for (size_t i = 0; i < matrix.size(); ++i) {
        auto it = std::find_if(matrix[i].begin(), matrix[i].end(), [target](int value) {
            return value == target;
        });
        if (it != matrix[i].end()) {
            std::cout << "要素 " << target << " は行 " << i << " に存在します。" << std::endl;
            found = true;
            break;
        }
    }
    if (!found) {
        std::cout << "要素 " << target << " は見つかりませんでした。" << std::endl;
    }
    return 0;
}

要素 5 は行 1 に存在します。

このコードは、ラムダ式を用いて特定の要素を検索し、見つかった場合にその位置を出力します。

std::find_ifを用いた検索

std::find_ifは、条件を満たす最初の要素を見つけるための標準ライブラリ関数です。

ラムダ式と組み合わせることで、柔軟な検索が可能です。

検索結果の処理方法

検索結果の処理は、見つかった要素に対してどのような操作を行うかを決定します。

以下のような処理が考えられます。

見つかった要素の位置を出力する
見つかった要素を別の値に置き換える
見つかった要素を削除する

これらの処理は、検索の目的に応じて適切に選択することが重要です。

応用例

二次元vectorは、さまざまな応用に利用できる柔軟なデータ構造です。

ここでは、二次元vectorを用いたいくつかの応用例を紹介します。

二次元vectorを用いたマトリックス検索

二次元vectorは、数値データを格納するマトリックスとして利用できます。

特定の条件に基づいてマトリックス内の要素を検索することが可能です。

#include <iostream>
#include <vector>
int main() {
    // 二次元vectorをマトリックスとして定義
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int target = 6; // 検索したい要素
    bool found = false;
    // マトリックス内の要素を検索
    for (size_t i = 0; i < matrix.size(); ++i) {
        for (size_t j = 0; j < matrix[i].size(); ++j) {
            if (matrix[i][j] == target) {
                std::cout << "要素 " << target << " は位置 (" << i << ", " << j << ") にあります。" << std::endl;
                found = true;
                break;
            }
        }
        if (found) break;
    }
    if (!found) {
        std::cout << "要素 " << target << " は見つかりませんでした。" << std::endl;
    }
    return 0;
}

要素 6 は位置 (1, 2) にあります。

このコードは、マトリックス内の特定の要素を検索し、その位置を出力します。

二次元vectorでの文字列検索

二次元vectorは、文字列データを格納することもできます。

以下に、文字列を検索する例を示します。

#include <iostream>
#include <vector>
#include <string>
int main() {
    // 二次元vectorを文字列データとして定義
    std::vector<std::vector<std::string>> grid = {
        {"apple", "banana", "cherry"},
        {"date", "fig", "grape"},
        {"kiwi", "lemon", "mango"}
    };
    std::string target = "fig"; // 検索したい文字列
    bool found = false;
    // 文字列データ内の要素を検索
    for (size_t i = 0; i < grid.size(); ++i) {
        for (size_t j = 0; j < grid[i].size(); ++j) {
            if (grid[i][j] == target) {
                std::cout << "文字列 \"" << target << "\" は位置 (" << i << ", " << j << ") にあります。" << std::endl;
                found = true;
                break;
            }
        }
        if (found) break;
    }
    if (!found) {
        std::cout << "文字列 \"" << target << "\" は見つかりませんでした。" << std::endl;
    }
    return 0;
}

文字列 "fig" は位置 (1, 1) にあります。

このコードは、二次元vector内の文字列を検索し、その位置を出力します。

二次元vectorを用いた座標検索

二次元vectorは、座標データを格納するのにも適しています。

特定の座標に基づいてデータを検索することができます。

#include <iostream>
#include <vector>
int main() {
    // 二次元vectorを座標データとして定義
    std::vector<std::vector<int>> coordinates = {
        {0, 1, 2},
        {3, 4, 5},
        {6, 7, 8}
    };
    int x = 2, y = 1; // 検索したい座標
    if (x < coordinates.size() && y < coordinates[x].size()) {
        std::cout << "座標 (" << x << ", " << y << ") の値は " << coordinates[x][y] << " です。" << std::endl;
    } else {
        std::cout << "指定された座標は範囲外です。" << std::endl;
    }
    return 0;
}