0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@deseart

【ソートを例に】C++の本気を見てみようぜ【機能紹介】

0
Last updated at Posted at 2026-04-23

TL;DL

C++で仕様デカすぎて多分標準化委員会くらいしか全容を把握してないですよね（ご挨拶）

といきなり知ったような口を叩いて多くのプログラマを不愉快にさせたところで、自分のプログラムがどれだけ標準と違うかが知りたくなった今日この頃。

ということでCによる簡単なソートについて、C++の機能をふんだんに使った最高にモダンなプログラムへと改造していく様をお送りします。

Cによる交換ソート

バブルソートを書こうとしていたんですが、誤って交換ソートを書いてしまいました。面倒なのでこのままいきます。

#define swap(a, b, type)                                                       \
  do {                                                                         \
    type temp = a;                                                             \
    a = b;                                                                     \
    b = temp;                                                                  \
  } while (0)

void esort(int *seq, size_t size) {
  for (int i = 0; i < size - 1; i++) {
    for (int j = i + 1; j < size; j++) {
      if (cp[i] > cp[j]) {
        swap(cp[i], cp[j], int);
      }
    }
  }
}

では、行きましょう。

vector化/組み込み関数の利用

原則C++では、生の配列ではなくvectorを使うべきです。というのもvectorは

  • サイズ管理の安全性が高い
  • vectorのほうが STL との相性がいい
  • 生配列の場合、関数で扱うならポインタとして扱う必要があるため

ということでこうなります。

void esort(std::vector<int> &seq) {
  if (seq.empty()) return;
  
  for (std::size_t i = 0; i < seq.size() - 1; i++) {
    for (std::size_t j = i + 1; j < seq.size(); j++) {
      if (seq[i] > seq[j]) {
        std::swap(seq[i], seq[j]);
      }
    }
  }
}

また、一応

  • size()がstd::size_tを返すことを考慮して、iやjもこの型に合わせておきます。
  • 仮に引数の要素数が0だった場合0 - 1がアンダーフローを起こしてめちゃくちゃデカい数になってしまいます。対策のためのバリデーションを置いておきます。

総称型（テンプレート）

このコードではint型しか取れません。doubleなりなんなりを使いたい場合もあります。C++では多重定義ができるので、型だけが違う同じ関数を定義してもいいんですが、あまりにも WET です。ということで総称型で一気に書いてしまいましょう。

template <typename T> void esort(std::vector<T> &seq) {
  if (seq.empty()) return;
  
  for (std::size_t it1 = 0; it1 < seq.size() - 1; it1++) {
    for (std::size_t it2 = it1 + 1; it2 < seq.size(); it2++) {
      if (seq[it1] > seq[it2]) {
        std::swap(seq[it1], seq[it2]);
      }
    }
  }
}

総称型2（反復子）

しかしこれではまだvecotr<T>にしか対応できません。アルゴリズム的に、array<T>などほかのコンテナでも成り立つはずです。

イテレータはこのようにアルゴリズムとデータ構造を切り離すための機能です。しくみや記法的にはポインタと似たような感じで、C++から提供されているあらゆるコンテナにアクセスできます。

template <typename RandomIt> void esort(RandomIt first, RandomIt last) {
    if (first == last) return;

    for (auto it1 = first; it1 != last - 1; it1++) {
        for (auto it2 = it1 + 1; it2 != last; it2++) {
            if (*it1 > *it2) {
                std::iter_swap(it1, it2);
            }
        }
    }
}

反復子の抽象化

なかなか良い関数が出来上がってきましたが、テンプレート/イテレータにも問題点があります。
間違った型を渡したときにエラーメッセージが長大な怪文書になることと、単純に関数呼び出しがf(v.begin(), v.end())のように長ったらしくダサいことです。

これを解決するのがコンセプトとRangeです。ひとまずコードを提示します。

void esort(std::ranges::random_access_range auto& seq) {
    if (std::ranges::empty(seq)) return;

    auto begin = std::ranges::begin(seq);
    auto end = std::ranges::end(seq);

    for (auto it1 = begin; it1 != end - 1; it1++) {
        for (auto it2 = it1 + 1; it2 != end; it2++) {
            if (*it1 > *it2) {
                std::ranges::swap(*it1, *it2);
            }
        }
    }
}

この定義であれば、呼び出しはf(v)と書けばよいです。やっとモダンな言語らしくなってきましたね。

ところで、引数の前に指定されているstd::ranges::random_access_rangeはなんなのでしょうか。
これは「コンセプト」の指定で、PythonでいうTypeVarの境界みたいなものです1
。具体的な説明は最後にします。

右辺値/左辺値参照の問題とフォワーディング参照

いきなりですが、右辺値と左辺値という概念について説明します2。
C++において、すべての値は次の二つに分類できます。

  • 左辺値 (Lvalue): 名前がついていて、メモリ上に明確な場所を持つもの。
    • 例: std::vector<int> vec; の vec
  • 右辺値 (Rvalue): 式の評価途中で生まれる、名前のない「一時オブジェクト」。
    • 例: std::vector<int>{1, 2, 3}（その場で作った配列）や、関数の戻り値など。

ここで問題が出てくるのですが、先ほどのstd::ranges::random_access_range auto& seqという引数の宣言、これ左辺値しか受け取れないんですよね。

template <typename T>
void esort(T& seq) { ... }

std::vector<int> vec = {3, 1, 2};
exchange_sort_v3(vec);  // OK: vec は名前がある（左辺値）

// エラー！: その場で作った一時オブジェクト（右辺値）は R& で受け取れない
exchange_sort_v3(std::vector<int>{3, 1, 2});

実は、Rangeを使っていくうえでこの仕様は致命的です。というのも、以下のようにRangeの革新的な機能であるViewsのパイプ処理3はゴリゴリに右辺値で実装されているためです。

std::vector<int> vec = {5, 1, 4, 2, 3};

// vecの最初の3要素だけをソートしたい場合
// vec | std::views::take(3) は、その場で作られる「一時的なビュー（右辺値）」

// もし引数が R& だと、ここでコンパイルエラーになる！
esort(vec | std::views::take(3));

当然の話ながらRubyの軽快なメソッドチェーン風のコードが書きたいからこのパイプ記法が導入されたわけで、左辺値化（変数の割り当て）なんてやってられないですよね。

しかしここでT& seqという宣言が邪魔になってきます。

そこで登場するのが、R&&の形式で記述できるフォワーディング参照です。
普通、特定の型に対する&&（例：std::vector<int>&&）は「右辺値しか受け取らない（右辺値参照）」という意味になります。

ただし、テンプレート引数Rと合わせてR&&と記述した場合のみ左辺値なら左辺値として解釈、右辺値なら右辺値として解釈という都合のいい挙動になります。

比較器の注入

Cのqsortは比較関数を外部から注入する必要がありました。これを実装してみます。
テンプレートの細かい設定が必要になるので、「反復子の抽象化」で使っていた省略記法をやめて正式な書き方をします。

// Comp: 比較器の型。デフォルトは std::ranges::less（小なり演算子による昇順）
template <std::ranges::random_access_range R, typename Comp = std::ranges::less>
void esort(R&& seq, Comp comp = {}) {
    if (std::ranges::empty(seq)) return;

    auto begin = std::ranges::begin(seq);
    auto end = std::ranges::end(seq);

    for (auto it1 = begin; it1 != end - 1; it1++) {
        for (auto it2 = it1 + 1; it2 != end; it2++) {
            if (comp(*it2, *it1)) {
                std::ranges::swap(*it1, *it2);
            }
        }
    }
}

射影

例えばこういう構造体があるとします。

struct Employee {
  std::string id;
  std::string name;
  unsigned int age;
}

そしてvector<Employee>という型のデータがあったとして、esortで年齢について整列しようとすると

esort(employees, [](const Employee& a, const Employee& b) { return a.age < b.age; })

と、ラムダ式を渡す必要があるわけです。さすがにこれは長すぎますね...

というわけで射影（Projection）を導入しましょう。

// Proj: 射影の型。デフォルトは std::identity（値をそのまま返す）
template <std::ranges::random_access_range R,
          typename Comp = std::ranges::less,
          typename Proj = std::identity>
void esort(R&& seq, Comp comp = {}, Proj proj = {}) {
    // ... ループ処理 ...
            // 値に射影を適用してから比較する
            // proj(*it1) が Employee の age を取り出すイメージ
            if (comp(proj(*it2), proj(*it1))) {
                std::ranges::swap(*it1, *it2);
            }
}

この工夫により

esort(employees, std::ranges::less{}, &Employee::age);

と簡潔に書けるようになりました。

呼び出し可能オブジェクトの多様な構文にまつわる問題とその解決

射影を導入したのはいいのですが、このコードのままでは致命的な欠陥が存在します。「Collableがたくさんある」ことです。

まずCollableというのは、f()のように関数として呼び出し可能な型です。C++なる言語はそれがたくさんあるというのです。

  • 通常の関数とラムダ式
auto f = [] (int x) { return x * 2; };
int r = f(10);
  • メンバ関数ポインタ
struct Dog { void bark(int n) { /* ... */ } };

Dog d;
auto p = &Dog::bark;

(d.*p)(3);
  • メンバ変数ポインタ
struct Dog { unsigned int age = 3; };

Dog d;
auto p = &Dog::age;

x.*p;

ちなみに先ほどのesort(employees, std::ranges::less{}, &Employee::age);というのはメンバ変数ポインタですね。

問題は、呼び出し方法がそれぞれちがうということなんです。

// 高階関数
template <typename F>
void do_something(Employee emp, F f) {
    // さて、ここで f を使って値を取り出したいが、どう書けばいい？
    // 呼び出し方1
    auto val = f(emp);
    // 呼び出し方2
    auto val = emp.*f;
    // 当然ながら片方の書き方はもう片方でエラーとなります。
}

この複数ある呼び出し方を統一して扱うのがstd::invokeです。実際に見てみましょう。

// f が関数であろうが関数ポインタだろうが
// メンバ関数ポインタだろうがメンバ変数ポインタだろうがこれ一つ
auto val = std::invoke(f, emp);

ということで、最終的にこうなります。

template <std::ranges::random_access_range R,
          typename Comp = std::ranges::less,
          typename Proj = std::identity>
void esort(R&& seq, Comp comp = {}, Proj proj = {}) {
    // ... ループ処理 ...
            auto val1 = std::invoke(proj, *it1);
            auto val2 = std::invoke(proj, *it2);

            if (std::invoke(comp, val2, val1)) {
                std::ranges::swap(*it1, *it2);
            }}

コンセプトによる契約の明示

長年C++の契約は抽象基底クラスと純粋仮想関数の組み合わせないしダックタイピングが主流だったようです。しかし、近年ではモダンな静的型付け言語と同様の契約の宣言が可能になっています。それがコンセプトです。

ここではその内容に深入りせず、最後の味付けとして「ソート可能な引数だけを取る」という契約を明示してみます。

template <std::ranges::random_access_range R,
          typename Comp = std::ranges::less,
          typename Proj = std::identity>
// ソート可能であることを保障！
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
void esort(R&& seq, Comp comp = {}, Proj proj = {}) {
    auto begin = std::ranges::begin(seq);
    auto end = std::ranges::end(seq);

    if (begin == end) return;

    for (auto it1 = begin; it1 != end - 1; ++it1) {
        for (auto it2 = it1 + 1; it2 != end; ++it2) {
            if (std::invoke(comp, std::invoke(proj, *it2), std::invoke(proj, *it1))) {
                std::ranges::swap(*it1, *it2);
            }
        }
    }
}

std::sortable<I, R, P>は何らかの反復子Iが比較関数Rによって整列可能であることを表すコンセプトです。この時射影Pを指定することができます。

もし存在しないメンバを指定したり、比較できない型同士を比較しようとしたりすると、この requires 節が弾いてくれ、分かりやすいエラーメッセージを出してくれます。

コンパイル時計算

そもそも人間的には、プログラムと向き合うには「3つの時」があります。
1つ目に、静的。実際にプログラムを書いているときです。
2つ目に、コンパイル時。コンパイラに通して前処理やらアセンブルやらを行うときです。
3つ目に、実行時。プログラム的には人間と向き合う時間が最も長いのはここですね。実際に動いているときです。

実行時は非常に忙しいです。外部から情報を受け取り、加工して、吐き出す。このサイクルを爆速で回さなければなりません。
最近はコンピュータの性能がよくなってきたので少々ならどうにかなります。だからこそ、パフォーマンスを意識する場合にはなるべく静的かコンパイル時に済ませられるものは済ませておきたいわけです。

ここで扱うのは「コンパイル時計算」の指定...constexp, consteval, constinitの3つです。

  • constexp

こういう関数を考えます。

constexpr int square(int x) {
    return x * x;
}

これはコンパイラに対する「可能ならコンパイル時に計算しておいてね」というお願いです。

例えばsquare(5)とするとコンパイルするときに25と置き換えらえて出てきます。

ただし、

const int x = 5;
square(x);

と変数を渡してしまうと、コンパイル時には計算できないので、何も警告を出さずに「普通の実行時の関数」として実行されるのです。

  • consteval

先述したようにsquare()に変数を渡してしまうと勝手に普通の関数に格下げされてしまうという勝手な挙動をするのがconstexpでした。
そこで絶対に格下げせず、必ずコンパイル時に計算せよという命令を与えるのがconstevalです。さもなくばエラーとなります。

これは別名即時関数と呼ばれていて、オーバーヘッドを必ず消し去るという強い意志を記述できるようになりました。

  • constinit

これは前二つと若干毛色が違い、グローバル変数の初期化なども実行時ではなくコンパイル時に前倒しせよという命令を表しています。実態としては静的初期化順序の乱れと呼ばれるバグを修正するために標準化されました。

このように、constexpやconstevalにおいては「コンパイル時に評価する」という都合上、外部の変数を参照したり副作用を及ぼすような処理は記述できません。しかしこれは大した問題ではないと思います。

さて、実際にこれをesortに付与したいところですが、この二つのうちどちらを選ぶべきでしょうか？
実務的にはおおよそconstexpを選んだ方がいいでしょう。というのも例えばソースコードにソートしたいコンテナを直書きする場合はいいでしょうが、そんな場面はあまりなく、大概外部から読み込んでくるのがほとんどかと思います。
そんな時に即時関数はコンパイル時に解決できないことからエラーを出してしまいます。正直使い勝手が悪いので、ここはコンパイル時、実行時と柔軟に切り替えが可能なconstexpを使うのが得策でしょう。

template <std::ranges::random_access_range R,
          typename Comp = std::ranges::less,
          typename Proj = std::identity>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
// ここに consteval を追加するだけ！
consteval void exchange_sort(R&& seq, Comp comp = {}, Proj proj = {}) {
    auto begin = std::ranges::begin(seq);
    auto end = std::ranges::end(seq);

    if (begin == end) return;

    for (auto it1 = begin; it1 != end - 1; ++it1) {
        for (auto it2 = it1 + 1; it2 != end; ++it2) {
            if (std::invoke(comp, std::invoke(proj, *it2), std::invoke(proj, *it1))) {
                std::ranges::swap(*it1, *it2);
            }
        }
    }
}

番外：マージソート

#include <ranges>
#include <algorithm>
#include <functional>
#include <vector>

template <std::random_access_iterator I, std::sentinel_for<I> S,
          typename Comp, typename Proj>
constexpr void merge_sort_impl(I first, S last, Comp comp, Proj proj) {
    auto len = std::ranges::distance(first, last);
    if (len <= 1) return;

    auto mid = first + len / 2;

    merge_sort_impl(first, mid, comp, proj);
    merge_sort_impl(mid, last, comp, proj);

    using value_type = std::iter_value_t<I>;
    std::vector<value_type> buffer;
    buffer.reserve(len);

    std::ranges::merge(
        std::ranges::subrange(first, mid), // 左ブロック
        std::ranges::subrange(mid, last),  // 右ブロック
        std::back_inserter(buffer),        // バッファの末尾に追加
        comp, proj, proj                   // 比較器と射影（左右に同じ射影を適用）
    );

    std::ranges::copy(buffer, first);
}

template <std::ranges::random_access_range R,
          typename Comp = std::ranges::less,
          typename Proj = std::identity>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
constexpr void merge_sort(R&& seq, Comp comp = {}, Proj proj = {}) {
    // コンテナ全体を受け取り、イテレータのペアにして内部実装へ渡す
    merge_sort_impl(std::ranges::begin(seq), std::ranges::end(seq), comp, proj);
}

  1. C++の「組込みコンセプト」で、ランダムアクセスが可能なコンテナを指しています。具体的には、deque、array、string、vectorです。 ↩

  2. ノリ的には普通の関数とラムダ式の違いと同じですよね。→余談 ↩

  3. ごめんなさい、さすがに長くなるので説明を端折らせてもらいますが、UNIXのパイプやC#のLINQみたいなもんです。 ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?