Klasse "Queue" mit Teplate-Funktionen?

[rendner]

Ich versuche gerade eine Klasse "Queue" zu schreiben.
Nun ist es aber so das diese als Membervariable ein Array enthält und dieses Array jeden Datentyp aufnehmen soll.
Das nächste kleinere Problem wäre das wenn die Membervariable queue (ein Array) leer ist und ich die Funktionen remove oder peek aufrufe soll eine Art null-Zeiger zurück gegeben werden.

Zuerst hatte ich gedacht das ich das Array vom Datentyp Object erstelle, aber dies ist in C++ nicht möglich (?).

Dann hatte ich gelesen das man in einem solchem Fall ein Template benutzt, um diese Problem zu umgehen.

Oder gebe es da noch eine andere alternative...?

Hier mal meine Klasse vor dem Versuch mit dem Template ( ausser einer Menge von Fehlern ist da nix bei raus gekommen ):

Header Datei:

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

class Queue
{

	public:
		Queue( unsigned int );
		~Queue();
		int length();
		int size();
		double add( double );
		double* remove();
		double peek();

	private:
		double* m_queue;
		unsigned int m_cnt;
		unsigned int m_size;

};
#endif	//  QUEUE_H_INCLUDED

Die cpp Datei:

#include "Queue.h"

Queue::Queue( unsigned int size = 0 )
{
	m_cnt = 0;
	m_size = size;
	m_queue = new double[ size ];
}

Queue::~Queue()
{
	delete[] m_queue;
}

double Queue::add( double o )
{
	if ( m_cnt + 1 > m_size ) return NULL;

	m_queue[ m_cnt++ ] = o;	

	return o;
}

double Queue::remove()
{
	if ( m_cnt ) 
	{
		double o = new double( m_queue[0] );
		unsigned int i = 0;

		while( i++ < m_cnt )
		{
			m_queue[i-1] = m_queue[i];
		}

		m_queue[ --m_cnt ] = NULL;

		return o;
	}
         else return NULL;

}

double Queue::peek()
{
	return m_cnt ? m_queue[0] : NULL;
}

int Queue::size()
{
	return m_size;	
}

int Queue::length()
{
	return m_cnt;	
}

Ich hoffe ihr könnt mir bei diesem Problem helfen...

mfg rendner

[CStoll (off)]

Templates definierst du, indem du das Schlüsselwort "template" verwendest:

template<typename T>
class Queue
//Queue für Typ T - kann beliebig verwendet werden
{
public:
  Queue(unsigned int);
  //const-Referenzen sind vorteilhafter als Kopien, gerade bei eigenen Klassen
  const T& add(const T&);
  //...

private:
  T* m_data;
  unsigned int m_cnt;
  unsigned int m_size;
}

template<typename T>
Queue<T>::Queue(unsigned int size)
{
  ...
}

Das nächste kleinere Problem wäre das wenn die Membervariable queue (ein Array) leer ist und ich die Funktionen remove oder peek aufrufe soll eine Art null-Zeiger zurück gegeben werden.

remove() kann notfalls einen Null-Zeiger zurückgeben, bei peek() wäre das etwas schwieriger, dort könntest du höchstens eine Exception werfen oder einen Default-Wert zurückgeben.

PS: Über das Design der Klasse rede ich lieber nicht

[rendner]

Danke erstmal...werd das gleich mal umsetzen.

PS: Über das Design der Klasse rede ich lieber nicht

Schade, wäre trotzdem toll wenn du mal die groben Fehler sagen könntest (oder zumindest ein paar Vorschläge zur Verbesserung), da ich dies ja lernen will und da nicht so den Durchblick habe.

Ach ja, gibts einen Unterschied zwischen

template <class T>
// und
template <typename T>      // ?

mfg rendner

[.filmor]

Beispielsweise benutzt man bei Queues entweder zyklisches Array (wenn man am Ende ankommt, geht man wieder nach vorne) oder eine Liste, der lineare Aufwand in remove ist nicht sinnvoll (du hast im Prinzip einen Stack programmiert). Außerdem haben sich die Namen push und pop für add und remove eingebürgert.

Diese Zeile

double o = new double( m_queue[0] );

ist schlichtweg falsch. Das sollte dir auch dein Compiler ankreiden. Was du meinst ist eine einfache Zuweisung (p[i] entspricht *(p + i)).

Zu deiner Frage: Es gibt keinen. Manche Leute benutzen typename wenn auch POD-Typen erlaubt sind, den Compiler scherts nicht.

[CStoll (off)]

Ein grober Fehler ist schonmal, daß sich der Rückgabetyp der remove() zwischen Deklaration und Definition geändert hat.

Als nächstes ist es ein ziemlicher Aufwand, bei jedem remove() die Liste umzuräumen. Und drittens ist es immer problematisch, wenn du Fehlerwerte und echte Daten durcheinander ausgibst (das aufrufende Programm kann nicht unterscheiden, ob dort gerade eine 0 im Queue stand oder ob es remove() auf einen leeren Queue anwenden wollte).

PS: Wenn es dir nicht um die Programmier-Übung geht, verwende lieber std::queue

[rendner]

@ .filmor
Ein Stack ist aber doch ein bischen was anderes, ich hatte immer gedacht wenn eine queue voll ist, ist die voll und nimmt nicht irgendwelche Elemente auf und überschreibt somit andere.

Als nächstes ist es ein ziemlicher Aufwand, bei jedem remove() die Liste umzuräumen.

Wie könnte man dann die Methode remove( shift, da pop ja eigentlich das hinterste Element entfernt ) implementieren ohne andauernd das Array aufzuräumen?

Und drittens ist es immer problematisch, wenn du Fehlerwerte und echte Daten durcheinander ausgibst (das aufrufende Programm kann nicht unterscheiden, ob dort gerade eine 0 im Queue stand oder ob es remove() auf einen leeren Queue anwenden wollte).

Was könnte man im diesem Fall machen?

mfg rendner

Danke für den Tipp mit der std::queue werd ich mir mal angucken.

[CStoll]

rendner schrieb:

Wie könnte man dann die Methode remove( shift, da pop ja eigentlich das hinterste Element entfernt ) implementieren ohne andauernd das Array aufzuräumen?

Wie filmor schon sagte, entweder per Ringliste (du hast zwei Pointer in dein Daten-Array, die beim Lesen und Schreiben jeweils weiterrücken - wenn der Schreibzeiger den Lesezeiger "überrundet", ist das Feld voll und du mußt entweder Platz schaffen oder einen Fehler zurückgeben.

Was könnte man im diesem Fall machen?

Entweder eine Exception zurückwerfen oder "undefined behavior" (der Aufrufer muß selber sicherstellen, daß er remove() nicht auf eine leere Warteschlange anwendet).