世界の隅の開発室

 

◎  スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

◎  割と汎用的なstd::tuple活用モジュールの例をいくつか 

std::tupleってなんぞ

無限個の型を持つデータ構造のいわゆるタプル(そのまま)
動的型付けにはとてもよく見られるデータ構造だが、静的型付けのC++でタプルを扱うのはとても面倒くさい。

再帰的に展開したり、メタなことしたり、そんなことにいちいち補助関数を作っていては時間と労力の無駄である。

特にライブラリアンみたいな人には、汎用的にタプルを扱う技術が必須になる、と思う。

というわけで、私がノリと勢いで作った汎用的なタプル専用の補助関数を紹介してみる。
正直どっかで想定しないコピーなどが発生してそうだけれど、まあ、こういう風にやると割とジェネリックになるよ、くらいに留めて読んでほしい。

サンプルのために用意した関数オブジェクトチルドレンと、テンプレート関数オブジェクトを紹介する。


struct A{
public:
A(int init):value(init){}
int value;
void print(){ std::cout << \"I am A, value is \" << value << std::endl; }
};

struct B{
public:
B(int init):value(init){}
int value;
void print(){ std::cout << \"I am B, value is \" << value << std::endl; }
};

struct C{
public:
C(int init):value(init){}
int value;
void print(){ std::cout << \"I am C, value is \" << value << std::endl; }
};

struct f{
template<typename T>
int operator()(T& object,int result, int n){
object.value = (object.value * n)+result;
object.print();
return object.value;
}

template<typename T>
int operator()(T& object,int n){
object.value *= n;
object.print();
return object.value;
}

};

なんか自己紹介とvalueをプリントするだけの関数オブジェクトだ。

フリー関数は、valueをn倍、またresultも受け取った場合は加算したりするものだ。ついでに型情報を自己紹介する。

さて、こいつら関数オブジェクトは同じprintメソッドを持っている。
オブジェクト同士に言語的の関係性はないが、インターフェースが共通のためダックタイピングを利用することができる。

タプルとかはそういうのが得意らしい。仕方ないので使いづらいこいつを一つ腕試ししてやろう。

前方展開

タプルのサイズをNとして
タプルの0~N-1の要素を取り出し、逐次関数にぶん投げる補助関数。


template<size_t index, size_t end, bool isEnd = index == end>
struct forwardExecute;

template<size_t index, size_t end>
struct forwardExecute<index, end, false>
{
template<typename Tuple, typename F, typename... Args>
static void Execute(Tuple&& tuple, F&& f, Args&&... args)
{
f(std::get<index>(tuple),std::forward<Args>(args)...);
forwardExecute<index+1,end>::Execute(
std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<Args>(args)...
);

}
};

template<size_t index, size_t end>
struct forwardExecute<index, end, true>
{
template<typename Tuple, class F, typename... Args>
static void Execute(Tuple&& tuple, F&& f, Args&&... args)
{
//end
}
};

template< std::size_t begin, std::size_t end,typename Tuple, typename F,typename... Args>
void forwardExecuteApply(Tuple&& tuple, F&& f, Args&&... args)
{
forwardExecute<begin, end>::Execute(
std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<Args>(args)...
);
}


割とよくあるイディオムだとは思う。
データ構造から関数から引数までテンプレートなため、まぁ汎用的と言える。

使ってる技術はC++11ではメジャーなものだ。
1. 可変長引数テンプレート
2. ムーブセマンティクス

この辺りはたぶんここで説明するより、C++erたちのブログを見た方が早い。

使ってみる。


int main(){
A a(1);
B b(2);
C c(3);

auto tuple = std::make_tuple(a,b,c);

forwardExecuteApply<0,3>(tuple,f(),2);

return 0;
}


実行結果

I am A, value is 2
I am B, value is 4
I am C, value is 6

全部に引数の2がかけられて、forwardに展開されている。

二分展開


template<size_t begin, size_t end, bool isEnd = begin + 1 == end>
struct partExecute;

template<size_t begin, size_t end>
struct partExecute<begin, end, true>
{
template<typename Tuple, typename F, typename... Args>
static void Execute(Tuple && tuple, F&& f, Args&&... args)
{
f(std::get<begin>(tuple),std::forward<Args>(args)...);
}
};

template<size_t begin, size_t end>
struct partExecute<begin, end, false>
{
template<typename Tuple, typename F, typename... Args>
static void Execute(Tuple&& tuple, F&& f, Args&&... args)
{
partExecute<begin, (begin + end) / 2>::Execute
(std::forward<Tuple>(tuple), std::forward<F>(f), std::forward<Args>(args)...);

partExecute<(begin + end) / 2, end>::Execute
(std::forward<Tuple>(tuple), std::forward<F>(f), std::forward<Args>(args)...);
}
};

template<std::size_t begin, std::size_t end,typename Tuple, typename F, typename... Args>
void partExecuteApply(Tuple&& tuple, F&& f, Args&&... args)
{
partExecute<begin, end>::Execute(
std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<Args>(args)...
);
}

プログラム停止性問題?
なんかそんな感じの問題が証明されているように、コンパイラはコンパイルが終わることを立証することができないため、コンパイル時再帰に制限をかけている。
C++11では16とか32とかそこらへんだった気がするが、そんなちっこい値だと非常に困るので、二分再帰してやることにする。
こうするとlog2(N)しか再帰しなくなるので、よほど大きくなければだいたい処理できる。

二分再帰をしているところを、適当に並列化すれば速度も向上させることができる。
ただし、それには並列化の条件を満たしている必要がある。

前方展開と特に変わったことはしてない。

実行してみる。


int main(){
A a(1);
B b(2);
C c(3);

auto tuple = std::make_tuple(a,b,c);

partExecuteApply<0,3>(tuple,f(),2);

return 0;
}


実行結果

I am A, value is 2
I am B, value is 4
I am C, value is 6

再帰展開


/* recursive and propagate return value. */
template<std::size_t index>
struct propagationTuple{
template<class Tuple, class F, class R,typename... Args>
static auto Execute(Tuple&& tuple,
F&& f,
R&& result,
Args&&... args){
return propagationTuple<index-1>::Execute(std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<F>(f)(std::get<index>(tuple),
std::forward<Args>(args)...,
std::forward<R>(result)
),
std::forward<Args>(args)...
);
}
};

template<>
struct propagationTuple<0>{
template<class Tuple,class F, class R,typename... Args>
static auto Execute(Tuple&& tuple,
F&& f,
R&& result,
Args&&... args)
{
return std::forward<F>(f)(std::get<0>(tuple),std::forward<Args>(args)...,std::forward<R>(result));
}
};

template<std::size_t index,class Tuple, class F, typename... Args>
auto propagationTupleApply(Tuple&& tuple,F&& f, Args&&... args){
return propagationTuple<index-1>::Execute(std::forward<Tuple>(tuple),
std::forward<F>(f),
std::forward<F>(f)(std::get<index>(tuple),std::forward<Args>(args)...),
std::forward<Args>(args)...
);
}


使った技術
1. expression型推論(decltype)
2. 関数返り値推論
3. タプルのサイズとったりとか参照外したりみたいなメタ関数

_tがついてるメタ関数はテンプレートエイリアスによって::typeが省略されたものだ。
C++14から追加されている。最the高。

はぁ、私はただ後方展開しつつ、計算結果を伝播していくモジュールを作りたかっただけなのにどうしてこうなった...

ま、まぁこういうコードは大概ブラックボックス化するし、多少はね?

実行してみる。


int main(){

A a(1);
B b(2);
C c(3);

auto tuple = std::make_tuple(a,b,c);

std::cout << backPropagationApply(tuple,f(),2) << std::endl;

return 0;
}

実行結果

I am C, value is 6
I am B, value is 10
I am A, value is 12
12

n倍されかつ、結果が後方伝播し加算されている。
A*2 + B*2 + C*2といった感じ。

まぁ、それっぽく動いてるんじゃなかろうか。

ここまではあくまで実装のサンプルで、これらが万能ということでは決してない。
つまり総合的に何が言いたいかというと、テンプレート特殊化と可変長引数テンプレートあたりをうまく使えば、ジェネリックなタプル活用コードか書けるってこと。

このクソコードを見て吐き気を催してしまった方は是非添削をお願いしたいものだ。
自分自身リファクタリングとインデントを放り投げるくらい面倒になった。反省。
スポンサーサイト

◎  静的ポリモーフィズムの安全で簡単な実装 -動的から静的にしてパフォーマンス向上- 

動的ポリモーフィズムの確認



C++はオブジェクト指向言語です。
当然、オブジェクト指向の要素「ポリモーフィズム」を、言語仕様としてサポートしています。

C++では一般にポリモーフィズムは「動的ポリモーフィズム」を指し、実行時に基底クラスから派生クラスへと振る舞いを変化させます。


#include<iostream>

class Base{
public:
virtual void print(){ std::cout << \"Base\" << std::endl; }
virtual ~Base()=default;
};

class Super : public Base{
public:
void print() override{ std::cout << \"Super\" << std::endl; }
};

int main(){
Base* array[2] = {new Base,new Super} ;
array[0]->print();
array[1]->print();
delete array[0]; delete array[1];
return 0;
}


このプログラムを実行すると
Base
Super
と出力されます。

Baseポインタで管理されているインスタンスですが、片方の実体はその継承クラスSuperであるため、virtualで定義された仮想関数の機能によりSuperのprint()が実行されます。

このように、Base*ポインタとして扱われているインスタンスが、実際の仮想関数呼び出し時に本来の姿を取り戻すこの性質を動的ポリモーフィズムと呼びます。
動的ポリモーフィズムのデメリット

このように、とても強力な動的ポリモーフィズムですが、欠点も多くあります。

代表的なものとして、スタックの圧迫、関数呼び出しのオーバーヘッドの増加、インライン展開が不可能、などが挙げられます。

というのも、C++がこの動的ポリモーフィズムを実装するために使っているvtableが原因なのです。
これは仮想関数のポインタ解決を行うためのテーブルで、各インスタンスはそのテーブルを保持し、そのテーブルから仮想関数の呼び出しをする機構になっています。

各インスタンスが関数ポインタテーブルを持つことでスタックを圧迫し、
関数ポインタテーブルで関数を間接参照することでオーバーヘッドが生じ、
終いの果てには実行時まで呼び出す関数が分からないためにインライン展開ができなくなる、というパフォーマンスに関する多くのディスアドバンテージを抱えてしまいます。

これを解決するために、多くのC++ユーザは動的ではない静的なポリモーフィズムでの実装を推奨しています。
つまり、コンパイル時に呼び出す関数を解決するのです。

まぁ、テンプレートを使うんですけど。
静的ポリモーフィズムの実装

継承ではなくテンプレートを使うだけです。


#include<iostream>

class myclass1{
public:
void print(){ std::cout << \"myclass1\" << std::endl; }
};

class myclass2{
public:
void print(){ std::cout << \"myclass2\" << std::endl; }
};

template<class T>
class Printer{
T obj;
public:
void print(){
obj.print();
}
};

int main(){
Printer<myclass1> a;
Printer<myclass2> b;

a.print();
b.print();

return 0;
}


非常に簡単ですが、色々と問題があります。

まず、動的ならばできるはずの、一つの配列で複数の種類のインスタンスを管理することができません。
テンプレートはクラスを自動で展開しているだけなので、Printer<myclass1>とPrinter<myclass2>は完全に別のクラスですから。

また、このままだとテンプレート引数は何を渡していいのか分かりません。
こういった場合変なクラスを渡してしまい読み辛いエラーが返ってきたりします。

継承をうまく使って「インターフェースの共通化」を行い、ついでにちょこっとメタなことをして「変なクラスを弾く」ようにしてみましょう。


#include<iostream>

template<class T>
class _Printer; //prototype

template<class T>
class Interface; //prototype

template<bool is_base,class T>
struct Dummy;

template<class T>
struct Dummy<true,T>{ // T is extends Interface<T>
using type = _Printer<T>;
};

template<class T>
using Printer = typename Dummy<std::is_base_of<Interface<T>,T>::value,T>::type;

template<class T>
class Interface{
public:
void print(){ static_cast<T &>(this)->print(); }
};

class myclass1 : Interface<myclass1>{
public:
void print(){ std::cout << \"myclass1\" << std::endl; }
};

class myclass2 : Interface<myclass2>{
public:
void print(){ std::cout << \"myclass2\" << std::endl; }
};

class myclass3{
void print(){ std::cout << \"myclass3\" << std::endl; }
};

template<class T>
class _Printer{
T _obj;
public:
void print(){ _obj.print(); };
};

int main(){

Printer<myclass1> a;
Printer<myclass2> b;

//Printer<myclass3> c; //compile error

a.print();
b.print();

return 0;
}


Interfaceクラスを継承する際、動的で良いのなら純粋仮想関数を定義するところですが
ここでは、テンプレート引数でキャストしたthisポインタに定義したいインターフェース呼び出しをしています。

これによりインターフェースクラスとしての性質を持つことができます。

このインターフェースクラスのテンプレート引数は、継承したクラス自身の型で、コードを見れば分かりますが

class myclass1 : Interface<myclass1>{
///

のように宣言します。

そして、myclass1と2を静的ポリモーフィズムで扱うことができます。

また、myclass3のようなインターフェースは同一でもInterfaceクラスを継承していない不正なクラスを弾くために、メタ関数とstd::is_base_ofを使っています。

テンプレートエイリアスをかけてDummyメタ関数をクッションするようにし、テンプレート引数Tの型がInterfaceを継承しているかどうかを検査します。

もしstd::is_base_ofの結果がtrueならば、特殊化テンプレート最優先の規則に従い、trueで特殊化されたDUMMYが展開されます。
逆に、falseだった場合(継承していない場合)、未定義のテンプレートクラスを展開しようとするため、エラーを吐きます。

Dummyが無事展開されれば、Dummyは隠蔽した_Printerクラスをtypedefし、無事テンプレートエイリアスのPrinterは目的のクラスのシンボルとなります。

こんな感じでしょうか。

全体的に、テンプレートに理解があればそんなに難しくはないと思いますが、一方その恩恵はかなり大きいので、もし動的から静的へ置換可能である場合には是非試してみると良いと思います。

残念ながら、動的ポリモーフィズムの特徴の一つ、基底ポインタで複数の派生クラスインスタンスを扱うのと同じことを、静的に行う方法は分かりませんでした。

多分無理かな? わかりません、C++は奥が深いですからね。

では。

◎  std::remove_ifでメモリリークした話 

どうも。

ちょっと、std::remove_ifでメモリリークを起こす件について軽く。

std::remove_ifは、STLアルゴリズムの一つで、コンテナを受け取り、3つ目の引数にとった関数オブジェクトを使って、「有効な要素」を前に詰めて、無効な要素の先頭イテレータを返すような仕様になっています。

使い方はこんな感じです。


std::vector<int> arr = {1,5,6,4,3,8};

std::remove_if(arr.begin(),arr.end(),[](int n){return n > 3;});


このケースですと、ラムダ式の返り値がfalse、つまり有効な要素の数が2つですので
1と3が前に詰められ、それ以降は無効な要素であるため、begin+2...つまり3つ目を指すイテレータが返ってきます。

そのため


std::vector<int> arr = {1,5,6,4,3,8};

arr.erase(std::remove_if(arr.begin(),arr.end(),[](int n){return n > 3;}),arr.end());


と書くと、無効イテレータからendイテレータまでが削除されて、晴れて1と3のみの要素を持つコンテナになります。


まあ、ここまではいいんですが、ではこれを動的要素にするとどうなるでしょうか。


std::vector<int*> arr = {new int(1),new int(5),new int(6),new int(4),new int(3),new int(8)};

auto invalidIt = std::remove_if(arr.begin(),arr.end(),[](int* n){return *n > 3;});
for(auto it = invalidIt; it<arr.end(); it++){
delete *it;
}

arr.erase(invalidIt,arr.end());



当然動的要素ですので、eraseする前にヒープから解放してあげないといけません。
なので、forでdeleteしています。
ちゃんと動くように見えるんですが
このコード、メモリリーク起こします。

その原因は、remove_ifの動作の厳密な正体にありまして。

この関数、無効な要素の先頭イテレータを返す、という動作をすると聞いたので
てっきり有効な要素を前に、無効な要素を後ろに並べ替える関数かと思っていたんですね。

しかし、実際には、たんなる有効要素の前進代入でして。

つまり、先ほどのint*ベクターの関数実行前と実行後の中身は

実行前
1,5,6,4,3,8

期待していた動作 1,3,5,6,4,8
実際の動作 1,3,6,4,3,8


というわけで、実際の動作を見て頂ければ分かる通り、スワップやソートでもなんでもなく、代入だったんですね。
コスト的に見れば当然なんですが、すっかりハマってしまいまして。

つまり、この関数実行後のコンテナの3番目〜6番目に対してdeleteをかけると、本来有効な要素である3に対しても解放処理を行ってしまい、結果的に2番目に位置する要素が無効なポインタになり、メモリリークを起こす、といった次第です。

そのため、deleteないし解放に関するクラスメソッドを実行する際は十分に注意する必要があります。

修正案としては、無効な要素にdeleteをして、nullptrを突っ込んだ後、remove_ifでそのnullptrを検知する、という感じですね。

コードも載ってけておきます。



for(int *n: arr){
if(*n > 3){
delete n;
n=nullptr;
}
}

arr.erase(remove_if( arr.begin(), arr.end(), [](int* n){return n==nullptr;} ),arr.end());





ではでは。

◎  C++11のTemplate Aliasesで、TTPやTMPがちょこっとだけわかりやすくなった気がする 

TTP = Template Template Parameters
TMP = Template Meta Programming
です。特に前者は分かり辛くてすいません


C++11から、Template Ailiasesというものが導入されました。

テンプレート機能が使えるtypedefと言った方が最も分かりやすいでしょうが、typedefよりも色々できることが増えています。
using構文というものです。

まずtypedefの置換としての扱い方から。
例えば以下のコードは同じ意味を持ちます。


//typedef int Type; 古来から伝わるシンタックス

using Type = int; //新たなシンタックス(こっちの方が直感的)



typedefはC言語からずっとお世話になっている構文ですが...
まず以下のようなコードを考えます。



typedef std::vector<int> vec_int;
vec_int a;



このコードは合法です。vec_intはstd::vector<int>のエイリアスとなります。
では次のコードはどうか?


typedef std::vector aliasVec;
aliasVec<int> vec;


これはコンパイルエラーとなります。
typedefはテンプレートをサポートしていません。
単なる置換じゃなくてエイリアスですから。

この問題も、usingを使えば解決します。


template<typename T>
using aliasVec = std::vector<T>;
////////////////
aliasVec<int> vec;


これでテンプレートクラスのエイリアスもつくれます。
これが可能になると、定数や型のテンプレート引数の埋め込みが可能になります。


template<typename T,typename U>
class myclass{
//なんか凄い処理
}

template<typename T>
using BoolMyClass = myclass<T,bool>; //引数二つ目はbool使うことが多い

///////

BoolMyClass<int> a; //myclass<int,bool>
BoolMyClass<double> b;
myclass<int,int> c; //引数二つ目を使う時は元のクラス名を使えば良い


この技法で、コンテナに独自のアロケーターを仕込んでも普段と同じ感覚で使うことができたりします。


で、こっからが本題なのですが
今まで少しばかりややこしい構文であった
Template Template Paramaters
Template Meta Programming
が、少しだけ分かり易く書けるようになります。


まず、Template Template Paramatersの基本から。


template<class T>
struct TemplateContainer{
T<int> container;
}

template<typename T>
class myclass{
};

////////////

TemplateContainer<myclass> a; //error!



あれ、typedefでも似たようなことをやったような。
テンプレートクラスのシンボル名だけを引数にとるようなテンプレートの使い方は違法なんですね。


このコードを動くようにするには
Template Template Paramatersという、テンプレート引数に「型」を取るのではなく、「テンプレートクラス」を取るような工夫を施す必要があります。


template <template <typename> class Container>
struct TemplateContainer{
T<int> container;
}



こうすることで、TemplateContainerという宣言が合法になります。

しかし、このTemplate Template Paramaters、クラスを引数に取るということで、当然その条件として引数の型が一致していなければなりません。

template <template <typename> class Container>

この宣言はテンプレート引数1つを取るクラスのテンプレート引数の宣言ですので(ややこしい)
デフォルトテンプレート引数が設定されている
std::vectorなどを渡すと、見かけ上同じ型に見えても、引数不一致でエラーを吐いてしまいます。

template <class T, class Allocator=allocator<T> > 
//std::vectorのテンプレート宣言、一方はデフォルト引数があるけども、実際の型としては引数を二つとる


これを解決する為に、引数側でAllocatorのデフォルト引数を設定する、という方法があります

template <template<typename T, class Allocator=std::allocator<T> > class TemplateContainer>

しかしこれだとAllocatorを使い分けたい時に困ります。
std::vectorではmyallocatorを、std::listではstd::allocatorを...といった状況ですかね。
あと私のような雑魚C++erには非常に分かり辛い構文になってしまっています。


ここで、先ほどのTemplate Aliasesを使うと
どうしてもコンテナの型はテンプレートクラス側で決めたいのに、アロケータだけは呼び出しもとで決定したい....!!
という超変態さんの欲求を満たすことができます。


template <template<typename> class T>
struct TemplateContainer{
T<int> container;
};

template <typename T>
using vector = std::vector<T, MyAllocator<T>>;
/////////////////////////
TemplateContainer<vector> a;




これで解決ですね!


また、Template Meta Programmingでよく見かける、ローカルエイリアス宣言された型
あるいは、ローカル定義されたクラスをスコープ参照する構文、これに不便を感じたことはないでしょうか。

もっとも身近なのは、コンテナのイテレータ型の取り出しでしょうか?

std::vector::iterator

ってやつですね。(型推論が追加されて使う機会も減りましたが)
今までも、typedefして簡単に使う工夫はされてきましたが、前述の通りtypedefはテンプレートに対応していないので、

typedef std::vector<int>::iterator vecIntIt;

のように、せっかくのテンプレートクラスに型を限定してしかシンタックスを宣言できませんでした。

しかし、Template Aliasesを使うことで、


template<typename T>
using vecIt = typename std::vector<T>::iterator;
/////////////
vecIt<int> = vec.begin(); //vec宣言済み



このように、複雑なイディオムを簡略化することができます。
あ、このときはtypenameで型であることを明示してくださいね。メタプログラミングに慣れている方なら忘れることはないと思いますが。


これらを更に応用して、より美しいTMPコードが書けるようになります。
以下は、引数に取った二つの型のうち、小さい方を選択するTMPコードになります。




template<bool b,class T,class U>
struct smaller_class{
typedef U type;
};

template<class T,class U>
struct smaller_class<false,T,U>{
typedef T type;
};

class myclass01{
public:
void operator()()const{
std::cout << \"実体化されたのは01でした\" << std::endl;
}
};

class myclass02{
public:
double a;
void operator()()const{
std::cout << \"実体化されたのは02でした\" << std::endl;
}

};

int main(){
smaller_class<sizeof(myclass01)>=sizeof(myclass02),myclass01,myclass02>::type()();
}



このコードを実行すると当然doubleの要素を持つmyclass02の方が大きいので

実体化されたのは01でした

と表示されます。


ですが、大変気持ち悪いと思います。TMPは嫌いです。
ただ、usingを使うと、少しだけ使い方が分かり易くなります。


template<typename T,typename U>
using smallClass = typename smaller_class<sizeof(T)>=sizeof(U),T,U>::type;

int main(){
smallClass<myclass01,myclass02>()();
}




こうしてあげることで、この呼び出しは先ほどのものと全く等価になります。

他にも色々メタプログラミングにおけるTemplate Aliasesの用途はたくさんあります。

どんどん気持ち悪くもどこか美しい、そんなTMPコードを書いていきましょう。


今回は長くなりましたがこの辺で。



back to TOP

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。