std::views::commonレンジアダプタの制約

C++20 RangeからC++17互換イテレータペアへの変換にはstd::views::commonレンジアダプタ(range adaptor)を利用する。ただしstd::ranges::basic_istream_viewなどムーブのみ／コピー不可なイテレータからなる一部Rangeは変換できない。*1

#include <sstream>
#include <ranges>
#include <vector>

auto ints = std::istringstream{"0 1 2 3 4"};
auto cv = std::ranges::istream_view<int>(ints)
        | std::views::filter([](int n){ return n % 2 == 0; })
        | std::views::common;  // NG: ill-formed
std::vector<int> vec(cv.begin(), cv.end());

これはstd::ranges::common_view<V>クラステンプレート制約として、対象Viewのイテレータ型(iterator_t<V>)がstd::copyableコンセプトを満たすことを要求するため。C++17互換イテレータではコピー可能・ムーブ可能を要求するが、C++20 Rangeを構成するイテレータはコピー不可・ムーブ可能であればよい。*2

前掲コードのようにRange／Viewからコンテナへ変換したい場合、次期C++2b(C++23)標準ライブラリではstd::views::toレンジアダプタ（→id:yohhoy:20210902）が利用可能となる。

// C++2b(C++23)
#include <sstream>
#include <ranges>
#include <vector>

auto ints = std::istringstream{"0 1 2 3 4"};
auto vec = std::ranges::istream_view<int>(ints)
         | std::views::filter([](int n){ return n % 2 == 0; })
         | std::views::to<std::vector>();
// vec == std::vector<int>{0, 2, 4}

C++20 24.6.4.3, 24.7.13.1, 24.7.13.2より一部引用。

namespace std::ranges {
  template<movable Val, class CharT, class Traits>
    requires default_initializable<Val> &&
             stream-extractable<Val, CharT, Traits>
  class basic_istream_view<Val, CharT, Traits>::iterator {
  public:
    // (snip)
    iterator(const iterator&) = delete;
    iterator(iterator&&) = default;
    iterator& operator=(const iterator&) = delete;
    iterator& operator=(iterator&&) = default;
    // (snip)
  };
}

1 common_view takes a view which has different types for its iterator and sentinel and turns it into a view of the same elements with an iterator and sentinel of the same type.
2 [Note: common_view is useful for calling legacy algorithms that expect a range's iterator and sentinel types to be the same. --end note]
3 The name views::common denotes a range adaptor object (24.7.1). (snip)

namespace std::ranges {
  template<view V>
    requires (!common_range<V> && copyable<iterator_t<V>>)
  class common_view : public view_interface<common_view<V>> {
    // (snip)
  };
}

関連URL

• c++ - How can I collect an istream_view into a container? - Stack Overflow
• ［C++］ C++17イテレータ <=> C++20イテレータ != 0 - 地面を見下ろす少年の足蹴にされる私
• cppreference: std::ranges::common_view, cpprefjp: std::ranges::common_view
• https://twitter.com/yohhoy/status/1316652888416874497

*1:std::ranges::istream_view<Val> は std::ranges::basic_istream_view<Val, char> のエイリアステンプレート。(PDF)P2432R1によりC++20 DRとして遡及適用。

*2:現行gcc/libstdc++は難解なエラーメッセージを生成する https://wandbox.org/permlink/qu5Hl1Lbj6fdhQot

コンセプト定義への属性指定

C++20言語仕様では、コンセプト定義に対して属性(attribute)を指定できない。

template <typename T>
[[deprecated("concept")]]  // NG: ill-formed
concept C = /*...*/;

// OK: 変数テンプレート
template <typename T>
[[deprecated("variable")]]
T var = /*...*/;

// OK: 関数テンプレート
template <typename T>
[[deprecated("function")]]
void func(T) { /*...*/ }

// OK: クラステンプレート
template <typename T>
class [[deprecated("class")]] S0 { /*...*/ };

// OK: エイリアステンプレート
template <typename T> struct S1 {};
template <typename T>
using A [[deprecated("alias")]] = S1<T>;

メモ：エイリアステンプレート(alias template)に対するdeprecated属性指定は、GCC／Clangともに機能しない模様… MSVCは期待通り警告C4996が報告される。

• https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93607
• https://bugs.llvm.org/show_bug.cgi?id=17862

C++20 13.1/p1, 13.7.8/p1より一部引用。

1 A template defines a family of classes, functions, or variables, an alias for a family of types, or a concept.

template-declaration:
　　template-head declaration
　　template-head concept-definition
template-head:
　　template < template-parameter-list > requires-clause_opt
template-parameter-list:
　　template-parameter
　　template-parameter-list , template-parameter
requires-clause:
　　requires constraint-logical-or-expression
(snip)

1 A concept is a template that defines constraints on its template arguments.

concept-definition:
　　concept concept-name = constraint-expression ;
(snip)

関連URL

• https://www.reddit.com/r/cpp/comments/sh20ya/c20_concept_deprecate_use/
• C++ Standard Core Language Active Issues, 2428. Deprecating a concept

クラステンプレート特殊化型判定

プログラミング言語C++において、与えられた型があるクラステンプレートの特殊化(specialization)か否かを判定する方法。

下記コードは複素数std::complexの特殊化か否かを判定するメタ関数およびコンセプト実装例。

// C++11/14/17: is_complexメタ関数
#include <complex>
#include <type_traits>

template <typename T>
struct is_complex : std::false_type {};
template <typename T>
struct is_complex<std::complex<T>> : std::true_type {};

static_assert( is_complex<std::complex<float>>::value );
static_assert( !is_complex<double>::value );

// C++20: is_complexコンセプト
#include <concepts>
#include <complex>

template <typename T>
concept is_complex = requires (T t) {
  { std::complex{std::move(t)} } -> std::same_as<T>;
  // ムーブのみ可能な型を考慮してrvalueへキャスト
  // コピー可能な型では単にt（lvalue）記述でもよい
};

static_assert( is_complex<std::complex<float>> );
static_assert( !is_complex<double> );

メタ関数バージョンは非型テンプレートパラメータ(non-type template parameter)を含むクラステンプレート（例：std::array, std::span）には利用できない。コンセプトバージョンはコピー／ムーブ不可のクラステンプレート（例：std::atomic, std::counting_semaphore）には利用できない。

関連URL

• (PDF) P2098R1 Proposing std::is_specialization_of *1
• C++ Concepts: checking for template instantiation - Stack Overflow
• ［C++］WG21月次提案文書を眺める（2020年4月） - 地面を見下ろす少年の足蹴にされる私

*1:提案 P2098R1 は2020年5月会合で棄却済み。https://github.com/cplusplus/papers/issues/812 参照。

Math.min＠浮動小数点数の実装

Java標準ライブラリMath.minメソッドの実装についてメモ。

浮動小数点数型(float, double)に対するminでは、NaN(Not a Number)および負のゼロ(-0.0)を考慮する必要がある。*1

public static double min(double a, double b) {
  if (a != a)
    return a;   // a is NaN
  if ((a == 0.0d) && (b == 0.0d)
      && (Double.doubleToRawLongBits(b) == negativeZeroDoubleBits)) {
    // Raw conversion ok since NaN can't map to -0.0.
    return b;
  }
  return (a <= b) ? a : b;
}

// Use raw bit-wise conversions on guaranteed non-NaN arguments.
private static final long negativeZeroDoubleBits
  = Double.doubleToRawLongBits(-0.0d);

2つのdouble値のうち小さいほうを返します。 つまり、結果は負の無限大に近いほうの値となります。 引数の値が同じ場合は同じ値を返します。 どちらかの値がNaNの場合はNaNを返します。 数値比較演算子とは異なり、このメソッドは負のゼロが厳密には正のゼロよりも小さいと見なします。 一方の引数が正のゼロでもう一方が負のゼロの場合は、負のゼロを返します。

https://docs.oracle.com/javase/jp/10/docs/api/java/lang/Math.html#min(double,double)

一方、整数型(int, long)に対するminは比較演算<=を用いてシンプルに実装される。*2

public static int min(int a, int b) {
  return (a <= b) ? a : b;
}

関連URL

• floating point - Why is Java's double/float Math.min() implemented this way? - Stack Overflow
• C++ min/maxアルゴリズムの正しい実装 - yohhoyの日記

*1:https://github.com/openjdk/jdk/blob/jdk-10%2B46/src/java.base/share/classes/java/lang/Math.java#L1556-L1580

*2:https://github.com/openjdk/jdk/blob/jdk-10%2B46/src/java.base/share/classes/java/lang/Math.java#L1501-L1514

C++ min/maxアルゴリズムの正しい実装

C++標準ライブラリstd::min, std::maxアルゴリズムの動作仕様についてメモ。
問題：C++ min/maxアルゴリズムを「正しく」実装せよ。

template <typename T>
const T& min(const T& a, const T& b)
{
  // どちらのmin実装が正しい？
  return a < b ? a : b;  // #1
  return b < a ? b : a;  // #2
}

template <typename T>
const T& max(const T& a, const T& b)
{
  // どちらのmax実装が正しい？
  return a < b ? b : a;  // #3
  return b < a ? a : b;  // #4
}

答え：#2 と #3

2個の値を比較するmin/maxアルゴリズムでは、値が等価(equivalent)*1なときは1番目の値を返すと規定されている。実装#1や#4ではC++標準ライブラリの仕様違反となる。C++03 25.3.7/p2-3, p5-6より引用。

template<class T> const T& min(const T& a, const T& b);
template<class T, class Compare>
  const T& min(const T& a, const T& b, Compare comp);

2 Returns: The smaller value.
3 Remarks: Returns the first argument when the arguments are equivalent.

template<class T> const T& max(const T& a, const T& b);
template<class T, class Compare>
  const T& max(const T& a, const T& b, Compare comp);

5 Returns: The larger value.
6 Remarks: Returns the first argument when the arguments are equivalent.

関連URL

• c++ - Why use “b < a ? a : b” instead of “a < b ? b : a” to implement max template? - Stack Overflow
• (PDF) Alexander Stepanov, Notes on Programming

*1:C++標準ライブラリでは a < b が偽かつ b < a が偽のとき、a と b は等価(equivalent)とみなす。

move in accumulateアルゴリズム

C++20標準ヘッダ<numeric>のstd::accumulateアルゴリズム内部実装では、T型のアキュムレータ変数(acc)への累積操作時にstd::move関数適用（右辺値への変換）が規定される。

// C++20仕様の累積演算（1要素あたり）
acc = std::move(acc) + *iterator;
//    ^^^^^^^^^^^^^^
//    右辺値

// C++17仕様の累積演算（1要素あたり）
acc = acc + *iterator;
//    ^^^
//    左辺値

C++17以前の標準ライブラリ仕様では左辺値に対する演算となっていたが、右辺値に変更されたことで（代入右辺の）accオブジェクトに対する破壊的操作が可能となり、より効率的な実装が選択される可能性が広がる。

本ライブラリ仕様変更の提案文書P0616R0では、事前メモリ確保した文字列型に対する累積（連結）操作において大幅な性能改善を報告している。*1

1 Motivation
(snip)

A very simple measurement program showing the difference of using accumulate with strings with or without move show a significant improvement for that case (150 to over 200 times faster with concatenating 10000 short strings, with the additional potential of pre-allocating the whole string size up front when using move). (snip)

同様の改善はinner_product, partial_sum, adjacent_differenceアルゴリズムに対しても適用される。

C++20

C++20 25.10.2/p2より引用（下線部は強調）。

template <class InputIterator, class T>
  constexpr T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  constexpr T accumulate(InputIterator first, InputIterator last, T init, 
                         BinaryOperation binary_op);

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = std::move(acc) + *i or acc = binary_op(std::move(acc), *i) for every iterator i in the range [first, last) in order.

C++17以前

C++17 29.8.2/p2より引用。

template <class InputIterator, class T>
  T accumulate(InputIterator first, InputIterator last, T init);
template <class InputIterator, class T, class BinaryOperation>
  T accumulate(InputIterator first, InputIterator last, T init, 
               BinaryOperation binary_op);

Effects: Computes its result by initializing the accumulator acc with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first, last) in order.

関連URL

• LWG2055. std::move in std::accumulate and other algorithms
• (PDF) P0616R0 de-pessimize legacy <numeric> algorithms with std::move
• c++ - Use of std::move in std::accumulate - Stack Overflow
• cppreference std::accumulate, cpprefjp std::accumulate

*1:https://wandbox.org/permlink/VJuFbbc1hp37a3AM

どうしてstd::basic_iosは否定演算子(!)オーバーロードを提供するの？

C++標準ライブラリのI/Oストリーム基底クラステンプレートstd::basic_iosが否定演算子!オーバーロードを提供する理由。本記事の内容はStackOverflowで見つけた質問と回答に基づく。

答え：歴史的理由

標準化前のC++言語仕様では暗黙の型変換に関する仕様が曖昧であり、operator!演算子オーバーロード以外でI/Oストリームから真偽値へと変換する手段がなかったとのこと。つまりif (!s)のような否定形でしか記述できなかったらしい。

C++03

C++03ではoperator void*ユーザ定義変換が追加提供され、if (s)／if (!s)のいずれの書き方も可能となった。C++03 27.4.4.3/p1より引用。

operator void*() const;

1 Returns: If fail() then a null pointer; otherwise some non-null pointer to indicate success.

bool operator!() const;

2 Returns: fail().

C++11/14/17/20

operator void*ユーザ定義変換にはプログラマの意図とは異なる動作を引き起こすリスク（→id:yohhoy:20120406）があるためC++11にて削除され、代わりに導入されたexplicit operator bool*1によってif (s)表記がサポートされる。また仮にoperator!オーバーロードが提供されなくとも、if (!s)表記でもexplicit operator boolが利用されるようになる。

C++20現在も後方互換性のためoperator!オーバーロードは提供される。C++20 29.5.5.4/p1-2より引用。

explicit operator bool() const;

Returns: !fail().

bool operator!() const;

Returns: fail().

関連URL

• C++ - c++ のクラスで否定演算子!を積極的にオーバーロードする場合はどんな時なのでしょうか？｜teratail
• C++標準I/Oストリームと暗黙型変換の落とし穴 - yohhoyの日記

*1:https://cpprefjp.github.io/lang/cpp11/explicit_conversion_operator.html