Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

概要

要素数が多い 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;
}
_meki
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした