ラベル template metaprogramming の投稿を表示しています。 すべての投稿を表示
ラベル template metaprogramming の投稿を表示しています。 すべての投稿を表示

2014年10月13日月曜日

Pythonのmap関数をC++で作る試み

Pythonのmapが便利なので、同じように使えそうなmapをC++14で作ってみました。
ソースはこちら。(勉強がてらなので、雑然としてます。)
サンプル: https://github.com/muumu/lib/blob/master/sample/sample_functional.cpp
ライブラリ: https://github.com/muumu/lib/blob/master/functional.h
以下、作ったfn::mapのだいたいの使用感です。

それぞれの要素に関数やメンバ関数を適用したコンテナを作る

{
    vector<string> source = {"a?", "ab?", "abc?", "abcd?"};
    auto output = fn::map(source, fn::init);
    print(output); // {"a","ab","abc","abcd"}
}
{
    list<string> source = {"", "occupied", "", "occupied"};
    auto output = fn::map(source, &string::empty);
    print(output); // {true,false,true,false}
}
{
    array<string, 4> source = {"add", "sub", "mul", "div"};
    auto output = fn::map(source, util::upper);
    print(output); // {"ADD","SUB","MUL","DIV"}
}

違うデータ型になる関数はそのデータ型のコンテナに変換

{
    set<string> source = {"tea", "wine", "milk", "coffee"};
    auto output = fn::map(source, &string::size);
    print(output); // {3,4,6}
}
{
    multiset<string> source = {"tea", "wine", "milk", "coffee"};
    auto output = fn::map(source, &string::size);
    print(output); // {3,4,4,6}
}

キーとバリューを逆転したマップの作成

{
    map<string, int> source_map = {{"RED", 0}, {"GREEN", 1}, {"BLUE", 2}};
    auto reversed_map = fn::map(source_map, fn::swap<string, int>);
    print(reversed_map); // {{0,"RED"},{1,"GREEN"},{2,"BLUE"}}
}

vectorの出力を違うコンテナで受け取る

{
    multimap<string, int> src_map = {{"RED", 0}, {"RED", 0}, {"GREEN", 1}};
    auto func = [](const pair<string, int>& pair) {
        return pair.first + ": " + util::to_string(pair.second);};
    auto result = fn::map(src_map, func);
    print(result); // {"GREEN: 1","RED: 0","RED: 0"}
    set<string> result_set = fn::map(src_map, func);
    print(result_set); // {"GREEN: 1","RED: 0"}
}

2014年1月5日日曜日

C++で数値を2進数表記で出力する方法 (コンパイル時編)

実行時に数値のビット列を出力する方法を前回紹介しました。
http://code-mynote.blogspot.jp/2014/01/c2.html
ここでは、コンパイル時にビット列の文字列定数を用意したい場合(他のメタ関数に渡したり、実行時の文字列生成コストが無視できない場合など)を考えます。
自分の経験では今までそんな場合は無かったのですが、boost::mplの勉強を兼ねて下記のメタ関数を作ってみました。

#include <boost/mpl/string.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/bitwise.hpp>

namespace mpl = boost::mpl;

template <typename c>
struct bin_string {
    typedef typename boost::mpl::push_back<
        typename bin_string<typename mpl::shift_right<c, mpl::int_<1> >::type>::type,
        boost::mpl::char_<'0' + (c::value & 1)>
        >::type type;
};
template <typename T>
struct bin_string<mpl::integral_c<T, 0> > : boost::mpl::string<> {};

template <long long unsigned N>
struct bin_string_c : bin_string<mpl::integral_c<long long unsigned, N> > {};

処理内容

bin_stringがメタ関数の本体、bin_string_cが実行時に呼び出すメタ関数の転送役です。
templateを使用しているので見た目が少々違いますが、やってることは前回実装したto_bin_strと同じです。
数値を1つずつ右にシフトし、右端のビットを0か1の文字に変換することを数値が0になるまで(1のビットが無くなるまで)繰り返します。
再帰で実装しているので左端のビットが出力文字列でも左端となり、最後に文字列を反転する必要がありません。

使用例

メタ関数の返す文字列はmpl::c_str<>に渡すことでコンパイル時にconst char[]文字列が生成されます。
長いので、最初だけフルの名称で呼び出し、後はマクロ定義の呼び出しをしています。
下段のformat_bin_stringは表示桁を揃えたい場合に使用するメタ関数です。(ソースは後述)

#include <iostream>

namespace mpl = boost::mpl;

#define BINSTR(x) mpl::c_str<bin_string_c<x>::type >::value
#define FBINSTR(x, n) mpl::c_str<format_bin_string<bin_string_c<x>::type, n>::type>::value

int main() {
    const char x_c = 4;
    const unsigned y_c = 11;
    const int z_c = 103;
    const unsigned long long w_c = 4527856554780ULL;
    std::cout << mpl::c_str<bin_string_c<x_c>::type >::value << std::endl;
    std::cout << BINSTR(y_c) << std::endl;
    std::cout << BINSTR(z_c) << std::endl;
    std::cout << BINSTR(w_c) << std::endl;

    std::cout << mpl::c_str<format_bin_string<bin_string_c<x_c>::type, n>::type>::value << std::endl;
    std::cout << FBINSTR(y_c, n) << std::endl;
    std::cout << FBINSTR(z_c, n) << std::endl;
    std::cout << FBINSTR(w_c, n) << std::endl;
}

出力結果

100
1011
1100111
1000001111000111001010010000001001100011100
00100
01011
00111
11100

メタ関数format_bin_stringのソース。


template <typename Sequence1, typename Sequence2>
struct concat :
    mpl::insert_range<Sequence1, typename mpl::end<Sequence1>::type, Sequence2> {};

template <int N>
struct zero_string :
    mpl::push_back<typename zero_string<N-1>::type, mpl::char_<'0'> > {};
template <>
struct zero_string<0> : mpl::string<> {};

template <typename Sequence, int DigitNum, bool greater = (DigitNum >= mpl::size<Sequence>::value)>
struct format_bin_string {};

template <typename Sequence, int DigitNum>
struct format_bin_string<Sequence, DigitNum, true> :
    concat<
        typename zero_string<DigitNum - mpl::size<Sequence>::value>::type,
        Sequence
    > {};

template <typename Sequence, int DigitNum>
struct format_bin_string<Sequence, DigitNum, false> :
    mpllib::tail_n_c<Sequence, DigitNum> {};

mpllib::tail_n_cのソース。

#include <boost/mpl/size.hpp>
#include <boost/mpl/advance.hpp>
#include <boost/mpl/erase.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/less.hpp>
#include <boost/mpl/minus.hpp>

namespace mpllib {
namespace mpl = boost::mpl;

template <typename Sequence, typename N>
struct erase_head_n {
    typedef typename mpl::begin<Sequence>::type begin_iter;
    typedef typename mpl::advance<begin_iter, N>::type cut_iter;
    typedef typename mpl::erase<Sequence, begin_iter, cut_iter>::type type;
};

template <typename Sequence, typename N>
struct tail_n {
    typedef typename mpl::eval_if<
        mpl::less<mpl::size<Sequence>, N>,
        Sequence,
        erase_head_n<Sequence, mpl::minus<mpl::size<Sequence>, N> >
    >::type type;

};

template <typename Sequence, int N>
struct tail_n_c {
    typedef typename tail_n<Sequence, mpl::int_<N> >::type type;
};

}; // end of namespace mpllib

2014年1月4日土曜日

C++で64bit整数に対応したビットやビットマスク定数の生成

C++でビットの定数を書く時に、いちいち4096とか、(1 << 12)のように書くのは面倒です。
特に64bit整数の大きさのビットの場合、2305843009213693952と書かれても意味不明ですし、(1ULL << 62)も少々見づらいです。
さらにビットマスクを書く場合、2305843009213693951や((1ULL << 62) - 1)などとても見づらくなります
そこで今回、bit<N>::value、bitmask<N>::valueでアクセスできるビット定数を作ります。

コンパイル時ビット

まず、bit<N>::valueとして(1 << N)が取得できるメタ関数bitを用意します。
桁数が大きくて64bit整数が必要になった時も型を自動選択できるように、uint_selectorというメタ関数も用意しました。

#include <boost/mpl/if.hpp>
namespace mpl = boost::mpl;

const int BITS_PER_BYTE = 8;

template <int DigitNum>
struct uint_selector :
    mpl::if_c<
        (DigitNum > sizeof(unsigned) * BITS_PER_BYTE),
        unsigned long long,
        unsigned
    > {};

template <int DigitNum, typename T = typename uint_selector<DigitNum>::type>
struct bit {
    typedef T type;
    static const T value = (static_cast<T>(1) << (DigitNum - 1));
};
template <>
struct bit<0> {
    enum {value = 0};
};

型は、明示的にも指定できるようにしてあります。

実行サンプル

typedef unsigned long long ull_t;

int main() {
    const auto bit1 = bit<3>::value;
    const ull_t bit2 = bit<5, ull_t>::value;
    const auto bit3 = bit<64>::value;
    std::cout << bit1 << std::endl;
    std::cout << bin_string<bit1>::str() << std::endl;
    std::cout << bit2 << std::endl;
    std::cout << bin_string<bit2>::str() << std::endl;
    std::cout << bit3 << std::endl;
    std::cout << bin_string<bit3>::str() << std::endl;
}

なお、bin_string::str()は2進数表記のstd::stringを生成する自作の関数です。

実行結果

4
100
16
10000
9223372036854775808
1000000000000000000000000000000000000000000000000000000000000000

コンパイル時ビットマスク

次にこれを利用し、bitmask<N>::valueとしてビットマスクを取得できるメタ関数bitmaskを用意します。

template <int DigitNum, typename T = typename uint_selector<DigitNum>::type>
struct bitmask {
    typedef T type;
    static const T value = bit<DigitNum + 1>::value - 1;
};

bitと同様に、型は明示的にも指定できるようにしてあります。

実行サンプル

typedef unsigned long long ull_t;

int main() {
    const auto mask1 = bitmask<3>::value;
    const ull_t mask2 = bitmask<5, ull_t>::value;
    const auto mask3 = bitmask<64>::value;
    std::cout << mask1 << std::endl;
    std::cout << bin_string<mask1>::str() << std::endl;
    std::cout << mask2 << std::endl;
    std::cout << bin_string<mask2>::str() << std::endl;
    std::cout << mask3 << std::endl;
    std::cout << bin_string<mask3>::str() << std::endl;
}

実行結果

7
111
31
11111
18446744073709551615
1111111111111111111111111111111111111111111111111111111111111111

いずれもコンパイル時に定数を生成するメタ関数なので、通常の定数と同じく実行時のコストはゼロで使用することができます。