C++ で FibBuzz

C++ Boost

震源地: Codnote.net
やりましょう．
fibbuzz.cpp

#if !defined(BOOST_PP_IS_ITERATING)
    #include <boost/preprocessor/iteration/iterate.hpp>
    #include <boost/preprocessor/slot/slot.hpp>
    #define BOOST_PP_VALUE 1
    #include BOOST_PP_ASSIGN_SLOT(1)
    #define BOOST_PP_VALUE 1
    #include BOOST_PP_ASSIGN_SLOT(2)
    #define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 29, "fibbuzz.cpp"))
    #include BOOST_PP_ITERATE()
#else
    #if BOOST_PP_SLOT(1) % 15 == 0
FizzBuzz
    #elif BOOST_PP_SLOT(1) % 3 == 0
Fizz
    #elif BOOST_PP_SLOT(1) % 5 == 0
Buzz
    #else
BOOST_PP_SLOT(1)
    #endif
    #define BOOST_PP_VALUE BOOST_PP_SLOT(1)
    #include BOOST_PP_ASSIGN_SLOT(3)
    #define BOOST_PP_VALUE BOOST_PP_SLOT(2)
    #include BOOST_PP_ASSIGN_SLOT(1)
    #define BOOST_PP_VALUE BOOST_PP_SLOT(3) + BOOST_PP_SLOT(2)
    #include BOOST_PP_ASSIGN_SLOT(2)
#endif

実行

$ g++ -E -P -I $BOOST_ROOT -I . fibbuzz.cpp
1
1
2
Fizz
Buzz
8
13






Fizz



34
Buzz
89
Fizz
233
377
Buzz
Fizz
1597
2584
4181
FizzBuzz
10946
17711
28657
Fizz
Buzz
121393
196418
Fizz
514229
Buzz

VC や Clang でも動くと思いますが，空白行だらけになってしまうので GCC で実行するのがいいと思います．

C++ で 2 進数を書く

C++ Boost

BOOST_BINARY を使う

やっぱり基本はマクロですね．ある車輪は使いましょう．

#include <boost/utility/binary.hpp>
#include <boost/static_assert.hpp>

BOOST_STATIC_ASSERT((BOOST_BINARY(1001 1100 1011 111) == 0x4E5F));

テンプレートを使う

C++ と言えばテンプレートメタプログラミング．あまり大きな数を扱えないのが難点．

#include <boost/static_assert.hpp>

template <unsigned long N>
struct binary
{
    BOOST_STATIC_ASSERT((N % 10 == 0 || N % 10 == 1));
    static const unsigned long value = binary<N / 10>::value * 2 + N % 10;
};

template <>
struct binary<0>
{
    static const unsigned long value = 0;
};

BOOST_STATIC_ASSERT((binary<11001>::value == 25));

constexpr を使う

ここからは C++11 限定．コンパイル時にも実行時にも使えるのが constexpr 関数の素晴らしいところです．

#include <iostream>
#include <stdexcept>
 
template <class Char>
constexpr unsigned long long binary_impl(Char const *s, Char zero, Char one, unsigned long long acc)
{
    return *s == Char('\0') ?
        acc :
        binary_impl(
            s + 1,
            zero, one,
            (acc << 1) + (*s == zero ? 0 : *s == one ? 1 : throw std::invalid_argument("binary")));
}

template <class Char>
constexpr unsigned long long binary(Char const *s, Char zero = Char('0'), Char one = Char('1'))
{
    return binary_impl(s, zero, one, 0);
}

static_assert(binary("1110001110110110") == 0xE3B6, "");

ユーザー定義リテラル

いらない子と言われて久しいですが，コンパイル時に評価されることが保証されていれば，少しは役に立ったかもしれません (正規表現リテラルの誤りをコンパイル時に検出するとか)．

#include <type_traits>

template <unsigned long long acc, char ...cs>
struct binary_impl
  : std::integral_constant<unsigned long long, acc>
{};

template <unsigned long long acc, char c, char ...cs>
struct binary_impl<acc, c, cs...>
  : binary_impl<(acc << 1) + (c == '0' ? 0 : c == '1' ? 1 : throw), cs...>
{};

template <char ...cs>
constexpr unsigned long long operator "" _b()
{
    return binary_impl<0, cs...>::value;
}

static_assert(11001_b == 25, "");

コンパイルは通してないのでミスがあるかもしれません．そもそもユーザー定義リテラルを実装した処理系がないのですが (2011/09 時点)．

もっと楽しく

二進数リテラル(嘘) - とくにあぶなくないRiSKのブログ
いいですねー．

実行時に評価するなら

boost::dynamic_bitset などが使えます．C++03 でも OK．

#include <string>
#include <boost/dynamic_bitset.hpp>
#include <cassert>

int main()
{
    assert((boost::dynamic_bitset<>(std::string("1010")).to_ulong() == 10));
}

固定長多次元配列のラッパ

C++ Boost

std::array, M> に要素の連続性の保証がないなら*1，生の多次元配列(配列の配列)をラップすれば確実にそれを保証できるのではないかという．3 秒くらい考えれば，コンテナの要件を満たせない残念なものができるのはわかる気がしますが，書いてしまったものは仕方がないということで．
https://gist.github.com/1222262

#include "multi_array.hpp"

int main()
{
    uni::multi_array<int, 3, 2> a = { { { 1, 2 }, { 3, 4 }, { 5, 6 } } };
    
    a[0][0] = 7;                              // 普通にアクセス
    uni::multi_array<int, 2> a0 = a[0];       // 子配列をコピー
    for (int i : a.flatten()) std::cout << i; // 配列を 'ならす'
}

Variadic Templates を使って可変次元に対応しつつ，プリプロセッサを最後まで避けえたことが個人的満足ポイント．

*1:保証できそうな感じはしますが，配列以外にメンバを持つかも，処理系が末尾に要らんパディングを入れるかも，と言われたらそんな気もする

C++0x でスリープソート

C++

某 KUIS の院試でスリープソートが出題されたらしいので，以前話題になったときに書きかけてそのままにしていた C++0x での実装を晒しておきます．
まず sleep.cpp がこちら．

constexpr int f(int x, int y, int n)
{
    return y == 0 ? 0 : f(x * 2, y - 1, n) + f(x * 2 + 1, y - 1, n);
}

constexpr int g(int n)
{
    return n == 0 ? 0 : f(0, 16, n) + g(n - 1);
}

#define PP_STR(x) PP_STR_I(x)
#define PP_STR_I(x) #x

static_assert(g(N), PP_STR(N));

これを #define N 10 としてコンパイルし，時間を計ります．

$ time g++ -std=c++0x -DN=10 sleep.cpp
sleep.cpp:14:1: error: static assertion failed: "10"

real    0m5.208s
user    0m0.000s
sys     0m0.031s

約 5 秒後に，"10" がエラーメッセージとして出力されました．N の値を変えて，時間を計ります．

N real (s) N real (s)
1 0.624 11 5.476
2 1.139 12 6.349
3 1.732 13 6.786
4 2.246 14 7.207
5 2.777 15 7.644
6 3.510 16 8.112
7 3.791 17 8.627
8 4.056 18 9.141
9 4.492 19 9.626
10 4.930 20 10.030

正の相関があるような気がしますね．では sleepsort.sh を書きましょう．

#!/bin/bash
function f() {
    g++ -std=c++0x -DN="$1" sleep.cpp
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

整数列を与えて実行します．

$ ./sleepsort.sh 2 3 5 3
sleep.cpp:14:1: error: static assertion failed: "2"
sleep.cpp:14:1: error: static assertion failed: "3"
sleep.cpp:14:1: error: static assertion failed: "3"
sleep.cpp:14:1: error: static assertion failed: "5"

要素数以上のプロセッサがあれば，それなりに動くんじゃないでしょうか (たぶん)．
アイデアはこちらから．

これを通じて知ったのですが，GCC は constexpr 関数の実行結果をメモ化するようです．

Phoenix で variant を返す条件演算子

C++ Boost

Boost.Phoenix の if で戻り値を返す - C++でゲームプログラミング
Phoenix の if_else は then 節と else 節の common_type を返しますが，それらの型が異なる場合は variant に収めて返すという戦略もあるでしょう．Phoenix ではそのような条件演算子もユーザーが書くことができます (Proto の知識は必要ありません)．
if2.hpp
https://gist.github.com/1130400
if2.cpp

#include <iostream>
#include <boost/phoenix/core/argument.hpp>
#include <boost/phoenix/core/value.hpp>
#include <boost/phoenix/operator/arithmetic.hpp>
#include <boost/phoenix/operator/comparision.hpp>
#include "if2.hpp"

int main()
{
    using namespace boost::phoenix;
    using namespace boost::phoenix::arg_names;

    // divide = \x y -> if y == 0 then Left "division by zero" else Right (x `div` y)
    auto const divide = if2(arg2 == 0, val("division by zero"), arg1 / arg2);

    std::cout << divide(54, 6) << '\n';
    // 9

    std::cout << divide(54, 0) << '\n';
    // division by zero
}

MPL でカリー化

C++ Boost

curryN<F> で，N-ary なメタ関数クラス F をカリー化します．

#ifndef CURRY_HPP
#define CURRY_HPP

#include <boost/mpl/bind.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/protect.hpp>
#include <boost/preprocessor/arithmetic/dec.hpp>
#include <boost/preprocessor/cat.hpp>
#include <boost/preprocessor/iteration/local.hpp>
#include <boost/preprocessor/repetition/enum_shifted_params.hpp>

template <class F>
struct curry1
  : F
{};

#define BOOST_PP_LOCAL_MACRO(n) \
template <class F> \
struct BOOST_PP_CAT(curry, n) \
{ \
    template <class A1> \
    struct apply \
    { \
        typedef \
            BOOST_PP_CAT(curry, BOOST_PP_DEC(n))< \
                boost::mpl::protect< \
                    BOOST_PP_CAT(boost::mpl::bind, n)< \
                        F, \
                        A1, \
                        BOOST_PP_ENUM_SHIFTED_PARAMS(n, boost::mpl::_) \
                    > \
                > \
            > \
        type; \
    }; \
}; \
/**/
#define BOOST_PP_LOCAL_LIMITS (2, BOOST_MPL_LIMIT_METAFUNCTION_ARITY)
#include BOOST_PP_LOCAL_ITERATE()

#endif

#include <boost/mpl/assert.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/plus.hpp>
#include "curry.hpp"

using namespace boost::mpl;

struct my_plus
{
    template <class A1, class A2, class A3>
    struct apply
      : plus<A1, A2, A3>
    {};
};

typedef curry3<my_plus> curried_my_plus;

BOOST_MPL_ASSERT_RELATION(
    curried_my_plus::apply<int_<1> >::type::apply<int_<2> >::type::apply<int_<3> >::type::value,
    ==,
    6
);

bind や protect に合わせて，::type せずに使う仕様にしています．

Variadic template template parameters に関して，ちょっとした疑問

C++

次のコードは gcc 4.6.0 と clang 2.9 でコンパイルの通るものです．

template <class T = void>
struct A {};

template <template <class ...> class U>
struct B
{
    U<> a;
};

B<A> b;

B<A> のインスタンス化中は U = A となっているわけですが，U<> が通るということは，U には A のデフォルト引数が使えるということです．この挙動があまり自然には思えません．FDIS からはこれを明示的に認める記述を見つけられなかったのですが，使ってよいものでしょうか．
気にしすぎかもしれませんが．