Forward-Iterator für Circular Queue



  • Hallo zusammen,

    ich soll eine Template-Queue erstellen, die ihre Daten in einem dynamischen Array als Ringspeicher speichert.

    STL-Nutzung ist explizit nicht erlaubt.

    Zudem soll noch ein Forward-Iterator implementiert werden.

    Meine Klasse samt inerer Iterator Klasse sieht so aus:

    template <class TYPE=int> class Queue {
            int size;
            int count;
            TYPE *pData;
            int top;
            int bottom;
            void resize(int newSize);
            void copy(const Queue& org);
            bool isFull();
    public:
            Queue();
            Queue(const Queue<TYPE>& org);
            Queue(Queue<TYPE>&& org);
            Queue<TYPE>& operator=(const Queue<TYPE>& org);
            Queue<TYPE>& operator=(Queue<TYPE>&& org);
            TYPE& operator[](int index);
            const TYPE& operator[](int index) const;
            ~Queue();
            void enqueue(TYPE t);
            TYPE dequeue();
    
            friend ostream& operator<<(ostream& o, const Queue<TYPE>& q){
            	int bot = q.bottom;
            	o<<"Q(";
            	while(bot != q.top){
            		o<< "[" << bot <<"]: " <<q.pData[bot];
            		bot = (bot+1)%q.size;
            	}
            	o<<")";
            	return o;
            }
    
            class QueueIterator: public iterator<std::input_iterator_tag,TYPE> {
            public:
                    QueueIterator(Queue* q=nullptr):q(q){
                    	this->index = q->bottom;
                    }
    
                    const TYPE& operator*()const{
                    	return q->pData[index];
                    }
    
                    const TYPE* const operator->()const{
                    	return &(q->pData[index]);
                    }
    
                    QueueIterator& operator++(){
                    	if(index != q->top)
                    		index = (index+1)%q->size;
                    	return *this;
                    }
    
                    QueueIterator operator++(int dummy){
                    	Queue old = *this;
                    	++*this;
                    	return old;
                    }
    
                    bool operator !=(const QueueIterator& qi) const {
                    	return index != qi.index;
                    }
    
                    bool operator==(const QueueIterator& qi) const {
                    	return index == qi.index;
                    }
    
                    Queue *q;
                    int index;
            };
    
            const Queue<TYPE>::QueueIterator begin(){
                    return QueueIterator(this);
            }
    
            const Queue<TYPE>::QueueIterator end(){
                    return QueueIterator();
            }
    };
    

    Enqueue und dequeue klappen ohne Probleme.

    Hatte den != und == operator auch schon so probiert:

    bool operator !=(const QueueIterator& qi) const {
                    	return q->pData[index] != qi.q->pData[index];
                    }
    
                    bool operator==(const QueueIterator& qi) const {
                    	return q->pData[index] == qi.q->pData[index];
                    }
    

    Jedoch stürzt das Programm immer wenn ich in der main dann den Iterator nutzen will gnadenlos ab...

    Hat jemand ne Idee, wie ich den Iterator zum laufen bringe?
    Und noch ne Frage: wenn ich den Iterator so nutze wie er ist, wäre dann auch sichergestellt, dass er, wenn er bis top gelaufen ist nicht weiter springt?

    Zum Schluß noch die ganzen Implementierungen der Konstruktoren, Operatoren und Methoden & Funktionen.

    template <class TYPE>
    Queue<TYPE>::Queue() {
    	this->bottom = 0;
    	this->top = 0;
    	this->count = 0;
    	this->size = 4;
    	this->pData = new TYPE[size];
    }
    
    template <class TYPE>
    bool Queue<TYPE>::isFull(){
    	return count == size;
    }
    
    template <class TYPE>
    void Queue<TYPE>::resize(int newSize){
    	if(newSize < count || newSize < 4)
    		throw std::out_of_range("Fehler resize: newSize zu klein!");
    	else {
    		int oldsize = this->size;
    		this->size = newSize;
    		TYPE *newData = new TYPE[size];
    		//cout << "bottom: " << bottom << ", count: " << count << ", top: " << top << endl;
    		int counter = 0;
    		while(counter < count){
    			newData[counter] = pData[bottom];
    			counter++;
    			bottom = (bottom+1)%oldsize;
    		}
    		this->bottom = 0;
    		this->count = counter;
    		this->top = count;
    
    		delete[] pData;
    		pData = newData;
    	}
    }
    
    template <class TYPE>
    Queue<TYPE>::Queue(const Queue<TYPE>& org) {
    	this->size = org.size;
    	this->bottom = 0;
    	this->count = org.count;
    	this->top = count;
    
    	pData = new TYPE[size];
    	copy(org);
    }
    
    template<class TYPE>
    void Queue<TYPE>::copy(const Queue<TYPE>& org){
    	int index = 0;
    	int otop = org.top;
    	int obot = org.bottom;
    	while(obot != otop){
    		pData[index] = org.pData[obot];
    		index = (index+1)%org.size;
    		obot = (obot+1)%org.size;
    	}
    }
    
    template<class TYPE>
    Queue<TYPE>::Queue(Queue<TYPE>&& s) {
    	pData = s.pData;
    	bottom = s.bottom;
    	count = s.count;
    	size = s.size;
    	top = s.top;
    
    	s.pData = nullptr;
    	s.bottom = 0;
    	s.count = 0;
    	s.size = 0;
    	s.top = 0;
    }
    
    template <class TYPE>
    Queue<TYPE>& Queue<TYPE>::operator=(const Queue<TYPE>& org) {
    	if(this != &org){
    		delete[] pData;
    		this->pData = new TYPE[org.size];
    		this->bottom = 0;
    		this->top = org.count;
    		this->count = org.count;
    		this->size = org.size;
    		copy(org);
    	}
    	return *this;
    }
    
    template <class TYPE>
    Queue<TYPE>& Queue<TYPE>::operator=(Queue<TYPE>&& org){
    	swap(pData, org.pData);
    }
    
    template <class TYPE>
    inline Queue<TYPE>::~Queue() {
    	delete[] pData;
    }
    
    template <class TYPE>
    void Queue<TYPE>::enqueue(TYPE t) {
    	pData[top] = t;
    	count++;
    	top = (top+1)%size;
    
    	//cout << "top " << top << endl;
    
    	if(top == bottom)
    		resize(size*2);
    }
    
    template <class TYPE>
    TYPE Queue<TYPE>::dequeue() {
    	TYPE tmp;
    	if(bottom < top){
    		tmp = pData[bottom];
    		count--;
    		bottom = (bottom+1)%size;
    
    		if((count*4) < size)
    			resize(size/2);
    	} else
    		throw std::out_of_range("Fehler dequeue: Liste leer!");
    
    	return tmp;
    }
    
    template <class TYPE>
    TYPE& Queue<TYPE>::operator[](int index){
    	if(index < 0 || index > size)
    		throw std::out_of_range("Fehler operator[]: Falscher Index!");
    	return pData[index];
    }
    
    template <class TYPE>
    const TYPE& Queue<TYPE>::operator[](int index) const{
    	if(index < 0 || index > size)
    			throw std::out_of_range("Fehler operator[]: Falscher Index!");
    		return pData[index];
    }
    

    Wäre für Hilfe sehr dankbar :).



  • Jedoch stürzt das Programm immer wenn ich in der main dann den Iterator nutzen will gnadenlos ab...

    Dein Programm kann also Gedanken lesen?

    Hat jemand ne Idee, wie ich den Iterator zum laufen bringe?

    Benutze einen Debugger.

    Das

    if(index < 0 || index > size)
    

    sieht verdächtig aus. Welche Indexwete sind gültig?



  • bool operator !=(const QueueIterator& qi) const { 
                        return q->pData[index] != qi.q->pData[index]; 
                    } 
    
                    bool operator==(const QueueIterator& qi) const { 
                        return q->pData[index] == qi.q->pData[index]; 
                    }
    

    sieht beim überfliegen falsch aus.

    oder sind die iteratoren gleich, wenn zufällig der gleiche wert an der jeweiligen stelle steht? 😮



  • Wenn du

    QueueIterator(Queue* q=nullptr):q(q){
                        this->index = q->bottom;
                    }
    

    In end() aufrufst setzt du q=nullptr und willst dann auf q->bottom zugreifen. Dass muss schief gehen.


Log in to reply