vector

[C++] 二次元のvectorをキーでソートする方法

C++で二次元のvectorをキーでソートするには、std::sort関数を使用します。

std::sortは、カスタムの比較関数を受け取ることができるため、特定のキーに基づいてソートすることが可能です。

例えば、vector<vector<int>>を2番目の要素でソートしたい場合、比較関数をラムダ式で定義し、std::sortに渡します。

比較関数は、2つの要素を受け取り、ソートの順序を決定するためにそれらを比較します。

これにより、任意のキーに基づいて二次元ベクトルを柔軟にソートできます。

目次から探す

二次元ベクトルの基本
ソートの基本
二次元ベクトルのソート
キーによるソートの実装
応用例
まとめ

二次元ベクトルの基本

二次元ベクトルは、C++において多次元データを扱うための便利なデータ構造です。

通常の一次元ベクトルと同様に、std::vectorを使用して実装されますが、二次元ベクトルはベクトルの中にベクトルを格納することで、行列のような構造を持ちます。

これにより、表形式のデータや複雑なデータセットを簡単に管理することが可能です。

二次元ベクトルは、動的にサイズを変更できるため、データの追加や削除が容易であり、柔軟なデータ操作が求められる場面で特に有用です。

以下に、二次元ベクトルの基本的な使い方を示します。

#include <iostream>
#include <vector>
int main() {
    // 二次元ベクトルの宣言
    std::vector<std::vector<int>> matrix;
    // 行を追加
    matrix.push_back({1, 2, 3});
    matrix.push_back({4, 5, 6});
    matrix.push_back({7, 8, 9});
    // 二次元ベクトルの要素を出力
    for (const auto& row : matrix) {
        for (int value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

1 2 3
4 5 6
7 8 9

この例では、3×3の行列を二次元ベクトルとして作成し、各要素を出力しています。

push_backを使用して行を追加し、ネストされたループで各要素にアクセスしています。

二次元ベクトルは、行列のようなデータを扱う際に非常に便利です。

ソートの基本

ソートの概念

ソートとは、データを特定の順序に並べ替える操作のことを指します。

一般的には、数値や文字列を昇順または降順に並べ替えることが多いです。

ソートは、データの検索や分析を効率的に行うための基本的な操作であり、アルゴリズムの中でも非常に重要な役割を果たします。

ソートアルゴリズムには、バブルソート、クイックソート、マージソートなど、さまざまな種類がありますが、C++では標準ライブラリを利用することで簡単にソートを実現できます。

C++におけるソートの方法

C++では、標準ライブラリの<algorithm>ヘッダーに含まれるstd::sort関数を使用して、配列やベクトルをソートすることができます。

この関数は、内部で効率的なクイックソートやイントロソートを使用しており、一般的な用途において非常に高速です。

std::sortは、デフォルトで昇順にソートを行いますが、カスタムの比較関数を指定することで、降順や特定の条件に基づいたソートも可能です。

std::sort関数の使い方

std::sort関数を使用するには、まず<algorithm>ヘッダーをインクルードする必要があります。

次に、ソートしたいデータの範囲を指定してstd::sortを呼び出します。

以下に、std::sortを使用した簡単な例を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // ベクトルの宣言と初期化
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    // 昇順にソート
    std::sort(numbers.begin(), numbers.end());
    // ソートされたベクトルを出力
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

1 2 5 5 6 9

この例では、std::sortを使用して整数のベクトルを昇順にソートしています。

numbers.begin()とnumbers.end()でベクトル全体の範囲を指定し、ソート後の結果を出力しています。

std::sortは、非常にシンプルでありながら強力なソート機能を提供します。

二次元ベクトルのソート

二次元ベクトルをソートする理由

二次元ベクトルをソートする理由は、データの整理や検索を効率化するためです。

例えば、行列形式のデータを特定の列に基づいて並べ替えることで、データの分析や視覚化が容易になります。

また、ソートされたデータは、バイナリサーチなどのアルゴリズムを適用する際に有利です。

特に、データベースのような構造を持つデータセットでは、特定のフィールドに基づいてデータをソートすることが一般的です。

ソートのための比較関数

二次元ベクトルをソートする際には、どの列を基準にソートするかを指定する必要があります。

これを実現するために、std::sort関数にカスタムの比較関数を渡します。

比較関数は、2つの要素を受け取り、それらの順序を決定するためのブール値を返します。

以下に、特定の列を基準にソートするための比較関数の例を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
// 比較関数：第2列を基準に昇順ソート
bool compareBySecondColumn(const std::vector<int>& a, const std::vector<int>& b) {
    return a[1] < b[1];
}
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<int>> matrix = {
        {3, 2, 5},
        {1, 4, 7},
        {2, 1, 6}
    };
    // 第2列を基準にソート
    std::sort(matrix.begin(), matrix.end(), compareBySecondColumn);
    // ソートされた二次元ベクトルを出力
    for (const auto& row : matrix) {
        for (int value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

2 1 6
3 2 5
1 4 7

この例では、二次元ベクトルの第2列を基準に昇順でソートしています。

ラムダ式を使ったソート

C++11以降では、ラムダ式を使用して簡潔に比較関数を定義することができます。

ラムダ式を使うことで、コードの可読性が向上し、比較関数を別途定義する必要がなくなります。

以下に、ラムダ式を使用したソートの例を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<int>> matrix = {
        {3, 2, 5},
        {1, 4, 7},
        {2, 1, 6}
    };
    // ラムダ式を使って第2列を基準にソート
    std::sort(matrix.begin(), matrix.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[1] < b[1];
    });
    // ソートされた二次元ベクトルを出力
    for (const auto& row : matrix) {
        for (int value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

2 1 6
3 2 5
1 4 7

この例では、ラムダ式を使用して第2列を基準にソートしています。

ラムダ式を使うことで、コードがより簡潔になり、特定の条件に基づいたソートを容易に実装できます。

キーによるソートの実装

特定の列をキーにしたソート

二次元ベクトルをソートする際に、特定の列をキーとして使用することがよくあります。

これにより、データを特定の属性に基づいて整理することができます。

以下に、特定の列をキーにしてソートする方法を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<int>> matrix = {
        {3, 2, 5},
        {1, 4, 7},
        {2, 1, 6}
    };
    // 第1列を基準にソート
    std::sort(matrix.begin(), matrix.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[0] < b[0];
    });
    // ソートされた二次元ベクトルを出力
    for (const auto& row : matrix) {
        for (int value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

1 4 7
2 1 6
3 2 5

この例では、第1列を基準に昇順でソートしています。

複数のキーによるソート

複数のキーを使用してソートすることも可能です。

これは、主キーと副キーを持つデータを整理する際に便利です。

以下に、複数のキーを使用したソートの例を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<int>> matrix = {
        {3, 2, 5},
        {1, 4, 7},
        {2, 1, 6},
        {2, 3, 8}
    };
    // 第1列を基準に昇順、同じ場合は第2列を基準に昇順でソート
    std::sort(matrix.begin(), matrix.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        if (a[0] == b[0]) {
            return a[1] < b[1];
        }
        return a[0] < b[0];
    });
    // ソートされた二次元ベクトルを出力
    for (const auto& row : matrix) {
        for (int value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

この例では、第1列を主キー、第2列を副キーとしてソートしています。

降順ソートの実装

降順でソートする場合は、比較関数の条件を逆にするだけです。

以下に、降順ソートの例を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<int>> matrix = {
        {3, 2, 5},
        {1, 4, 7},
        {2, 1, 6}
    };
    // 第1列を基準に降順でソート
    std::sort(matrix.begin(), matrix.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[0] > b[0];
    });
    // ソートされた二次元ベクトルを出力
    for (const auto& row : matrix) {
        for (int value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

3 2 5
2 1 6
1 4 7

この例では、第1列を基準に降順でソートしています。

降順ソートは、比較関数内で>演算子を使用することで実現できます。

応用例

文字列を含む二次元ベクトルのソート

二次元ベクトルは、整数だけでなく文字列を含むデータも扱うことができます。

文字列を含む二次元ベクトルをソートする際には、文字列の辞書順を基準にすることが一般的です。

以下に、文字列を含む二次元ベクトルのソート例を示します。

#include <iostream>
#include <vector>
#include <algorithm> // std::sortを使用するために必要
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<std::string>> data = {
        {"apple", "red"},
        {"banana", "yellow"},
        {"grape", "purple"}
    };
    // 第1列(果物名)を基準にソート
    std::sort(data.begin(), data.end(), [](const std::vector<std::string>& a, const std::vector<std::string>& b) {
        return a[0] < b[0];
    });
    // ソートされた二次元ベクトルを出力
    for (const auto& row : data) {
        for (const std::string& value : row) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

apple red
banana yellow
grape purple

この例では、果物名を基準に辞書順でソートしています。

カスタムオブジェクトを含む二次元ベクトルのソート

二次元ベクトルは、カスタムオブジェクトを含むデータも扱うことができます。

カスタムオブジェクトをソートする際には、オブジェクトの特定のメンバ変数を基準にすることが一般的です。

以下に、カスタムオブジェクトを含む二次元ベクトルのソート例を示します。

#include <algorithm> // std::sortを使用するために必要
#include <iostream>
#include <vector>
// カスタムオブジェクトの定義
struct Person {
    std::string name;
    int age;
};
int main() {
    // 二次元ベクトルの宣言と初期化
    std::vector<std::vector<Person>> people = {
        {{"Alice", 30},   {"Bob", 25}  },
        {{"Charlie", 35}, {"David", 20}}
    };
    // 年齢を基準にソート
    std::sort(people.begin(), people.end(),
              [](const std::vector<Person>& a, const std::vector<Person>& b) {
                  return a[0].age < b[0].age;
              });
    // ソートされた二次元ベクトルを出力
    for (const auto& row : people) {
        for (const Person& person : row) {
            std::cout << person.name << " (" << person.age << ") ";
        }
        std::cout << std::endl;
    }
    return 0;
}

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

この例では、各行の最初の人物の年齢を基準にソートしています。

ソートのパフォーマンス最適化

ソートのパフォーマンスを最適化することは、大規模なデータセットを扱う際に重要です。

C++のstd::sortは、内部で効率的なアルゴリズムを使用していますが、データの特性に応じてさらなる最適化が可能です。

以下に、ソートのパフォーマンスを向上させるためのいくつかの方法を示します。

データの前処理: ソート前にデータをフィルタリングして、不要な要素を削除することで、ソートの負荷を軽減できます。
適切なデータ型の選択: ソートするデータの型を適切に選択することで、メモリ使用量を削減し、パフォーマンスを向上させることができます。
並列ソートの利用: C++17以降では、std::sortに並列実行ポリシーを指定することで、マルチスレッドによるソートが可能です。

これにより、ソートの速度を大幅に向上させることができます。

これらの方法を組み合わせることで、ソートのパフォーマンスを最大限に引き出すことができます。

まとめ

この記事では、C++における二次元ベクトルのソート方法について、基本的な概念から応用例までを詳しく解説しました。

特定の列をキーにしたソートや複数のキーによるソート、さらには文字列やカスタムオブジェクトを含む二次元ベクトルのソート方法を学ぶことで、データの整理や検索を効率化する手法を身につけることができたでしょう。

これを機に、実際のプログラムで二次元ベクトルのソートを試し、データ操作のスキルをさらに高めてみてください。