Schleifen mit bzw. in Templates realisieren

Don06

Ich habe gerade mein Template zur Primzahlüberprüfung fertiggestellt. Es sieht ungefähr so aus:

template <ulong Number>
struct IsPrime
{
private:
	static const ulong divisors = NumberOfDivisors<Number>::value;

public:
	static const bool value = (divisors == 2);
};

Ich würde jetzt gerne alle Primzahlen bis 100 ausgeben oder ähnliches. Ich habe schon ein bisschen gegoogelt, aber nichts Konkretes gefunden.
Ich dachte schon daran irgendwas in der Richtung PrintOutIf<Number, Condition> zu machen:

template <ulong Number, bool Condition>
struct PrintOutIf
{ 
private:
	template <bool Condition>
	struct Printer
	{ };

	template <>
	struct Printer<true>
	{
		Printer()
		{
			std::cout << Number;
		}
	};

	Printer<Condition> printer;
};

// Damit geht dann sowas Tolles:
PrintOutIf < 5, IsPrime<5>::value > >();

Klappt auch alles soweit. Aber bei der Umsetzung von Schleifen happerts noch ein bisschen. Bin für jeden Denkanstoß dankbar.

Gruß
Don06

simon.gysi

Bin mir nicht sicher aber so sollte es gehen:

for (ulong i = 0; i < 100; ++i)
	{
		PrintOutIf<i, IsPrime<i> > ();
	}

Edit:
Ist aber komisch, denn eigentlich werden die Templates ja zur Kompilezeit ausgewertet und die Schleife nicht... also ich weiss nicht so recht.. ???

Simon

Don06

Also der MS-Kompiler sagt mir bei der Variante:

error C2971: 'IsPrime': Vorlagenparameter 'Number': 'i': Eine lokale Variable kann nicht als Nichttyp-Argument verwendet werden

Der Compiler hat recht (leider). Die üblichen Variablen scheiden als template-Parameter aus, da diese zur compilier-Zeit bekannt sein müssen (d.h. zur Laufzeit konstant sind). Damit helfen die üblichen Schleifen hier nicht weiter.

Aber Rekursion ist möglich:

template <typename T, unsigned int i>
struct Loop {
  enum { value = T<i>::value };
  enum { counter = Loop<T, i-1>::counter };
};

template <typename T>
struct Loop<T, 0> {
  enum { value = T<0>::value };
  enum { counter = 0 };
};

Mag sein, dass das jetzt nicht fehlerfrei ist, habs aus dem Gedächnis gekramt; aber das Prinzip sollte klar werden.

Übringens nicht zu große Zahlen verwenden; der Compiler kann bezüglich der Rekursionstiefe recht eingeschränkt sein.

hustbaer

Äh.
Was meinst du mit ausgeben? Mit so Template-Tricks kannst du nur Compile-Time Zeugs zusammenbasteln, wirklich ausgeben kannst du da nix. Du kannst höchstens eine Funktion basteln die eine bestimmte Range ausgibt, oder einen boost::mpl::vector zusammenbasteln der das Ergebnis enthält.

Eine (wahrscheinlich etwas umständliche) Möglichkeit ersteres zu machen wäre so:

#include <iostream>

typedef unsigned long ulong;

template <ulong N> struct is_divisible_by_3 // nur als Beispiel, hab grad kein "is_prime" Template zur Hand
{
	static const bool value = (N % 3) == 0;
};

template <ulong BEGIN, ulong END, template <ulong N> class F, class STREAM, bool FINISHED> struct print_range_helper;

template <ulong BEGIN, ulong END, template <ulong N> class F, class STREAM> struct print_range_helper<BEGIN, END, F, STREAM, false>
{
	static void do_print(STREAM& s)
	{
		s << BEGIN << ": " << F<BEGIN>::value << std::endl;
		static const ulong NEXT = BEGIN < END ? BEGIN + 1 : BEGIN - 1;
		print_range_helper<NEXT, END, F, STREAM, NEXT == END>::do_print(s);
	}
};

template <ulong BEGIN, ulong END, template <ulong N> class F, class STREAM> struct print_range_helper<BEGIN, END, F, STREAM, true>
{
	static void do_print(STREAM& s)
	{
		s << BEGIN << ": " << F<BEGIN>::value << std::endl;
	}
};

template <ulong BEGIN, ulong END, template <ulong N> class F, class STREAM> void print_range(STREAM& s)
{
	print_range_helper<BEGIN, END, F, STREAM, BEGIN == END>::do_print(s);
};

int main() 
{	
	print_range<1, 100, is_divisible_by_3>(std::cout);
}

p.S.: es müsste auch gehen ohne den Typ für das "Funktor Template" auf "unsigned long" zu fixieren - mag mir darüber aber grad nicht nochmehr den Kopf zerbrechen.

Wirdbald

Nein, hier machen Templates irgendwie keinen Sinn. Was Du brauchst sind ganz normale Funktionen und nicht nur reine Datentypen.

bool ist_primzahl(int zahl)
{
   // Hier muss ein Primzahltest rein. Siehe 
   // http://de.wikipedia.org/wiki/Primzahl#Primzahltests
}

//Template vielleicht für den Datentyp
template<typename zahlT>
bool ist_primzahl(zahlT zahl)
{
   ...
}

//Funktion, um die nächsthöhere Primzahl zu finden
template<typename zahlT>
zahlT next_primzahl(zahlT start)
{
   ...
}

Wenn Du versuchst in einer Schleife die Template Parameter zu verändern, dann müsste der Compiler für jeden Wert eine neue Instanz Deiner Funktion erzeugen. Bei i=0 bis 99 sind das also 100 Funktionen. Das kommt mir doch ein wenig komisch vor.

simon.gysi

Wirdbald schrieb:

Nein, hier machen Templates irgendwie keinen Sinn. Was Du brauchst sind ganz normale Funktionen und nicht nur reine Datentypen.
bool ist_primzahl(int zahl)
{
   // Hier muss ein Primzahltest rein. Siehe 
   // http://de.wikipedia.org/wiki/Primzahl#Primzahltests
}

//Template vielleicht für den Datentyp
template<typename zahlT>
bool ist_primzahl(zahlT zahl)
{
   ...
}

//Funktion, um die nächsthöhere Primzahl zu finden
template<typename zahlT>
zahlT next_primzahl(zahlT start)
{
   ...
}
Wenn Du versuchst in einer Schleife die Template Parameter zu verändern, dann müsste der Compiler für jeden Wert eine neue Instanz Deiner Funktion erzeugen. Bei i=0 bis 99 sind das also 100 Funktionen. Das kommt mir doch ein wenig komisch vor.

Vielleicht ist dieses Beispiel nicht so günstig gewählt. Grundsätzlich geht es aber genau darum gewisse Berechnung schon zur Compiletime durchzuführen.

http://de.wikipedia.org/wiki/C%2B%2B-Metaprogrammierung

Simon

pumuckl

http://www.erwin-unruh.de/primorig.html Ist es das was du suchst? (Uebrigens eine der ersten Anwendungen von Metaprogramming mit templates)

Don06

Ich weiß schon, dass man das mit normalen Funktionen hinbekommt. Ich wollte mich aber ein wenig in die Metaprogrammierung einarbeiten und dazu ein paar mathematische Berechnungen durchführen. Fakultäten+Fibonacci-Zahlen sind ja ziemlich simpel, also hab ich mal eine Primzahlprüfung gemacht, die ja auch funktioniert. Inzwischen sieht mein Code auch schon so aus:

If < IsPrime<5>,
    PrintNumber<5>
>();

Die Ausgabe findet natürlich zur Laufzeit statt, anders wäre es schliesslich nicht möglich. Der Vorteil ist, dass man einen Algorithmus formulieren kann, dieser aber schon zur Kompilierzeit durchgeführt wird. Es sind also zur Laufzeit keine Berechnungen nötig, sogar die "If-Abfrage" wird vollkommen eliminiert.
Das Prinzip der Schleifen Realisierung habe ich dank euren Tipps auch verstanden. Werde mal sehen, was sich da noch so machen lässt.

EDIT:
Okay, hab eure Ratschläge mal beherzigt. Das Ausgeben erfolgt nun erst in einen Stream und wird dann erst über eine Funktion ausgegeben. Die For-Schleife funktioniert schon mal ganz gut:

int main()
{
	using namespace dons::meta;

	ForTo <1, 100, 
		PrintIfIsPrime 
	>();

	print(std::cout);

	return 0;
}

Das Programm gibt die Primzahlen bis 100 auf std::cout aus. Berechnet werden sie zur Kompilierzeit (das dauert etwas, da meine Methode nicht gerade optimal ist).
Nochmal Danke für die Hilfe.

Gruß
Don06

hustbaer

Don06, guck dir boost.mpl an, das wird dein Herz erfreuen denke ich

Don06

Danke, ich hab mir schon den mpl::vector angeschaut. Das ist echt Wahnsinn, was man so alles machen. Das ganze sollte halt nur mal zum Ausprobieren von einigen Template-Mechanismen sein (was ist möglich, und was nicht).

Gruß
Don06