C++魔術回路構成法

はじめに

これはC++ Advent Calendar 2017の25日目の記事です。
皆さん、C++は好きですか？
僕は好きではありません。

愛　し　て　ま　す　！

C++魔術回路って？

C++ってちょっと凝ったことするときにどういう風にすれば実現できるのか。
そういった黒魔術を書くときに使うテクニックを僕は C++魔術回路 と呼んでます。
まあ、普段使いできる程度に簡単なテクニックだと思います。

オーバーロード魔術回路

基礎テクニック。
テンプレートに型制約をもたせ、またそれを利用しオーバーロードを呼び分ける。
ところでオーバーロードってなんかカッコイイ響きだよねぇ。

SFINAE

特定の操作が可能な型を引数にとるということが可能である。C++11からの仕様。
テンプレートが実体化に失敗してもエラーにならず別のオーバーロードを探してくれる仕様になっており、これを利用してオーバーロード解決順序を操ることが可能。

enable_ifによるSFINAE

enable_if<B, T>

はBがtrueの場合実体化に成功し、Tになる。
Bがfalseの場合は実体化に失敗する。
第2テンプレート引数のTはデフォルトでvoidになっており、省略できる。
SFINAEを使ったテンプレートの制限において乱舞することになる。

// 引数が整数型の場合実体化に成功し、返り値がvoidになる
template < class T >
std::enable_if_t<std::is_integral<T>::value> func(T i){
    std::cout << "T is integral" << std::endl;
}

decltypeによるSFINAE

decltypeはSFINAEで考慮される、decltypeの推論に失敗しても即座にエラーにならず別のオーバーロードを探してくれる。

以下のように書いた場合、decltypeの中身が成功した場合にオーバーロード解決に成功することになる。

template < class T>
auto func(T&& range)
 -> decltype(std::begin(range), std::end(range), true)
{
  for(auto itme: range){
     // std::begin, std::endが有効なのでレンジ回せるかなぁみたいな
  }
  return false;
}

オーバーロード解決の順序について

SFINAEはインスタンス化に失敗したテンプレートをoverload condidatesから除外してくれる程度の仕様なので、オーバーロードに優先順位をつけてはくれない。
一つのテンプレートが実体化に成功するとき、他のテンプレートが実体化に失敗しなければならない。

以下の様な場合、より強い型制約を持つ下の関数が優先されてほしいものだが、そうはならない。

#include <iostream>
#include <cstdlib>
#include <type_trais>

template < class T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr >
void func(T&&) { std::cout << "unsigned integral" << std::endl; }

template < class T, std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>,td::nullptr_t> = nullptr >
void func(T&&) { std::cout << "signed integral" << std::endl; }


int main()
{
    func(1);  // Error: func is ambiguous
    func(1u); // ok
}

以下のようにどちらかがインスタンス化に失敗するように書くのが正しい。

#include <iostream>
#include <cstdlib>
#include <type_traits>

// && std::is_unsinged_v<T> を追加
template < class T, std::enable_if_t<std::is_integral_v<T> && std::is_unsinged_v<T>, std::nullptr_t> = nullptr >
void func(T&&) { std::cout << "unsinged integral" << std::endl; }

template < class T, std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>, std::nullptr_t> = nullptr >
void func(T&&) { std::cout << "signed integral" << std::endl; }


int main()
{
    func(1);  // ok
    func(1u); // ok
}

SFINAEを使ったオーバーロードのつらさは、ある型で関数をインスタンス化したときオーバーロードに成功する関数テンプレートが複数ないように考えるというプロセスによると思う。
さらに恐ろしいことは、この永遠に玄人しか使いこなせないような機能がC++ではある状況下では使わないとやってられないような状態にあり、そのような状況化で書かれたコードを見ればオーバーロードが乱舞しているということだ。

##SFINAEの必要に迫られる場面

僕の経験上、SFINAEの必要性の根源の一つはForwarding Referenceを引数にもつ関数テンプレートのオーバーロードを書くことからきている。
以下のような関数テンプレートである。
**T&&**型を使ったことがなければわからないかもしれないが、実に多くの呼び出しでこの関数テンプレートがoverload candidatesになる。

template < class T >
void func(T&& x){
   // ...
   other_func(std::forward<T>(x));
}

このようなオーバーロードを書く理由は完全転送したいからである。
完全転送の必要がないなら書くべきではない。
このようなジェネリックすぎの引数を含む関数テンプレートはSFINAEで制限を加えておかないと2000%意図しない呼び出しに頭を悩ませる。

もう一つは特定の性質を満たした型だけをアクセプトしたいという要求から来る必要性だ。
これはもっともな理由で、range-based forに突っ込める型を引数に取りたいとかそういうやつだ。
だいたいはC++にコンセプトが入らんかったから仕方のない感じでかかれている。

##まったく同じ文法（関数）を型によって呼び分けたいとき

処理内容がガラッと変わるような場合はSFINAEの出番がある。
最適化にもSFINAEが出張る。

ここでは最適化ではなく、ちょっと違った例をあげたいと思う。

コンテナに対する処理の遅延と終端処理の呼び出しによる遅延評価をやってみる。
基本的なアイデアとして、コンテナに適用する操作を関数オブジェクトにして、タグ型で呼び分けを行う。
評価の遅延はラムダ式でラップすることで行う。
終端評価が呼ばれた時点でラムダ式を再帰的に呼び出して操作済みのコンテナを取り出す。

さて、operator|をSFIANEでじゃんじゃんオーバーロードしていくか。

#include <iostream>
#include <algorithm>
#include <vector>
#include "concept.hpp"

namespace examples {
    
namespace concept = cranberries::experimental::concepts;
    
struct Reverse {
    using lazy = void;
    template < class Traversable,
        concept::concept_required<std::decay_t<Traversable>, concept::iterable> = nullptr >
    decltype(auto) operator()(Traversable&& trv) const {
        using std::begin; using std::end;
        std::reverse(begin(trv), end(trv));
        return std::forward<Traversable>(trv);
    }
};
    
template < class F >
struct ForEach {
    F f;
    using eager = void;
    
    template < class Traversable,
        concept::concept_required<std::decay_t<Traversable>, concept::iterable> = nullptr >
    void operator()(Traversable&& trv) const {
        for(auto&& item: trv){
            f(item);
        }
    }
};
    
template < class Traversable, class Operation,
    std::enable_if_t<concept::required_v<Traversable, concept::iterable>, std::nullptr_t> = nullptr,
    std::enable_if_t<std::is_same<typename std::decay_t<Operation>::lazy,void>::value,std::nullptr_t> = nullptr >
decltype(auto) operator| (Traversable&& trv, Operation&& op){
    return [t = std::forward_as_tuple(std::forward<Traversable>(trv), std::forward<Operation>(op))]{
        return std::get<1>(t)(std::get<0>(t));
    };
}

template < class Traversable, class Operation,
    std::enable_if_t<!concept::required_v<Traversable, concept::iterable>, std::nullptr_t> = nullptr,
    std::enable_if_t<std::is_same<typename std::decay_t<Operation>::lazy,void>::value,std::nullptr_t> = nullptr >
decltype(auto) operator| (Traversable&& trv, Operation&& op){
    return [t = std::forward_as_tuple(std::forward<Traversable>(trv), std::forward<Operation>(op))]{
        return std::get<1>(t)(std::get<0>(t)());
    };
}

template < class Traversable, class Operation,
    std::enable_if_t<std::is_same<typename std::decay_t<Operation>::eager,void>::value,std::nullptr_t> = nullptr >
decltype(auto) operator| (Traversable&& trv, Operation&& op){
    return std::forward<Operation>(op)(std::forward<Traversable>(trv)());
}
    
    
namespace lazy {
    constexpr Reverse reverse{};
}
    
namespace eager {
    template < class F >
    ForEach<F> for_each(F&& f) { return {std::forward<F>(f)}; }
}

}
int main(){
    
    
    using namespace examples;
    
    {
        std::vector<int> vec{1,2,3,4,5};
        vec | lazy::reverse; // 終端処理を呼ぶまで評価されない
        for(auto const& e: vec) std::cout << e << std::endl; // そのまま
    }
    std::cout << std::endl;
    
    {
        std::vector<int> vec{1,2,3,4,5};
        // 終端処理が呼ばれているのでreverseが評価される
        vec | lazy::reverse
            | eager::for_each([](auto&& e) { std::cout << e << std::endl; })
        ;
    }
}

output

1
2
3
4
5

5
4
3
2
1

このようにoperator|を呼び分けるということも可能である。
説明なしに様々な技巧を使った可能性もあるが、説明を書いている時間がない。

これはC++14の範囲内で書かれている。
自分が作っているCranberries Libraryがガッツリ使われているが許してほしい。

##C++17 if constexpr

詳しいことは説明しないが、C++17で導入されたif constexprという機能のおかげでSFINAEによるオーバーロードの乱舞は半分姿を消す。
しかし、依存bool式というテクニックを用いる用いる必要があるようだ。

##C++2a Concept

C++11のときに提案されたConcept Map付きのフルのConceptはドラフト入りの状態で最終局面を迎え、そしてリジェクトされた。
結果、C++0xは200x年にでる予定だったのにConceptの削除で丸一年かかり、そこからConceptにの抜けた穴を埋めるために1年。
その間、C++0xの0xは16進数を表すとの冗談がC++界隈で流行した。
C++14でConcept Mapをなくし軽量化したConcept Liteという提案がされるも、マイナーアップデートなので大幅な修正はしないとリジェクト。
C++17でgccが実験的実装を行い、しれっとTechnical Specificationに入るも、gccの実装経験からもうちょっと推敲してから入れるべきではとの意見が発生し、リジェクト。
現在C++2aのドラフトに入っているらしい。

これも詳しいことは述べない。
C++2aでドラフト入りしている機能である制約とコンセプト的なやつ。
おそらくSFINAEは表面的にはほぼ姿を消し、コンパイラが生成するような時代になるのだろう（適当
そして、オーバーロード優先順位がつくようになる。

C++ Advent Calendar 2017 10日目に都合の良い記事が存在するので読むといい。
制約とコンセプトとオーバーロードと半順序

#インデックスシーケンス魔術回路

##Variadic Templates

Variadic Templatesとは可変長の引数をとれるテンプレートである。
これの基本、または応用に関してはC++のパラメータパック基礎&パック展開テクニックでかなり詳細に解説しているのでそちらを参考にした方がいい。
この記事ではindex tuple魔術回路の構成法について特に解説する。

##Swallow Idiom（序論）

C++では可変長テンプレートを展開した上で関数などを適用できるパック展開の拡張という機能があるのだが、展開後の評価順序という難題がある。

f(g(args)...);

のように関数の中に展開すると、関数の引数の評価順序が規定されていないこと
によりg(args)...の評価順序が実装依存になってしまう。
順番に評価してほしい場合には困る。

C++14まででは、評価順序が定まったまともに展開できる場所が初期化子しかない。
そこでinitializer_listに次のように展開する。

(void)std::initializer_list<int>{ (void(g(args)),0)... };

initializer_listではなんか初期化子リストを使っているように見えるし
型別名をつけてそれっぽくする。
Swallow Idiomと呼ばれるテクニックである。
これで可変長引数の左から右に順番にgが適用されることが保証される。

using swallow = std::initializer_list<int>;
(void)swallow{ (void(g(args)),0)... };

###(void)swallow{ (void(g(args)),0)... }; の解説

####最初の(void)

swallow自体は使われない。
そのままだとDiscardされるのでコンパイラが警告を出す。
(void)でキャストすると警告を抑制できる。
最初の(void)は単にSuprress Warningである。

####void(g(args))

関数の戻り値が使われることもないのでvoid()で囲ってます。

####,0

これはカンマ演算子です。

x, y;

と書いたとき、xが評価され（副作用が発生）、次にyが評価されてyが返ります。

void(g(args)),0

とすれば、g(args)が評価されたあと0が返ります。

####(void(g(args)),0)...

一番外側の（）単位でパック展開されますので

(void(g(args)),0)

swallowの初期化子に展開されることになります。

引数の左側から順番にg(args)を評価しますが、結果は使用せずにカンマ演算子で0をinitializer_listに展開しています。
関数の副作用だけが残ります。

###すごくどうでもいいコード例

パック展開を入れ子にすると多重for文みたいなことができる（もはや何がやりたいのやら……

#include <iostream>
#include <utility>
#include <tuple>
#include <initializer_list>

template < size_t... I, size_t... J >
void test_(std::index_sequence<I...>,std::index_sequence<J...>){
    using swallow = std::initializer_list<int>;
    (void)swallow{
        (void( [N = sizeof...(I)](auto j){
            swallow{ (void( [&](auto i){ std::cout << i + j*N << " "; }(I) ), 0)... };
            std::cout << std::endl;
        }(J) ),0)... 
    };
}

template < size_t I, size_t J >
void test() { test_(std::make_index_sequence<I>{}, std::make_index_sequence<J>{}); }

int main(){
    test<10,4>();
}

output

0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 

実行結果｜Wandbox

##index_sequenceとtuple

index_sequenceの利用は、主にtupleの展開にあると思う。

###Index Tuple Idiom

index tupleのモチベーションはtupleを展開して渡したいというとき

tuple<int,char,long> t(1,1,1);
some_func(std::get<0>(t),std::get<1>(t),std::get<2>(t));

のように手動で展開するのは馬鹿らしいという事実による。

index_sequence<0,1,2>のようにインデックスをテンプレートに含むクラスを作り
以下のようにVariadic Templatesで推論することでパック展開の拡張でtupleを展開できるというのがindex tupleのアイデアである。

template < class Tuple, size_t... Indices >
void helper(Tuple&& t, index_sequence<Indices...>){
    some_func(std::get<I>(std::forward<Tuple>(t))...);
}
tuple<int,char,long> t(1,1,1);
helper(t, std::index_sequence<0,1,2>{})

このように関数にtupleを分解して渡す関数applyがC++17で入った。

std::apply(
    [](auto a, auto b, auto c){ std::cout << a << b << c; },
    std::make_tuple(1,"1", 1u)
);
// 111

N個のインデックスのシーケンスを作るヘルパクラスがあるので

std::make_index_sequence<100>{}

とかするとstd::index_sequence<0,1,2, ... ,99>が出来上がる。

これにより、可変長引数をTupleにパッキングしてあとでアンパッキングじゃーとかできるのである。

これが威力を発揮するのは、複数の値を別々の関数（やコンストラクタ）に転送したい場合だ。

#include <tuple>
#include <utility>
#include <iostream>
#include <initializer_list>

namespace cranberries {
namespace cranberries_magic {

template <class F, class Tuple, std::size_t... I>
constexpr decltype(auto) apply_impl( F&& f, Tuple&& t, std::index_sequence<I...> )
{
  return f(std::get<I>(t)...);
}

} // ! namespace cranberries_magic

template <class F, class Tuple>
constexpr decltype(auto) apply(F&& f, Tuple&& t)
{
  return cranberries_magic::apply_impl(std::forward<F>(f), std::forward<Tuple>(t),
    std::make_index_sequence<std::tuple_size<std::decay_t<Tuple>>::value>{});
}

} // ! namespace cranberries

template < typename T >
void print(T const& a){
  std::cout << " " <<  a;
}

template < typename... Args >
void f(Args... args) {
  std::cout << "called f with :";
  using swallow = std::initializer_list<int>;
  (void)swallow{ (void( print(args) ), 0)... };
  std::cout << std::endl;
}
template < typename... Args >
void g(Args... args) {
  std::cout << "called g with :";
  using swallow = std::initializer_list<int>;
  (void)swallow{ (void( print(args) ), 0)... };
  std::cout << std::endl;
}

// 引数を2個のtupleにわけてわたす
template < typename... Left, typename... Right >
void ok( std::tuple<Left...> largs, std::tuple<Right...> rargs){
  // tupleの要素を関数に展開するためにapply関数をつかう
  // もっとちゃんとしたものがC++17に採択決定している
  cranberries::apply([](auto... args){ f(args...); }, largs);
  cranberries::apply([](auto... args){ g(args...); }, rargs);
}

int main(){
    // forward_as_tupleで引数を完全転送
    ok( std::forward_as_tuple( 1,2,3 ),
        std::forward_as_tuple( 4,5,6 ) );
}

可変長引数をtupleに固めてから分解するということはあったりなかったりするので、結構使ったり使わなかったりする。

##コード例を書くのが面倒だからgithubのリンク貼っとく

自分史上最もパック展開とインデックスシーケンスを乱舞させたライブラリ
Cranberries.FunctionUtility
を書いたときに一生分パック展開したので参考に……しないほうが良いかもしれないね……

このライブラリが一体何をするものなのかはWikiやブログを読むとわかる可能性もあります。

C++17 Fold Expression

C++17で入ったFold Expressionを使えばいつでもどこでもパック展開できる。
（しかも、C++17からusing宣言でパック展開できるようにもなった）。

template < class... Pack >
void func(Pack... pack){
    // ...
}

のような、パックがあったとして
Fold Expressionで展開する方法はおおよそ次の種類がある。
Fold Expressionは()で囲まれている必要がある。
opは二項演算子である。

( pack op ... )             //(1)
( ... op pack )             //(2)
( pack op ... op init )     //(3)
( init op ... op pack )     //(4)

(1)は右畳み込みで

(E + ...)

と書くと

E_1 + (... + (E_{N-1} + E_N))

のように展開される。

(2)は左畳み込み

(... + E)

と書くと

(((E_1 + E_2) + E_3 ) + ... ) + E_n

のように展開される。

(3)と(4)はそれぞれ(1)と(2)に初期値を与えたバージョンである。

これを使えば
いままで再帰や

auto old_sum1(){
    return 0;
}

template<typename T1, typename... T>
auto old_sum1(T1 s, T... ts){
    return s + old_sum1(ts...);
}

パック展開の魔術回路で

template < typename T, typename... Tail >
constexpr T old_sum2( T&& head, Tail&&... tail ){
  T result = head;
  using swallow = std::initializer_list<int>;
  (void)swallow{ (void(result += tail),0)... };
  return result;
}

などと書いていた関数は
以下のようにダイレクトに書ける。

template<typename... T>
auto fold_sum_1(T... s){
    return (... + s);
}

または初期値付きで
このように書くことができる。

template<typename... T>
auto fold_sum_2(T... s){
    return (1 + ... + s);
}

使用可能な二項演算子は決まっていて
以下が使える。
要するにオーバーロードしたらなんでもできそうだ（雑

+ - * / % ^ & | = < > << >> += -= *= /= %= ^= &= |= <<= >>= == != <= >= && || , .* ->*

#禁断のマクロ魔術回路

書こうと思ったのですが、魔黒を拡散させるのはダメなのではないかという意見もあり自粛します。

#まとめ

複雑なコードの利用は計画的に。
C++17でましになる部分も多そうだ。
さっさとC++14以下は滅んでほしい。