配列をオリジナルデータは変更せずにソートしたい

概要

要素数が多い or 格納要素のサイズが大きくてソートに時間がかかるなどの理由でオリジナルの配列は触りたくないけど、ソートした結果が欲しいという状況がときどきあります。

そんなときはオリジナル配列要素のポインタを要素とする配列を作ってそれをソートすると便利です。

オリジナル配列を変更することは無いですし、ソートの過程で動くデータがポインタなので、要素交換のコストが小さく高速です。

方法

下の例ではくだもの構造体のベクトルからポインタのベクトル作り、そのベクトルをソートしています。

サンプルコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

//! くだもの構造体
struct Fruit
{
    Fruit(int _id, int _price, string _name)
        : id(_id),
        price(_price),
        name(_name)
    { }

    int id;         //!< 品番.
    int price;      //!< 値段.
    string name;    //!< 名前.
};

int main() {

    // オリジナルデータ作成
    std::vector<Fruit> vec;
    vec.push_back(Fruit(0, 150, "apple"));
    vec.push_back(Fruit(1, 110, "orange"));
    vec.push_back(Fruit(2, 350, "strawberry"));
    vec.push_back(Fruit(3, 160, "persimmon"));
    vec.push_back(Fruit(4, 100, "kiwi"));

    // 参照配列作成
    std::vector<const Fruit*> ref;
    for (const Fruit& f : vec)
    {  // ポインタをコピー
        ref.push_back(&f);
    }

    std::sort(ref.begin(), ref.end(),
        [] (const Fruit* l, const Fruit* r)
        {   // 名前順にソート
            return l->name < r->name;
        });

    cout << "ソート結果：\n";
    for (const Fruit* f : ref)
    {
        cout << f->id << ", " << f->price << ", " << f->name << endl;
    }

    cout << "\nオリジナルは変わってないよ：\n";
    for (const Fruit& f : vec)
    {
        cout << f.id << ", " << f.price << ", " << f.name << endl;
    }

    return 0;
}

コンソール出力

ソート結果：
0, 150, apple
4, 100, kiwi
1, 110, orange
3, 160, persimmon
2, 350, strawberry

オリジナルは変わってないよ：
0, 150, apple
1, 110, orange
2, 350, strawberry
3, 160, persimmon
4, 100, kiwi

注意点

この例のようにオリジナルデータが動的配列の場合、 resize や push_back などでメモリの再確保が行われると、ポインタの配列は壊れてしまいます。

それに気づかずにポインタ経由で要素を参照しようとすると、無効なメモリアクセスが発生するため注意が必要です。

大変なことになる例

int main() {

    // オリジナルデータ作成
    std::vector<Fruit> vec;
    vec.push_back(Fruit(0, 150, "apple"));
    vec.push_back(Fruit(1, 110, "orange"));
    vec.push_back(Fruit(2, 350, "strawberry"));
    vec.push_back(Fruit(3, 160, "persimmon"));
    vec.push_back(Fruit(4, 100, "kiwi"));

    // 参照配列作成
    std::vector<const Fruit*> ref;
    for (const Fruit& f : vec)
    {  // ポインタをコピー
        ref.push_back(&f);
    }

    std::sort(ref.begin(), ref.end(),
        [] (const Fruit* l, const Fruit* r)
        {   // 名前順にソート
            return l->name < r->name;
        });

    "メモリ再確保 (=ref 内のデータが無効化)"
    vec.resize(100);

    cout << "ソート結果：\n";
    for (const Fruit* f : ref)
    {    これをやると大変なことになる！
        cout << f->id << ", " << f->price << ", " << f->name << endl;
    }

    return 0;
}