基数変換をメタ関数を用いて書けないでしょうか

[戻る]
メタ [HomePage] 2009/09/19(土) 00:04:21
10進数→radix進数へ、基数変換を行うプログラムです、(とりあえず16 進数まで)
C++テンプレートテクニック という本を読んで。メタ関数なるものを知りました、
このプログラムをメタ関数を用いて、再帰的にdeque コンテナに格納する術は無いでしょ
うか?
それとも無理なのでしょうか、ご教示願います。

#include <iostream>    // cout, endl
#include <map>        // map, pair
#include <deque>    // deque, push_front
#include <string>    // <<
//#include "Radix_transformation.h"

using namespace std;

int div_(int div, int radix)
{
    return div < radix ? div : div /= radix;
}

int mod_(int mod, int radix)
{
    return mod < radix ? mod : mod % radix;
}

int main()
{
    map<int, string> IntToStr;
    map<int, string>::iterator itr;

    IntToStr.insert(pair<int, string>(0, "0"));
    IntToStr.insert(pair<int, string>(1, "1"));
    IntToStr.insert(pair<int, string>(2, "2"));
    IntToStr.insert(pair<int, string>(3, "3"));
    IntToStr.insert(pair<int, string>(4, "4"));
    IntToStr.insert(pair<int, string>(5, "5"));
    IntToStr.insert(pair<int, string>(6, "6"));
    IntToStr.insert(pair<int, string>(7, "7"));
    IntToStr.insert(pair<int, string>(8, "8"));
    IntToStr.insert(pair<int, string>(9, "9"));
    IntToStr.insert(pair<int, string>(10, "A"));
    IntToStr.insert(pair<int, string>(11, "B"));
    IntToStr.insert(pair<int, string>(12, "C"));
    IntToStr.insert(pair<int, string>(13, "D"));
    IntToStr.insert(pair<int, string>(14, "E"));
    IntToStr.insert(pair<int, string>(15, "F"));

    deque<string> deq;
    int div = 906;
    int mod = 0;
    int radix = 16;

    while( div > radix - 1)
    {
        mod = mod_(div, radix);
        div = div_(div, radix);
        itr = IntToStr.find(mod);
        deq.push_front(itr->second);
    }
    itr = IntToStr.find(div);
    deq.push_front(itr->second);

    deque<string>::iterator it = deq.begin();
    while( it != deq.end() )
    {
        cout << *it << endl;
        ++it;
    }
}

επιστημη [E-Mail] [HomePage] 2009/09/19(土) 13:16:49
↓メタ関数をどう使うのかわからんので、とりあえず再帰だけ。

#include <iostream>
#include <string>
#include <deque>
#include <iterator>

template<typename Inserter>
void convert(int input, int radix, Inserter out) {
  static const char* table = "0123456789ABCDEF";
  if ( input > radix - 1 ) {
    convert(input/radix, radix, out);
  }
  *out++ = std::string(1,table[input%radix]);
}

int main() {
  std::deque<std::string> deq;
  convert(906,16,std::back_inserter(deq));
  for ( std::deque<std::string>::iterator it = deq.begin();
        it != deq.end(); ++it ) {
     std::cout << *it << std::endl;
  }
}

メタ 2009/09/19(土) 21:12:50
επιστημη さんお世話になります。
著者から直接ご教授願えますことを光栄に思います。
>>↓メタ関数をどう使うのかわからんので、とりあえず再帰だけ。
私が、メタ関数の意味を、錯誤し取り違えていました。
イメージとしては、再帰的に計算するプレディケートを用いfor_each と組み合わせ、そ
の結果をdeque コンテナに収めていくようなことだったのですが、
再帰的に計算するプレディケートとメタ関数を錯誤し混乱していました。
処で、現在template を用いてradix 進数を10進数にするプログラムを考えています、
アルゴリズムとしては、radix 進数を文字列とし、
各桁毎にその重み(radix の指数)を乗算し、全ての桁を足すという作戦でいきたいので
すがその際に、
static const char* table = "0123456789ABCDEF";
目的の文字が何文字目に現れるかという関数を書く必要があります、(10進化16進)
C++テンプレートテクニック のfind 関数及び、配列をポインタに置き換えるtemplate を
組み合わせればできそうな気がしてこのようにしたのですが、後一歩というか、上手くい
きません間違いを指摘願えないでしょうか。

#include <iostream>    // cout, endl
#include <string>        // <<

using namespace std;

template<class Iterator, class T>
Iterator array_find(T* first, T* last, T target)
{
    for(; first != last; ++first) {
        if(* first == target) {
            break;
        }
    }
    return *first;
}

int main()
{
    static char* table = "0123456789ABCDEF";
    char target = 'A';
    int number = array_find<int, char>(table, table + 16, target);
    cout << "number = " << number << endl;    // ←65(文字コードが出てしまう(^^;
}

メタ 2009/09/19(土) 21:52:07
お世話になります、なんとなくできたっぽいといいますか、これでいいでしょうか?
#include <iostream>    // cout, endl
#include <string>    // <<
#include <iterator>    // distance

using namespace std;

template<class Iterator, class T>
Iterator array_find(T* first, T* last, T target)
{
    T* top;
    top = first;
    for(; first != last; ++first) {
        if(* first == target) {
            break;
        }
    }
    size_t dist = distance(top, first);
    return dist;
}

int main()
{
    static char* table = "0123456789ABCDEF";
    char target = 'F';
    size_t number = array_find<size_t, char>(table, table + 16, target);
    cout << "number = " << number << endl;
}

επιστημη [E-Mail] [HomePage] 2009/09/20(日) 02:52:42
難しく考えすぎ。

#include <iostream>
#include <string>

int main() {
    char target = 'F';
    std::cout << "number = " 
              << std::string("0123456789ABCDEF").find(target) // ←こんだけ。
              << std::endl;
}

メタ 2009/09/20(日) 07:05:01
επιστημη さん、お世話になります、
>>難しく考えすぎ。
引き出しも少なく知識が乏しいので、しょっちゅう墓穴を掘って嵌ってしまいます、あり
がとうございました。こんな感じになりました。それから、
最後にもう一点知りたいことがございます、for_each を書くコツを教えて頂けないで
しょうか
1. for_each を使う場合、対象の配列がvectorのようにiterator で操作できなければな
らないのでしょうか?

2. C言語のネイティブな配列の場合には、「C++テンプレートテクニック」のリスト3-13
にあるような、ポインタを排除したtemplate 化してやればfor_each も可能になるので
しょうか?

#include <iostream>
#include <string>

int pow(int x, int n)
{
    return n == 0 ? 1 : x * pow(x, n - 1); 
}

using namespace std;
int main() {

    string target = "55550";
    int digit = (int)target.length();    // 桁数
    int value;
    int result = 0;
    int radix = 16;                                        // 基数
    for(int i = 0; i < digit; ++i) {
        value = (int)string("0123456789ABCDEF").find(target.substr(digit-1-i, 1));
        value = value * pow(radix, i);
        result += value;
    }
    cout << radix << "進数" << target << " は" << "10進数で" << result << " です"
<< endl;
}

tetrapod 2009/09/20(日) 08:26:15
iterator というものは以下の性質を持つものなので
・(コンテナ上の)ある要素を指し示すことができる
・その要素を * で取り出すことができる
名前こそ変わっているが結局のところポインタと文法上同等のものである。

ポインタにない性質として以下のような性質を持つことができる場合があり、
そういう性質を持つものは特別に後ろの名前を持っている
・ ++ 演算すると次の要素を指すことができる (forward iterator)
・ -- 演算すると前の要素を指すことができる (backward iterator)
・ ++ を n 回行うことより高速に +n 演算できる (random access iterator)

配列形式でデータを持っていれば上記の3つの性質すべてを満たすし
単方向リスト形式でデータを持っていれば forward しか満たさないし
双方向リスト形式でデータを持っていれば random access ではない

というあたりを理解しておけば、こんな例を理解できるだろうか?
const char text[]="01234567890ABCDEF";
std::cout << std::find(text, text+16, 'E') - text << std::endl;
std::find は見つけたところの iterator を返す。
インデックスにしたければ先頭要素へのポインタを引けばいい。

for_each が適切なのかどうかは見直したほうがいいよ。
STL の algorithm 系は書き方さえ工夫すればどれも同じ機能を実現できるので、
どれを使うと「プログラマにとって自然な表記になるか」で使い分けるものだ。

tetrapod 2009/09/20(日) 09:13:53
ものはついでだから考え方から書いてみるか・・・

STL の algorithm 系関数が何をやっているかはソース見たほうが理解が早く、
気の利いた STL 本ならソース示していると思う。
で、ご希望の std::for_each の実装は
fn for_each(iit b, iit e, fn f) {
  for (; b!=e; ++b) f(*b);
  return f;
}
となっている。これを見ると f(要素1つ) の形式で
関数、または operator() が呼ばれる
ということがわかる。逆に言えば、そのように呼ばれるような
関数を作ればよい、または、operator() を持つ使い捨てクラスを作ればよい
ということだ。

なのでそのような使い捨てクラスをできる限り便利に作ればよい。
基数の異なるhuman-readable表記を数値に直すわけだから
・result と radix なるメンバー変数が必要で
・ operator() メンバー関数が必要で
・そのメンバー関数の中で変換を行う
となるわけだ。 for_each は先頭要素から順に呼び出すので operator() は

返却値型は後で考える operator() (引数は後で考える) {
 // power などまったくもって不要。
  result = result*radix + 数値変換結果;
}
と実装すればよいことになる。この operator() は変換中に使われるものなので
返却値は不要、引数は char となり、数値変換には先ほどの発言の find を使って
void operator() (char n) {
 static const char text[]="0123456789ABCDEF";
 int x=std::find(text, text+16, n)-text;
 result=result*radix+x;
}
ここまで思いついて実装できたら後は簡単

struct radix_converter {
 int radix; // 基数
 int result; // 変換結果
 radix_converter(int radix0) : radix(radix0), result(0) {}
 void operator() (char n) { ... } // 中略
};

int main() {
 static const char testtext[]="BEAF"; // 0xBEAF=48815
 std::cout << std::for_each(testtext, testtext+4, radix_converter(16)).result
 <<std::endl;
}

エラーチェック類は一切省略しているのでよろしく。
このクラスは今のままでも無修正で8進数や10進数に対応できているし、
ちょっと拡張すると36進数まで対応可能。

メタ 2009/09/21(月) 06:54:30
[[解決]]
tetrapod さん、お世話になります。
詳しい解説をしていただき、ありがとうごいました。

古いスレッドには追加発言できません。