C++ テンプレート・コンセプト・STL アルゴリズム・ranges

シリーズ：C++講座 5/6（上級）。 クラスが書けてスマートポインタも使える人（第4回）で、これからライブラリのコードを読み、汎用的な関数を書き、テンプレートのエラーと付き合っていく人向けです。読み終えると、100 行のテンプレートエラーを1分で読み、C++20 のコンセプトでそれを短いメッセージに変え、STL アルゴリズムとラムダと ranges を組み合わせ、std::sort・std::stable_sort・qsort を実測値で選べるようになります。実測には、こちらも驚いた結果が1つあります。

「テンプレートのエラーで画面が埋まり、そっと閉じた」。C++ を学ぶ人の多くが一度は通る道です。1文字の間違いで、自分が書いた覚えのない型名が何十行も並びます。役に立つのは理屈より実践的な知識で、どの行を読むか、何がノイズを減らすか、手元の標準ライブラリで「定説」の性能が本当に成り立つか、です。以下はすべて Apple Silicon Mac（M1 Pro）、macOS 26、Apple clang 21.0.0 + libc++ で、clang++ -std=c++23 -Wall -Wextra -pedantic、時間計測は -O2 で実行しました。GCC・MSVC・Linux は動かしていません。出力中の長い SDK のパスは .../c++/v1/ に縮めています。

関数テンプレートと、最初に出会うエラー

テンプレートは、使う型ごとにコンパイラが本物のコードに起こす「レシピ」です。これをインスタンス化と呼び、T は引数から推論されます（テンプレート引数推論）。

#include <cstdio>
#include <string>

template <typename T>
T biggest(T a, T b) { return a < b ? b : a; }

int main() {
    std::printf("%d\n", biggest(3, 9));
    std::printf("%.1f\n", biggest(2.5, 1.0));
    std::printf("%s\n", biggest(std::string("pear"), std::string("apple")).c_str());
    std::printf("%.1f\n", biggest(1, 2.5));
}

tmax.cpp:9:27: error: no matching function for call to 'biggest'
    9 |     std::printf("%.1f\n", biggest(1, 2.5));
      |                           ^~~~~~~
tmax.cpp:4:3: note: candidate template ignored: deduced conflicting types for parameter 'T' ('int' vs. 'double')
    4 | T biggest(T a, T b) { return a < b ? b : a; }
      |   ^
1 error generated.

1 からは T = int、2.5 からは T = double と推論され、テンプレートはどちらかに変換して合わせてはくれません。明示すれば通ります。biggest<double>(1, 2.5) は 2.5 を出力しました。ほかの3つの呼び出しは 9、2.5、pear で、1つのレシピから3つの別々の関数ができています。

114 行のテンプレートエラーを読む

定番の例です。std::list に std::sort。

#include <algorithm>
#include <list>
int main() {
    std::list<int> xs{3, 1, 2};
    std::sort(xs.begin(), xs.end());
}

Apple clang 21 の出力は 114 行・14,321 バイト・エラー4件でした。冒頭はこうです（長いテンプレート引数は <...> に縮めました）。

In file included from listsort.cpp:1:
In file included from .../c++/v1/algorithm:1875:
.../c++/v1/__algorithm/make_heap.h:37:31: error: invalid operands to binary expression ('std::__list_iterator<int, void *>' and 'std::__list_iterator<int, void *>')
   37 |   const __diff_t __n = __last - __first;
      |                        ~~~~~~ ^ ~~~~~~~
.../c++/v1/__algorithm/partial_sort.h:41:8: note: in instantiation of function template specialization 'std::__make_heap<...>' requested here
.../c++/v1/__algorithm/partial_sort.h:65:12: note: in instantiation of function template specialization 'std::__partial_sort_impl<...>' requested here
.../c++/v1/__algorithm/sort.h:934:10: note: in instantiation of function template specialization 'std::__partial_sort<...>' requested here
.../c++/v1/__algorithm/sort.h:945:8: note: in instantiation of function template specialization 'std::__sort_impl<...>' requested here
.../c++/v1/__algorithm/sort.h:951:8: note: in instantiation of function template specialization 'std::sort<...>' requested here
listsort.cpp:5:10: note: in instantiation of function template specialization 'std::sort<std::__list_iterator<int, void *>>' requested here
    5 |     std::sort(xs.begin(), xs.end());

どのテンプレートエラーにも使える3段階の読み方です。

1. 最初の error: 行のメッセージだけ読む。 invalid operands to binary expression (list_iterator と list_iterator)、場所は __last - __first。list のイテレータ同士を引き算しようとした、ということです。
2. 自分のファイル名が出る note: を探す。 listsort.cpp:5:10 ... requested here。直すのはこの行です。1 と 2 の間の note はライブラリ内部の呼び出しの連鎖で、「なぜ」を知りたいときだけ下から読みます。
3. その操作が何を要求しているか考える。 イテレータの引き算にはランダムアクセスイテレータが必要で、vector や deque は持っていますが、連結リストの list は持っていません。残り3件のエラーは別の内部関数からの同じ文句なので無視します。

直し方は、ノードをつなぎ替えるメンバ関数 xs.sort(); を使うか、std::vector にコピーすることです。

コンセプト：同じ間違いが 22 行に

C++20 のコンセプトは、テンプレート引数に付ける名前付きの要件です。std::ranges のアルゴリズムはこれで制約されているので、ライブラリのコードがインスタンス化される前、呼び出しの時点でチェックされます。

#include <algorithm>
#include <list>
int main() {
    std::list<int> xs{3, 1, 2};
    std::ranges::sort(xs);
}

rlistsort.cpp:5:5: error: no matching function for call to object of type 'const __sort'
    5 |     std::ranges::sort(xs);
      |     ^~~~~~~~~~~~~~~~~
.../c++/v1/__algorithm/ranges_sort.h:64:3: note: candidate template ignored: constraints not satisfied [with _Range = std::list<int> &, _Comp = ranges::less, _Proj = identity]
.../c++/v1/__algorithm/ranges_sort.h:61:13: note: because 'std::list<int> &' does not satisfy 'random_access_range'
.../c++/v1/__ranges/concepts.h:116:59: note: because 'iterator_t<std::list<int, std::allocator<int>> &>' (aka '__list_iterator<int, void *>') does not satisfy 'random_access_iterator'
.../c++/v1/__iterator/concepts.h:219:36: note: because 'derived_from<_ITER_CONCEPT<std::__list_iterator<int, void *>>, random_access_iterator_tag>' evaluated to false
.../c++/v1/__concepts/derived_from.h:27:24: note: because 'is_base_of_v<std::random_access_iterator_tag, std::bidirectional_iterator_tag>' evaluated to false

22 行・2,606 バイト・エラー1件。最初の note がもう答えです：'std::list &' does not satisfy 'random_access_range'。because の行は1段ずつ深くなり、最後の行は「list のイテレータは双方向でしかない」と言っています。

自作のテンプレートでも同じ効果があります。制約のない次の mean は何でも受け付け、奥のほうで失敗します。

template <typename T>
double mean(const std::vector<T> &v) {
    T sum{};
    for (const T &x : v) sum += x;
    return static_cast<double>(sum) / v.size();
}
// mean(std::vector<std::string>{"ann", "bo"});

mean_t.cpp:7:12: error: no matching conversion for static_cast from 'std::string' to 'double'
mean_t.cpp:11:12: note: in instantiation of function template specialization 'mean<std::string>' requested here

ここに罠があります。文字列でも sum += x はコンパイルが通る（連結になる）ので、エラーは本当の問題と関係ない後ろの行に出ます。コンセプトを付けるとエラーは呼び出し側に移り、満たさなかった規則を名指しします。

#include <concepts>
template <typename T>
concept Number = std::integral<T> || std::floating_point<T>;

template <Number T>
double mean(const std::vector<T> &v) { /* same body */ }

mean_c.cpp:15:12: error: no matching function for call to 'mean'
mean_c.cpp:8:8: note: candidate template ignored: constraints not satisfied [with T = std::string]
mean_c.cpp:7:11: note: because 'std::string' does not satisfy 'Number'
mean_c.cpp:5:18: note: because 'std::string' does not satisfy 'integral'
mean_c.cpp:5:38: note: and 'std::string' does not satisfy 'floating_point'

この例ではコンセプト版のほうが長い（22 行対 10 行）のですが、内容が正しいのです。副作用ではなく要件そのものを説明しています。-std=c++17 では同じファイルが error: unknown type name 'concept' になります。コンセプトは C++20 からです。

STL アルゴリズムとラムダ

<algorithm> にはイテレータ範囲に働く関数が 100 ほどあります。ラムダ（[キャプチャ](引数) { 本体 }）はその場で書く名前のない関数オブジェクトで、キャプチャリストはどのローカル変数が見えるかを決めます。

std::vector<int> v{5, 3, 8, 1, 9, 2, 8};

auto newEnd = std::remove(a.begin(), a.end(), 8);   // a is a copy of v
// print a here
a.erase(newEnd, a.end());

auto n = std::erase(b, 8);                          // C++20: one call

int limit = 4;
auto big = std::count_if(v.begin(), v.end(), [limit](int x) { return x > limit; });

after remove: size=7 -> 5 3 1 9 2 2 8 | after erase: size=5
std::erase removed 2, size=5
count > 4: 4
sum=36 max=9

1 行目が STL で一番多い誤解です。std::remove は削除しません。 イテレータしか持っていないのでコンテナのサイズは変えられず、残す要素を前に詰めて新しい論理的な終端を返すだけです。後ろ（ここでは 2 8）はただの残骸です。erase を呼ぶ必要があります。戻り値を捨てると、今は少なくとも ignoring return value of function declared with 'nodiscard' attribute [-Wunused-result] と警告され、vector は要素3つのままでした。C++20 なら両方を1回でやる std::erase / std::erase_if を使いましょう。

std::ranges の射影（projection）を使うと小さなラムダがかなり減ります。注文を金額順に並べるなら、メンバへのポインタを渡すだけです。

struct Order { std::string user; int yen; };
std::vector<Order> orders{{"kim", 1200}, {"sato", 300}, {"lee", 800}};
std::ranges::sort(orders, {}, &Order::yen);   // sato:300 lee:800 kim:1200

ranges のビューは遅延評価：動く様子を見る

ビューは、列を保持せずに「どう並ぶか」だけを表す軽いオブジェクトです。| でつなぎ、反復するまで何も実行されません。各段に print を入れてみました。

auto pipeline = v
    | std::views::filter([](int x) { std::print("[f{}]", x); return x % 2 == 0; })
    | std::views::transform([](int x) { std::print("[t{}]", x); return x * 10; })
    | std::views::take(2);
std::println("pipeline built, nothing printed yet");
for (int x : pipeline) std::print(" -> {}\n", x);

pipeline built, nothing printed yet
[f5][f3][f8][t8] -> 80
[f1][f9][f2][t2] -> 20
[f8]

見るべき点は3つ。パイプラインを組んだ時点では何も出ません。要素は1つずつ全段を通ってから次に進み、一時的な vector は作られません。そして最終行です。2つ目の結果の後、イテレータを進めたときにフィルタがもう一度（[f8]）動き、それから take(2) が終わりに気づきました。フィルタの述語は思ったより多く呼ばれ得るので、副作用を持たせてはいけません。

この環境で使えた C++23 の追加機能：std::ranges::to<std::vector>() でビューをコンテナに集められ、std::ranges::fold_left(evens, 0, std::plus{}) は 18 を出しました。<print> の std::print / std::println も動きました（上の出力がそれです）。std::views::enumerate は使えず error: no member named 'enumerate' in namespace 'std::ranges::views'。C++17 の並列アルゴリズム std::execution::par もこの libc++ では no member named 'par' in namespace 'std::execution' でした。

std::sort・std::stable_sort・qsort を実測

std::mt19937（シード 42）のランダムな int 100 万個を、毎回新しいコピーに対してソートしました。-O2、7 回の中央値、std::is_sorted で確認済みです。

static int cmp_int(const void *a, const void *b) {
    int x = *static_cast<const int *>(a), y = *static_cast<const int *>(b);
    return (x > y) - (x < y);
}
// std::sort(v.begin(), v.end());
// std::stable_sort(v.begin(), v.end());
// std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });
// std::qsort(v.data(), v.size(), sizeof(int), cmp_int);

qsort が4倍遅いのは予想どおりです。約 2,000 万回の比較のたびに関数ポインタ経由で呼び出し、インライン化できません。驚きは libc++ 自身から来ていて、どちらもヘッダで確認しました。

• std::stable_sort が std::sort に勝った。 __algorithm/stable_sort.h では、比較が既定の < で要素が整数のとき、1,024〜65,536 要素の塊を基数ソートしてからマージします。基数ソートは比較を一切しません。
• a < b と同じことをするラムダで std::sort が 2.6 倍遅くなった。 libc++ が分岐のない分割（branchless partition）を使うのは、比較が std::less か std::greater に「還元できる」ときだけです（__algorithm/sort.h の __use_branchless_sort）。さらに既定の比較の int 用 std::sort はライブラリ本体にコンパイル済みで入っています。自作のラムダは汎用の経路になります。ただの比較なら手書きのラムダより std::ranges::less{} / std::greater{} を使いましょう。同じデータの降順ソートは std::greater<>() で 19.10 ms、ラムダ a > b で 52.43 ms でした（7 回の中央値）。

コンパイル済みであることは第6回の結果も説明します。既定の std::sort は -O0 でも -O2 と同じ速さ（20.88 ms）で、ラムダ版は 123.64 ms まで落ちました。

使い分け：

アルゴリズムの中身はソートアルゴリズムの記事で扱っています。

よくある間違い → 実際に起きたこと → 直し方

比較関数の件は詳しく見ておく価値があります。std::sort は狭義の弱順序を要求し、comp(a, a) は false でなければなりません。<= で同じ値が多いと、libc++ の分割ループが配列の終わりを越えて進みます。ASan は heap-buffer-overflow ... in std::__1::__partition_with_equals_on_right と報告し、libc++ のデバッグ用ハードニングモードは本当の原因を表示しました。

.../c++/v1/__algorithm/sort.h:603: libc++ Hardening assertion __first != __end failed: Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?

このときの終了コードは 134。FAST と EXTENSIVE のハードニングモードでも止まりました（終了コード 133）が、メッセージは出ませんでした。

正直な限界・バージョンの注意

• 実行環境は Apple clang 21.0.0 と libc++（_LIBCPP_VERSION 220106）、arm64 の macOS 26 だけです。GCC/libstdc++ や MSVC はエラーの文面もソートの実装も違い、数値も変わるはずです（ここでは動かしていません）。
• バージョン：コンセプトと std::ranges は C++20（-std=c++17 では concept が拒否される）。std::print・std::ranges::to・fold_left は C++23（-std=c++20 では no member named 'print' in namespace 'std'）。std::erase は C++20。
• fold_left は、libc++ が機能テストマクロ __cpp_lib_ranges_fold を定義していないのにコンパイルできました。views::enumerate と std::execution::par はありませんでした。機能はドキュメントではなくコンパイルして確かめましょう。
• 基数ソートやコンパイル済みの std::sort<int> は libc++ の実装の詳細で、変わる可能性があります。
• エラーの行数はコンパイラのバージョンや端末の幅で変わります（clang は診断ごとにソース行とキャレットを出すため）。

練習問題

1. orders{{"kim",1200},{"sato",300},{"lee",800},{"tanaka",450},{"park",950}} から、500 円を超える注文のユーザー名を金額の高い順に、ranges と射影を使って出力してください。

2. 次のコードはコンパイルが通り、0 を出して終了コード 0 で終わります。期待値は 4 です。何がおかしいのか、また std::ranges はどうやってこれをコンパイル時に止めるのか答えてください。

std::vector<int> make() { return {1, 2, 3, 4}; }
auto it = std::max_element(make().begin(), make().end());
std::printf("%d\n", *it);

解答

1.

auto big = orders | std::views::filter([](const Order &o) { return o.yen > 500; })
                  | std::ranges::to<std::vector>();
std::ranges::sort(big, std::ranges::greater{}, &Order::yen);
for (const auto &name : big | std::views::transform(&Order::user)) std::print("{} ", name);

出力は kim park lee。先に ranges::to で集めるのは、sort には並べ替え可能なランダムアクセスの範囲が必要で、フィルタビューはそうではないからです。

2. make() を呼ぶたびに別の一時 vector が返るので、begin() と end() は別々のオブジェクトのもので、しかも両方とも文の終わりで破棄されます。it はぶら下がりです。ASan：heap-buffer-overflow ... READ of size 4 ... dangle2.cpp:6。std::ranges::max_element(make()) と書くと、libc++ は一時的な範囲に対して std::ranges::dangling を返し、それを参照外しするとコンパイルエラーになります：indirection requires pointer operand ('borrowed_iterator_t<std::vector<int>>' (aka 'std::ranges::dangling') invalid)。直し方は auto v = make(); auto it = std::ranges::max_element(v); です。

次回

第6回は、性能が効く場面で何を使うかを測ります。vector・list・deque・map・unordered_map の比較、reserve、小さな文字列の最適化（SSO）、スレッド、ThreadSanitizer で捕まえるデータ競合、アトミック対ミューテックス、-O0 対 -O2 です。

• 前回：C++講座 第4回：スマートポインタとムーブセマンティクス
• 次回：C++講座 第6回：コンテナ・性能・並行処理
• それ以前：第1回、第2回、第3回
• 関連：比較用に C# のジェネリクス、プログラミング学習ロードマップ