メタ関数の再帰停止の方法についての質問です.
最大公倍数を求めるメタ関数を作ろうとして引数をintに固定したものはすぐ作れたのですが
引数を任意の整数にしたものを作ろうとしたところ,いろいろな方法を試みましたがどれもだめで結局以下のようにしました.
template<typename IntegerT, IntegerT Rhs, IntegerT Lhs>
struct gcd;
template<int Rhs, int Lhs>
struct gcd<int, Rhs, Lhs>
{
typedef int integer_type;
typedef gcd<integer_type, Rhs, Lhs> type;
typedef integer_type value_type;
static const value_type value =
gcd<integer_type, Lhs, Rhs % Lhs>::type::value;
};
template<int Rhs>
struct gcd<int, Rhs, 0>
{
typedef int integer_type;
typedef gcd<integer_type, Rhs, 0> type;
typedef integer_type value_type;
static const value_type value = Rhs > 0 ? Rhs : -Rhs;
};
template<long long Rhs, long long Lhs>
struct gcd<long long, Rhs, Lhs>
{
typedef long long integer_type;
typedef gcd<integer_type, Rhs, Lhs> type;
typedef integer_type value_type;
static const value_type value =
gcd<integer_type, Lhs, Rhs % Lhs>::type::value;
};
template<long long Rhs>
struct gcd<long long, Rhs, 0ll>
{
typedef long long integer_type;
typedef gcd<integer_type, Rhs, 0ll> type;
typedef integer_type value_type;
static const value_type value = Rhs > 0ll ? Rhs : -Rhs;
};
しかし,この方法だと考えられる整数全てに対して特殊化を定義せねばならず何のためにテンプレートを使っているのかわかりません.
テンプレートのインスタンス化の順序を考えてみるとコンパイル時に再帰を停止するための条件が普通に考えたものとは異なるように思うのですが,どのようにすればもっと簡単に一般の整数型(short,long等)に対してメタ関数を定義できるでしょうか?
A 回答 (5件)
- 最新から表示
- 回答順に表示
No.5
- 回答日時:
とりあえず「多倍長整数」は「渡せたとしてもコンパイル時に計算できないから無意味」な気がします. 「整数のラッパ」は渡せるけど, 結局のところ「最も長い整数」で計算しちゃえば問題にならないと思いますよ.
メタ関数として定義するなら
template <typename Int, Int Lhs, Int Rhs> struct gcd;
template <long long Lhs, long long Rhs> struct gcd<long long, Lhs, Rhs> {
// それなりに
};
template <long long Lhs> struct gcd<long long, Lhs, 0LL> {
// それなりに
};
template <typename Int, Int Lhs, Int Rhs> struct gcd {
typedef Int value_type;
static const value_type value = gcd<long long, Lhs, Rhs>::value;
};
という形で, 一度 long long として計算してから適切な型にキャストしなおせばいいと思う.
あと, 次の C++ では constexpr が導入されるので
template <typename Int>
constexpr Int gcd(Int Lhs, Int Rhs)
{
return (Lhs < 0) ? gcd(Rhs, -Lhs) : (Rhs < 0) ? gcd(Lhs, -Rhs) : (Rhs == 0) ? Lhs : gcd(Rhs, Lhs % Rhs);
}
のような感じになるかと. ただ, 型の問題は難しいなぁ. 卑怯だけど
template <typename IntA, typename IntB>
constexpr auto gcd(IntA Lhs, IntB Rhs) -> decltype(Lhs+Rhs)...
のようにする?
No.4
- 回答日時:
No.3 です。
> 作りたかったのはコンパイル時に最大公倍数を計算するものでした.
そういう意図でしたか。なるほど。やっとわかりました。
C++のテンプレートは、引数に合わせた関数を(演算子も含めて)呼び出すだけなので、それは困難かと思います(少なくとも、私にはできません)
そして、関数呼び出しが絡むので、普通に書いただけではコンパイル時に計算してくれるほどの最適化も期待できません。
これだけでは何なので、boost の gcd がわざわざテンプレートになっているのは、多倍長整数のようなものを想定しているからです。
これとは別に、rational (有理数)クラスがあって、これが、内部的に分数表現を用いたクラスになっています。
gcd は、約分のために、このクラスから頻繁に呼び出されるわけですが、分母分子とも64bit幅とかではなく、多倍長(もしくは、任意精度)整数が使用可能な構成になっています。
失礼しました。
私はコンパイラの挙動等わからないことがいっぱいあるのでうまく説明できないところがあり,ご迷惑をおかけしたかも知れません.ただインスタンス化の順序で追っかけて考えたときの挙動とは異なる挙動をしているように思い,そこが良くわからないのでメタ関数を作ろうとすると試行錯誤的な作り方になってしまい先を見通すことがうまくできないでいます.
有理数の通分と似たことになりますが,実数の整数化に最大公倍数を利用しようと思っていたのでご紹介のBoostの関数が使えそうです(自分で作ったものよりそちらをつかったほうが良いでしょう)いろいろとお教えいただきどうもありがとうございます.
メタ関数を作るときの考え方については引き続き教えていただけるとありがたいです.
No.3
- 回答日時:
失礼しました。
再帰ですね。こんなのでは(Boost のほとんど丸写し)
再帰呼び出しの際の引数の型を確定する必要があるので、いちいち、同じ型の変数で一度受けるのがミソ。
#include <iostream>
// Greatest common divisor for rings (including unsigned integers)
template < typename RingType >
RingType
gcd_euclidean
(
RingType a,
RingType b
)
{
// Avoid repeated construction
#ifndef __BORLANDC__
RingType const zero = static_cast<RingType>( 0 );
#else
RingType zero = static_cast<RingType>( 0 );
#endif
RingType c;
if ( a == zero )
return b;
else
{
c = a % b;
return gcd_euclidean(c, b);
}
}
int main()
{
unsigned short a = 1001;
unsigned short b = 13;
std::cout << gcd_euclidean(a, b) << "\n";
return 0;
}
この回答への補足
Boostにあるというのは知りませんでした.
わざわざ作ることは無いですね.
実は実行時関数版は別に作りました(車輪の再発明でしたが)
作りたかったのはコンパイル時に最大公倍数を計算するものでした.
私がよく理解していないところがあるかも知れませんが,このようにした場合
引数に定数を与えても実際の計算がなされるのが実行時ではないかと思いましたので
それとは別にメタ関数版を作ろうとしたわけです.
本当は引数が定数の関数は全てコンパイル時に計算して定数に置き換えるという最適化
をしてくれるなら良いわけですがそこが良くわかりませんでした.
でも私の作ったのは関数オブジェクトで関数ではありません.
関数オブジェクトだと使用時にインスタンスが必要なので実行時にしか計算できないと思うのですが,関数だと引数が定数のときコンパイル時に結果の定数に置き換えてくれるとかいうことはあるのでしょうか?
No.2
- 回答日時:
たとえば、Boost というライブラリの中には、汎用的な整数型に対応した gcd() があります。
http://www.boost.org/doc/libs/1_44_0/boost/math/ …
にあるヘッダの、
namespace detail
の中の、
gcd_euclidean()
がその実体です。
このソースの中でも、
RingType zero = static_cast<RingType>( 0 );
のように、あらかじめゼロを定義して使っていたりしますが。
これをそのまま使って、
#include <iostream>
// Greatest common divisor for rings (including unsigned integers)
template < typename RingType >
RingType
gcd_euclidean
(
RingType a,
RingType b
)
{
// Avoid repeated construction
#ifndef __BORLANDC__
RingType const zero = static_cast<RingType>( 0 );
#else
RingType zero = static_cast<RingType>( 0 );
#endif
// Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]
while ( true )
{
if ( a == zero )
return b;
b %= a;
if ( b == zero )
return a;
a %= b;
}
}
int a;
double b = 0.11;
int main()
{
unsigned short a = 1001;
unsigned short b = 13;
std::cout << gcd_euclidean(a, b) << "\n";
return 0;
}
だけでも、ちゃんと動作することがわかります。
このあたり、少しずつ確認してみるというのは、どうでしょう。
ちなみに C++ のテンプレートは、引数の型から適切な型を判断してくれますから、実行時に型を指定する必然性はないです。
(Boost のものも、実行時には、gcd_euclidean(1001, 13) だけですね)
No.1
- 回答日時:
gcd の引数をどうするか (型を明示するかどうか) という問題はありますが, 型を含めて 3引数にするなら long long だけ特殊化すればいいんじゃないかなぁ?
「long long より大きい型」を見なくていいなら, それ以外は「long long で計算してから適切にキャスト」すればいいだけだし.
この回答への補足
メタ関数については最近使い始めたばかりでよく理解できていないのですが
たとえば型として多倍長整数とか整数のラッパーのようなクラスを使うことは
できるのでしょうか?
素人目にはユーザー定義の型をコンパイル時に使ってくれるのかななどと思ってしまいます.
もしそのような型に対してもメタ関数が定義できるなら,ユークリッドの互除法が
使える任意のクラスに対して最大公倍数をいっぺんで定義できて便利かなと思いました.
もっともメタ関数として最大公倍数が必要かどうか疑問ですけど.
いろいろ試してみる段階で0を型にキャストしたものでの部分特殊化でできないだろうか
と思って以下のようにやってみたことがあります.
template<typename IntegerT, IntegerT Rhs, IntegerT Lhs>
struct gcd
{ ... }
template<typename IntegerT, IntegerT Rhs>
struct gcd<IntegerT, Rhs, static_cast<IntegerT>(0)>
{ ... }
これはstatic_cast<IntegerT>(0)がテンプレートパラメータIntegerTに依存しているので
エラーとなってしまいます.
しかし,考えてみるとインスタンス化の段階でIntegerTは具体的な型(intやlong等の)が
決まっているはずなので何故できないんだろうと思ってしまいます.
このあたりのことがわからないので質問しました.
まだ最終解決には至っていないですが考えてみるとあなたの示唆なさったようにlong longに対して定義しておけばとりあえず他の型について定義しなくてもよいわけです.
なので取りあえずはそのように対応することにしました.
ご教唆いただきどうもありがとうございます.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 野球 野球のポジションでlhsやrhsって何ですか? 3 2022/08/26 01:01
- JavaScript プログラムがうまく動きませんレビューお願いします 1 2022/07/10 05:08
- HTML・CSS ただいま勉強始めたての初心者です。フォームを縦並べにしたいです。 2 2022/11/20 17:18
- JavaScript javascript作成してます。ラジオボタンで判定するコードを書いてます。 1 2023/07/18 11:03
- PHP 入力した部分を表示させたまま(保持)するにはどうすれば良いでしょうか? 1 2023/01/25 11:14
- Visual Basic(VBA) 数式が消える 1 2023/03/19 16:55
- C言語・C++・C# アセンブラ指令 3 2023/06/17 14:47
- JavaScript コードレビューをお願いします。 1 2022/07/16 05:38
- JavaScript clear機能を失わずにファイルアップロード機能を作成したい 3 2023/06/10 16:12
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
hiddenのvalueの値を変えたい
-
複数のsubmitボタンで押された...
-
演算対象の数字と演算子を入力...
-
ラジオボタンとテキストを同時...
-
value内に変数を入れたい
-
Pythonで会員サイトの自動ログ...
-
Kintone(キントーン)でドロップ...
-
selectboxのoptionタグのvalue...
-
VBAをJavaScriptに変換したいです
-
JavaScriptでセレクトボックス...
-
JAVASCRIPTで、ボタンを押した...
-
eval()を使わずに数値を取得し...
-
javascriptにてHTMLのhiddenエ...
-
checkboxとselectメニューの連...
-
name属性が同じフォームが複数...
-
VB.NET DateTimeの型について
-
マクロ オブジェクト変数With...
-
Jqueryを使って値の合計を簡単...
-
setIntervalの間隔を途中で変更...
-
正規表現で複数マッチ条件で悩...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
hiddenのvalueの値を変えたい
-
value内に変数を入れたい
-
引数に数値、文字列の混在
-
複数のsubmitボタンで押された...
-
VB.NET DateTimeの型について
-
3桁区切りのカンマをつけたい...
-
javascriptでhiddenに二次元配...
-
フォームで入力した値を別のフ...
-
setIntervalの間隔を途中で変更...
-
jsで、配列内の文章を改行する...
-
Pythonで会員サイトの自動ログ...
-
selectboxのoptionタグのvalue...
-
テキストボックスに入力された...
-
フォーカスすると初期値が消去...
-
ラジオボタンと連動して文字列...
-
セレクトボックスの初期選択状...
-
sessionStorageを調べています。
-
VBAをJavaScriptに変換したいです
-
ダミーフォームの内容を送信用...
-
javascriptで複数の計算を同時...
おすすめ情報