C++標準ライブラリが定める InputIterator 要件(requirement) と input_iteratorコンセプト(concept) の変遷についてメモ。


N4835(C++2a WD)


An iterator i for which the expression (*i).m is well-defined supports the expression i->m with the same semantics as (*i).m.

N4835*1 23.2, 23.3.1/p1,,,, Table 83より一部引用。

Header <iterator> synopsis

namespace std {
  template<class T> using with-reference = T&;  // exposition only
  template<class T> concept can-reference       // exposition only
    = requires { typename with-reference<T>; };
  template<class T> concept dereferenceable     // exposition only
    = requires(T& t) {
      { *t } -> can-reference;  // not required to be equality-preserving
  // (snip)

1 Iterators are a generalization of pointers that allow a C++ program to work with different data structures (for example, containers and ranges) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, the library formalizes not just the interfaces but also the semantics and complexity assumptions of iterators. An input iterator i supports the expression *i, resulting in a value of some object type T, called the value type of the iterator. (snip)

1 Types that are readable by applying operator* model the readable concept, including pointers, smart pointers, and iterators.

template<class In>
  concept readable =

2 Given a value i of type I, I models readable only if the expression *i is equality-preserving. [Note: The expression *i is indirectly required to be valid via the exposition-only dereferenceable concept (23.2). -- end note]

1 The input_or_output_iterator concept forms the basis of the iterator concept taxonomy; every iterator models input_or_output_iterator. This concept specifies operations for dereferencing and incrementing an iterator. Most algorithms will require additional operations to compare iterators with sentinels (, to read ( or write ( values, or to provide a richer set of iterator movements (,,

template<class I>
  concept input_or_output_iterator =
    requires(I i) {
      { *i } -> can-reference;
    } &&

1 The input_iterator concept defines requirements for a type whose referenced values can be read (from the requirement for readable ( and which can be both pre- and post-incremented. [Note: Unlike the Cpp17InputIterator requirements (, the input_iterator concept does not need equality comparison since iterators are typically compared to sentinels. -- end note]

template<class I>
  concept input_iterator =
    input_or_output_iterator<I> &&
    readable<I> &&
    requires { typename ITER_CONCEPT(I); } &&
    derived_from<ITER_CONCEPT(I), input_iterator_tag>;

Table 83: Cpp17InputIterator requirements (in addition to Cpp17Iterator)

Operational semantics
Assertion/note pre-/post-condition
Expects: a is dereferenceable.


Input iterator要件はoperator->オーバーロードを要求する。 C++17 27.2.3 Table 95より該当箇所を引用。

Operational semantics
Assertion/note pre-/post-condition
Requires: a is dereferenceable.

C++17以降、LWG DR 2790にて istreambuf_iterator::operator-> は削除された。


Input iterator要件はoperator->オーバーロードを要求する。 C++11 24.2.3 Table 107より該当箇所を引用。C++14でも同一。

Operational semantics
Assertion/note pre-/post-condition
pre: a is dereferenceable.

C++11以降、LWG DR 659にて istreambuf_iterator::operator-> が追加された。


Input iterator要件はoperator->オーバーロードを要求する。 C++03 24.1.1 Table 72より該当箇所を引用。

semantics, pre/post-condition
pre: (*a).m is well-defined
Equivalent to (*a).m



same_asコンセプトとSymmetric Subsumption Idiom

C++2a(C++20)ライブラリ提供の標準コンセプトstd::same_as、およびコンセプト定義における対称包摂イディオム(Symmetric Subsumption Idiom)についてメモ。

制約式std::same_as<X, Y>と制約式std::same_as<Y, X>は対称関係、つまり互いに一方が他方を包摂する(subsume)関係にある。これによりコンセプトへのテンプレートパラメータ指定順が一致していなくとも、制約式を用いた関数オーバーロード解決の半順序関係を表現できる。

// C++2a(C++20)
#include <concepts>

template <typename X, typename Y>
  requires std::same_as<X, Y>
constexpr int f() { return 1; }  // #1

template <typename X, typename Y>
  requires std::same_as<Y, X> && (1 < sizeof(X))
constexpr int f() { return 2; }  // #2

f<int, int>();  // OK: #2を呼び出す



標準コンセプトsame_as<T,U>の定義では動作説明用(exposition only)のコンセプトsame-as-implを用いて、型パラメータT, Uに対象関係が成り立つようにしている。ここではC++2a言語仕様上、メタ関数is_same_vの直接記述ではなくコンセプトsame-as-impl経由が必須となる。(詳細後述)
N4830*2 14.8.2より引用。

template<class T, class U>
  concept same-as-impl = is_same_v<T, U>;  // exposition only

template<class T, class U>
  concept same_as = same-as-impl<T, U> && same-as-impl<U, T>;

1 [Note: same_as<T, U> subsumes same_as<U, T> and vice versa. -- end note]


The specification of the Same concept in 18.4.2 [concept.same]:

template<class T, class U>
  concept Same = is_same_v<T, U>;

-1- Same<T, U> subsumes Same<U, T> and vice versa.

seems contradictory. From the concept definition alone, it is not the case that Same<T, U> subsumes Same<U, T> nor vice versa. Paragraph 1 is trying to tell us that there's some magic that provides the stated subsumption relationship, but to a casual reader it appears to be a misannotated note. We should either add a note to explain what's actually happening here, or define the concept in such a way that it naturally provides the specified subsumption relationship.

Given that there's a straightforward library implementation of the symmetric subsumption idiom, the latter option seems preferable.


コンセプトsame_as定義にコンセプトsame-as-implを利用するとき、2つの制約式[A]same_as<X, Y>, [B]same_as<Y, X>の関係は次のように説明できる。

template<class T, class U>
  concept same-as-impl = is_same_v<T, U>/*#0*/;

template<class T, class U>
  concept same_as = same-as-impl<T, U> && same-as-impl<U, T>;

それぞれの制約式を正規化(normalization)すると、原子制約(atomic constraint)導出時のパラメータマッピング(parameter mapping)を ↦ 表記して、次の正規形(normal form)が得られる:

  • [A]same_as<X, Y>の正規形は is_same_v<T↦X, U↦Y>#0is_same_v<T↦Y, U↦X>#0
  • [B]same_as<Y, X>の正規形は is_same_v<T↦Y, U↦X>#0is_same_v<T↦X, U↦Y>#0

制約P=[A]same_as<X, Y>, 制約Q=[B]same_as<Y, X>とおくと、PのDNF(選言標準形; disjunctive normal form)およびQのCNF(連言標準形; conjunctive normal form)の各項は次の通り:

  • P1=(is_same_v<T↦X, U↦Y>#0is_same_v<T↦Y, U↦X>#0)
  • Q1=is_same_v<T↦Y, U↦X>#0, Q2=is_same_v<T↦X, U↦Y>#0

項P1は2つの原子制約 P1,1=is_same_v<T↦X, U↦Y>#0, P1,2=is_same_v<T↦Y, U↦X>#0からなり、QのCNF項に含まれる原始制約Qj,bに対して同一(identical; ≡ 表記)な原子制約Pi,aが存在する:

  • 原子制約Q1,1=is_same_v<T↦Y, U↦X>#0 ≡ 原子制約P1,2=is_same_v<T↦Y, U↦X>#0 つまり “項P1 subsumes 項Q1
  • 原子制約Q2,1=is_same_v<T↦X, U↦Y>#0 ≡ 原子制約P1,1=is_same_v<T↦X, U↦Y>#0 つまり “項P1 subsumes 項Q2

以上より、制約Pの全てのDNF項(P1)は制約Qの全てのCNF項(Q1, Q2)を包摂する、つまり “[A]same_as<X, Y> subsumes [B]same_as<Y, X>” が導出される。

制約P, Qを入れ替えると、同様に対称な関係 “[B]same_as<Y, X> subsumes [A]same_as<X, Y>” が導出される。


コンセプトsame_as定義にメタ関数is_same_vを直接利用したとき、2つの制約式[A]same_as<X, Y>, [B]same_as<Y, X>の関係は次のように説明できる。

template<class T, class U>
  concept same_as = is_same_v<T, U>/*#1*/ && is_same_v<U, T>/*#2*/;


  • [A]same_as<X, Y>の正規形は is_same_v<T↦X, U↦Y>#1is_same_v<U↦Y, T↦X>#2
  • [B]same_as<Y, X>の正規形は is_same_v<T↦Y, U↦X>#1is_same_v<U↦X, T↦Y>#2

制約P=[A]same_as<X, Y>, 制約Q=[B]same_as<Y, X>とおくと、PのDNFおよびQのCNFの各項は次の通り:

  • P1=(is_same_v<T↦X, U↦Y>#1is_same_v<U↦Y, T↦X>#2)
  • Q1=is_same_v<T↦Y, U↦X>#1, Q2=is_same_v<U↦X, T↦Y>#2

項P1は2つの原子制約 P1,1=is_same_v<T↦X, U↦Y>#1, P1,2=is_same_v<U↦Y, T↦X>#2からなるが、QのCNF項に含まれる原始制約Q1,1やQ2,1と “同じ式(the same expression)” かつ “同等のパラメータマッピング” をもつ原子制約が無い、つまりいずれの原子制約Qj,bに対しても同一(identical)な原子制約Pi,aは存在しない。*4

つまり[A]same_as<X, Y>は[B]same_as<Y, X>を包摂しない。制約P, Qを入れ替えても同様に包摂関係は成り立たない。


*1:C++言語仕様を厳格に解釈すると 1 == sizeof(int) となる処理系が存在しうるため、該当コードでオーバーロード#1が選択される可能性もある。本記事ではそのような処理系の存在は無視する。


*3:N4820以前のコンセプト名は Same とされていたが、(PDF)P1754R1採択によって same_as へと改名された。詳細はC++標準コンセプトの名前付けガイドラインを参照。

*4:N4830 "Two atomic constraints are identical if they are formed from the same expression and the targets of the parameter mappings are equivalent according to the rules for expressions described in"



本文こちら→C++ MIX #5に参加しました - yohhoyの日記(別館)

スライド資料:https://www.slideshare.net/yohhoy/20c20 [B!] 20分くらいでわかった気分になれるC++20コルーチン





要約:制約式の包摂関係(subsumption relation)判定では、制約を構成するトークン列が同じというだけではダメで、C++ソースコード上での記述位置(=構文木におけるノード)の同一性が考慮される。こんなん分かる気がしない_(:3」∠)_


// C++2a(N4830)
#if コンセプト
template <typename T> concept C1 = true;  // #1
template <typename T> concept C2 = true;  // #2
#elif 変数テンプレート
template <typename T> inline constexpr bool C1 = true;
template <typename T> inline constexpr bool C2 = true;

// [A] 制約式C1<T> && C2<T>
template <typename T>
  requires C1<T> && C2<T>  // #3
constexpr int foo() { return 0; }

// [B] 制約式C1<T>
template <typename T>
  requires C1<T>           // #4
constexpr int foo() { return 1; }

foo<int>();  // ★ [A]/[B] or...?
C1, C2がコンセプト名の場合
制約式C1<T> && C2<T>は制約式C1<T>を包摂する(subsume)ため、より強く制約された(more constrained) 関数[A] が選択される。正規化(normalization)によって前者はtrue#1true#2に、後者はtrue#1となる。このとき原子制約(atomic constraint) true#1は “同一の式(the same expression)” から構成されるため、C1<T> && C2<T> subsume C1<T>という包摂関係が成立する。
C1, C2が非コンセプト名(テンプレート)の場合
制約式C1<T> && C2<T>と制約式C1<T>は互いに包摂関係になく、関数呼び出しのオーバーロード解決は曖昧となるためプログラムはill-formed。正規化(normalization)によって前者はC1<T>#3C2<T>#3に、後者はC1<T>#4となる。このとき原子制約C1<T>#3C1<T>#4は “同一の式(the same expression)” からは構成されておらず、無関係な制約式として解釈される。

原子制約の同一性(identical)判定基準は、Concepts TS時点の (PDF)P0717R1 Semantic constraint matching for concepts にて次のように説明される(下線部は強調)。

Equivalence during partial ordering
We propose to use a different model for determining whether two atomic constraints are equivalent. Tersely, we can describe this as follows: two atomic constraints are equivalent only if they originate from the same source-level construct.

メモ:C++20標準ライブラリ提供のコンセプト実装にて exposition only なコンセプトを多用しているのは、そのコンセプト名から期待される包摂関係が成り立つよう考慮した結果と思われる。

2019-09-11追記:P0717R1を実装したVisual Studio 2019 16.3 Preview 2で動作確認を行ったところ、上記解釈通りの実行結果「コンセプト名では[A]を選択/非コンセプト名ではオーバーロード解決が曖昧」が得られた。後者のエラー出力は下記の通り:

error C2668: 'foo': ambiguous call to overloaded function
message : could be 'int foo<int>(void)'
message : or       'int foo<int>(void)'
message : while trying to match the argument list '()'

2019-10-17追記:GCC 10.0.0 20191015(experimental)でも上記解釈通り動作することを確認。後者のエラー出力は下記の通り:

In function 'int main()':
error: call of overloaded 'f<int, int>()' is ambiguous
  |   return f<int, int>();
  |                      ^
note: candidate: 'constexpr int f() [with T = int; U = int]'
  | constexpr int f() { return 1; }  // #1
  |               ^
note: candidate: 'constexpr int f() [with T = int; U = int]'
  | constexpr int f() { return 2; }  // #2
  |               ^


N4830*1(C++2a WD), 13.4.3/p1-2, 13.4.4/p1-4,より一部引用(下線部は強調)。

1 An atomic constraint is formed from an expression E and a mapping from the template parameters that appear within E to template arguments involving the template parameters of the constrained entity, called the parameter mapping (13.4.2). [Note: Atomic constraints are formed by constraint normalization (13.4.3). E is never a logical AND expression (7.6.14) nor a logical OR expression (7.6.15). -- end note]
2 Two atomic constraints are identical if they are formed from the same expression and the targets of the parameter mappings are equivalent according to the rules for expressions described in

1 The normal form of an expression E is a constraint (13.4.1) that is defined as follows:

  • The normal form of an expression ( E ) is the normal form of E.
  • The normal form of an expression E1 || E2 is the disjunction ( of the normal forms of E1 and E2.
  • The normal form of an expression E1 && E2 is the conjunction of the normal forms of E1 and E2.
  • The normal form of an id-expression of the form C<A1, A2, ..., An>, where C names a concept, is the normal form of the constraint-expression of C, after substituting A1, A2, ..., An for C's respective template parameters in the parameter mappings in each atomic constraint. (snip)
  • The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping.

2 The process of obtaining the normal form of a constraint-expression is called normalization. [Note: Normalization of constraint-expressions is performed when determining the associated constraints (13.4.1) of a declaration and when evaluating the value of an id-expression that names a concept specialization (7.5.4). -- end note]

1 A constraint P subsumes a constraint Q if and only if, for every disjunctive clause Pi in the disjunctive normal form132 of P, Pi subsumes every conjunctive clause Qj in the conjunctive normal form133 of Q, where

  • a disjunctive clause Pi subsumes a conjunctive clause Qj if and only if there exists an atomic constraint Pia in Pi for which there exists an atomic constraint Qjb in Qj such that Pia subsumes Qjb, and
  • an atomic constraint A subsumes another atomic constraint B if and only if the A and B are identical using the rules described in

[Example: Let A and B be atomic constraints ( The constraint A ∧ B subsumes A, but A does not subsume A ∧ B. The constraint A subsumes A ∨ B, but A ∨ B does not subsume A. Also note that every constraint subsumes itself. -- end example]
脚注132) A constraint is in disjunctive normal form when it is a disjunction of clauses where each clause is a conjunction of atomic constraints. (snip)
脚注133) A constraint is in conjunctive normal form when it is a conjunction of clauses where each clause is a disjunction of atomic constraints. (snip)

2 [Note: The subsumption relation defines a partial ordering on constraints. This partial ordering is used to determine

  • (snip)
  • the partial ordering of function templates (

-- end note]
3 A declaration D1 is at least as constrained as a declaration D2 if

  • D1 and D2 are both constrained declarations and D1's associated constraints subsume those of D2; or
  • D2 has no associated constraints.

4 A declaration D1 is more constrained than another declaration D2 when D1 is at least as constrained as D2, and D2 is not at least as constrained as D1. (snip)

2 Partial ordering selects which of two function templates is more specialized than the other by transforming each template in turn (see next paragraph) and performing template argument deduction using the function type. The deduction process determines whether one of the templates is more specialized than the other. If so, the more specialized template is the one chosen by the partial ordering process. If both deductions succeed, the partial ordering selects the more constrained template as described by the rules in 13.4.4.

§ [temp.constr.atomic]/p2 で言及される "the same expression" の解釈については、https://github.com/cplusplus/draft/issues/2554 が挙げられている。より明確化されたWordingへと変更されるかも。



C言語の可変引数リストアクセス用 va_arg マクロにおける奇妙な制限事項についてメモ。

va_argマクロの第二引数へ指定する型名には、“関数ポインタ型” や “配列へのポインタ型” を直接記述できない。ただしtypedefによる別名であればOK。こんなコード書くやつおらんやろ

#include <stdarg.h>

void f0(int x, ...)
  va_list ap;
  va_start(ap, x);
  // NG: 関数ポインタ型 int(*)(int) は直接指定できない
  int (*pf)(int) = va_arg(ap, int(*)(int));
  // NG: 配列へのポインタ型 int(*)[N] は直接指定できない
  int (*pa)[3] = va_arg(ap, int(*)[3]);

void f1(int x, ...)
  typedef int (*PF)(int), (*PA)[3];
  va_list ap;
  va_start(ap, x);
  // OK: typdefされた別名 PF ならば指定可能
  PF pf = va_arg(ap, PF);
  // OK: typdefされた別名 PA ならば指定可能
  PA pa = va_arg(ap, PA);

int h(int n);
int a[3];
f0(0, &h, &a);
f1(0, &h, &a);

C99 p1-2より一部引用(下線部は強調)。

#include <stdarg.h>
type va_arg(va_list ap, type);

The va_arg macro expands to an expression that has the specified type and the value of the next argument in the call. (snip) The parameter type shall be a type name specified such that the type of a pointer to an object that has the specified type can be obtained simply by postfixing a * to type. If there is no actual next argument, or if type is not compatible with the type of the actual next argument (as promoted according to the default argument promotions), the behavior is undefined, except for the following cases:

  • one type is a signed integer type, the other type is the corresponding unsigned integer type, and the value is representable in both types;
  • one type is pointer to void and the other is a pointer to a character type.

一見すると奇妙なこの制限は、va_argマクロの実装を考慮して設けられた。プリプロセッサでは単純なトークン列操作しか行えないため、型名に*を後置するだけで妥当なポインタ型名を生成できる必要がある。(PDF)C99 Rationaleより引用(下線部は強調)。 The va_arg macro
Changing an arbitrary type name into a type name which is a pointer to that type could require sophisticated rewriting. To allow the implementation of va_arg as a macro, va_arg need only correctly handle those type names that can be transformed into the appropriate pointer type by appending a *, which handles most simple cases. Typedefs can be defined to reduce more complicated types to a tractable form. When using these macros, it is important to remember that the type of an argument in a variable argument list will never be an integer type smaller than int, nor will it ever be float (see §

va_arg can only be used to access the value of an argument, not to obtain its address.

例:古の GCC 2.95.3*1 では下記マクロ定義となっていた(読みやすさのため簡略化している)

#define va_arg(AP, TYPE)  \
  (AP = (va_list) ((char *) (AP) + __va_rounded_size(TYPE)),  \
   *((TYPE *) ((char *) (AP) - __va_rounded_size(TYPE))))

/* __va_rounded_size(T) := sizeof(T)をsizeof(int)の倍数に切り上げ */

GCC 3.0以降*2LLVM/Clang*3では組み込み関数__builtin_va_argにより実装されるため、厳密に同制限を守らないコードでもコンパイルできてしまう。
VisualC++ 2017(MSVC 19.10)の場合、同制限に違反するコードは(一見すると不可解な)コンパイルエラーを引き起こすが、このMSVCの振る舞いはC言語仕様準拠といえる。



C++2a(C++20)標準ライブラリに導入される コンセプト(concept) の名前付けガイドラインについて。

2019年Cologne会合にて (PDF)P1754R1 が採択され、Ranges TS提案当初から PascalCase 形式で検討されていた命名規則から snake_case 形式へと変更された。これにより従来C++標準ライブラリとの一貫性は向上したが、その名前のみからはコンセプトなのかクラスやメタ関数*1なのかを判別しづらくなっている。*2


  • コンセプト名は snake_case 形式とする。
  • コンセプトを示す接頭辞(prefix)/接尾辞(suffix)は使わない。
  • コンセプトの目的に応じた3つのカテゴリ:特性(Capabilities)、抽象(Abstrations)、その他の述語(predicate)
  • 特性コンセプト(capability concept):ある関数/メンバ関数呼び出しが可能といった単一要件で構成される。
    • 特性コンセプトの名前は、その要件を説明する形容詞(adjective)とする。
    • 要求する特性が関数のとき、そのコンセプト名には関数名に-ible-able接尾辞をつけたものとする。例:swap可能を要求するswappable, コピー構築可能を要求するcopy_constructible
  • 抽象コンセプト(abstract concept):複数要件から構成されたりコンセプト構成のルートにあたるハイレベル・コンセプト。
    • 抽象コンセプトの名前は、新しい専門用語(terminology)を導入する名詞(noun)とする。例:forward_iterator(要件を列挙しただけのhas_increment_equality_and_dereferenceはNG)
    • 抽象コンセプトの名前は、同コンセプトを満たす型の名前よりも総称的(general)であること。
  • その他の述語コンセプト:下記に該当する場合は、型トレイツ(type traits)の命名規則に従う。ただしis_接頭辞はつけない。
    • 主に複数の型引数をとり型制約に利用されるときは、適切な前置詞(preposition)で終わる名前とする。例:swappable_with, same_as<int>, constructible_with<args>, sentinel_for<iterator>
    • 主に別コンセプトの定義やrequires節で利用されるときは、前置詞(preposition)は付けない。例:swappable, mergeable


*1:標準ヘッダ <type_traits> で提供される、ある型の特性(traits)をコンパイル時に判別するテンプレート関数群。

*2:P1754R1では変更根拠として、PascalCase はドメイン固有のエンティティ名として用いられるケースが多いことと、アプリケーションコードでの using namespace std; 利用によって生じる名前衝突回避を挙げている。