要素を整列する | Programming Place Plus　新C++編

整列

ポーカーのプログラムの話を続けていきます。

前のページでは、52枚のカード（今後は山札と呼ぶことにします）を準備しました。山札のカードはシャッフルされ、ここからカードが５枚配られます。この５枚のカードを手札と呼ぶことにします。

山札のカードはシャッフルされた状態で開始するのが望ましいのに対し、手札のカードはプレイヤーに見せなければならないので、分かりやすいように規則正しく並べて提示したほうがいいでしょう。また、このあと役の判定コードを作らなければなりませんが、そのときにも、規則的に並んでいてくれたほうが取り扱いやすくなります。

そこで、このページでは、std::vector<Card> を規則的に並び替える方法を説明していきます。Card型の場合なら、カードの数字が小さい方から大きい方へ並び、数字が同じならマークの順番（scoped enum の列挙子の定義順がいいでしょう）に並ばせるようにします。

このように、いくつかある要素をなんらかの規則にしたがった並び順になるように並べることを、整列（ソート）(sort、sorting) と呼びます。整列を実現する方法（アルゴリズム）はいくつも存在します。それらを知っていれば、自力で整列のプログラムを書けますが、標準ライブラリにはすでにいくつか用意されたものがあるので、原則としてこちらを使うべきです。

整列のアルゴリズムについては、アルゴリズムとデータ構造編【整列】で解説しています（Ｃ言語による解説です）。

要素が数値なのであれば、小さい数から大きい数になるように並べるでしょうし、要素が文字や文字列の場合なら、辞書の並び順に合わせることが一般的でしょう。こういった、一般的に自然と思われる順序に並べること、あるいはそのように並んでいることを昇順（正順） (ascending order)、その反対の順序に並べること、あるいはそのように並んでいることを降順（逆順） (descending order) といいます。

また、整列アルゴリズムの種類によって、安定な整列（安定ソート） (stable sort) と、そうでない整列があります。安定な整列では、データ列の中にまったく同じ値を持った要素が複数あった場合に、整列をおこなう前と後で、それらの要素の位置関係（どちらが手前にあるか）が変わらない保証があります。安定な整列でない場合は、位置関係の保証がありません（保証されないだけで、必ずしも位置関係が崩れるとはかぎりません）。

このページで紹介する整列に関する標準ライブラリの機能を使うには、#include <algorithm> の記述が必要です。

std::sort関数

まずは、std::sort関数を紹介します。std::sort関数は、安定な整列を保証しません。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト（cpprefjp、cppreference.com）で確認してください。

【上級】std::sort関数がどのような整列アルゴリズムを用いているかに関する規定はありませんが、計算量が O(N log N) であることが求められています¹。クイックソート（アルゴリズムとデータ構造編【整列】第６章）は最悪時の計算量がこの要件を満たせないため、多くの場合、イントロソート²などが使われています。

【上級】std::sort関数は安定な整列を保証しませんが、一見して安定な整列であるかのような結果になる場合はあります。たとえば要素数が少ない場合にかぎって、挿入ソートなどの安定な整列アルゴリズムを使うように実装されることがあるためです。このような実装をするのは、イントロソートのような高度な整列アルゴリズムは要素数がある程度多ければ非常に効果的ですが、要素が少ないと、処理が複雑な分だけかえって遅くなるためです。

std::sort関数に、整列したい要素の範囲をあらわす２つのイテレータを指定すると、それだけで昇順に整列してくれます。

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

int main()
{
    std::vector<int> v {5, 6, -1, 3, 7, 2, 3};

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

実行結果：

-1 2 3 3 5 6 7

降順に整列したい場合は、第３引数を追加します。

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

int main()
{
    std::vector<int> v {5, 6, -1, 3, 7, 2, 3};

    std::sort(std::begin(v), std::end(v), [](int a, int b){ return a > b; });
    
    for (auto e : v) {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

実行結果：

7 6 5 3 3 2 -1

第３引数には、要素の大小関係を決める関数を指定します（関数オブジェクトやラムダ式でも構いません）。

この引数の意味を理解するためには、整列の仕組みを知っておかなければなりません。整列の際には、２つの要素の大小関係の比較が何度も繰り返されます。そして、大小関係が、最終的に望む順番と反対になっていたら、その２つの要素の位置を入れ替えます。これを整列したい範囲内の要素すべてに対して行っていけば、整列が完了します。

この過程の中にある、「２つの要素の大小関係の比較」の部分を実装したものが、std::sort関数の第３引数に渡す関数です。そのため、注目している２つの要素が実引数となって渡されてきます。今現在手前側にある要素が１つ目の引数になり、後ろ側にある要素が２つ目の引数になります。仮引数の型は要素の型と同じか、その参照型でなければなりません。

第３引数に渡す関数の戻り値は、望む関係性を満たすときに true を、そうでなければ false を返すようにします。int型の要素を降順にしたいのであれば、左側の要素（仮引数a）のほうが大きいことを望むので、a > b の結果を返すように実装すればいいということになります。昇順のサンプルプログラムでは第３引数がありませんが、実際には a < b の結果を返すように実装したことになります。

このサンプルプログラムのように、ラムダ式を使って書くのもいいですが、a > b の意味で使える関数オブジェクトのためのクラスが標準ライブラリに定義されているので、そちらを使う方法もあります。

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

int main()
{
    std::vector<int> v {5, 6, -1, 3, 7, 2, 3};

    std::sort(std::begin(v), std::end(v), std::greater<int>{});
    
    for (auto e : v) {
        std::cout << e << " ";
    }
    std::cout << "\n";
}

実行結果：

7 6 5 3 3 2 -1

std::greater は関数オブジェクトとして使えるクラスで、return a > b; という実装の operator() が定義されています。int型を扱うのなら、std::greater<int> という型名で使用します。

また、std::greater<int>{} という構文は、クラス型の変数を作るが、変数には格納せず、使い捨てにするという意味です。{} の部分は初期化子です。

std::greater のほかにも、関係演算子・等価演算子の違いによって合計６種類のクラスが定義されています。いずれも、使用するには #include <functional> が必要です。

名前	operator() の実装
std::greater	return a > b;
std::greater_equal	return a >= b;
std::less	return a < b;
std::less_equal	return a <= b;
std::equal_to	return a == b;
std::not_equal_to	return a != b;

複数のキーによる整列

std::sort関数の第３引数を利用して、複数のキーによる整列が実現できます。

たとえば、姓と名が分かれて登録されているとき、姓で整列を行い、姓が同じ人がいたら名によって並び順を決めることができます。

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

struct Name {
    std::string  family_name;
    std::string  first_name;
};

int main()
{
    std::vector<Name> names {
        {"Saitou", "Ken"},
        {"Yoshida", "Emiko"},
        {"Saitou", "Yuuko"},
        {"Saitou", "Akihisa"},
        {"Nakamura", "Hideo"},
    };

    std::sort(std::begin(names), std::end(names),
        [](const Name& a, const Name& b) {
            if (a.family_name == b.family_name) {
                return a.first_name < b.first_name;
            }
            return a.family_name < b.family_name;
        }
    );
    
    for (auto e : names) {
        std::cout << e.family_name << " " << e.first_name << "\n";
    }
}

実行結果：

Nakamura Hideo
Saitou Akihisa
Saitou Ken
Saitou Yuuko
Yoshida Emiko

ラムダ式がやや複雑になりました。姓が一致しているかどうかを確認し、一致しているなら名の方の比較結果を返しています。姓が一致しないなら、姓だけの比較結果を返します。

安定な整列（std::stable_sort関数）

安定な整列が必要なときは、std::stable_sort関数を使います。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト（cpprefjp、cppreference.com）で確認してください。

使い方は std::sort関数とまったく同じです。

安定な整列になることを確認してみます。まず次のサンプルプログラムは、std::sort関数を使って、安定でない整列の場合どういうことが起こるのかを確認するものです。

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

using int_pair = std::pair<int, int>;

int main()
{
    std::vector<int_pair> numbers {
        {5, 7}, {4, 7}, {3, 7}, {2, 7}, {1, 7},
        {5, 6}, {4, 6}, {3, 6}, {2, 6}, {1, 6},
        {5, 5}, {4, 5}, {3, 5}, {2, 5}, {1, 5},
        {5, 4}, {4, 4}, {3, 4}, {2, 4}, {1, 4},
        {5, 3}, {4, 3}, {3, 3}, {2, 3}, {1, 3},
        {5, 2}, {4, 2}, {3, 2}, {2, 2}, {1, 2},
        {5, 1}, {4, 1}, {3, 1}, {2, 1}, {1, 1},
    };

    std::sort(std::begin(numbers), std::end(numbers),
        [](const int_pair& a, const int_pair& b) {
            return a.first < b.first;
        }
    );
    
    for (auto e : numbers) {
        std::cout << e.first << " " << e.second << "\n";
    }
}

実行結果：

std::pair（「関数から値を返す」のページを参照）の配列を整列しています。比較の条件は、first の昇順になるようにしています。

実行結果は、first の側だけをみると、1 から 5 に向かって昇順に並んでいますが、second の側はばらばらです。整列前のデータでは、second を意図的に 7 から 1 の順番になるように並べているのですが、みごとに破壊されました。これが安定でない整列の結果です。

要素数が少なすぎると、std::sort関数でも安定な整列になってしまうことがあります。Visual Studio の場合、要素数 32個が境になるようなので、それより要素数を多くして試す必要があります。

同じプログラムで、std::sort関数のところを std::stable_sort関数に変えてみます。

    std::stable_sort(std::begin(numbers), std::end(numbers),
        [](const int_pair& a, const int_pair& b) {
            return a.first < b.first;
        }
    );

すると、実行結果はこうなります。

second の側を注目してみると、7 から 1 への並びが維持されていることがわかります。

【上級】std::stable_sort関数がどのような整列アルゴリズムを用いているかに関する規定はありませんが、計算量が最大でも O(N log²(N)) であることが求められています³。多くの場合、マージソート（アルゴリズムとデータ構造編【整列】第７章）によって実装されます。

文字列の整列

文字列の整列では、各文字を表現する整数値に応じて並び順が決まります。そのため、使用している文字コードによって結果は変わります。

大文字と小文字のアルファベットが混在した文字列を整列すると、結果を意外なものに感じるかもしれません。

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

int main()
{
    std::string s {"BaAb"};

    std::sort(std::begin(s), std::end(s));
    std::cout << s << "\n";
}

実行結果：

ABab

“BaAb” を昇順に整列した結果、“ABab” になりました。‘a’ の手前に ‘B’ がありますが、これは納得できる結果でしょうか？

この結果は、ASCII やそれと互換性のある文字コード (Shift_JIS、UTF-8 など) では、大文字のアルファベットに、小文字のアルファベットよりも小さい数が割り当てられていることから起こります（A～Z は 65～90、a～z は 97～122）。つまり、昇順に整列すると、どの大文字のアルファベットも、小文字のアルファベットより前に来ることになります。

もし、“aAbB” のように、‘b’ や ‘B’ は ‘a’ や ‘A’ より後ろになるべきだと思うのなら、比較条件を工夫して実現しなければなりません。

大文字と小文字の違いを無視する

そこで、大文字と小文字の違いを無視するという方法があります。つまり、‘a’ と ‘A’ を同じ文字のつもりで整列するということです。これを実現するには、比較条件の中で、大文字か小文字のどちらかに統一してから比較すればいいです。

そのためには、std::toupper関数や std::tolower関数を使います。前者は、実引数で与えた文字を大文字に変換した結果を返します。後者は、実引数で与えた文字を小文字に変換した結果を返します。変換できない文字を渡した場合は、変換せずそのまま返されます。なおいずれも、使用するには #include <cctype> が必要です。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト（cppreference.com）で確認してください。std::toupper関数、std::tolower関数

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>

int main()
{
    std::string s {"BaAb"};

    std::sort(std::begin(s), std::end(s),
        [](char a, char b) {
            return std::toupper(a) < std::toupper(b);
        }
    );
    std::cout << s << "\n";
}

実行結果：

aABb

比較関数に渡されてきた文字を、std::toupper関数で大文字化してから比較しています（小文字化する方法でも問題ありません）。

実行結果は “aABb” です。少なくとも、‘a’ や ‘A’ が ‘b’ や ‘B’ よりも先に来るようにはなりました。しかし、aA のように小文字が先に来たかと思えば、Bb のほうは大文字が先に来ており、一貫性がありません。これが許せない場合はさらに工夫が必要です。

#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>

int main()
{
    std::string s {"BaAb"};

    std::sort(std::begin(s), std::end(s),
        [](char a, char b){
            auto upper_a = std::toupper(a);
            auto upper_b = std::toupper(b);

            if (upper_a == upper_b) {
                // 大文字化した結果が同じなら、小文字が先に来るように返す。
                // そもそもアルファベットでないこともあるが、その場合は std::toupper関数は変換をしないので、
                // そのまま取り扱って構わない。
                return a > b;
            }

            return upper_a < upper_b;
        }
    );
    std::cout << s << "\n";
}

実行結果：

aAbB

‘a’ と ‘A’ のように、大文字か小文字かの違いだけのときに、必ず小文字の側を先に持ってきたいという話なので、std::toupper関数で大文字に変換した結果が同じときにだけ、比較の仕方を変えます。小文字のアルファベットのほうが大きいのですから、return a > b; とすれば、a の方が大きいとき（＝a が小文字で、b が大文字のとき）に、a の方が手前に来るようになります。

重複を取り除く (std::unique関数)

要素を整列するだけでなく、重複した要素を取り除きたい場合があります。たとえば、{5, 6, -1, 3, 7, 2, 3} という要素を昇順に整列して、重複も取り除いた場合には、{-1, 2, 3, 5, 6, 7} になります。

重複を取り除くには、std::unique関数を使います。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト（cpprefjp、cppreference.com）で確認してください。

std::unique関数の引数は、範囲をあらわす２つのイテレータだけです。

std::unique関数は、隣り合った要素が同じ値の場合に、一方を取り除きます。隣り合っていなければならないことが注意すべき点です。すべての重複を取り除くことが目的なのであれば、事前に整列しておかなければなりません。単に隣り合っている同じ要素だけが取り除かれればいいのであれば、あらかじめ整列しておく必要はありません。たとえば、{5, 6, 6, 4, 3, 3, 7, 3} をそのまま std::unique関数にかければ、{5, 6, 4, 3, 7, 3} という結果が得られます。

また、要素を取り除くという動作を取りますが、これは std::remove関数などと同じで、本当の意味での要素の削除ではなく、取り除くべき要素が末尾に移動しているだけです（「要素を取り除く」のページを参照）。戻り値で返されるイテレータが、要素を取り除いたあとの正しい末尾を指しているので、これを受け取る必要があります。

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

int main()
{
    std::vector<int> v {5, 6, -1, 3, 7, 2, 3};

    std::sort(std::begin(v), std::end(v));
    auto itEnd = std::unique(std::begin(v), std::end(v));
    
    for (auto it = std::cbegin(v); it != itEnd; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
}

実行結果：

-1 2 3 5 6 7

本当の意味で削除したければ、erase関数と組み合わせる方法を使ってください（「要素を取り除く」のページを参照）。

整列されているかどうか調べる（std::is_sorted関数）

std::is_sorted関数を使うと、ある範囲の要素が整列されているかどうかを簡単に調べられます。

細かい仕様や、ここで紹介していない機能については、リファレンスサイト（cpprefjp、cppreference.com）で確認してください。

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

int main()
{
    std::vector<int> v {5, 6, -1, 3, 7, 2, 3};

    std::cout << std::boolalpha << std::is_sorted(std::cbegin(v), std::cend(v)) << "\n";
    std::sort(std::begin(v), std::end(v));
    std::cout << std::boolalpha << std::is_sorted(std::cbegin(v), std::cend(v)) << "\n";

    std::cout << std::boolalpha << std::is_sorted(std::cbegin(v), std::cend(v), std::greater<int>{}) << "\n";
    std::sort(std::begin(v), std::end(v), std::greater<int>{});
    std::cout << std::boolalpha << std::is_sorted(std::cbegin(v), std::cend(v), std::greater<int>{}) << "\n";
}

実行結果：

false
true
false
true

std::is_sorted関数の引数は、std::sort関数や std::stable_sort関数と同じです。第１・第２引数で指定したイテレータで表現される範囲内の要素が、第３引数の比較条件の下で整列できていれば true が、整列できていなければ false が返されます。

まとめ

いくつかある要素をなんらかの規則で並べ替えることを整列（ソート）という
一般的に自然と思われる順序に並べることや、そのように並んでいることを昇順（正順）という
昇順の反対になるように並べることや、そのように並んでいることを降順（逆順）という
まったく同じ値を持つ要素があったとき、整列前後でそれらの要素の位置関係が変わらないことが保証された整列を、安定な整列という
std::sort関数は安定でない整列を、std::stable_sort関数は、安定な整列をおこなう
- これらの関数に２つの要素を比較する関数を指定すると、降順にしたり、複数のキーを組み合わせたりといったさまざまな整列が実現できる
std::unique関数を使うと要素の重複を取り除ける
- この関数は隣り合った同じ値を持つ要素の一方を取り除くため、完全に重複を消し去るためには、事前に整列しておく必要がある
std::is_sorted関数は、要素が整列されているかどうかを調べる

新C++編の【本編】の各ページには、末尾に練習問題があります。ページ内で学んだ知識を確認する簡単な問題から、これまでに学んだ知識を組み合わせなければならない問題、あるいは更なる自力での調査や模索が必要になるような高難易度な問題をいくつか掲載しています。

参考リンク

1. C++ standard working draft N4140 §25.4.1.1 sort - 3 | 14882: Contents
2. イントロソート | Wikipedia
3. C++ standard working draft N4140 §25.4.1.2 stable_sort - 3 | 14882: Contents
Programming Place Plus　新C++編　参考書籍
- 当サイトの参考書籍一覧ページ。C++ に関する書籍を多数紹介
Programming Place Plus　新C++編　リンク集
- 当サイトの参考Webサイト集。C++ の全般的な学習に有益なサイトを紹介

練習問題

問題の難易度について。

(確認★) このページの内容の理解を確認する問題
(基本★～★★) このページの内容を使って解く問題
(応用★★～★★★) このページまでに学んだことを活用して、現実的な問題を解決する問題
(調査★★～★★★) 自力で情報を探したり、模索したりする問題
(発展★★★) プログラムの改善など、より上を目指すような問題

★は、すべての方が取り組める入門レベルの問題です。
★★は、自力でプログラミングができるようなるために、入門者の方であっても取り組んでほしい問題です。
★★★は、本格的にプログラマーを目指す人のための問題です。

問題１　（確認★）

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

⇒解答・解説

問題２　（基本★★）

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

⇒解答・解説

問題３　（応用★★）

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

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

using CardNumber = signed char;

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

struct Card {
    CardNumber number;
    CardMark mark;
};

⇒解答・解説

問題４　（応用★★）

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

⇒解答・解説

⇒解答・解説ページの先頭

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

要素を整列する | Programming Place Plus　新C++編

このページの概要

整列

std::sort関数

複数のキーによる整列

安定な整列（std::stable_sort関数）

文字列の整列

大文字と小文字の違いを無視する

重複を取り除く (std::unique関数)

整列されているかどうか調べる（std::is_sorted関数）

まとめ

参考リンク

練習問題

問題１　（確認★）

問題２　（基本★★）

問題３　（応用★★）

問題４　（応用★★）

更新履歴

このページの概要

整列

std::sort関数

複数のキーによる整列

安定な整列（std::stable_sort関数）

文字列の整列

大文字と小文字の違いを無視する

重複を取り除く (std::unique関数)

整列されているかどうか調べる（std::is_sorted関数）

まとめ

参考リンク

練習問題

問題１ （確認★）

問題２ （基本★★）

問題３ （応用★★）

問題４ （応用★★）

更新履歴

問題１　（確認★）

問題２　（基本★★）

問題３　（応用★★）

問題４　（応用★★）