yohhoyの日記

技術的メモをしていきたい日記

可変長コンセプト×畳み込み式: The glass is half full or half empty?

C++20コンセプトと論理演算子(&&, ||)による畳み込み式(fold expression)の関係について。本記事の内容はStackOverflowで見つけた質問と回答に基づく。

まとめ:&&||による畳み込み式を用いた制約式(constraint-expression)は機能するものの、コンセプト間の包摂関係(subsumption relation)は期待通りに成り立たない。

#include <concepts>

// コンセプト any_of<T, Us...>
// 型Tが型リストUs..のいずれかと一致する?
template <typename T, typename... Us>
concept any_of = (std::same_as<T, Us> || ...);

template <typename T>
constexpr int f(T) { return 1; }  // #1

template <typename T>
  requires any_of<T, int, double>
constexpr int f(T) { return 2; }  // #2
// または
template <any_of<int, double> T> 
constexpr int f(T) { return 2; }  // #2

static_assert(f(42) == 2);    // OK: #2 int型
static_assert(f(3.14) == 2);  // OK: #2 double型
static_assert(f(0.f) == 1);   // OK: #1 float型
static_assert(f('X') == 1);   // OK: #1 char型

C++20コンセプト仕様では、畳み込み式(std::same_as<T, Us> || ...)それ自体で一つの原始制約(atomic constraint)を構成する。オーバーロード解決のために制約式の包摂関係を求める(≒強弱の判定)正規化(normalization)過程で、std::same_as<T, Us[0]>std::same_as<T, Us[1]>...のようには展開解釈されない。*1

// 畳み込み式による(可変長)コンセプト定義
template <typename T, typename... Us>
concept any_of = (std::same_as<T, Us> || ...);

template <any_of<int, double> T> 
constexpr int f(T) { return 2; }  // #2

template <std::same_as<double> T>
constexpr int f(T) { return 3; }  // #3

static_assert(f(42) == 2);    // OK: #2の制約のみ満たす
static_assert(f(3.14) == 3);  // NG: #2,#3間でオーバロード解決が曖昧

可変長コンセプトをあきらめて制約式(std::same_as<T, U1> || std::same_as<T, U2>)とすれば包摂関係が成立し、自然なオーバーロード選択が行われる。つまり制約any_of2<T, int, double>よりも制約std::same_as<T, double>の方がより強い制約(more constrained)と解釈される。

// 畳み込み式を利用しない(2型版)コンセプト定義
template <typename T, typename U1, typename U2>
concept any_of2 = (std::same_as<T, U1> || std::same_as<T, U2>);

template <any_of2<int, double> T> 
constexpr int f(T) { return 2; }  // #2

template <std::same_as<double> T>
constexpr int f(T) { return 3; }  // #3

static_assert(f(42) == 2);    // OK: #2
static_assert(f(3.14) == 3);  // OK: #3は#2より強く制約される

関連URL

*1:C++20 §13.5.1.1/p1 Note: "(snip) For the purpose of exposition, conjunction is spelled using the symbol ⋀ and disjunction is spelled using the symbol ⋁. (snip)"

requires式中でのコンセプト制約表現には要注意

C++20 requires式(requires-expression) において、コンセプトや条件式を用いた制約(constraints)表現には注意が必要。

下記コードのように式std::signed_integral<decltype(N)>N == 42をrequires式中に単に記載すると単純要件(simple-requirement)となり、式の妥当性のみがチェックされプログラマが意図する制約は行われない。std::signed_integral<decltype(N)>N == 42の評価結果は利用されず、それ自身は常に有効な式となるため。*1

#include <concepts>

// 符号付き整数型の定数42を表すコンセプト(?)
template <auto N>
concept magic_number = requires {
  std::signed_integral<decltype(N)>;  // ★
  N == 42;  // ★
};

static_assert(  magic_number<42> );   // OK
static_assert( !magic_number<42u> );  // NG !?
static_assert( !magic_number<0> );    // NG !?

requiresキーワードを用いて入れ子要件(nested-requirement)として記述とするか、単に制約式の&&(conjunction; 連言/合接)として記述する。両記述はセマンティクス上ほぼ等価だが、後者の方がコンセプトベースのオーバーロード解決における包摂関係(→id:yohhoy:20190903)を自然に表現できる*2。Simpe is the best.

// 符号付き整数型の定数42を表すコンセプト
template <auto N>
concept magic_number = requires {
  requires std::signed_integral<decltype(N)>;
  requires (N == 42);
};
// または
template <auto N>
concept magic_number = std::signed_integral<decltype(N)> && (N == 42);

static_assert(  magic_number<42> );   // OK
static_assert( !magic_number<42u> );  // OK
static_assert( !magic_number<0> );    // OK

関連URL

*1:C++20 13.3/p8: "A concept-id is a simple-template-id where the template-name is a concept-name. A concept-id is a prvalue of type bool, and does not name a template specialization. A concept-id evaluates to true if the concept's normalized constraint-expression is satisfied by the specified template arguments and false otherwise."

*2:https://wandbox.org/permlink/xhGW29ycmxLWJIR7

HRESULT型からのエラーメッセージ取得

WindowsOS環境のHRESULT型エラーコードからエラーメッセージ文字列へのお手軽変換。Microsoft Visual C++(MSVC)限定。

#include <windows.h>
#include <system_error>

std::string get_message(HRESULT hr)
{
  return std::system_category().message(hr);
}

// GetLastError()戻り値などDWORD型 Windows Error Code の場合は、
// HRESULT_FROM_WIN32マクロによりHRESULT型へと事前変換する。

上記コードではWindows OSのロケールに応じた文字列(日本語OSなら日本語のメッセージ)が取得される。英語メッセージで固定したい場合などは、FormatMessage関数を自前で呼び出す必要がある。

おまけ:FormatMessage関数のdwLanguageId引数=0で実装されているため*1SetThreadUILanguage関数でスレッドのLANGIDを事前に変更しておく案もある。シングルスレッドプログラムならこれでもいいか...

関連URL

*1:"If you pass in zero, FormatMessage looks for a message for LANGIDs in the following order: 1.Language neutral / 2.Thread LANGID, based on the thread's locale value / 3.(snip)"

ジュラシック・パーク in C++ Standard

プログラミング言語C++標準規格に潜む恐竜たち。🦕🦖

C++20(N4861) D.5 Deprecated volatile typesより引用。*1

1 Postfix ++ and -- expressions (7.6.1.5) and prefix ++ and -- expressions (7.6.2.2) of volatile-qualified arithmetic and pointer types are deprecated.

volatile int velociraptor;
++velociraptor;  // deprecated

2 Certain assignments where the left operand is a volatile-qualified non-class type are deprecated; see 7.6.19.

int neck, tail;
volatile int brachiosaur;
brachiosaur = neck;                // OK
tail = brachiosaur;                // OK
tail = brachiosaur = neck;         // deprecated
brachiosaur += neck;               // deprecated
brachiosaur = brachiosaur + neck;  // OK

3 A function type (9.3.3.5) with a parameter with volatile-qualified type or with a volatile-qualified return type is deprecated.

volatile struct amber jurassic();                             // deprecated
void trex(volatile short left_arm, volatile short right_arm); // deprecated
void fly(volatile struct pterosaur* pteranodon);              // OK

4 A structured binding (9.6) of a volatile-qualified type is deprecated.

struct linhenykus { short forelimb; };
void park(linhenykus alvarezsauroid) {
  volatile auto [what_is_this] = alvarezsauroid;  // deprecated
  // ...
}

メモ:

おまけ:

関連URL

*1:Annex D Compatibility features は normative のため、正式C++20仕様の一部とみなされる。

RangeとViewとconst修飾

C++20 RangesライブラリのRangeとViewとconst修飾の関係についてメモ。

まとめ:

  • 対象Rangeのconst修飾(要素の変更可否)と、Viewのconst修飾(const-iterableの可否)は異なる概念である。
  • C++20標準ライブラリ提供の一部Rangeアダプタでは、const修飾によりViewとして機能しなくなるものがある。
    • 具体例:std::views::filter, std::views::drop_while
  • Viewを受け取るパラメータでは不用意にconst修飾を行わないこと。
    • Viewは定義上「軽量にコピー/ムーブ」されるオブジェクトのため、パラメータ型は非constな値型とすればよい。

下記コードのようにViewをconst修飾しても、対象Range要素がconst修飾されていなければ要素値を書き換え可能。要素書き換えから保護するには、対象Range側をconst修飾する(ここではstd::as_constを利用)。*1

#include <ranges>
#include <utility>  // as_const

int a[] = {1, 2, 3, 4, 5};
// Rangeに対するconst-View:要素を変更可能
const auto view1 = a | std::views::take(3);
for (auto& e: view1) {
  e *= 2;  // OK
}
// a == {2, 4, 6, 4, 5}

// const-Rangeに対するView:要素変更は不可能
auto view2 = std::as_const(a) | std::views::take(3); 
for (auto& e: view2) {
  e *= 2;  // NG: ill-formed
}

const性(const-ness)に関するRangeとViewとの関係性は、コンテナ(container)に対するイテレータ(iterator)、配列(array)に対するポインタ(pointer)に相当する。イテレータやポインタが指す先のconst性は重要視されるが、イテレータやポインタそのものをconst修飾する必要性は低い。

  • 例1:コンテナVec=std::vector<T>に対するVec::const_iteratorconst Vec::iterator
  • 例2:配列T[N]に対するconst T *T * const

C++20標準ライブラリRangeアダプタstd::views::filterは const-iterable でないため、関数f0のようにViewをconst修飾(const View&)するとfilterが適用されたViewを受け取れず、汎用アルゴリズムとしての一般性が失われる*2。コンテナCイテレータのアナロジーで解釈すると:関数f0const C::iterator&を、関数f1C::iteratorを受け取るインタフェースに相当する。

#include <iostream>
#include <ranges>

// const-View参照を引数にとる関数テンプレート
template <std::ranges::view View>
void f0(const View& view)
{
  for (const auto& e : view)
    std::cout << e;
}

// Viewを引数にとる関数テンプレート
template <std::ranges::view View>
void f1(View view)
{
  for (const auto& e : view)
    std::cout << e;
}

int a[] = {1, 2, 3, 4, 5};
auto take3  = std::views::take(3);
auto is_odd = std::views::filter([](int n){ return n % 2; });

f0(a | take3);   // OK: "123"
f0(a | is_odd);  // NG: ill-formed

f1(a | take3);   // OK: "123"
f1(a | is_odd);  // OK: "135"

Rangeアダプタfilterdrop_whileが const-iterable でないのは、Range要件「beginイテレータ取得は償却定数時間(amortized constant time)」を満たしつつ「const操作のスレッド安全性を担保するオーバーヘッド追加を避ける」というライブラリ設計上の選択による。

C++20 24.4.2/p1, 3より引用(下線部は強調)。

1 The range concept defines the requirements of a type that allows iteration over its elements by providing an iterator and sentinel that denote the elements of the range.

template<class T>
  concept range =
    requires(T& t) {
      ranges::begin(t);
      ranges::end(t);
    };

3 Given an expression t such that decltype((t)) is T&, T models range only if

  • [ranges::begin(t), ranges::end(t)) denotes a range (23.3.1),
  • both ranges::begin(t) and ranges::end(t) are amortized constant time and non-modifying, and
  • if the type of ranges::begin(t) models forward_iterator, ranges::begin(t) is equality-preserving.

C++20採択済み(PDF)P0896R4にマージされた提案文書P0789R3 Design Considerations, 1.3.1/p3-4より一部引用(下線部は強調)。

1.3.1 The filter adaptor is not const-iterable

3 The filter view, which skips elements that fail to satisfy a predicate, needs to do an O(N) probe to find the first element that satisfies the predicate so that begin can return it. The options are:

  1. Compute this position on adaptor construction. This solution has multiple problems. First, constructing an adaptor should be O(1). Doing an O(N) probe obviously conflicts with that. Second, the probe would return a position in the source range, but when the filter view is copied, the iterator becomes invalid, lest it be left pointing to an element in the source range. That means that copies and moves of the filter view would need to invalidate the cache and perform another O(N) probe to find the first element of the filtered range. O(N) copy and move operations make it difficult to reason about the cost of building adaptor pipelines.
  2. Recompute the first position on each invocation of begin. This is obviously in conflict with the semantic requirements of the Range concept, which specifies that begin is amortized constant-time.
  3. Compute the first position once in begin on demand and cache the result, with synchronization. Taking a lock in the begin member function in order to update an internal cache permits that operation to be const while satisfying [res.on.data.races], but obviously incurs overhead and violates the "don't pay for what you don't use" mantra.
  4. Compute the first position once in begin on demand and cache the result, without synchronization. The downside of this approach is that begin cannot be const without violating [res.on.data.races].

4 None of these are great options, and this particular design point has been discussed at extensive length (see range-v3#385) in the context of the filter view and an assortment of other adaptors that are unable to provide const iteration. The general consensus is that option (4) above is the least bad option, and is consistent with the perspective that adaptors are lazily-evaluated algorithms: some algorithms can be implemented without the need to maintain mutable state. Others cannot.

C++20 Rangesライブラリ仕様のベースとなった、range-v3ライブラリのIssue#385より関連議論を一部引用(下線部は強調)。

There's a lot of wrong-thinking about views here: people need to stop thinking of views as being like references to containers and start thinking of views as being like iterators that denote zero or more elements instead of zero or one. Accepting a view by const& has the same semantics as accepting an iterator by const&: it has no effect on the mutability of the denoted elements, it only forbids modifying the iterator/view such that it denotes different elements. Algorithms that take views and/or iterators typically take them by value.
(snip)

https://github.com/ericniebler/range-v3/issues/385#issuecomment-290164218

関連URL

*1:C++20 Rangesライブラリ仕様のベースとされた range-v3 ライブラリでは、要素に対してconst修飾を行う ranges::views::const_ アダプタが提供される。C++20現在の標準ライブラリでは同等機能は提供されない。P2214R0 A Plan for C++23 Ranges によれば将来的に採用される可能性があるが、低優先度 Tier 3 グループに区分されている。

*2:関数テンプレート f1 に誤ってコンテナ(View ではない Range)を渡すと、意図せずコンテナ全体がコピーされてしまうリスクがある。本文中サンプルコードのようにテンプレートパラメータを std::ranges::view コンセプトで制約すべき。

Rangeアダプタ std::view::reverse

C++20 Rangesライブラリの逆順ビューstd::ranges::reverse_viewおよびRangeアダプタstd::views::reverse*1についてメモ。

基本の使い方

範囲for構文とRangeアダプタreverseを組み合わせて、配列や文字列やコンテナなどRangeとして扱えるものを逆順に列挙できる。*2 *3

#include <iostream>
#include <map>
#include <string>
#include <string_view>
#include <ranges>
using namespace std::literals;  // ""sv

int a[] = {1, 2, 3, 4, 5};
for (int n: a | std::views::reverse) {
  std::cout << n;  // 54321
}

for (char c: "Hello"sv | std::views::reverse) {
  std::cout << c;  // olleH
}
// 文字列リテラル "Hello" に適用すると終端NUL文字を含む6文字が
// '\0', 'o', 'l', 'l', 'e', 'H' 順で列挙されることに注意。

std::map<int, std::string> m = {{1, "apple"}, {2, "banana"}, {3, "cinnamon"}};
for (const auto& [k, v]: m | std::views::reverse) {
  std::cout << k << ":" << v << '\n';
  // 3:cinnammon
  // 2:banana
  // 1:apple
}

対象を逆順走査するには、そのイテレータが双方向(bidirectional)走査可能である必要がある。例えば単方向リストstd::forward_listイテレータは双方向走査をサポートしないため、reverseと組み合わせるとコンパイルエラーとなる。膨大なエラーメッセージと共に_(:3 」∠)_*4

#include <forward_list>
#include <ranges>

std::forward_list lst = {1, 2, 3, 4, 5};
// std::forward_list は forward_range だが bidirectional_range ではない
static_assert( !std::ranges::bidirectional_range<decltype(lst)> );

for (int n: lst | std::views::reverse) {  // NG: ill-formed
  // ...
}

応用例

Range分割アダプタstd::views::splitの適用後は Forward Range となり、下記コードのように直接reverseと組み合わせてもコンパイルエラーになる。これはC++20 Rangesライブラリは遅延(lazy)評価戦略をとるため、分割処理が前方向(forward)にのみ行われることに起因する。

#include <iostream>
#include <string_view>
#include <ranges>

std::string_view str = "apple,banana,cinnamon";

// NG: カンマ(,)区切りで分割後にアイテム名を逆順表示
for (auto item: str | std::views::split(',') | std::views::reverse) {  // ill-formed
  std::cout << item << '\n';
}

次期C++2b(C++23)向けの提案文書P2210R2は欠陥修正としてC++20へも遡及適用されるため、C++20標準ライブラリ+P2210R2適用済みであれば下記コードで所望の動作となる*5。さらにC++2b標準ライブラリであれば、式(分割後subrange) | std::views::reverseからstd::string_viewを直接構築できるようになる。(→id:yohhoy:20210624

// C++20 + P2210R2
// OK: カンマ(,)区切りで分割後にアイテム名を逆順表示
for (auto rev_item: str | std::views::reverse | std::views::split(',')) {
  // rev_itemは nomannic, ananab, elppa と列挙されるため
  // 個別にreverseを適用して元の文字並び順に復元する
  auto item = rev_item | std::views::reverse;
  // coutストリーム出力を行うには部分範囲itemの型
  // subrange<const char*, const char*, subrange_kind::sized>
  // から文字列型std::stringへの明示変換が必要となる
  std::cout << std::string{item.begin(), item.end()} << '\n';
}
// cinnamon
// banana
// apple
// C++2b(C++23)
// OK: カンマ(,)区切りで分割後にアイテム名を逆順表示
for (auto rev_item: str | std::views::reverse | std::views::split(',')) {
  std::cout << std::string_view{rev_item | std::views::reverse} << '\n';
}

// OK: カンマ分割結果を逆順にstring_view化するRangeアダプタ
auto split_reverse =
  std::views::reverse
  | std::views::split(',')
  | std::views::transform([](auto rv){
    return std::string_view{rv | std::views::reverse};
  });
for (auto item: str | split_reverse) {
  std::cout << item << '\n';
}

C++20 24.7.14.1/p1-2より引用。

1 reverse_view takes a bidirectional view and produces another view that iterates the same elements in reverse order.
2 The name views::reverse denotes a range adaptor object (24.7.1). Given a subexpression E, the expression views::reverse(E) is expression-equivalent to:

  • If the type of E is a (possibly cv-qualified) specialization of reverse_view, equivalent to E.base().
  • Otherwise, if the type of E is cv-qualified
    subrange<reverse_iterator<I>, reverse_iterator<I>, K>
    for some iterator type I and value K of type subrange_kind,
    • if K is subrange_kind::sized, equivalent to:
      subrange<I, I, K>(E.end().base(), E.begin().base(), E.size())
    • otherwise, equivalent to:
      subrange<I, I, K>(E.end().base(), E.begin().base())

  However, in either case E is evaluated only once.

  • Otherwise, equivalent to reverse_view{E}.

関連URL

*1:完全修飾名は std::ranges::views::reverse だが標準ヘッダ<ranges>内で namespace std { namespace views = ranges::views; } と宣言されており、std::views::reverse とも記述できる。

*2:厳密には View として扱えるものを対象とする。View は Range の一種であり、コピー/ムーブ操作や破棄操作を定数時間で行えるものが View と定義される(C++20 24.4.4)。両者には構文上の差異がないため、ユーザ定義型向けのカスタマイズポイントとして変数テンプレート std::range::enable_view<T> が提供される。

*3:例示コードではRangeアダプタ適用によるテンプレートクラス型推論過程で int[5] は std::ranges::ref_view<int [5]> へ、std::map<int, std::string> は std::ranges::ref_view<std::map<int, std::string>> へと View に自動変換されている。2例目の std::basic_string_view は字面通りそのまま View とみなされる。仮に std::string とした場合は std::ranges::ref_view<std::string> へ変換される。

*4:https://gist.github.com/yohhoy/4ff16f93d62e35be3788c5cdca5858d0

*5:R2210R2修正前の場合、split適用後の内部イテレータは Forward Iterator となりそのままでは逆順走査を行えない。一旦バッファリングしてから文字列反転させる必要がある。実装例:https://gist.github.com/yohhoy/5f104e6d3aee2b3e927419664abf63af

std::views::splitで文字列分割 @ C++23

次期C++2b(C++23) Rangesライブラリstd::views::splitstd::string_viewを利用した文字列分割処理。

C++標準ライブラリのアップデートによりC++20時点よりシンプルに記述可能となり、またstd::stringを介さないため実行効率改善も見込める。

// C++2b(C++23)
#include <iomanip>
#include <iostream>
#include <string_view>
#include <ranges>

int main() {
  std::string_view s = "apple,banana,cinnamon";
  for (std::string_view word : s | std::views::split(',')) {
    std::cout << std::quoted(word) << "\n";
  }
}
// "apple"
// "banana"
// "cinnamon"

split2str関数は「char範囲を区切り文字delimで分割しstd::stringのViewへ変換するレンジアダプタ(range adaptor)」を返す。

// C++20(一部抜粋)
auto split2str(char delim) {
  return std::views::split(std::views::single(delim))
       | std::views::transform([](auto v) {
           auto cv = v | std::views::common;
           return std::string{cv.begin(), cv.end()};
         });
}

std::string_view s = "apple,banana,cinnamon";
for (const auto& word : s | split2str(',')) {
  std::cout << std::quoted(word) << "\n";
}
std::views::splitで文字列分割 - yohhoyの日記

これらは、C++2b標準ライブラリのRangeライブラリ仕様変更とへの小さな機能追加により実現される。前者P2210R2は仕様欠陥扱いとされ、C++20に対しても遡及適用される。

  • P2210R2std::views::split仕様修正により、Rangeカテゴリが引き継がれる。これによりsplit分割後の要素=内部Rangeが、入力Rangeカテゴリを引き継いでContiguous Rangeとみなされる。
  • (PDF)P1989R2std::string_viewにRange版コンストラクタが追加される。これによりsplit分割後の内部Rangeから直接std::string_viewへと変換可能となる。

提案文書P2210R2 §4.Proposalより一部引用(下線部は強調)。

Introduce a new range adapter under the name views::split / ranges::split_view with the following design:

  • a. It can only support splitting forward-or-better ranges.
  • b. Splitting a V will yield subrange<iterator_t<V>>s, ensuring that the adapted range's category is preserved. Splitting a bidirectional range gives out bidirectional subranges. Spltiting a contiguous range gives out contiguous subranges.
  • c. views::split will not be const-iterable.

This could certainly break some C++20 code. But I would argue that views::split is so unergonomic for its most common intended use-case that the benefit of making it actually usable for that case far outweighs the cost of potentially breaking some code (which itself is likely to be small given both the usability issues and lack of implementations thus far).

P2210R2 Superior String Splitting

関連URL