C++のrange-based forで複数のコンテナをイテレーションする

C++は健康に良い。C++11で導入されたrange-based forが腱鞘炎の治療に役立つことは世界のどこに行っても変わらない普遍的な事実だ。だが、関節に優しいC++のrange-based forでも出来ないことがある。複数のコンテナのイテレーションだ。これだけは素直にwhile文を書いた方が楽に書ける。

using std::begin, std::end;
int a1[] = {1, 2, 3};
int a2[] = {3, 2, 1};
// while
{
    auto b1 = begin(a1);
    auto b2 = begin(a2);
    while(b1 != end(a1) && b2 != end(a2)) { /* hoge hoge */ ++b1; ++b2; }
}
// range-based for
{
    auto b = begin(a2);
    for(auto&& i1 : a1) {
        auto&& i2 = *b++;
        { /* hoge hoge */ }
    }
}

でも僕だって腱鞘炎は嫌だし、どうせならrange-based forで短いコードを書きたい。そのほうが意図が伝わりやすいからだ。以下のように書くことができれば全人類の腱鞘炎は悉く完治してC++erから新しい腱鞘炎患者が生まれることはないだろう。

int a1[] = {1, 2, 3};
int a2[] = {3, 2, 1};
for(auto[i1, i2] : hoge{a1, a2}) { /* hoge hoge */ }

そういうわけで作った。

github.com

これはコンテナか配列の要素数さえ等しければ如何なるコンテナや配列でも同時にイテレーションできる。

std::vector<int> v1{ 1, 2, 3 };
int v2[] = { 3, 2, 1 };

for (auto [i1, i2] : ouchi::multiitr{ v1, v2 }) {
    assert(i1 + i2 == 4);
}

大学の演習課題を解いている時にあったら便利だなぁと思って今作っただけで、本当は腱鞘炎はどうでもいいし私は腱鞘炎ではない。

wandbox.org

大学生でもわかる！双方向連結リストの実装！

Twitterを見る限り大学2年では双方向リストの実装を課題として課されることが多いようだ。もちろん弊学もその課題がある。ご学友がイテレータやリストへの要素の削除などで苦労していた。別に難しいことはないのでリストの実装を書く。

リストというデータ構造

リストと言うのはそれぞれの要素が隣り合う*1要素へのポインタをもち、シーケンシャルにそれぞれにアクセスできるようなデータ構造だ。図で表すと以下のようなデータ構造を連結リストという。

リストの各要素のつながり

リストの各要素を表現するnode型はユーザーが使いたい型の値へのポインタvalueと次と前の要素へのポインタを持つ。要素数が二つの場合それぞれのnodeは以下のようにリンクする。

nodeだけで実装

nodeを操作する関数だけで要素の追加、削除、移動を実装してみよう。

template<class T>
struct node {
    T* value;
    node* next;
    node* prev;
};

要素の追加

要素を追加するときは追加した前後のnodeのnextメンバとprevメンバを書き換えるとともに、追加したnodeのインスタンスのnextとprevにも前後の要素のポインタを代入しなければならない。

あるnodeのインスタンスの位置に新しいnodeのインスタンスを挿入するためにinsert関数を作成する。

insertのイメージ

挿入した後のポインタの接続

insertでは挿入したい値と、挿入する位置にあるnodeへのポインタを取り、挿入してできた新しいノードへのポインタを返す。特別な場合として、引数のnodeのポインタがnullptrだった時は、新しく一つの要素を持つリストを作ることにしよう。

template<class T>
node<T>* insert(node<T>* pos,  T value) {
    node<T>* fresh = new node<T>;
    fresh->value = new T(value);
    fresh->next = fresh->prev = nullptr;
    if(!pos) return fresh;
    // posがi番目だったとき、新しいnodeをi番目に挿入
    fresh->next = pos;
    fresh->prev = pos->prev;
    // ポインタの付けかえ
    if(pos->prev) pos->prev->next = fresh;
    pos->prev = fresh;
    return fresh;
}

要素の削除

要素を削除するときは、削除する要素の前後のノードのポインタを付け替え、削除する要素をdeleteするだけでよい。削除するノードを指すポインタを受け取るerase関数を作って要素の削除を実装しよう。便利のためerase関数は削除されたノードの次の位置にあったノードへのポインタを返す。

template<class T>
node<T>* erase(node<T>* pos) noexcept {
    auto n = pos->next;
    assert(pos);
    if(pos->next) pos->next->prev = pos->prev;
    if(pos->prev) pos->prev->next = pos->next;
    delete pos->value;
    delete pos;
    return n;
}

要素間の移動

配列と違って、リストの要素間を移動するためには少し面倒な処理をしなければならない。配列ではポインタをインクリメントするだけだったが、リストでは必ずしもメモリ空間上に連続して並んでいるとは限らないので、普通はあるノードを指すポインタにそのノードの次 (前) のノードを指すポインタを代入して移動する。

要素間の移動のイメージ

// posを直接書き換えて見るnodeを変える
template<class T>
void advance(node<T>*& pos, size_t n = 1) noexcept {
    if(!n) return;
    assert(pos);
    pos = pos->next;
    advance(pos, n - 1);
}

// posを直接書き換えて見るnodeを変える
template<class T>
void backward(node<T>*& pos, size_t n = 1) noexcept {
    if(!n) return;
    assert(pos);
    pos = pos->prev;
    backward(pos, n - 1);
}

// posを書き換えずにposのn個あとのnodeを指すポインタを返す
template<class T>
node<T>* next(node<T>* pos, size_t n = 1) noexcept {
    return n ? next(pos->next, n - 1) : pos;
}
// posを書き換えずにposのn個まえのnodeを指すポインタを返す
template<class T>
node<T>* prev(node<T>* pos, size_t n = 1) noexcept {
    return n ? next(pos->prev, n - 1) : pos;
}

---

wandbox.org

今までの関数をクラスにまとめる

関数をクラスにまとめてつながっているノードの全体を一つのリストとしてインスタンス化することができるようになれば便利になる。リストを一つのコンテナとしてイメージしやすくなるからだ。

listクラスのイメージ

listクラスは最初と最後の要素だけを保持する。ユーザーの求めに応じて最初のnodeか最後のnodeを返したり、スコープを外れるときに自動でメモリを解放したりできる*2。せっかくなのでnodeにもコンストラクタとデストラクタを追加してポインタの付け替えやメモリの解放を自動化してみよう*3。

template<class T>
class list{
public:
    struct node{
        node* next;
        node* prev;
        T* value;
        
        node()
            : next {nullptr}
            , prev {nullptr}
            , value{nullptr}
        {}
        node(node* prev, node* next, T* vptr = nullptr)
            : next {next}
            , prev {prev}
            , value{vptr}
        {
            if(next) next->prev = this;
            if(prev) prev->next = this;
        }
        node(node* next, T* vptr)
            : node(next->prev, next, vptr)
        {}
        ~node() {
            if(next) next->prev = prev;
            if(prev) prev->next = next;
            delete value;
        }
    };
    list()
        : first_{new node}
        , last_ {new node}
    {
        first_->next = last_;
        last_->prev = first_;
    }
    ~list() {
        while(first_) first_ = erase(first_);
    }
    
    node* insert(node* pos, T value) {
        auto* fresh = new node(pos, new T(std::move(value)));
        return fresh;
    }
    void push_back(T value) {
        insert(end(), std::move(value));
    }
    node* erase(node* pos) {
        auto n = pos->next;
        delete pos;
        return n;
    }
    node* begin() const noexcept { return first_->next; }
    node* end() const noexcept { return last_; }
    
    
private:
    node* first_;
    node* last_;
};

int main() {
    list<int> l;
    for(auto i = 0; i < 5; ++i)
        l.push_back(i);
    for(auto i = l.begin(); i != l.end(); i = i->next)
        std::cout << *(i->value);
}

イテレータを書く

イテレータを書けばC++の標準ライブラリと同じように扱えるようになる。ここでは先ほど作ったリストにおけるイテレータの簡易的な実装のみをする。

このリストは双方向連結リストなので標準で言うとBidirectionalIteratorが適合する。イテレータのすべての要件を満たすのは大変なので最低限イテレータとして使えるように++演算子、--演算子、*単項演算子、!=演算子のみを定義してみよう。また、イテレータを実装するとnodeの中身をlistの外に公開する必要がなくなるため、nodeやnode*を返す関数はイテレータに置き換えよう。

#include <iostream>
#include <vector>
#include <cstdint>
#include <cassert>

template<class T>
class list{
    struct node{
        node* next;
        node* prev;
        T* value;
        
        node()
            : next {nullptr}
            , prev {nullptr}
            , value{nullptr}
        {}
        node(node* prev, node* next, T* vptr = nullptr)
            : next {next}
            , prev {prev}
            , value{vptr}
        {
            if(next) next->prev = this;
            if(prev) prev->next = this;
        }
        node(node* next, T* vptr)
            : node(next->prev, next, vptr)
        {}
        ~node() {
            if(next) next->prev = prev;
            if(prev) prev->next = next;
            delete value;
        }
    };
public:
    
    class iterator{
        node* node_;
    public:
        friend list;
        /*implicit*/ iterator(node* c)
            : node_{c}
        {}
        iterator()
            : node_{nullptr}
        {}
        
        iterator& operator++() noexcept {
            node_ = node_->next;
            return *this;
        }
        iterator operator++(int) noexcept {
            auto cp = *this;
            ++(*this);
            return cp;
        }
        T& operator*() noexcept {
            return *(node_->value);
        }
        friend bool operator!=(const iterator& a, const iterator& b) noexcept {
            return a.node_ != b.node_;
        }
    };
    
    list()
        : first_{new node}
        , last_ {new node}
        , size_ {0}
    {
        first_->next = last_;
        last_->prev = first_;
    }
    ~list() {
        while(first_) first_ = erase(first_).node_;
    }
    
    iterator insert(iterator pos, T value) {
        auto* fresh = new node(pos.node_, new T(std::move(value)));
        ++size_;
        return iterator{fresh};
    }
    void push_back(T value) {
        insert(end(), value);
    }
    iterator erase(iterator pos) {
        auto n = pos.node_->next;
        delete pos.node_;
        --size_;
        return iterator{n};
    }
    iterator begin() const noexcept { return first_->next; }
    iterator end() const noexcept { return last_; }
    
    
private:
    node* first_;
    node* last_;
    size_t size_;
};

int main() {
    list<int> l;
    for(auto i = 0; i < 5; ++i)
        l.push_back(i);
    for(auto i : l)
        std::cout << i;
}

wandbox.org

*1:論理的なメモリ空間上で隣り合うということではなく、リストの中の次の要素と前の要素という意味

*2:これだけでもクラス化する意味がある

*3:そのためにデストラクタがある

大学でフィボナッチ数列の第N項を求める課題が出たが再帰は遅いので速くする

フィボナッチ数列はループで書くより再帰で書いた方が書きやすい。ループではプログラマーが意識して変数を3つほど宣言する必要があるが、再帰で書けば変数は要らない。ただ、再帰には以下のような極めて致命的な問題がある。

• まず再帰は関数呼び出しなのでスタックをかなり多く消費する
• フィボナッチ数列の場合、計算量がO(2ⁿ)になる

特に後者は強烈だ。64bit符号なし整数でオーバーフローしない最大のフィボナッチ数は93項目だが、再帰でこれを求める間に令和が終わる。ループで書いた場合の計算量はO(n)なので93項目を求めている間に瞬きすらできない。

// 再帰でFibonacci数列を計算する。
uintmax_t fibonacci_recursion(uintmax_t n)
{
    return n < 2
        ? n
        : fibonacci_recursion(n-2) + fibonacci_recursion(n-1);
}

// 反復文でFibonacci数列を計算する。
uintmax_t fibonacci_loop(uintmax_t n)
{
    if (n <= 1) return n;
    uintmax_t last = 1;
    uintmax_t sum = 1;
    for (uintmax_t i = 2; i < n; ++i) {
        auto buf = sum;
        sum += last;
        last = buf;
    }
    return sum;
}

実際のソースコードを見てもループで書いたフィボナッチ関数は長ったらしい。やはり再帰で書く以外に道はない。

---

ここから速い再帰の話

再帰で書いた時計算量が爆発する原因は一度計算した値を覚えておらず、何度も計算してしまうからだ。それさえなくなれば再帰でもO(n)に収まる。では一度計算した値を関数内で覚えておこう。このような手法をメモ化再帰という。

普通の実装

uintmax_t memo_recursion(unsigned n) {
    // 一度計算した値を覚えておくための変数。すべての要素を0で初期化しておく。
    static std::vector<uintmax_t> memo(94, 0);
    // もしnを計算したことがあればメモの内容を返す。
    if(memo.at(n)) return memo.at(n);
    // 計算したことがなければメモに計算し、メモに代入し、値を返す。
    return memo.at(n) = (n < 2 ? n: memo_recursion(n - 1) + memo_recursion(n - 2));
}

ラムダ式

せっかくC++を書いているのでC++に特有の言語機能を使って再帰を手軽に書きたい。そういえばC++11でラムダ式というのが追加されているのを思い出したのでせっかくだからラムダ式で再帰してみよう。

using memo_t = std::vector<uintmax_t>;
auto f =
[impl = [memo = std::make_unique<memo_t>(94, 0)](auto& fn, unsigned n)
->uintmax_t {
    if(memo->at(n)) return memo->at(n);
    return memo->at(n) = (n < 2 ? n : fn(fn, n-2) + fn(fn, n-1));
}]
(unsigned n){return impl(impl, n);};

コンパイル時

テンプレートがあればもはや実行時に計算することは何もない (レポートにも書いた)。さあ、Let's template!!!!!

// コンパイル時オーバーフロー検出和算
template<class Int, Int M, Int N>
struct add : std::integral_constant<Int, M + N> {
    static_assert(std::numeric_limits<Int>::max() - M >= N, "overflow check failed");
};

template<uintmax_t N>
struct fibonacci_meta
    : std::integral_constant < uintmax_t, add<uintmax_t, fibonacci_meta<N - 1>::value, fibonacci_meta<N - 2>::value>::value > {};

template<>
struct fibonacci_meta<0> : std::integral_constant<uintmax_t, 0> {};

template<>
struct fibonacci_meta<1> : std::integral_constant<uintmax_t, 1> {};

template<uintmax_t N>
inline constexpr auto fibonacci_v = fibonacci_meta<N>::value;

wandbox.org

イテレータを作る回

STLのコンテナを操作するための共通の手段としてiteratorというものがある。とても便利なこのiteratorを自分で実装したことはあるだろうか。iteratorの要件は規格書に書いてあるので、それさえ満たせばどんなイテレータもiteratorを名乗っていいことになる。

この記事ではごく簡単なイテレータもどきの実装を通してイテレータに必要なメソッドや演算子の実装方法を紹介する。また、おまけとして、一番使う頻度が高くなりそうな他のイテレータをそのまま利用する方法も紹介する。

自分のクラスにイテレータがあると何が良いのか

algorithmヘッダのことを知っているだろうか。あそこにある関数はほとんどすべてイテレータを引数に取る。逆に言えばイテレータさえ準備できればalgorithmヘッダの関数を自分で書いたクラスに適用できるということだ。std::findやstd::partitionのような便利関数を使って大学の課題をスラスラ終わらせることができるだろう。

範囲for文もイテレータを使う構文の一つだ。

std::initializer_list<int> il{1, 2, 3};
for(auto i : il) { std::cout << i << ' '; }

簡単な構文でリストの中身を走査できる範囲for文はC++11で導入された。これを知ってしまえばもうC-likeな冗長なfor文には戻れないはずだ。範囲for文はシンタックスシュガーだ。N4810の8.5.4ではfor (for-range-declaration : for-range-initializer)statementは以下と同等であると定義されている*1。

{
    auto&& range = for-range-initializer;
    auto begin = begin-expr; // range.begin()やstd::begin(range)など
    auto end = end-expr; // range.end()やstd::end(range)など
    for ( ;begin!=end; ++begin) {
        for-range-declaration= *begin;
        statement
    }
}

イテレータもどき

簡単に実装できるのはLegacyInputputIteratorだ。この要件は規格書ドラフトのN4810の23.3.5.3に記述されている。規格書での表記はCpp17InputIteratorだが、つまりC++20より前の古いイテレータの要件だ *2。ここではcppreferenceの表記に合わせてLegacyInputIteratorという表記を用いる。

この章では二つの整数mとnの間を反復するイテレータを持つクラスstepを実装してイテレータの実装方法の概要を説明する。下に示すような文を用いて整数を取り出すことが目的だ。

for(auto i : step(m, n)) { std::cout << i << ' '; }

イテレータを実装する前にクラスstepについて考えよう。クラスstepはmからnまでを反復するイテレータを提供するだけのクラスだ。保持すべき値はmとn (ただし分かりやすさのために名前はfirstとlastになる)。用意すべきメソッドは、イテレータを取得するためのbegin()とend()だ。簡単だな。

template<class Int>
class step{
    Int first_;
    Int last_;
public:
    step(Int first, Int last)
        : first_{ first }
        , last_{ last }
    {}
    
    class iterator;
    
    iterator begin() const noexcept;
    iterator end() const noexcept;
};

今はまだiteratorがどのようなものになるかは分からない。これから考える。 firstとlastが等しくない限り、iteratorはbegin()とend()が異なるものでなくてはならない。例えば、stepのコンストラクタに、0uとstd::numeric_limits<unsigned int>::max()が渡された時でも正しく動く必要がある。end()はlast_ + 1の値を指すiteratorを返すだけでは正しく動かない。iteratorは自分が指す値に加え、last_のコピー、そして無効値を表現するための特殊な状態を持つ必要がある。

template<class Int>
class step{
    Int first_;
    Int last_;
public:
    step(Int first, Int last)
        : first_{ first }
        , last_{ last }
    {}
    
    class iterator {
        Int value_;
        Int last_;
        bool is_valid_;
    public:
        using value_type = Int;
        using reference = const Int&;
        using pointer = const Int*;
        using iterator_category = std::input_iterator_tag;
        
        iterator(Int value, Int last)
            : value_(value)
            , last_(last)
            , is_valid_(true)
        {} 
        iterator()
            : is_valid_(false)
        {}
        // この演算子は前置インクリメント
        iterator& operator++() {
            is_valid_ = value_++ != last_;
            return *this;
        }
        // この演算子は後置インクリメント
        iterator operator++(int) {
            auto cp = *this;
            ++(*this);
            return cp;
        }
        reference operator*() const noexcept { return value_; }
        pointer operator->() const noexcept { return &value_; }
        friend bool operator==(const iterator& a, const iterator& b) noexcept {
            return (!a.is_valid_ && !b.is_valid_) ||
                (a.is_valid_ && b.is_valid_ && a.value_ == b.value_);
        }
        friend bool operator!=(const iterator& a, const iterator& b) noexcept {
            return !(a == b);
        }
    };
    
    iterator begin() const noexcept { return iterator{first_, last_}; }
    iterator end() const noexcept { return iterator{}; }
};

wandbox.org

たったこれだけでLegacyInputIterator実装完了だ。範囲for文で好きな回数ループできるようになった。例えば10回ループしたいならfor(auto i : step(1, 10)) {}と書く。なんども言うが、イテレータに対してどのような式が有効でなくてはならないかは規格書で定められている。何を実装すればいいのかわからなくなったときは規格書を参照してほしい。規格書が難しければ日本語に訳されているcppreferenceがよい。

イテレータに必要な機能は理解できただろうか。しかし、それらはiterator_categoryによって若干異なってくる。他のカテゴリーのイテレータを作るときは都度規格書を参照してほしい。

他のクラスのイテレータをそのまま使う (おまけ)

例えばSTLの何かのコンテナを保持しているクラスで、そのコンテナの各要素に対して外部からアクセスしたいとき自分でイテレータを作るのは馬鹿げている。

class container {
    std::vector<int> v_;
public:
    container()
        : v_ (10, 1)
    {}

    using iterator = std::vector<int>::iterator;
    
    iterator begin() { return v_.begin(); }
    iterator end() { return v_.end(); }
};

*1:はてなブログではソースコード中に斜体を混ぜられないので規格書を読んでほしい。また、N4810ではC++20のrange-based forについて書いているが、C++20はまだなのでC++17までのrange-based forに書き換えた

*2:要件が変わったわけではないが、C++20ではconceptでこの要件が実装されているため呼び分けている

大学でC++の演習が始まったがムーブには触れないようなので触れさせる

弊学ではC++の演習が始まったが演習では右辺値参照とかムーブとかは全く触れない。ムーブがないC++はC++ではなくBetter Cというのはさすがに言い過ぎだが (C++03以前のC++がC++ではなくなってしまうため)、ムーブがないC++を書くならわざわざ大学でC++を学ぶ意味はない。ムーブという概念を知るにあたってvalue categoryは非常に重要だ。この記事ではvalue categoryからムーブまでを解説する。

私はこの記事を書くにあたって規格書を少し読んでいる。英語力がクソ雑魚なので翻訳のミスや解釈違いがあればマサカリを投げずに優しく教えてほしい。

rvalue

rvalueはもともと代入演算子の右にある値という意味しか持っていなかった。C++ではもはやそんな単純な話ではなくなってしまった。C++11以降のrvalueはxvalueとprvalueのことを指す。式は以下の図のような分類でカテゴライズされる。

N4810 7.2.1 Figure 1 - Expression category texonomy

xvalue

An xvalue is a glvalue that denotes an object or bit-field whose resources can be reused (usually because it is near the end of its lifetime).*1

xvalueは、その寿命の終わりが近いためリソースを再利用することができるオブジェクトを指すglvalueだ。xvalueは右辺値参照を返す関数の呼び出す式(1)、右辺値参照へのキャスト式(2)、xvalueの配列に対する添え字演算(3)、オブジェクト式がxvalueである非参照型の非静的データメンバを指定するクラスメンバアクセス式(4)か若しくは最初のオペランドがxvalueで二番目のオペランドがデータメンバへのポインタである.* (pointer-to-member)演算式(5)はxvalueである。

規格書の文言を眺めるよりも実際のソースコードを見たほうが理解しやすいはずだ。

struct A{ int m; };
A&& f();
A a;
A arr[10];
auto m_ptr = &A::m;

// 1)
f();
// 2)
static_cast<A&&>(a);
// 3)
std::move(arr)[0];
// 4)
f().m;
// 5)
f().*m_ptr;

prvalue

N4810ではprvalueについて以下のように書かれている。

A prvalue is an expression whose evaluation initializes an object or a bit-field, or computes the value of an operand of an operator, as specified by the context in which it appears, or an expression that has type cv void.*2

prvalueはその評価がオブジェクトまたはビットフィールドを初期化するか、それが表れる文脈で指定される演算子のオペランドを計算する式か、若しくはcv void型をもつ式だ。

prvalueをオペランドに期待する演算子にglvalueが現れたときは常に lvalue-to-rvalue, array-to-pointerもしくは function-to-pointer変換が式をprvalueに変換するため適用される (lvalueをrvalue referenceに束縛するような試みはそのような文脈ではない)。

prvalueは常に完全型かvoid型をもつ。prvalueがクラス型かクラスの (多次元) 配列型を持つ場合、クラスは抽象型ではない。

規格書の文言を見つめるより実際のコードを見たほうが理解しやすいだろう。

int f();
auto il = {0};
auto it = il.begin();

enum e { c = 0 };

// リテラルはprvalue
1; "hoge";
// 参照型でない関数の戻り値はprvalue
f();
// 参照型ではない結果を持つ演算子の結果はprvalue
1+1;
it++;
// 組み込みのアドレス演算子
&il;
// 非参照型へのキャストはprvalue
(int)10;
// 列挙子はprvalue
e::c;
// そのほかthisポインタなど

ムーブとrvalue reference

ある構造体が他の巨大なオブジェクトへのポインタを持っているとしよう。深いコピーを行うようなコピーコンストラクタとコピー代入演算子がプログラムされたその構造体は頻繁に関数の戻り値になったりする。

struct A {
    super_big_type* m;
    A() = default;
    A(const A& src)
        : m{ new super_big_type }
    {
        memcpy(src.m, m, sizeof super_big_type);
    }
    A& operator=(const A& src) & noexcept
    {
        m = new super_big_type;
        memcpy(src.m, m, sizeof super_big_type);
    }
    // デストラクタの定義は省略...
};

A f();

A a;
a = f(); // copy

コピーしかできないA構造体はf()の戻り値のオブジェクトを直接使うことはないのに、いつもいつも別の領域にメモリを確保してsuper_big_typeをコピーしなければならない。ああ、なんと無駄なことか！これがmのコピーだけであったらどんなに動作が速くなることか！

ムーブとはそういう問題を解決する。ところが、いつムーブして、いつコピーすればいいのかを明確に判断するのは従来のC++では難しかった。そこでrvalue referenceが登場した。先に解説したようにrvalueはprvalueとxvalueのことだった。つまりすでに寿命がつきかけているか、リテラルや参照でない関数の戻り値のようなオブジェクトだ。そのようなオブジェクトはもう使用されないことが前提だ。rvalue referenceとはそのようなオブジェクトへの参照だ。

C++ではrvalue referenceを受け取る代入演算子とコンストラクタをムーブ代入演算子/ムーブコンストラクタと呼び、その動作をムーブと呼ぶ。rvalue referenceに束縛されているオブジェクトはこれ以降使われないので、どのように弄繰り回しても問題ない。先ほどの例で言えばrvalue referenceに束縛されているオブジェクトのデータメンバmにnullptrを代入したりしてもよい。

struct A {
    super_big_type* m;
    A() = default;
    A(const A& src)
        : m{ new super_big_type }
    {
        memcpy(src.m, m, sizeof super_big_type);
    }
    // ムーブコンストラクタ
    A(A&& src)
        : m{ src.m }
    {
        src.m = nullptr;
    }
    A& operator=(A&& src) & noexcept
    {
        m = src.m;
        src.m = nullptr;
    }
    // コピー代入演算子とデストラクタの定義は省略...
};

A f();

A a;
a = f(); // ムーブ!!

便利な標準ライブラリ関数 std::move std::forward

時にはlvalueをムーブしたいときもあるだろう。lvalueをrvalue referenceにキャストすればその目的はすぐに達成できる。

struct A{};

A a, b;
a = static_cast<A&&>(b); // move

ただし、この記述は冗長だ。標準ライブラリにはオブジェクトをrvalue referenceにキャストしてくれる関数がある。std::move()だ。

a = std::move(b);  // move

std::move()を使えば左辺値だろうが何だろうがとにかく全部rvalue referenceにキャストしてくれる。これにて一件落着....とはいかないのがC++だ。本当にすべてムーブしても良いのだろうか。以下のようなとあるオブジェクトを生成する関数を考えよう。

template<class T, class ...Args>
std::remove_reference_t<T> make(Args&& ...args) {
    return std::remove_reference_t<T>{ std::move(args)... };
}

std::vector<int> a{1, 2, 3};
auto b = make<std::vector<int>>(a);  // 本当はコピーしたい
assert(a == b);

aというlvalueを渡しているのだから、当然aはbに"コピー"されるのかと思いきや、この場合アサーションは常に失敗する。create関数の中でaをムーブしてしまうからだ。引数がlvalue referenceの時lvalue referenceを返し、それ以外の時はrvalue referenceを返すような仕組みが必要だ。もちろんC++の標準ライブラリにはstd::forwardがその仕組みを持っている。以下はstd::forwardの実装だ

template <class _Ty>
constexpr _Ty&& forward(remove_reference_t<_Ty>& _Arg) noexcept {
    return static_cast<_Ty&&>(_Arg);
}

template <class _Ty>
constexpr _Ty&& forward(remove_reference_t<_Ty>&& _Arg) noexcept {
    static_assert(!is_lvalue_reference_v<_Ty>, "bad forward call");
    return static_cast<_Ty&&>(_Arg);
}

例えばiをint型の左辺値だとしてstd::forward<int&>(i)と書けば最初のオーバーロードに解決される。最初のオーバーロードでは_Ty&&は参照の圧縮によってint&と同じになる。

また、int f()があるとき、std::forward<int>(f())と書けば2番目のオーバーロードに解決される。参照型ではない関数の戻り値は左辺値参照になり得ないためだ。この場合はforwardの戻り値はint&&型となる。

通常は起こり得ないが、std::forward<int&>(f())はコンパイルエラーとなるはずだ。

先ほどのアサーションが通るようなmakeの実装は以下のようになる。

template<class T, class ...Args>
std::remove_reference_t<T> make(Args&& ...args) {
    return std::remove_reference_t<T>{ std::forward<Args>(args)... }; // argsがlvalue referenceの時はムーブしない
}
std::vector<int> a{1, 2, 3};
auto b = make<std::vector<int>>(a);  // コピーしたい
assert(a == b);
auto c = make<std::vector<int>>(std::move(a)); // ムーブしたい

*1:N4810 7.2.1

*2:N4810 7.2.1

大学でC++の演習が始まったが例外には触れないようなので触れさせる

例外は本当に便利な機能だ。戻り値でエラーを通知するC的な関数を排除して、戻り値は関数の計算結果のために予約しつつエラーを通知できる。大学ではC++をやるが、例外を使わないC++はC++ではなくBetter Cだ。とは言え、例外にはデメリットもある。メリットとデメリットのバランスを調整してうまく使えばC++erを名乗れるようになるだろう (知らんけど)。

最初に言っておくと私はC++の規格書を読んでいない。そのため、規格書を通読した人間より多くの間違いを書くことがあるのだが、マサカリを投げずに優しく指摘してくれたら誠実に対応したいと思う。

この記事の対象読者は大学でC++の講義や演習が始まったけど、それらで例外を習わないことが確定している大学生だ。

例外の構文

まず例外の構文を知ろう。例外についての解説はそのあとに行う。解説は実際のコードを交えて進めるので解説を理解するために例外の構文を知ることは必要不可欠だ。

例外を投げる

例外を投げるにはthrow式を用いる。throw式には二つの意味がある。一つは新しい例外を投げる意味、もう一つは現在処理中の例外を投げなおす意味だ。後者はcatch節内でしか使うことができない。

新しく例外を投げる場合、throw式には例外オブジェクトを指定する。例外オブジェクトは完全型でCopyConstructibleかつ Destructibleな静的型である必要がある。

throw std::runtime_error("some error!");

処理中の例外を投げなおす場合、throw式には例外オブジェクトを指定しない。

try { /* ... */ }
catch(...) {
    throw;
}

例外をキャッチする

tryブロックがフライングして先に登場してしまった。お察しの通り、投げられた例外をキャッチするのはtryブロックだ。例外をキャッチするにはtryの直後に続く複文で例外が送出される必要がある。tryブロックは一つ以上の例外ハンドラーを伴う。例外ハンドラーはcatch(処理する例外オブジェクトの型)の形で記述される。すべての例外オブジェクトをキャッチする例外ハンドラーもcatch(...)と書くことができる。

try{ throw_exception(); }
catch(std::exception&) { /* do something */ } // std::exceptionとその派生型のみをハンドルする
cathc(...) {}                                 // すべての例外をハンドルする

例外が投げられた場合、catch節の順番通りに例外オブジェクトとマッチするかチェックされるため、制約の厳しいcatch節は緩いcatch節より前に書く必要がある。

try{ throw_exception(); }
catch(...) {}
catch(std::exception&) { /* この副文は絶対に実行されない */ }

tryブロックは文なので関数本体をマルっとtryブロックにすることができる。

void hoge() try{}
catch(...){}

例外の基本

例外というのはエラーが発生したときに投げるものだ。例えばオーバーフローを検出して符号なし整数同士を足し算する関数を書きたいが、計算結果は当然戻り値で受け取りたいし、オーバーフローがあったかどうかも当然知りたい。そんなときに例外は役に立つ。試しにその関数を書いてみよう。

#include <type_traits>

template<class Unsigned, std::enable_if_t<std::is_unsigned_v<Unsigned>>* = nullptr>
auto add(Unsigned a, Unsigned b) {
    using u_t = Unsigned;
    return std::numeric_limits<u_t>::max() - a >= b
        ? a + b
        : throw std::overflow_error("result is out of range");
}

この関数ではオーバーフローが発生する場合は例外を投げてそのことを通知し、オーバーフローが起きない場合はそのまま和を返す。比較のためにCでもオーバーフロー検出付きの加算関数を書こう。

#include <stdbool.h>
#include <limits.h>
bool add(unsigned a, unsigned b, unsigned* const result) {
    return UINT_MAX - a >= b
        ? *result = a + b, true
        : false;
}

ついでに両関数を実際に使って例外の便利さとC的関数でエラー処理する苦痛を実感しよう。加算して値を標準出力に出力する。利用側コードは簡単のためC++でunsigned int型が32bitと仮定して書く。[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

#include <climits>
#include <type_traits>
#include <iostream>

template<class Unsigned, std::enable_if_t<std::is_unsigned_v<Unsigned>>* = nullptr>
auto add(Unsigned a, Unsigned b) {
    using u_t = Unsigned;
    return std::numeric_limits<u_t>::max() - a >= b
        ? a + b
        : throw std::overflow_error("result is out of range");
}
bool add(unsigned a, unsigned b, unsigned* const result) {
    return UINT_MAX - a >= b
        ? *result = a + b, true
        : false;
}

int main() {
    {   // C-like
        unsigned result;
        if(!add(0xFFFF'FF0E, 2, &result))
            std::cout << "overflow!!!!\n";
        else std::cout << result << '\n';
        
        if(!add(0xFFFF'FFFE, 2, &result))
            std::cout << "overflow!!!!\n";
        else std::cout << result << '\n';
    }
    try {   // C++-like
        std::cout << add(0xFFFF'FF0Eu, 2u) << '\n';
        std::cout << add(0xFFFF'FFFEu, 2u) << '\n';
    } catch(std::runtime_error& e) { std::cout << e.what() << '\n'; }
}

好奇心が旺盛な読者諸君ならC++-likeなadd関数の実引数を色々と値を変えてみて実行しているだろう。例えば、現状のコードでは最初のadd呼び出しは例外を投げないが、30行目と31行目の文を入れ替えて実行してみると出力されるものが変わってくるはずだ。

例外が投げられたらそれ以降のtry内の文が実行されないことに気づいただろうか。C++では例外が投げられるとスタックをtryブロックの先頭まで巻き戻す。時間が巻き戻るわけではないので、すでに実行された副作用などに影響を受けた状態が復元するわけではないが、tryブロック内で積まれたスタックは元に戻る。スタックにあったオブジェクトのデストラクタは確実に呼ばれるので安心してほしい。スタックがtryブロックの先頭にまで戻ったら次は投げられた例外オブジェクトにマッチする例外ハンドラーが前から順番に検索される。最初にマッチした例外ハンドラーが実行されて、制御はtryブロックの次の段階に移る。ここでもしマッチする例外ハンドラーがなければ、例外は外側のスコープに伝播する。例外が最終的にどのcatch節でも処理されなかった場合std::terminateが呼ばれプログラムは終了する。例えば以下のようなプログラムは例外を処理しないためstd::terminateが呼ばれる。

int main() { throw 1; }

処理しなかった場合にプログラムが絶対に終了してしまうというのは例外のデメリットの一つだが、そんなものは処理すれば関係なくなるのでこの際どうでもいい。より深刻なデメリットにはスタック巻き戻しや、例外オブジェクトのコピーによって発生する時間的、空間的損失だ。例外を使うことはプログラムの実行速度を下げ、少しのスタックと未既定の記憶領域を消費する。気になるのは例外を使うことによってどのくらい速度が落ちるのかだが、これは例外が送出される頻度と処理系に依存する。

では早速エラーの検出を例外を使うか、if文を使うかでどちらがどのくらい速くなるのか例外の送出頻度ごとに計測しよう。処理系はGCC8.3.0にしよう。wandboxで気軽にコードを実行できるのはとてもいい時代になったものだ。実行結果は上から順に100%、50%、33%、10%、1%、0.1%、0.01%、0.01%、0%の確率でエラーが起こる場合の条件分岐によるエラーチェックが例外を使う場合に比べて何倍速いかを表している。高い確率でエラーが起こる場合、例外を使うとifによるエラーチェックより1000倍近く遅くなっている。逆にエラーがほとんど起こらない場合、例外を使う場合の方が若干早くなっている。このように例外は大量に送出すると非常に遅くなるので注意が必要だ。

wandbox.org

診断のためのライブラリ

標準ライブラリでは例外オブジェクトやそれに関連する様々な関数やクラスが定義されている。stdexceptのあたりを見ておけばひとまず困ることはないだろう。

ja.cppreference.com

例外仕様

関数が例外を投げるか投げないか投げるとしたらどんな例外を投げるかは関数の宣言から分かる場合がある。

古の方法 (C++17で削除)

例外を投げることを指定する古の方法はC++17で削除された。古のコードを読む必要がある場合だけ見てほしい。古のコードを読まない場合はココを飛ばして次のクールでスマートな最新の方法に飛ぼう。

古の方法で関数が例外を投げることを伝えるのは非常に苦労する。まず関数が投げる可能性がある例外をすべてリストアップする。これはまぎれもなくすべてだ。関数内でメモリアロケーションをする若しくはメモリアロケーションを行う関数を呼び出している場合はstd::bad_allocが投げられる可能性がある。STLのコンテナにアクセスしてatメソッドを使えばstd::out_of_rangeが投げられる可能性がある。std::wstring_convert::from_bytesかstd::wstring_convert::to_bytesを呼び出していたらstd::range_errorを投げる可能性がある。まさにありとあらゆる可能性を考えて全ての例外オブジェクトの型をthrow()の括弧の中に書く必要がある。が、投げるオブジェクトの基底クラスを書けば実は問題ない。std::exceptionの派生クラスしか例外オブジェクトになり得ないような関数であれば、throw(std::exception)で事足りるので安心だ。

古の方法では例外を投げない場合はとても簡単だ。関数の引数リストの後ろ (にある非静的メンバ関数のcv修飾の後ろ) にthrow()と書くだけだ。ただし、クールでスマートな最新の方法はもっと簡単だ。

// std::exceptionとstd::stringとそれらの派生クラスだけを投げる(C++17で削除された例外仕様)
// 他の例外を投げた場合、たとえ適切なcatch節があったとしても実行時エラー
void hoge() throw(std::exception, std::string);

// 例外を投げない
// 例外を投げない古い例外仕様まだ削除されていないが、C++20で削除される予定だ (C++11で非推奨)
void fuga() throw();

クールでスマートな最新の方法

実際のところ、throw(types...)を使う古い例外仕様はどのコンパイラもまともに実装しなかった。例外を投げないことを指定するthrow()だけは便利に使うことができたため、2019年現在も非推奨ながら生き残っている。

古の時代は終わった。令和も始まろうかという現代にthrow(types...)は古いのだ。新しい例外仕様にはnoexcept指定子を使う。ちなみに、C++にはnoexcept演算子もある。これらは意味が違う。

noexcept指定子は関数の引数リストの後ろ (にある非静的メンバ関数のcv修飾の後ろ) に書く。式を指定しない場合はその関数は例外を投げない (投げた場合はstd::terminateが呼ばれる)。noexcept指定子には式を指定することも出来る。その式がtrueに評価されるとき関数は如何なる例外も投げることはない (投げた場合はstd::terminateが呼ばれる)。

// noexceptに式を指定しない場合
void hoge() noexcept;

// noexceptに式を指定する場合
void fuga() noexcept(true);
void piyo() noexcept(false); // 例外を投げるかもしれない。
void nya() noexcept(1 == 1); // 1==1はtrueなのでnya関数は例外を投げない。

noexcept演算子は式が例外を投げる可能性があるかどうかをbool型の定数値にしてくれる。例外を投げない場合にtrue、それ以外の場合でfalseに評価される。

void hoge() noexcept;
void fuga() noexcept(false);
void piyo();

static_assert(noexcept(hoge()) == true);
static_assert(noexcept(fuga()) == false);
static_assert(noexcept(piyo()) == false);

例外を投げるべきときと投げるべきでないとき

例外を投げるべきかどうかの判断は非常に難しい。例外を投げるかどうか迷ったときはスタックを巻き戻したいかどうかを考えると良い。引数が不正だった とか、むしゃくしゃしてやった などとエラーメッセージに書くために例外を投げることは避けるべきだ。引数が不正な場合はassertでもいいかもしれない。もしくは例外も投げず、assertもせず、単にログを出力して後で見たときにわかればいいだけかもしれない。例外を投げるのはもっと例外的な状況に限るべきだ。リソースの確保に失敗した とか、関数を実行するための事前条件が満たされていなかった とか、実行時に直ちに問題になる状況では例外を投げるのは適切であることが多い。

例外を投げるべきでないという判断は非常に簡単だ。例外を投げることはスタックを巻き戻すことだ。もし関数がfor文の中で使われるようなものなら、どう考えても例外を投げるべきではない。STLのat()メソッドは例外を投げる可能性があるが、その関数を呼び出す前に例外を投げるかどうかを実行時に判断できる。どうしても例外を投げる必要があるのにその関数がループの中で呼ばれそうならば、別の手段で例外を投げない事前条件を満たしているか判断できるようにするべきだ。

例外を投げるべきでない関数は他にもある。デストラクタのようなリソースを解放する種類の関数だ。例外を投げるとスタックが巻き戻り、自動オブジェクトのデストラクタが呼ばれる。スタックの巻き戻し中にデストラクタで例外が投げられ、それがデストラクタ内でキャッチされなければ漏れなくstd::terminateが呼ばれる。また、どうしてもデストラクタで例外を投げて、それをデストラクタの外に伝播させたい場合は、デストラクタの例外指定は明示的にnoexcept(false)にしなければならない。また、std::terminateが呼ばれるのを回避したいならばstd::uncaught_exceptions()で他の例外が処理中でないことを確かめなければならない。他の例外が処理中ならばデストラクタで起きたエラーは隠蔽するか別の方法で通知すべきだ。

大学でC++の演習が始まったがテンプレートには触れないようなので触れさせる

テンプレートは C++が闇たる所以だ。 C++に光あれ。しかし、テンプレートを使いこなすことができなければC++はC++ではない。そういうものはBetter C (Cよりはマシ) という。大学の演習ではテンプレートについて何もやらないようなので、この記事ではテンプレートの基本からすごく簡単なTMPくらいまで触る。

最初に言っておくと、私はC++の規格書を読んでいないので間違いが含まれる可能性がある。正しくないことを書きたくないのでテンプレートの使い方を紹介するにとどめる。

対象読者は大学でC++の講義や演習が始まったけど、それらでテンプレートを習わないことが確定している大学生だ。

テンプレートの文法

テンプレートは型や整数定数を引数にして雛形 (テンプレート) を作る機能だ。テンプレートは関数、クラス、変数で使用できる。それぞれ関数テンプレート、クラステンプレート、変数テンプレートという。関数、クラス、変数のテンプレートの定義は以下のように行う。

template< テンプレート引数 >
関数, クラス, 変数の定義

例えばクラステンプレートは以下のように定義する。

template<class T>
class hoge {};

テンプレートを実体化するときには以下のように行う。

識別子<テンプレート実引数>

先ほどのclass hogeをint型で実体化してみよう。

hoge<int> fuga;   // fugaはhoge<int>型のインスタンス

またコンパイラがテンプレート引数を推論できる場合はテンプレート引数は省略できる。そのような場合を除いてテンプレート引数を省略することはコンパイルエラーにつながる。C++17では関数とクラスのテンプレート引数を推論することができる場合がある。クラステンプレートの実引数推論はdeduction-guide (推論補助) を書くことでコンストラクタにテンプレート引数で渡された型がなくても推論することができる場合がある。

テンプレートの初歩

様々な型に適用したい処理をテンプレートで書くことで、関数オーバーロードや、扱う型や定数だけが異なる別のクラスと変数を自分で書く必要がなくなる。例えば二つの数値を足し算するプログラムをテンプレートを使って書こう。

C言語では以下のように書かざるを得なかった。

int add_int(int a, int b) { return a + b; }
long add_long(long a, long b) { return a + b; }
//...

Cではオーバーロードすらできないので愚直に違う名前の関数を並べる必要がある。はっきり言ってこんなものはクソだ。C++でこれをもっと簡単に書くことができる。

template<typename Ty>
Ty add(Ty a, Ty b) { return a + b; }

たったこれだけでint, long, doubleなどなど、足し算を適用できるすべての型についてadd関数を適用できる。さらに、上の関数はテンプレート実引数をコンパイラが推論できる。例えばadd(1,1)ではTyはintに解決される。

しかし、先のような関数では以下のコードはエラーになってしまう。

add(1.5, 3);    // error!

これをコンパイルするためにはテンプレート引数を明示的に渡してやる必要がある。

add<double>(1.5, 3);

テンプレートは型だけでなく整数定数も引数にできる。整数定数は何もint型とは限らない。関数ポインタやヌルポインタもコンパイル時定数なのでテンプレート引数になり得る。テンプレート引数で渡された整数値をプリントする関数を実装してみよう。

template<int Int>
void print_num() { std::cout << Int << std::endl; }

// 呼び出し
print_num<5>();

次に関数ポインタを受け取ってみよう。

template<void(*FuncPtr)()>
void call_func() { (*FuncPtr)(); } // 渡された関数ポインタを呼ぶだけ。

void f() { std::cout << "f()\n"; } // f()と出力するだけ

call_func<f>();                    // fを呼び出す

テンプレートの特殊化

テンプレートの特殊化は特定のテンプレート引数が渡された時、特別の動作を行うことだ。これによってコンパイル時条件分岐などができるようになってしまう。このことはC++の闇と密接にかかわっていると思う。C++に光あれ。

最初にテンプレートの特殊化を使ってintとlongで動作が変わる関数を作ってみよう。

template<typename Integral>
void f() {}

template<>
void f<int>() { std::cout << "int"; }
template<>
void f<long>() { std::cout << "long"; }

intが渡されたら"int"を出力し、longなら"long"、ほかの型ならば何もしない関数の出来上がりだ。この関数に利用価値は無いが、テンプレートの特殊化は様々な可能性を秘めた魅力的な機能だということを解ってもらうためちょっと難しいこともやってみよう。

テンプレートの特殊化を使ってちょっとした計算を行ってみよう。1からNまでの和を求める関数でテンプレートの特殊化を学ぶ。

template<unsigned int N>
unsigned int sum() { return N+sum<N-1>(); }

template<> // テンプレートの特殊化
unsigned int sum<1>() { return 1; }

ただしこれは実行時に関数呼び出しなどを行っているため、せっかくのテンプレートの特殊化の利点 (コンパイル時条件分岐) がほぼ無意味になっている。どうせなら実際の計算などもコンパイル時に行い、結果をコンパイル時定数にしたいものだ。関数にconstexprをつければ目的は達成できるが、もうすこしテンプレートの特殊化について学びたい人は次のコードも読んでほしい。

template<unsigned int N>
struct sum {
    static constexpr unsigned int value = N + sum<N-1>::value;
};

template<>
struct sum<1> {
    static constexpr unsigned int value = 1;
};

std::cout << sum<10>::value << std::endl;    // 55が出力される。

関数にconstexprを付けたほうが簡単に書けるが、こういったイディオムはconstexprが無かったり、制約が厳しかった時代のC++でよく見るので、古いコードを読む機会が多い人は見ておくと良いだろう。また、このイディオムはvalue(値)だけでなくtype(型)にも応用できるので、メタプログラミングが好きな人は見る機会が多いと思う。

では早速、今のイディオムを使って型をプログラミングしよう。標準ライブラリにあるいくつかの型特性のクラスは自分でも実装できるくらい簡単だ。例えば引数の型にポインタを付けるプログラムは以下のように実装できる。

template<typename Ty>
struct add_pointer {
    typedef Ty* type;
};

template<typename Ty>
struct add_pointer<Ty&> {
    typedef Ty* type;
};

template<typename Ty>
struct add_pointer<Ty&&> {
    typedef Ty* type;
};

// 動作確認
static_assert(std::is_same_v<int*, add_pointer<int>::type>);
static_assert(std::is_same_v<int*, add_pointer<int&>::type>);
static_assert(std::is_same_v<int*, add_pointer<int&&>::type>);

参照のポインタは宣言できないためテンプレートの特殊化で参照を取り除いたTyに対してポインタを付与している。テンプレートは、このように「型をプログラミング」することができる。

標準ライブラリみたいなかっこいいメタ関数を作る

標準ライブラリは型特性を問い合わせるときにis_xxxxみたいに書くことができる。例えば二つのテンプレート引数TとUが同じ型であるかどうかはstd::is_sameという構造体を使って確かめる。こういうのは思ったより簡単に作ることができる。

is_same

まず初めに二つの型が同じかどうか調べるis_sameを作ってみよう。といってもこれはものすごく簡単だ。テンプレートの特殊化をするだけだ。

template<class T, class U>
struct is_same : std::bool_constant<false> {};

template<class T>
struct is_same<T, T> : std::bool_constant<true> {};

// 動作確認
static_assert(is_same<int, int>::value);
static_assert(!is_same<int, double>::value);

二つの型が加算可能か確かめる

次はTとUが加算可能か確かめるメタ関数を作ろう。加算可能な場合にメンバ定数valueがtrueになり、そうでない場合falseになる。メタ関数は二つの部分に分かれる。実装とインターフェースだ。

struct can_be_added_impl {
    template<class ...Args>
    static auto check(...)
        ->std::bool_constant<false>;

    template<class T, class U>
    static auto check(T*, U*)
        ->decltype(std::declval<T>() + std::declval<U>(), std::bool_constant<true>{});
    
};

template<class T, class U>
struct can_be_added : decltype(can_be_added_impl::check<T, U>(nullptr, nullptr)) {};

// 動作確認
static_assert(can_be_added<int, int>::value);
static_assert(can_be_added<int, double>::value);
static_assert(!can_be_added<int, std::string>::value);

can_be_added<T, U>はcan_be_added_impl::check<T, U>関数の戻り値の型を継承する。check関数はT型とU型の値が+演算子で加算できるとき二番目のcheck関数に解決され、それ以外の場合では最初のcheck関数に解決される。二番目のcheck関数の戻り値の型はstd::bool_constant<true>型で、最初のはstd::bool_constant<false>型だ。それを継承すればtrueかfalseの値を持ったメンバ定数valueがcan_be_addedから使用可能になる。

型制約

テンプレートに何でもかんでも渡せてしまうのは良くないと思う人は目の付け所がシャープだ (適当) 。実際、整数型しか想定していないのに浮動小数点型を渡されたり、ユーザー定義の構造体を渡されたりするのは恐ろしいエラーメッセージか若しくはバグを生み出すかもしれない。だからテンプレートにおかしな引数をわたしてしまったときにわかりやすくコンパイルエラーになるような仕組みが必要だ。テンプレートに渡す型引数を制限することを型制約という。

型制約にはいろいろな方法があると思う。私は特定の条件を満たした時だけ実体が定義される方法とstd::enable_ifを使う方法しか知らないのでその2種類の方法について解説する。

嫌な奴は定義してやらない方法

クソみたいなテンプレート引数を渡してくる奴がいても安心だ。なぜならば実体化されないからである。例えばintしか渡せない関数テンプレートと、int以外しか渡せない関数テンプレートを書いてみよう。

template<typename Ty>
void int_only();

template<>
void int_only<int>() {}

int_only<long>();  // error! 定義がない
int_only<int>();   // errorじゃない

template<typename Ty>
void ban_int(){}
template<>
void ban_int<int>();

ban_int<int>();  // error!
ban_int<long>(); // errorじゃない

std::enable_ifを使う方法

クソみたいなテンプレート引数を渡してくるやつがいても安心だ。なぜならばstd::enable_ifがいるからである。std::enable_ifはクラステンプレートだ。最初の引数がtrueの場合、メンバ型typeが定義される。typeは第二引数で指定できるが、指定しなかった場合はvoidになる。

最初の引数に満たすべき条件を書いて、typeが定義されている場合で有効なコードを書いておくことで、条件が満たされなかった場合はコンパイルエラーになってくれる。

今度はTyが算術型である場合にwell-formedにしてみよう。

template<typename Ty, std::enable_if_t<std::is_arithmetic_v<Ty>>* = nullptr>
void arithmetic() {}

arithmetic<int>();
arithmetic<std::string>(); // error

難しいので、テンプレートの実体化される過程を追ってみよう。

intを渡した場合、std::is_arithmetic_v<Ty>はtrueになり、その場合、std::enable_if_t<true>* = nullptrがvoid* = nullptrになる。これはwell-formedだ。

次に、std::stringを渡してみた場合、std::is_arithmetic_v<Ty>はfalseになり、その場合、std::enable_if_t<false>* = nullptrは定義されないstd::enable_if<false>::typeを使おうとしているのでコンパイルエラーになる。

テンプレートで遊ぼう。(FizzBuzz)

FizzBuzzというのは3の倍数の時だけアホになる世界のナベアツさんのように、3の倍数の時にFizzといい、5の倍数の時にBuzzという遊びだ。アメリカでは長距離ドライブなどの最中でFizzBuzzをやるらしい。もちろんコンパイル時FizzBuzzではなく、人間が順番に数字をいう中でFizzとかBuzzとか言うだけだ。

Aさん「1」
Bさん「2」
Aさん「Fizz」
Bさん「4」

という風にやるが、プログラミング界隈でのFizzBuzzは、コードを書けないプログラマ志願者を見分ける方法として有名だ。今回はそれをコンパイル時にやる。

コンパイル時FizzBuzzをやるためにまず必要なのはテンプレート実引数が3の倍数の時に"Fizz”sv、5の倍数の時に"Buzz"sv、15の倍数の時に”FizzBuzz"sv、それ以外でその数字になるようなメンバ定数valueを持つFizzBuzz構造体だ。これはテンプレートの特殊化をすれば実装できる。

// クラステンプレートFizzBuzz
// 何も特殊化していない
// N : FizzBuzzする値
// D : divisor。Nを割る数
// S : 余り。NをDで割った余り
template<int N, int D, int S>
struct FizzBuzz {
    static constexpr std::string_view value = "";
};
// Nが1で割り切れる場合、メンバ定数valueがNの値を取るFizzBuzz構造体
// メンバ定数valueは基底クラスで定義されている。
template<int N>
struct FizzBuzz<N, 1, 0> : public std::integral_constant<int, N> {};

// Nが3で割り切れない場合の特殊化
template<int N, int S>
struct FizzBuzz<N, 3, S> : public FizzBuzz<N, 1, 0> {};

// Nが3で割り切れる場合の特殊化
// valueが”Fizz"svである。
template<int N>
struct FizzBuzz<N, 3, 0> {
    static constexpr std::string_view value = "Fizz";
};

// Nが5で割り切れない場合は3で割ってみて、FizzBuzz<N, 3, 0>かFizzBuzz<N, 3, S>を継承する。
// その結果メンバ定数valueが"Fizz"svかNの値を取る。
template<int N, int S>
struct FizzBuzz<N, 5, S> : public FizzBuzz<N, 3, N % 3> {};

// Nが5で割り切れる場合の特殊化
template<int N>
struct FizzBuzz<N, 5, 0> {
    static constexpr std::string_view value = "Buzz";
};

// Nが15で割り切れない場合、Nを5で割ってみる。
template<int N, int S>
struct FizzBuzz<N, 15, S> : public FizzBuzz<N, 5, N % 5>{};

// Nが15で割り切れる場合の特殊化。
template<int N>
struct FizzBuzz<N, 15, 0> {
    static constexpr std::string_view value = "FizzBuzz";
};

テンプレート引数にはコンパイル時定数しか渡せないのでfor文で上のFizzBuzz構造体のvalueを順番に出力することはできない。ループが使えないなら再帰を使えばいいじゃない。

FizzBuzz構造体のvalueに順番にアクセスするために正確には再帰ではないが、再帰っぽいことをしてみよう。

template<int N>
struct Run {
    static void run() {
        run<N - 1>::run();
        std::cout << FizzBuzz<N, 15, N%15>::value << '\n';
    }
};
template<>
struct Run<1> {
    static void run() {
        std::cout << FizzBuzz<1, 15, 1%15>::value << '\n';
    }
};
int main(){
    Run<100>::run();
}

これでコンパイル時FizzBuzzは完了だ。Wandboxで動作を確認できる。

wandbox.org

あとは標準ライブラリを使いこなすだけ！

テンプレートは闇だが、使いこなすことができればC++で表現の幅が広がる。ほとんどの処理をコンパイル時にすることも出来るようになるだろう。そのためにはまず標準ライブラリのtype_traitsヘッダにあるメタ関数を使いこなせるようにならなければならない。