先頭へ戻る

要素を整列する 解答ページ | Programming Place Plus 新C++編

Programming Place Plus トップページ新C++編要素を整列する

先頭へ戻る

このページの概要

このページは、練習問題の解答例や解説のページです。



解答・解説

問題1 (確認★)

std::vector<double> を std::sort関数を使って昇順に整列してください。このとき第3引数に、通常の関数、ラムダ式、関数オブジェクトを使う方法をそれぞれ試してください。


昇順への整列の場合、第3引数を指定しなくてもいいですが(本編解説)、ここではあえて指定しています。

まず関数を使う場合は次のように書けます。

#include <algorithm>
#include <iostream>
#include <vector>

bool compare_less(double a, double b)
{
    return a < b;
}

int main()
{
    std::vector<double> v {2.1, 2.5, 2.23, 1.999, 2.17};

    std::sort(std::begin(v), std::end(v), compare_less);

    for (auto e : v) {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

実行結果:

1.999 2.1 2.17 2.23 2.5

整列の作業の過程で、2つの要素が選ばれ、第3引数に指定した関数に渡されてきます。手前側にあった要素が第1引数、後ろにあった要素が第2引数になりますから、仮引数が2つで、型は要素と同じかその参照型の関数を用意します。戻り値は、望む関係性を満たしていたら true を、そうでなければ false を返すようにします。compare_less関数はそのような要件を満たすように作成した関数です。

次にラムダ式の場合です。

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<double> v {2.1, 2.5, 2.23, 1.999, 2.17};

    std::sort(std::begin(v), std::end(v), [](double a, double b){ return a < b; });

    for (auto e : v) {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

実行結果:

1.999 2.1 2.17 2.23 2.5

compare_less関数と同じことをラムダ式で表現しただけです。ラムダ式の場合、戻り値の型を明示的に書いていませんが、return a < b; の記述から bool型であることが型推論されています。

戻り値の型を明示的に書く記法もあります。[](double a, double b) -> bool { return a < b; } のように、あいだに -> 型名 を挟みます。

最後に、関数オブジェクトを使う方法です。

#include <algorithm>
#include <iostream>
#include <vector>

struct CompareLess {
    bool operator()(double a, double b)
    {
        return a < b;
    }
};

int main()
{
    std::vector<double> v {2.1, 2.5, 2.23, 1.999, 2.17};

    std::sort(std::begin(v), std::end(v), CompareLess{});

    for (auto e : v) {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

実行結果:

1.999 2.1 2.17 2.23 2.5

クラス(構造体)を定義し、operator() にこれまでと同じ実装を施します。std::sort関数の第3引数へは、CompareLess{} のように記述できます。いったん変数を宣言して渡しても構いません。

関数オブジェクトを使う場合は、標準ライブラリの std::less を使う方法もあります。#include <functional> が必要です。

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main()
{
    std::vector<double> v {2.1, 2.5, 2.23, 1.999, 2.17};

    std::sort(std::begin(v), std::end(v), std::less<double>{});

    for (auto e : v) {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

実行結果:

1.999 2.1 2.17 2.23 2.5

問題2 (基本★★)

std::vector<std::string> を、要素の文字数の昇順になるように整列するプログラムを作成してください。


std::sort関数の第3引数に、長さの昇順になる比較を実装したラムダ式(関数)を渡せば実現できます。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> v {
        "aaaaaa",
        "aaa",
        "aaaa",
        "aaa",
        "aaaaaaa",
        "aaaaa",
    };

    std::sort(std::begin(v), std::end(v),
        [](const std::string& a, const std::string& b){
            return a.length() < b.length();
        }
    );

    for (auto& e : v) {
        std::cout << e << "\n";
    }
}

実行結果:

aaa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa

問題3 (応用★★)

std::vector<Card> を整列するプログラムを作成してください。このとき、カードの番号の昇順に並べ、番号が同じ場合はマークの昇順になるようにしてください。

Card 構造体は次のように定義されています。

using CardNumber = signed char;

enum class CardMark : signed char {
    spade,
    club,
    diamond,
    heart,
};

struct Card {
    CardNumber number;
    CardMark mark;
};


たとえば、次のように書けます。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using CardNumber = signed char;

enum class CardMark : signed char {
    spade,
    club,
    diamond,
    heart,
};

struct Card {
    CardNumber number;
    CardMark mark;
};

std::string get_mark_string(CardMark card_mark)
{
    switch (card_mark) {
    case CardMark::spade:
        return "spade";
    case CardMark::club:
        return "club";
    case CardMark::diamond:
        return "diamond";
    case CardMark::heart:
        return "heart";
    default:
        return "";
    }
}

int main()
{
    std::vector<Card> cards {
        { 9, CardMark::diamond },
        { 5, CardMark::diamond },
        { 4, CardMark::club },
        { 7, CardMark::spade },
        { 7, CardMark::heart },
        { 9, CardMark::spade },
    };

    std::sort(std::begin(cards), std::end(cards),
        [](const Card& a, const Card& b){
            if (a.number == b.number) {
                return a.mark < b.mark;
            }
            return a.number < b.number;
        }
    );

    for (auto& card : cards) {
        std::cout << get_mark_string(card.mark) << " : " << static_cast<int>(card.number) << "\n";
    }
}

実行結果:

club : 4
diamond : 5
spade : 7
heart : 7
spade : 9
diamond : 9

std::sort関数の第3引数に指定する関数(ここではラムダ式)には、Card型の要素が2つ渡されてきます。構造体型の場合はデータメンバしだいでは大きくなるので、参照型で受け取るようにすると効率が良いです(Card構造体は非常に小さいですが)。

比較の処理は、まずカードの番号が同じかどうかを調べています。番号が同じときはマークの昇順にするというルールなので、return a.mark < b.mark; として、マークの昇順になるようにしています。番号が異なる場合は、return a.number < b.number; として、番号で昇順になるようにします。

問題4 (応用★★)

名前と得点で構成されている構造体があり、それを要素にする std::vector があります。得点の上位3名の名前と得点を出力するプログラムを作成してください。同じ得点のときは、名前の昇順で並べてください。


上位や下位から数件を知りたいといった場合、データを整列したあと、先頭から目的の件数分を取り出せばいいです。順位付け(ランキング)と整列は深い関係があります。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct ScoreData {
    std::string  name;
    int          score;
};

int main()
{
    std::vector<ScoreData> v {
        {"Saitou Ken", 75},
        {"Yoshida Emiko", 87},
        {"Saitou Yuuko", 64},
        {"Saitou Akihisa", 87},
        {"Nakamura Hideo", 91},
    };

    std::sort(std::begin(v), std::end(v),
        [](const ScoreData& a, const ScoreData& b){
            if (a.score == b.score) {
                return a.name < b.name;
            }
            return a.score > b.score;
        }
    );

    for (int i = 0; i < 3; ++i) {
        std::cout << v.at(i).name << ": " << v.at(i).score << "\n";
    }
}

実行結果:

Nakamura Hideo: 91
Saitou Akihisa: 87
Yoshida Emiko: 87

整列の考え方はここまでに何度かみてきたことと同じです。今回は、得点の降順に並べればいいことになりますが、得点が同じなら名前の昇順にします。不等号の向きに注意してください。

整列を終えたら、上位から3名分だけ出力すれば目的を果たせます。

この問題のように上位数件だけが分かればいい場合で、要素数が非常に多いときには、すべての要素を整列させると処理量が多くなって無駄になるかもしれません。代わりの方法として、std::partial_sort関数1 2を使うと、用がある範囲だけを整列済みにすることができ、処理量を削減できる可能性があります。


参考リンク



更新履歴




はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー