はじめに
C++プログラミングにコンパイルエラーは付き物です。コンパイラからのメッセージに頼らずに、正しいC++プログラムを書き上げることなど不可能です。（ここでは脳内C++コンパイラ搭載型超人の存在は無視します:D）
C++標準ライブラリは便利なアルゴリズムを数多く提供しており（通称 "STL"）、大部分のC++プログラマはその恩恵を受けています。しかしSTLを駆使したコードのコンパイルエラーは、時として長大で難解なメッセージを出力することがあります。
この記事ではソートアルゴリズムsortを題材にして、現状(C++17)エラーメッセージの問題点を確認し、きたるC++20時代のエラーメッセージを読み解いていきます。
C++17時代のエラーメッセージ
下記ソースコード片をコンパイルすると、どんなエラーメッセージが出力されるでしょう？
注：このコードはコンパイルに失敗します。
#include <algorithm>
#include <list>
int main()
{
// 双方向リンクリストの要素を並び替える
std::list<int> lst = {5, 3, 1, 4, 2};
std::sort(lst.begin(), lst.end());
// ...
}
動作デモ: https://wandbox.org/permlink/4j5LtFOz5IMZjd0C
GCCコンパイラ(g++)が出した答えは...（可読性のため大幅に加工・省略）
error: no match for 'operator-' (operand types are 'std::list::iterator<int>' and 'std::list::iterator<int>')
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
501 | operator-(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
note: template argument deduction/substitution failed:
note: 'std::_List_iterator<int>' is not derived from 'const std::reverse_iterator<_Iterator>'
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1542 | operator-(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
note: template argument deduction/substitution failed:
note: 'std::list::iterator<int>' is not derived from 'const std::move_iterator<_IteratorL>'
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
（無加工のエラーメッセージ全体）
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:62,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algo.h: In instantiation of 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_iterator<int>; _Compare = __gnu_cxx::__ops::_Iter_less_iter]':
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algo.h:4837:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = std::_List_iterator<int>]'
prog.cc:8:35: required from here
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algo.h:1955:22: error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>')
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algobase.h:67,
from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:61,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_iterator.h:501:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
501 | operator-(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_iterator.h:501:5: note: template argument deduction/substitution failed:
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:62,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algo.h:1955:22: note: 'std::_List_iterator<int>' is not derived from 'const std::reverse_iterator<_Iterator>'
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algobase.h:67,
from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:61,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_iterator.h:1542:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1542 | operator-(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_iterator.h:1542:5: note: template argument deduction/substitution failed:
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:62,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_algo.h:1955:22: note: 'std::_List_iterator<int>' is not derived from 'const std::move_iterator<_IteratorL>'
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
このメッセージからエラー原因を読み取れるプログラマは、相当にC++コンパイラに飼いならされた もとい 相応の熟練者と言っても過言ではないでしょう。
本当の原因は「std::listは汎用の並び替えアルゴリズムstd::sortに対応しない」ことです。より正確に表現するならば「std::sortはランダムアクセス・イテレータを要求する一方で、std::listのイテレータはランダムアクセス可能ではない」ためです。 C++17標準ライブラリstd::sort 定義では、ランダムアクセス・イテレータを要求する旨を間接的に表現しています。
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
// パラメータ名がRandomAccessIteratorの場合、ランダムアクセス・イテレータ要件を満たすべき
おまけ：修正後コード
本記事はエラーメッセージ解釈のみを取り上げますが、さすがに修正後コードの掲示はしておきます。std::listのsortメンバ関数を使う必要があります。
// 双方向リンクリストの要素を並び替える
std::list<int> lst = {5, 3, 1, 4, 2};
lst.sort();
C++20時代のエラーメッセージ：理想編
前掲エラーメッセージはイテレータに関して色々と指摘していますが、ランダムアクセス・イテレータへの言及はどこにも見当たりません。C++ STL利用の難しさの一因は、適切なエラーメッセージを提示できないことにもありそうです。
error: no match for 'operator-' (operand types are 'std::list::iterator<int>' and 'std::list::iterator<int>')
1955 | std::__lg(__last - __first) * 2,
| ~~~~~~~^~~~~~~~~
哀れな迷えるC++プログラマを救うため、C++20では念願の コンセプト(Concepts) が導入されました。コンセプト機能の提案文書 N3580 でも「テンプレート関連のエラーメッセージをより分かり易くする1」を掲げています。同文書より、期待されるメッセージ例を引用します
error: no matching function for call to 'sort(list<int>&)'
sort(l);
^
note: candidate is:
note: template<Sortable T> void sort(T)
void sort(T t) { }
^
note: template constraints not satisfied because
note: 'T' is not a/an 'Sortable' type [with T = list<int>] since
note: 'declval<T>()[n]' is not valid syntax
？？？：「きた！コンセプトきた！」「C++コンセプトきた！」「これで勝つる！」
さらにC++20では、STLにも大きな機能追加が行われます。並び替えアルゴリズムの 従来版std::sortはそのまま に、レンジライブラリ(Ranges Library)として std::ranges::sortが新たに追加 されます。早速、新しいレンジ版アルゴリズムを使ってみましょう。（参考記事「C++ STLアルゴリズムの進化：並列化からレンジ拡張まで」）
記述が煩雑なイテレータ・ペアlst.begin(), lst.end()ではなく、レンジ版には操作対象コンテナlstをそのまま渡せます。すごく読み易い！ただしコンパイルは通らない。
#include <algorithm>
#include <list>
int main()
{
// 双方向リンクリストの要素を並び替える
std::list<int> lst = {5, 3, 1, 4, 2};
std::ranges::sort(lst);
// ...
}
動作デモ: https://wandbox.org/permlink/FQpZBQalb2C3aUfp
ではC++コンパイラに叱られてみます（可読性のため大幅に加工・省略）
error: no match for call to '(const std::ranges::__sort_fn) (std::list<int>&)'
8 | std::ranges::sort(lst);
| ^
note: candidate: 'template<class I, class S, class Comp, class Proj>
requires (random_access_iterator<I>) && (sentinel_for<S, I>) && (sortable<I, Comp, Proj>)
constexpr I std::ranges::__sort_fn::operator()(I, S, Comp, Proj) const'
2018 | operator()(I __first, S __last,
| ^~~~~~~~
note: template argument deduction/substitution failed:
note: candidate expects 4 arguments, 1 provided
8 | std::ranges::sort(lst);
| ^
note: candidate: 'constexpr std::ranges::borrowed_iterator_t<R> std::ranges::__sort_fn::operator()(R&&, Comp, Proj) const
[with R = std::list<int>&; Comp = std::ranges::less; Proj = std::identity; std::ranges::borrowed_iterator_t<R> = std::list<int>::iterator]'
2031 | operator()(R&& __r, Comp __comp = {}, Proj __proj = {}) const
| ^~~~~~~~
note: constraints not satisfied
In instantiation of 'constexpr std::ranges::borrowed_iterator_t<R> std::ranges::__sort_fn::operator()(R&&, Comp, Proj) const
[with R = std::list<int>&; Comp = std::ranges::less; Proj = std::identity; std::ranges::borrowed_iterator_t<R> = std::list<int>::iterator]':
required from here
required for the satisfaction of 'derived_from<typename std::__detail::__iter_concept_impl<_Iter>::type, std::random_access_iterator_tag>'
[with _Iter = std::list<int>::iterator]
required for the satisfaction of 'random_access_iterator<decltype (std::__detail::__ranges_begin(declval<_Container&>()))>'
[with _Container = std::list<int>&]
required for the satisfaction of 'random_access_range<R>'
[with R = std::list<int>&]
note: 'std::random_access_iterator_tag' is not a base of 'std::bidirectional_iterator_tag'
67 | concept derived_from = __is_base_of(_Base, _Derived)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
（無加工のエラーメッセージ全体）
prog.cc: In function 'int main()':
prog.cc:8:24: error: no match for call to '(const std::ranges::__sort_fn) (std::__cxx11::list<int>&)'
8 | std::ranges::sort(lst);
| ^
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:64,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/ranges_algo.h:2018:7: note: candidate: 'template<class _Iter, class _Sent, class _Comp, class _Proj> requires (random_access_iterator<_Iter>) && (sentinel_for<_Sent, _Iter>) && (sortable<_Iter, _Comp, _Proj>) constexpr _Iter std::ranges::__sort_fn::operator()(_Iter, _Sent, _Comp, _Proj) const'
2018 | operator()(_Iter __first, _Sent __last,
| ^~~~~~~~
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/ranges_algo.h:2018:7: note: template argument deduction/substitution failed:
prog.cc:8:24: note: candidate expects 4 arguments, 1 provided
8 | std::ranges::sort(lst);
| ^
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:64,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/ranges_algo.h:2031:7: note: candidate: 'constexpr std::ranges::borrowed_iterator_t<_Range> std::ranges::__sort_fn::operator()(_Range&&, _Comp, _Proj) const [with _Range = std::__cxx11::list<int>&; _Comp = std::ranges::less; _Proj = std::identity; std::ranges::borrowed_iterator_t<_Range> = std::conditional<true, std::_List_iterator<int>, std::ranges::dangling>::type]'
2031 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
| ^~~~~~~~
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/ranges_algo.h:2031:7: note: constraints not satisfied
In file included from /opt/wandbox/gcc-head/include/c++/11.0.0/compare:39,
from /opt/wandbox/gcc-head/include/c++/11.0.0/bits/stl_pair.h:65,
from /opt/wandbox/gcc-head/include/c++/11.0.0/utility:70,
from /opt/wandbox/gcc-head/include/c++/11.0.0/algorithm:60,
from prog.cc:1:
/opt/wandbox/gcc-head/include/c++/11.0.0/concepts: In instantiation of 'constexpr std::ranges::borrowed_iterator_t<_Range> std::ranges::__sort_fn::operator()(_Range&&, _Comp, _Proj) const [with _Range = std::__cxx11::list<int>&; _Comp = std::ranges::less; _Proj = std::identity; std::ranges::borrowed_iterator_t<_Range> = std::conditional<true, std::_List_iterator<int>, std::ranges::dangling>::type]':
prog.cc:8:24: required from here
/opt/wandbox/gcc-head/include/c++/11.0.0/concepts:67:13: required for the satisfaction of 'derived_from<typename std::__detail::__iter_concept_impl<_Iter>::type, std::random_access_iterator_tag>' [with _Iter = std::_List_iterator<int>]
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/iterator_concepts.h:599:13: required for the satisfaction of 'random_access_iterator<decltype (std::__detail::__ranges_begin(declval<_Container&>()))>' [with _Container = std::__cxx11::list<int, std::allocator<int> >&]
/opt/wandbox/gcc-head/include/c++/11.0.0/bits/range_access.h:923:13: required for the satisfaction of 'random_access_range<_Range>' [with _Range = std::__cxx11::list<int, std::allocator<int> >&]
/opt/wandbox/gcc-head/include/c++/11.0.0/concepts:67:28: note: 'std::random_access_iterator_tag' is not a base of 'std::bidirectional_iterator_tag'
67 | concept derived_from = __is_base_of(_Base, _Derived)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
なんて簡潔で明解なエラーメッセージ！ ...ではないですね。目を凝らせばランダムアクセス・イテレータへの言及も見つかりはしますが、多くのC++プログラマが期待するメッセージからは程遠いと思われます。
？？？：「嘘だ‥‥‥夢だろ‥‥これ‥‥夢に決まってる‥‥‥‥‥！」
？？？：「ところがどっこい‥‥‥‥夢じゃありません‥‥‥‥！ 現実です‥‥‥！ これが現実‥！」
C++20時代のエラーメッセージ：実践編
さて、ここからが本題です。C++20時代のエラーメッセージを順番に解釈していきましょう。
エラー(error)としては「std::list<int>&を引数に1つだけ取るstd::ranges::sortが見つからない2」とのことです。あれ？
error: no match for call to '(const std::ranges::__sort_fn) (std::list<int>&)'
8 | std::ranges::sort(lst);
| ^
まずは C++20標準ライブラリstd::ranges::sort 定義を確認しましょう。どうやら、2種類のオーバーロードが提供されるようです。
// オーバーロード#1
template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity>
requires sortable<I, Comp, Proj>
constexpr I
ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
// オーバーロード#2
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
最新のC++コンセプト機能がふんだんに使われており、ちょっと難易度が高いかもしれません。説明のために、C++17知識でも読める形に簡約しておきます。（今回無関係なconstexpr省略、戻り値型は等価表現へ置換3）
// オーバーロード#1
template<class I, class S, class Comp = ranges::less, class Proj = identity>
I ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
// オーバーロード#2
template<class R, class Comp = ranges::less, class Proj = identity>
I ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
// I==レンジRのイテレータ型
イテレータのペア(first, last)を取る4引数版オーバーロード#1と、レンジ(r)を取る3引数版オーバーロード#2が存在するようです。いずれのオーバーロードでも、comp, projは省略可能とのこと。
note: candidate: 'template<class I, class S, class Comp, class Proj>
requires (random_access_iterator<I>) && (sentinel_for<S, I>) && (sortable<I, Comp, Proj>)
constexpr I std::ranges::__sort_fn::operator()(I, S, Comp, Proj) const'
2018 | operator()(I __first, S __last,
| ^~~~~~~~
note: template argument deduction/substitution failed:
note: candidate expects 4 arguments, 1 provided
8 | std::ranges::sort(lst);
| ^
上記noteは「イテレータ・ペアをとるオーバーロード#1にはマッチしなかった」と言っています。今回はイテレータ・ペアを使っていませんから、ごもっともな指摘ですね。
note: candidate: 'constexpr std::ranges::borrowed_iterator_t<R> std::ranges::__sort_fn::operator()(R&&, Comp, Proj) const
[with R = std::list<int>&; Comp = std::ranges::less; Proj = std::identity; std::ranges::borrowed_iterator_t<R> = std::list<int>::iterator]'
2031 | operator()(R&& __r, Comp __comp = {}, Proj __proj = {}) const
| ^~~~~~~~
note: constraints not satisfied
もう一方のnoteは「レンジをとるオーバーロード#2では、制約(constraints)を満たせなかった(not satisfied)」と言っています。なるほど？
C++コンセプトは、テンプレートパラメータが満たすべき制約条件を表現する機能です。つまりstd::list<int>型ではアルゴリズムstd::ranges::sortが要求する制約を満たせないと指摘しています。レンジを引数に取るオーバーロード#2の定義を再確認しましょう。
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
requires sortable<iterator_t<R>, Comp, Proj>
constexpr borrowed_iterator_t<R>
ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
ちょっとばかり複雑ですね。ここでは説明に直接関わる部分だけを残して、読みやすさのため思い切り変形してしまいます4。requires節で記述される式が、テンプレートパラメータに対する制約を表します。
template<class R, class Comp = /*...*/, class Proj = /*...*/>
requires (random_access_range<R> && sortable</*...*/>)
I ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
// I==レンジRのイテレータ型
requires節にある1番目の制約式random_access_range<R>は、レンジ型(R)ではランダムアクセス可能であるべきという制約を表します。いよいよ真相に近づいてきました。
In instantiation of 'constexpr std::ranges::borrowed_iterator_t<R> std::ranges::__sort_fn::operator()(R&&, Comp, Proj) const
[with R = std::list<int>&; Comp = std::ranges::less; Proj = std::identity; std::ranges::borrowed_iterator_t<R> = std::list<int>::iterator]':
required from here
required for the satisfaction of 'derived_from<typename std::__detail::__iter_concept_impl<_Iter>::type, std::random_access_iterator_tag>'
[with _Iter = std::list<int>::iterator]
required for the satisfaction of 'random_access_iterator<decltype (std::__detail::__ranges_begin(declval<_Container&>()))>'
[with _Container = std::list<int>&]
required for the satisfaction of 'random_access_range<R>'
[with R = std::list<int>&]
note: 'std::random_access_iterator_tag' is not a base of 'std::bidirectional_iterator_tag'
67 | concept derived_from = __is_base_of(_Base, _Derived)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ここまでの知識を踏まえて脳内フィルタを通すと「required for the satisfaction of 'random_access_range<R>'」が見つかるでしょうか。
Q.E.D.
エクストラ・ステージ
やはり最終行のnoteは気になりますか？これは、おそらく、C++コンセプト仕様によるエラーメッセージ表現の限界と考えられます。
note: 'std::random_access_iterator_tag' is not a base of 'std::bidirectional_iterator_tag'
67 | concept derived_from = __is_base_of(_Base, _Derived)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
コンセプトrandom_access_range はさらに別のコンセプトを使って定義されており、途中経緯を全てすっ飛ばすと コンセプトderived_from による制約式が登場します。
derived_from<bidirectional_iterator_tag, random_access_iterator_tag>
C++標準規格とは異なる制約式になっていますが、GCCコンパイラは効率化のため 型特性コンパイラサポート機能__is_base_of を利用するようです。ここではエラー原因の最小単位となる原始制約式(atomic constraints)として、該当行が出力されたのだと推測されます。
（参考：https://twitter.com/yohhoy/status/1278576616440860673）
-
"fundamentally improve diagnostics by checking template arguments in terms of stated intent at the point of use" ↩
-
エラーメッセージを注意深く読むと
std::ranges::sort関数テンプレートではなく、std::ranges::__sort_fn関数オブジェクトに対するoperator()演算子オーバーロード呼び出しとなっています。これはレンジライブラリのADL要件を満たす措置となっています。 ↩ -
borrowed_iterator_t<std::list<int>&>はstd::list<int>::iterator↩ -
template<random_access_range R> requires Cはtemplate<class R> requires (random_access_range<R> && C)と等価。 ↩