Problem mit Referenzübergabe an Funktion[gelöst]

skullyan

volkard schrieb:

Fein.

template <size_t S, class T>//Nur nette Abkürzung für feste Arrays
void bubbleSort(T (&a)[S]){
  bubbleSort(a,a+S);
}

int main()
{
    int* a = new int[S];
    srand(time(&t));
    for(int f = 0; f < S; ++f)
        a[f] = rand();
    bubbleSort(a);//abkürzung geht hier nicht
    bubbleSort(a,a+S);//geht

Hm, ich verstehe nicht ganz... So wars wohl nicht gemeint: xD

#include <iostream>
#include <time.h>
using namespace std;

template <size_t S, class T>//Nur nette Abkürzung für feste Arrays
void bubbleSort(T (&a)[S]);

int main()
{
    int* a = new int[S];
    srand(time(&t));
    for(int f = 0; f < S; ++f)
        a[f] = rand();
    bubbleSort(a,a+S);//geht 
    for(int i = 0; i < 18; ++i)
        cout << a[i] << endl;
    cin.get();
}

template <size_t S, class T>
void bubbleSort(T (&a)[S])
{
for(size_t g = 0; g < S ; ++g)
{
	for(size_t i = 0; i < S; ++i)
	if(a[++i] > a[i])
	{
		size_t tmp;
	    tmp = a[++i];
		a[++i] = a[i];
		a[i] = tmp;
	}
}
}

Sebastian Pizer

Ich habe das Gefühl, dass Du Templates nicht ganz verstanden hast. Der Begriff ist wörtlich zu nehmen. Wenn Du Dein Template mit

template<typename T, size_t N>
void bubblesort(T (&array)[N])
{
  ...
  bubblesort-Implementierung
  hier einfügen
  ...
}

definierst, gibst Du dem Compiler eine Bauanleitung für eine ganze Familie für Funktionen. Wenn Du jetzt also 99 Arrays der Längen 1,2,3,4,5,6,7,...,99 sortieren willst, erzeugt der Compiler 99 verschiedene Funktionen, die aber alle fast das gleiche machen. Ist doch einleuchtend, dass das "ungeschickt" ist, oder? Außerdem kannst Du dann nicht mehr auf Laufzeitgeschehnisse reagieren. Wenn Du zB aus einer Datei eine Liste von Zahlen lädst, die in einem Vektor speicherst, kannst Du die nicht sortieren, weil Du bei der Übersetzung des Programms noch nicht weißt, wieviele Elemente das später in der Datei sein werden. Deswegen hat volkard (und ich in dem anderen Thread) auch vorgeschlagen einen BubbleSort zu definieren, der ohne einen Template-Parameter für die Arraylänge auskommt. Wenn Du darüber hinaus, Arrays mit fester Länge noch sortieren können willst, ohne der Funktion die Länge separat übergeben zu müssen, kannst Du eine "Abkürzung bauen".

template<typename T>
void sort(T* const begin, T* const end)
{
  ptrdiff_t const length = end - begin;
  // BubbleSort implementieren
  //
  // erstes Element  = begin[0]
  // zweites Element = begin[1]
  // ...
  // letztes Element = begin[length-1]
}

template<typename T, size_t N>
inline void sort(T (&array)[N])
{
  sort(array,array+N);
}

Das sind überladende Funktions-Templates.
sort<int> sortiert Sequenzen beliebiger Länge
sort<int,44> kann nur 44-elementige int-Arrays sortieren. Macht aber nix, da es nur sort<int> aufruft -- also nicht besonders komplex ist (kein "code bloat").

int main()
{
  int blupp[] = {9,8,7,6,5,4,3,2,1};
  sort(blupp);         // --> sort<int,9>
  sort(blupp,blupp+9); // --> sort<int>
}

Klar soweit?

Gruß,
SP

skullyan

Sebastian Pizer schrieb:

Ich habe das Gefühl, dass Du Templates nicht ganz verstanden hast. Der Begriff ist wörtlich zu nehmen. Wenn Du Dein Template mit
template<typename T, size_t N>
void bubblesort(T (&array)[N])
{
  ...
  bubblesort-Implementierung
  hier einfügen
  ...
}
definierst, gibst Du dem Compiler eine Bauanleitung für eine ganze Familie für Funktionen. Wenn Du jetzt also 99 Arrays der Längen 1,2,3,4,5,6,7,...,99 sortieren willst, erzeugt der Compiler 99 verschiedene Funktionen, die aber alle fast das gleiche machen. Ist doch einleuchtend, dass das "ungeschickt" ist, oder? Außerdem kannst Du dann nicht mehr auf Laufzeitgeschehnisse reagieren. Wenn Du zB aus einer Datei eine Liste von Zahlen lädst, die in einem Vektor speicherst, kannst Du die nicht sortieren, weil Du bei der Übersetzung des Programms noch nicht weißt, wieviele Elemente das später in der Datei sein werden. Deswegen hat volkard (und ich in dem anderen Thread) auch vorgeschlagen einen BubbleSort zu definieren, der ohne einen Template-Parameter für die Arraylänge auskommt. Wenn Du darüber hinaus, Arrays mit fester Länge noch sortieren können willst, ohne der Funktion die Länge separat übergeben zu müssen, kannst Du eine "Abkürzung bauen".
template<typename T>
void sort(T* const begin, T* const end)
{
  ptrdiff_t const length = end - begin;
  // BubbleSort implementieren
  //
  // erstes Element  = begin[0]
  // zweites Element = begin[1]
  // ...
  // letztes Element = begin[length-1]
}

template<typename T, size_t N>
inline void sort(T (&array)[N])
{
  sort(array,array+N);
}
Das sind überladende Funktions-Templates.
sort<int> sortiert Sequenzen beliebiger Länge
sort<int,44> kann nur 44-elementige int-Arrays sortieren. Macht aber nix, da es nur sort<int> aufruft -- also nicht besonders komplex ist (kein "code bloat").
int main()
{
  int blupp[] = {9,8,7,6,5,4,3,2,1};
  sort(blupp);         // --> sort<int,9>
  sort(blupp,blupp+9); // --> sort<int>
}
Klar soweit?

Gruß,
SP

Vom Prinzip her habe ich das jetzt verstanden aber es hapert irgendwie an der Anwendung. Ein Beispiel wäre jetzt hilfreich (am besten direkt an meinem Programm)

Nexus

Beispiele wurden glaube ich genügend gebracht. Diese umzusetzen ist deine Aufgabe.

Aber vielleicht hilft dir ja das.

Sebastian Pizer

Beispiel wofür? Wo hapert es denn?

skullyan

#include <iostream>
#include <time.h>
using namespace std;

void bubbleSort(int* begin, int* end)
{
ptrdiff_t const length = end - begin; 
for(size_t g = 0; g < length ; ++g)
{ 
    for(; begin != end ; (begin+1)) // <--- WARUM IST DAS EINE ENDLOSSCHLEIFE??
	if(*(begin+1) < *begin)
    	{
        size_t tmp;
        tmp = *(begin+1);
        *(begin+1) = *begin;
        *begin = tmp;
	}
}
}

// UND

template<size_t S, typename T>
void bubbleSort( T ( &a )[S] )
{
   bubbleSort(a,a+S);
} 

int main()
{
	size_t S;
	time_t t;
	cin >> S;
    int* a = new int[S];
    srand(time(&t));
    for(int f = 0; f < S; ++f)
        a[f] = rand();
	bubbleSort(a, a+S);//geht
    for(int i = 0; i < 18; ++i)
        cout << a[i] << endl;
	cin.sync();
    cin.get();
}

Hier mein kläglicher Versuch das ganze zu implementieren. Irgendwie komme ich nicht dahinter...

Sebastian Pizer

skullyan schrieb:

void bubbleSort(int* begin, int* end)
{
  ptrdiff_t const length = end - begin; 
  for(size_t g = 0; g < length ; ++g) {
    for(; begin != end ; (begin+1)) // <--- WARUM IST DAS EINE ENDLOSSCHLEIFE??
      if(*(begin+1) < *begin) {
        size_t tmp;
        tmp = *(begin+1);
        *(begin+1) = *begin;
        *begin = tmp;
      }
  }
}

(begin+1) verändert begin nicht. Das ist aber auch gut so, weil Du ja mehrmals über die Sequenz laufen willst. Es wäre also eine schlechte Idee, begin in der inneren Schleige zu ändern. Am besten änderst Du begin und end gar nicht.

Für *(begin+x) gibt es übrigens eine Abkürzung: begin[x]. Zeiger und Arrays sind zwar verschieden, bieten aber in dieser Hinsicht dieselbe Syntax für einen Elementzugriff an.

Du solltest außerdem konsistent in der Benutzung des Ganzzahltyps sein. Also entweder komplett ptrdiff_t oder komplett size_t nutzen. ptrdiff_t ist vorzeichenbehaftet, size_t nicht. Ich hatte ptrdiff_t vorgeschlagen, damit, falls end<begin gilt, es keinen Überlauf gibt und die Funktion einfach nichts tut, statt zu einem Absturz zu führen.

Gruß,
SP

skullyan

Sebastian Pizer schrieb:

skullyan schrieb:
void bubbleSort(int* begin, int* end)
{
  ptrdiff_t const length = end - begin; 
  for(size_t g = 0; g < length ; ++g) {
    for(; begin != end ; (begin+1)) // <--- WARUM IST DAS EINE ENDLOSSCHLEIFE??
      if(*(begin+1) < *begin) {
        size_t tmp;
        tmp = *(begin+1);
        *(begin+1) = *begin;
        *begin = tmp;
      }
  }
}
(begin+1) verändert begin nicht. Das ist aber auch gut so, weil Du ja mehrmals über die Sequenz laufen willst. Es wäre also eine schlechte Idee, begin in der inneren Schleige zu ändern. Am besten änderst Du begin und end gar nicht.

Für *(begin+x) gibt es übrigens eine Abkürzung: begin[x]. Zeiger und Arrays sind zwar verschieden, bieten aber in dieser Hinsicht dieselbe Syntax für einen Elementzugriff an.

Du solltest außerdem konsistent in der Benutzung des Ganzzahltyps sein. Also entweder komplett ptrdiff_t oder komplett size_t nutzen. ptrdiff_t ist vorzeichenbehaftet, size_t nicht. Ich hatte ptrdiff_t vorgeschlagen, damit, falls end<begin gilt, es keinen Überlauf gibt und die Funktion einfach nichts tut, statt zu einem Absturz zu führen.

Gruß,
SP

So:

#include <iostream>
#include <time.h>
using namespace std;

void bubbleSort(int* begin, int* end)
{
ptrdiff_t const length = end - begin; 
int i = 0;
for(ptrdiff_t g = 0; g < length ; ++g)
{ 
	for(ptrdiff_t h = 0; h < length-g ; ++h){

		if(begin[i+1] < begin[i])// <--- Diese Bedingung tritt nie ein
    	{
        ptrdiff_t tmp;
        tmp = begin[i+1];
        begin[i+1] = begin[i];
        begin[i] = tmp;
		}
        ++i;
	}
}
}

// UND

template<size_t S, typename T>
void bubbleSort( T ( &a )[S] )
{

   bubbleSort(a,a+S);
}

int main()
{
    size_t S;
    time_t t;
    cin >> S;
    int* a = new int[S];
    srand(time(&t));
    for(int f = 0; f < S; ++f)
        a[f] = rand();
    bubbleSort(a, a+S);//geht
    for(int i = 0; i < 18; ++i)
        cout << a[i] << endl;
    cin.sync();
    cin.get();
}

Sortiert aber immer noch nicht

Sebastian Pizer

Dranbleiben. Du kannst nicht wegen jeder Kleinigkeit sofort um Hilfe bitten. Wo bleibt denn da der Lerneffekt? Nimm 'nen Debugger...

skullyan

Sebastian Pizer schrieb:

Dranbleiben. Du kannst nicht wegen jeder Kleinigkeit sofort um Hilfe bitten. Wo bleibt denn da der Lerneffekt? Nimm 'nen Debugger...

Die dynamische Speicherverwaltung spielt mir wohl 'nen Streich. Ich komme nicht dahinter. Denn ich sehe nciht, wo da ein Fehler sein soll.

Muss aber einer sein.

Nexus

skullyan schrieb:

Die dynamische Speicherverwaltung spielt mir wohl 'nen Streich. Ich komme nicht dahinter. Denn ich sehe nciht, wo da ein Fehler sein soll.

Muss aber einer sein.

Hast du nicht gelesen? Du sollst es einmal mit einem Debugger versuchen. Wenn du noch nicht damit umgehen kannst, wird es Zeit, das zu lernen.

skullyan

Nexus schrieb:

skullyan schrieb:

Die dynamische Speicherverwaltung spielt mir wohl 'nen Streich. Ich komme nicht dahinter. Denn ich sehe nciht, wo da ein Fehler sein soll.

Muss aber einer sein.

Hast du nicht gelesen? Du sollst es einmal mit einem Debugger versuchen. Wenn du noch nicht damit umgehen kannst, wird es Zeit, das zu lernen.

Habs versucht. Nicht geschafft. Debuggen kann ich schon, aber irgendwie reicht meine Erfahrung nicht aus, um dieses Problem zu lösen.

drakon

Dann schau halt mal nach, wie andere Implementierungen aussehen.. Bubblesort gibts wie Sand am Meer. Dann kannst du vergleichen, was du anderst machst und du weisst dann auch, wo der Fehler ist..

Sebastian Pizer

skullyan schrieb:

Habs versucht. Nicht geschafft. Debuggen kann ich schon, aber irgendwie reicht meine Erfahrung nicht aus, um dieses Problem zu lösen.

Wie hast Du es denn "debugt"? Was hast Du alles überprüft?

skullyan

Ähm, ich glaube, jetzt ist's gelöst:

#include <iostream>
#include <time.h>
using namespace std;

void bubbleSort(int* begin, int* end)
{
ptrdiff_t const length = end - begin;
for(ptrdiff_t g = 1; g < length ; ++g)
{
    for(ptrdiff_t h = 0; h < length-g ; ++h){
        if(begin[h] < begin[h+1])
        {
        int tmp = NULL;
        tmp = begin[h+1];
        begin[h+1] = begin[h];
        begin[h] = tmp;
        }
    }
}
}

// UND

template<size_t S, typename T>
void bubbleSort( T ( &a )[S] )
{

   bubbleSort(a,a+S);
}

int main()
{
    size_t S;
    time_t t;
    cin >> S;
    int* a = new int[S];
    srand(time(&t));
    for(int f = 0; f < S; ++f)
        a[f] = rand();
    bubbleSort(a, a+S);//geht
    for(int i = 0; i < S; ++i)
        cout << a[i] << endl;
    cin.sync();
    cin.get();
}