[c++] Iterator auf Element in double ended queue

[DarthShader]

Hallo,

ich verwende ein double ended queue (std::deque), um einige Daten zu speichern. Nun möchte ich eine Art Zeiger auf ein Element haben, welchen ich "hin und herschieben" kann, also inkrementieren und dekrementieren.

Also nahm ich da einen Iterator vom selben Typ wie mein deque, was so aussieht:

std::deque<bool> dqData;		// Double Ended Queue
std::deque<bool>::iterator dqPos;	// Iterator, der auf das aktuelle Element zeigt

indem ich nun im Programm "dqPos++" oder "dqPos--" mache, kann ich meinen "virtuellen Lesekopf" nun bewegen. Dabei liefert mir dann "*dqPos" das Element an der aktuellen Position, auf die dqPos zeigt.

Nun aber zum kleinen Verständnisproblem - wenn mein deque angelegt wird, so mache ich

dqData.push_back(0);
dqPos = dqData.end();

damit lege ich gleich das erste Element (mit Inhalt 0) an und lasse meinen Iterator darauf zeigen. Und hier die Frage, ist das richtig so? Oder zeigt "dqPos" dann immer auf den End-Iterator des deque's?

Falls das also Humbug ist, wie realisiere ich einen Iterator, den ich beliebig "verschieben" kann (++ oder --) und so immer auf ein Element aus dem deque zeigt?


Vielen Dank für Eure Hilfe

 

[uhu01]

Hy!

Eigentlich sollte der Iterator auch nach einer Einfügeoperation noch immer auf dasselbe Element zeigen. D.h. wenn du hinter dem als ersten eingefügten Element ein neues Element einfügst zeigt der Iterator auf das Element 0. Wenn du vor diesem ein Element einfügst, zeigt der Iterator auf das Element 1

Diesen Iterator kannst du auch mit ++ und -- hin- und herschieben.

Soweit ich weis, wird der Iterator ungültig wenn du das Element löschst auf das er zeigt.

mfg
uhu01

 

[Kachelator]

dqData.push_back(0);
dqPos = dqData.end();

end() liefert bei allen STL-Containern immer einen "Zeiger" der hinter das letzte Element des Containers zeigt, ist also grundsätzlich nicht dereferenzierbar. dqPos bleibt auch nach erfolgten Einfügungen ungültig. Üblicherweise wird end() nur verwendet, um einen Vergleichswert zu bekommen, ob ein Container vollständig durchlaufen wurde, so wie in diesem Beispiel aus der MSDN Lib:

#include <iostream>
#include <deque>

using namespace std;

typedef deque<int >  INTDEQUE;

int main()
{

    // Create A and fill it with elements 1,2,3,4 and 5
    // using push_back function

    INTDEQUE  A;
    A.push_back(1);
    A.push_back(2);
    A.push_back(3);
    A.push_back(4);
    A.push_back(5);

    // Print the contents of A using iterator
    // and functions begin() and end()

    INTDEQUE::iterator pi;

    for(pi= A.begin();  pi !=A.end(); pi++)
    {
        cout << *pi <<" " ;
    }
    cout<<endl;
}

Nimm also lieber begin().

 

[DarthShader]

Danke für Eure Antworten. Momentaner Status ist folgender:

ich lege die deque so an (data ist std::deque und it_pos ist der iterator)

data.push_back(0);
it_pos = data.begin();

Nun kann ich an aktueller Position (was nach dem Anlegen ja .begin() ist) z.b. eine 1 schreiben:

*it_pos = 1;

und per Dereferenzierung von it_pos wieder abrufen. Die Sache ist nun die, dass mein "virtueller Lese und Schreibkopf" it_pos nach links und nach rechts verschoben werden kann (man stelle sich data als eine Art horizontales Datenband vor). Schiebe ich nach rechts, sieht es so aus:

if (it_pos == (data.end()-1)) // Ist der Iterator am Ende?
	data.push_back(0);  // Dann das "Datenband" nach rechts erweitern

it_pos++;    // Und den Iterator "nach rechts" verschieben.

Das funktioniert auch - ist der "Lesekopf" nun am Ende und schiebe ich nach rechts, so wird ein neues Element ans Ende "gepusht" und der Iterator inkrementiert, so zeigt er dann aufs richtige Element.

Nun das nach links schieben - und das funktioniert leider nicht korrekt:

if (it_pos == data.begin())  // Ist der Iterator am Anfang?
	data.push_front(0);  // Dann das "Datenband" nach links erweitern, Iterator kann bleiben, da er ja eigentlich nun immernoch auf das 1. Element zeigt
else
        it_pos++;    //  Iterator "nach rechts" verschieben, nur wenn kein neues Element angelegt wurde

Das nach-links-schieben funktioniert jedoch nicht, ich kann mir das aber nicht erklären. Wenn ich push_front(0) mache, so füge ich ja am Anfang der deque etwas ein, welcehs dann quasi den Index 0 erhält, also das neue erste Element ist. Der Iterator zeigt aber noch darauf, deshalb muss ich ihn dann nicht ändern.

Was ist an dieser Denkweise verkehrt? Irgendwas muss es sein, da das Linksschieben einfach nicht laufen will :-/


Danke für Eure Hilfe

 

[jokey2]

Das nach-links-schieben funktioniert jedoch nicht, ich kann mir das aber nicht erklären. Wenn ich push_front(0) mache, so füge ich ja am Anfang der deque etwas ein, welcehs dann quasi den Index 0 erhält, also das neue erste Element ist. Der Iterator zeigt aber noch darauf, deshalb muss ich ihn dann nicht ändern.

Der Fehler ist, das der Iterator nach dem Einfügen auf das Element [1] zeigt. Der Iterator zeigt also nicht auf einen Index, sondern auf das Element. Und wenn Du vor dem Element ein weiteres einfügst, zeigt er immer noch auf das gleiche Element, das jetzt aber einen anderen Index hat.
Um nach dem Einfügen immer noch auf das Element [0] zu zeigen mußt du nach dem Einfügen den Iterator dekrementieren.

 

[DarthShader]

Um nach dem Einfügen immer noch auf das Element [0] zu zeigen mußt du nach dem Einfügen den Iterator dekrementieren.

Mein Code, um den "Lesezeiger" nach links zu verschieben, sieht nun so aus:

if (it_pos == data.begin())
	data.push_front(0);
	
it_pos--;

Ich schaue also, ob er am Anfang ist - falls ja, füge ich ein neues Element am Anfang ein (eine Null) und schiebe den Operator nach "links", dekrementiere ihn also.

Problem ist nun, wenn ich folgendes in dieser Reihenfolge mache:

1. deque anlegen
2. eine 1 an aktueller Position schreiben
3. Lesezeiger nach links bewegen (da am Anfang: ein Element '0' hinzufügen und it_pos--)
4. Aktuelle Position ausgeben / Aktuellen Iterator dereferenzieren

Und genau bei Punkt 4 kommt dann ein Fehler -> er kann nicht dereferenziert werden. Aber warum nicht?Eigentlich sollte er doch nach dem "it_pos--;" auf das zuvor angelegte Element zeigen (und es wurde angelegt, nach dem Linksschieben beträgt Size der deque = 2)?

Wo ist da nur der Fehler?


Danke nochmals

 

[jokey2]

Ich weiß leider nicht, auf was der iterator zeigt, wenn die liste neu angelegt wurde. Er kann ja nicht auf ein Element zeigen, da noch keines da ist. Evtl. mußt Du ihn nach dem ersten Einfügen noch auf data.begin() setzen. Aber da übernehme ich keine Garantie für . Vielleicht weiß ja noch eine etwas Genaueres.

 

[DarthShader]

Ich weiß leider nicht, auf was der iterator zeigt, wenn die liste neu angelegt wurde. Er kann ja nicht auf ein Element zeigen, da noch keines da ist. Evtl. mußt Du ihn nach dem ersten Einfügen noch auf data.begin() setzen. Aber da übernehme ich keine Garantie für . Vielleicht weiß ja noch eine etwas Genaueres.

Hast Du den Thread überhaupt gelesen? ;-) Das hier hatte ich oben bezüglich des Anlegens des deque schon geschrieben:

data.push_back(0);
it_pos = data.begin();