array mit vorberechneten werten füllen

[Skym0sh0]

tag zusammen,

wie kann ich ein array(oder halt vector, std::array etc) mit per TMP vorberechneten werten füllen?

über std::generate kann man ja werte berechnen und das array dann füllen lassen. aber TMP ist ja rekursiv und da fällt mir nicht mals ein ansatz ein...

ich könnte eine klasse(mit einem array als member) schreiben die intern etwas per TMP berechnet und diese werte direkt in den member schreibt. aber auch da bleibt mein denken an laufzeit operationen wie push_back hängen...

hat jemand einen starttipp für mich?

[Nexus]

Vielleicht was mit Boost.Fusion oder Boost.MPL. Aber bevor du dir das Leben unnötig schwer machst: Wieso muss es Template-Metaprogrammierung sein?

[Skym0sh0]

mh, mir gehts um nen kleinen wettbewerb mit nem kollegen. ein paar fibonacci zahlen berechnen, wers schnellere programm schreibt. (klar ich weis, es gibt diese formel, die die n-te fibonacci zahl berechnet, aber mir gehts um dieses problem)

naja, da kam ich auf die idee, dass man per TMP die zahlen vorberechnet und in dem vector speichert und dann je nach benutzereingabe die n-te fib zahl ausgibt.

und ich hab das gefühl, dass es recht einfach geht, aber ich einfach nicht drauf kommen will Oo

zu deiner frage:
für den praktischen fall müsste es keine TMP sein, aber ich würd gern wissen wie sowas geht, rein aus interesse. geht das auch ohne Boost?

[Oberon_0]

Google ist dein Freund: http://www.google.de/search?q=array+temlate+metaprogramming

[knivil]

fib.h:

#ifndef FIB_H
#define FIB_H

template <int i, int a, int b>
struct FibH
{
  int x;
  FibH<i-1, b, a+b> rest;

  FibH() : x(a) {}
};

template<int a, int b>
struct FibH<0,a,b>
{
  int x;
  FibH() : x(a) {}
};

#endif

main.cpp:

#include "fib.h"
#include <iostream>

int main()
{
  const int n = 45;
  FibH<n,0,1> f;

  for(int i = 0; i < n; ++i)
  {
    std::cout << i << ":  " << reinterpret_cast<int*>(&f)[i] << "\n";
  }
}

[volkard]

knivil schrieb:

...

lol.
Nett gemacht.

[knivil]

Prinzipiell von Stackoverflow kopiert: hier. Natuerlich ist der Konstruktor noch haesslich, da vielleicht die Arbeit nur dorthin verschoben wurde. C++11 erlaubt ja:

template <int n, int a, int b>
class FibH
{
  int x = a;
  ...
};

So kann auf den Konstruktor verzichtet werden. Obs besser ist und FibH dadurch ein POD wird, keine Ahnung. Ab der n=92 wird es fuer einen 64 Bit Integer kritisch.

[life]

Assembleroutput mit VS2010 bei mir:

mov	DWORD PTR _f$[esp+192], 0
	mov	DWORD PTR _f$[esp+196], 1
	mov	DWORD PTR _f$[esp+200], 1
	mov	DWORD PTR _f$[esp+204], 2
	mov	DWORD PTR _f$[esp+208], 3
	mov	DWORD PTR _f$[esp+212], 5
	mov	DWORD PTR _f$[esp+216], 8
	mov	DWORD PTR _f$[esp+220], 13		; 0000000dH
	mov	DWORD PTR _f$[esp+224], 21		; 00000015H
	mov	DWORD PTR _f$[esp+228], 34		; 00000022H
	mov	DWORD PTR _f$[esp+232], 55		; 00000037H
	mov	DWORD PTR _f$[esp+236], 89		; 00000059H
	mov	DWORD PTR _f$[esp+240], 144		; 00000090H
	mov	DWORD PTR _f$[esp+244], 233		; 000000e9H
	mov	DWORD PTR _f$[esp+248], 377		; 00000179H
	mov	DWORD PTR _f$[esp+252], 610		; 00000262H
	mov	DWORD PTR _f$[esp+256], 987		; 000003dbH
	call	??0?$FibH@$0BM@$0GDN@$0KBI@@@QAE@XZ	; FibH<28,1597,2584>::FibH<28,1597,2584>

??0?$FibH@$0BM@$0GDN@$0KBI@@@QAE@XZ PROC		; FibH<28,1597,2584>::FibH<28,1597,2584>, COMDAT
; _this$ = esi

; 9    :   FibH() : x(a) {}

	mov	DWORD PTR [esi], 1597			; 0000063dH
	mov	DWORD PTR [esi+4], 2584			; 00000a18H
	mov	DWORD PTR [esi+8], 4181			; 00001055H
	mov	DWORD PTR [esi+12], 6765		; 00001a6dH
	mov	DWORD PTR [esi+16], 10946		; 00002ac2H
	mov	DWORD PTR [esi+20], 17711		; 0000452fH
	mov	DWORD PTR [esi+24], 28657		; 00006ff1H
	mov	DWORD PTR [esi+28], 46368		; 0000b520H
	mov	DWORD PTR [esi+32], 75025		; 00012511H
	mov	DWORD PTR [esi+36], 121393		; 0001da31H
	mov	DWORD PTR [esi+40], 196418		; 0002ff42H
	mov	DWORD PTR [esi+44], 317811		; 0004d973H
	lea	eax, DWORD PTR [esi+52]
	mov	DWORD PTR [esi+48], 514229		; 0007d8b5H
	call	??0?$FibH@$0P@$0MLCCI@$0BEIKNN@@@QAE@XZ	; FibH<15,832040,1346269>::FibH<15,832040,1346269>
	mov	eax, esi
	ret	0

??0?$FibH@$0P@$0MLCCI@$0BEIKNN@@@QAE@XZ PROC		; FibH<15,832040,1346269>::FibH<15,832040,1346269>, COMDAT
; _this$ = eax

; 9    :   FibH() : x(a) {}

	mov	DWORD PTR [eax], 832040			; 000cb228H
	mov	DWORD PTR [eax+4], 1346269		; 00148addH
	mov	DWORD PTR [eax+8], 2178309		; 00213d05H
	mov	DWORD PTR [eax+12], 3524578		; 0035c7e2H
	mov	DWORD PTR [eax+16], 5702887		; 005704e7H
	mov	DWORD PTR [eax+20], 9227465		; 008cccc9H
	mov	DWORD PTR [eax+24], 14930352		; 00e3d1b0H
	mov	DWORD PTR [eax+28], 24157817		; 01709e79H
	mov	DWORD PTR [eax+32], 39088169		; 02547029H
	mov	DWORD PTR [eax+36], 63245986		; 03c50ea2H
	mov	DWORD PTR [eax+40], 102334155		; 06197ecbH
	mov	DWORD PTR [eax+44], 165580141		; 09de8d6dH
	mov	DWORD PTR [eax+48], 267914296		; 0ff80c38H
	mov	DWORD PTR [eax+52], 433494437		; 19d699a5H
	mov	DWORD PTR [eax+56], 701408733		; 29cea5ddH
	mov	DWORD PTR [eax+60], 1134903170		; 43a53f82H
	ret	0

[Skym0sh0]

mh also ich hab anfangs die falschen dinge bei google eignegeben und deswegen nix gefunden.

aber jetzt mit dem link von stackoverflow hat das gut geklappt
und wenn ich das richtig sehe, funktioniert es, dass man für alles berechenbare ein array erstellen kann ?!
man muss nur die "formel" im konstruktor anpassen...

[DrakoXP]

Also

mir war eben langweilig und da hab ich mich mal rangesetzt und das implementiert,
also dass ein richtiges array generiert wird

Der Code ist etwas länger, aber ich hoffe, man kannes trotzdem lesen und verstehen

Es werden ein paar C++11 Features verwendet (Variadic Templates & auto).

Ab Zeile 120 kommt der zur Laufzeit relevante Teil, davor ist alles TMP.

Hier der Code:

#include <iostream>
using std::cout;
using std::endl;

#include <exception>
using std::exception;

#include <stdexcept>
using std::range_error;

#include <boost/lexical_cast.hpp>
using boost::lexical_cast;

// maximum fibonacci number
// must be defined to the compiler using -DMAX_FIB=xxx
#ifndef MAX_FIB
#warning "MAX_FIB undefined! Defaulting to 50."
#define MAX_FIB 50
#endif

// simple fibonacci function
template <unsigned long long Number>
struct fib
{
    static unsigned long long const value = fib<Number - 2>::value + fib<Number - 1>::value;
};

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

template <>
struct fib<1>
{
    static unsigned long long const value = 1;
};

// determine the length of an integer pack
template <unsigned long long... Numbers>
struct length;

template <unsigned long long Head, unsigned long long... Tail>
struct length<Head, Tail...>
{
    static unsigned long long const value = 1 + length<Tail...>::value;
};

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

// a variadic integer pack to integer array converter
template <unsigned long long... Numbers>
struct to_array
{
    static unsigned long long const value[length<Numbers...>::value];
};

template <unsigned long long... Numbers>
unsigned long long const to_array<Numbers...>::value[] = { Numbers... };

// a number list
template <unsigned long long... Numbers>
struct list;

template <unsigned long long Head, unsigned long long... Tail>
struct list<Head, Tail...>
{
    static unsigned long long const head = Head;
    typedef list<Tail...> tail;
};

template <>
struct list<>
{
};

// append to a number list
template <typename List, unsigned long long Value>
struct append;

template <unsigned long long Value>
struct append<list<>, Value>
{
    typedef list<Value> type;
};

template <unsigned long long... Numbers, unsigned long long Value>
struct append<list<Numbers...>, Value>
{
    typedef list<Numbers..., Value> type;
};

// generate number list using fib function
template <unsigned long long Maximum>
struct fib_list
{
    typedef typename append<typename fib_list<Maximum - 1>::type, fib<Maximum>::value>::type type;
};

template <>
struct fib_list<0>
{
    typedef list<fib<0>::value> type;
};

// generate an array from a list
template <typename List>
struct array_from_list;

template <unsigned long long... Numbers>
struct array_from_list<list<Numbers...>>
{
    typedef to_array<Numbers...> type;
};

// our precalculated fibonacci numbers
typedef typename array_from_list<typename fib_list<MAX_FIB>::type>::type fibonacci_array;
unsigned long long const * const fibonacci = fibonacci_array::value;

inline void show_usage(char const * const program)
{
    cout << "Usage: " << program << " [number]" << endl;
}

int main(int argc, char ** argv)
{
    if (argc != 2)
    {
        cout << "Wrong number of parameters!\n";
        show_usage(*argv);
    }

    try
    {
        auto number = lexical_cast<unsigned long long>(argv[1]);
        if (number > MAX_FIB)
            throw range_error("The given number is too big!");

        cout << fibonacci[number] << endl;
    }
    catch (exception const & ex)
    {
        cout << "An exception occured: " << ex.what() << "\n";
        show_usage(*argv);
    }

    return 0;
}

[camper]

Das Ganze lässt sich auch ohne reinterpret_cast schreiben. Dann ist auch keine dynamische Initialisierung erforderlich.

#include <type_traits>
template <std::size_t i> struct fib : std::integral_constant<unsigned long long, fib<i-1>::value + fib<i-2>::value> {};
template <> struct fib<0> : std::integral_constant<unsigned long long, 0> {};
template <> struct fib<1> : std::integral_constant<unsigned long long, 1> {};

template <typename T> struct identity { typedef T type; };
template <std::size_t... i> struct indexes : identity<indexes<i...>> {};
template <typename T> struct append;
template <std::size_t... i> struct append<indexes<i...>> : identity<indexes<0, ( i + 1 )...>> {};
template <std::size_t N> struct make_indexes : append<typename make_indexes<N-1>::type> {};
template <> struct make_indexes<0> : identity<indexes<>> {};

template <template <std::size_t> class func, std::size_t a, std::size_t b, typename = typename make_indexes<b-a+1>::type>
struct func_data;
template <template <std::size_t> class func, std::size_t a, std::size_t b, std::size_t... i>
struct func_data<func, a, b, indexes<i...>>
{
    static const decltype(func<a>::value) data[b-a+1];
};

template <template <std::size_t> class func, std::size_t a, std::size_t b, std::size_t... i>
const decltype(func<a>::value) func_data<func, a, b, indexes<i...>>::data[b-a+1] = { func<a+i>::value... };
/*
template <template <std::size_t> class func, std::size_t a, std::size_t b, std::size_t... i>
struct func_data<func, a, b, indexes<i...>>
{
    static constexpr decltype(func<a>::value) data[] = { func<a+i>::value... };
};
*/
#include <iostream>

int main()
{
  const int n = 45;
  func_data<fib, 0, 44> f;

  for(int i = 0; i < n; ++i)
  {
    std::cout << i << ":  " << f.data[i] << "\n";  }
}

Edit: ok, Drako war etwas schneller.

[DrakoXP]

@camper:

wenn ich mir deinen Code so anschaue, muss ich sagen,
dass ich ein paar Sachen bei mir hätte besser machen können :p

Vor allem die Arrayerstellung mit dem Pattern "func<a+i>::value..." war mir vorhin irgendwie entfallen :S

Aber eine Frage zu deinem Code habe ich noch^^

const decltype(func<a>::value) func_data<func, a, b, indexes<i...>>::data[b-a+1] = { func<a+i>::value... };

Ist das const am Anfang wirklich nötig?
Ich bin mir eben nicht sicher, ob nicht decltype das schon enthalten müsste.

[camper]

DrakoXP schrieb:

const decltype(func<a>::value) func_data<func, a, b, indexes<i...>>::data[b-a+1] = { func<a+i>::value... };

Ist das const am Anfang wirklich nötig?

Erforderlich ist es sicher nicht (sofern man konsequent bleibt). Das ist hier einfach Gewohnheit. Eigentlich sollte es ja ohnehin constexpr sein, aber g++ unterstützt die Aggregatinitialisierung innerhalb der Klassendefinition noch nicht.

[camper]

Man kann das ganze auch ohne Verwendung eine fibonacci-Metafunktion schreiben:

#include <type_traits>

// index-Erstellung mit logarithmischer Komplexität
template <typename T> struct identity { typedef T type; };
template <std::size_t... i> struct indexes
    : identity<indexes<i...>> {};
template <typename... T> struct concat
    : concat<typename T::type...> {};
template <std::size_t... i, std::size_t... j, typename... T> struct concat<indexes<i...>, indexes<j...>, T...>
    : concat<indexes<i..., (sizeof... i + j)...>, T...> {};
template <typename T> struct concat<T>
    : T {};
template <typename T> struct twice
    : concat<T, T> {};
template <std::size_t N> struct make_indexes
    : concat<twice<make_indexes<N/2>>, make_indexes<N%2>> {};
template <> struct make_indexes<0>
    : indexes<> {};
template <> struct make_indexes<1>
    : indexes<0> {};

template <std::size_t N, typename = typename make_indexes<N-2>::type>
struct fib_data;
template <std::size_t N, std::size_t... i>
struct fib_data<N, indexes<i...>>
{
    static const unsigned long long data[N];
};

template <std::size_t N, std::size_t... i>
const unsigned long long fib_data<N, indexes<i...>>::data[N] = { 0, 1, ( data[i] + data[i+1] )... };

#include <iostream>

int main()
{
  const int n = 94;
  fib_data<n> f;

  for(int i = 0; i < n; ++i)
  {
    std::cout << i << ":  " << f.data[i] << "\n";
  }
}

Sieht man von dem Teil davor ab, dürfte diese Form der Initialisierung auch für relative Anfänger ohne TMP-Kentnisse lesbar sein. Allerdings führt das zumindest im Moment bei g++ zu dynamischer Initialisierung, weil die Verwendung von bereits initialisierten Subobjekten in konstanten Ausdrücken bisher nicht implementiert ist (das gleiche Problem hat man auch, wenn man einen constexpr Konstruktor schreiben will).

[knivil]

Mir faellt gerade auf, dass dieser Code mit den ganze ... eigentlich wie Scheme-Makros ausschaut.

[krümelkacker]

Ich hatte da eigentlich an eine Funktion gedacht, wo drin das Array per static deklariert wird. Aber sonst sieht das auch fast genauso aus, wie bei Euch:

#include <type_traits>

template<class T> struct identity {typedef T type;};

template<class...T> struct pack {};

template<int Beg, int End, int...Tail>
struct index_pack_type
  : index_pack_type<Beg,End-1,End-1,Tail...> {};
template<int BE, int...Tail>
struct index_pack_type<BE,BE,Tail...>
  : identity<pack<std::integral_constant<int,Tail>...> > {};

template<int B, int E>
typename index_pack_type<B,E>::type make_index_pack() {
  return typename index_pack_type<B,E>::type();
}

template<class ValueType, template<class> class MetaFunc, class...MetaArgs>
inline ValueType const* lookuptable(pack<MetaArgs...>) {
  static const ValueType data[] = {MetaFunc<MetaArgs>::value...};
  return data;
}

#include <iostream>

template<int I> struct fib_c : std::integral_constant<int,
  fib_c<I-1>::value + fib_c<I-2>::value
>{};
template<> struct fib_c<0> : std::integral_constant<int,0>{};
template<> struct fib_c<1> : std::integral_constant<int,1>{};

template<class MetaArg> struct fib : fib_c<MetaArg::value>{};

int main() {
  const int N = 10;
  const int* fibtab = lookuptable<int,fib>(make_index_pack<0,N>());
  for (int i=0; i<N; ++i) {
    std::cout << fibtab[i] << std::endl;
  }
}