end() und rend(): wo wird "leere" garantiert?

Andrey

Hi volks!
Ich habe da eine frage zu der "rend" funktion bei sequentiellen containern.
In der doku habe ich folgendes entdeckt:

documentation schrieb:

The member function returns a reverse iterator that points at the first element of the sequence

also stelle ich mir das bei einer sequenz

[A]<->[B]<->[C]<->[-]
// [-] ist das garantiert leere element nach dem ende des arrays
// (listen etc. lass ich erstma weg, nur zum vector jetzt)

etwa so vor: (rend liefert A zurück)

[C]<->[B]<->[A]<->[-]
            |
            |
            rend()

in der dritten auflage von "The c++ programming language" sehe ich jetzt aber etwas, was ich nicht verstehe:

[C]<->[B]<->[A]<->[-]
|                   |
|                   |
rbegin()           rend()

laut einer skizze aus dem kapitel 16.3.2 (wer das tolle büchlein hat, kanns gerne nachschlagen ) zeigt jetzt aber die "rend()" funktion auf ein leeres element vor dem array?

Fragen:
0) Welche version stimmt denn jetzt?

soll ich da als iterator einen zeiger auf das -1. element des arrays zurückgeben? (irgendwas sagt mir, dass ich das nicht tun darf, weil sogar der datentyp für das indizieren der arrays size_t als unsigned int definiert ist) *ungutes gefühl in der magengegend*
wird es garantiert, dass vor dem ersten element nichts ist, was man versehentlich kaputtmachen könnte, wenn ich das array mit "new" erschaffe?
soll ich das buch vielleicht zuerst mal in die dunkle ecke schmeissen? mir ist nähmlich etwas aufgefallen: seit ich es mir durchlese, mache ich mir nur noch sorgen über den guten stil, statt zu programmieren^^ :p

najo, danke allen im voraus

CStoll

rend() zeigt physikalisch auf das erste Element des Array, aber logisch auf das nicht existente Element davor (das liegt daran, daß eine Position VOR dem ersten Element nicht definiert ist).
Du darfst keine singulären Iteratoren dereferenzieren, weder das normale end() noch rend().

Andrey

da ist mir aber immer noch nicht alles klar: was heißt "logisch"?

for(rev_iter=rbegin(); rev_iter!=rend(); rev_iter++){}

wenn rend jetzt physikalisch die adresse von [A] liefert, dann werden die operationen im {}-block nicht für alle elemente der folge durchgeführt, sondern nur für [C] und [B], bei [A] wird es aber schon abgebrochen.

(rev_iter!=rend()) //liefert für [A] false? => abbruch! :( ?

Das ist doch irgendwie schräg, das kann doch nicht sein, dass wenn ich die sequenz in die normale richtung durchlaufe, ein element mehr anspreche, als wenn ich genau dasselbe in der anderen reihenfolge mache

und dann noch eine frage:

Du darfst keine singulären Iteratoren dereferenzieren

"darf nicht " oder "kann nicht"? durch welche sprachlichen elemente wird es dem benutzer des containers denn verboten? [krig ich da compilierfehler?]

thx schon mal

CStoll

Andrey schrieb:

da ist mir aber immer noch nicht alles klar: was heißt "logisch"?
for(rev_iter=rbegin(); rev_iter!=rend(); rev_iter++){}
wenn rend jetzt physikalisch die adresse von [A] liefert, dann werden die operationen im {}-block nicht für alle elemente der folge durchgeführt, sondern nur für [C] und [B], bei [A] wird es aber schon abgebrochen.
(rev_iter!=rend()) //liefert für [A] false? => abbruch! :( ?
Das ist doch irgendwie schräg, das kann doch nicht sein, dass wenn ich die sequenz in die normale richtung durchlaufe, ein element mehr anspreche, als wenn ich genau dasselbe in der anderen reihenfolge mache

Es gibt kein Element "vor dem Anfang" in einem Container. Deshalb zeigt der Reverse-Iterator physikalisch nicht auf das Objekt, das er logisch darstellt. Wenn er dereferenziert wird, liefert er das Element vor seiner physikalischen Position:

Das mußt du dir ungefähr so vorstellen:

[A] - [B] - [C] - [D] - [-]
 ^--+                 ^-----+
   rend()                  rbegin()

und dann noch eine frage:

Du darfst keine singulären Iteratoren dereferenzieren

"darf nicht " oder "kann nicht"? durch welche sprachlichen elemente wird es dem benutzer des containers denn verboten? [krig ich da compilierfehler?]

DARF NICHT - im Sinne von "wenn du's doch machst, landest du im siebten Kreis der Hölle" (aka 'undefines Behaviour')

viande

int arr[5];
int* iter = arr;
int* end = arr + 6;
while(iter != end)
{
   do_some(*iter);
   iter++;
}

do_some(*iter); //hier zeigt iter auf arr[5] -> außerhalb des Arrays und somit kracht es.

An dem Beispiel sollte das vielleicht anschaulich werden, wie teratoren funktionieren.

Andrey

und rückwärts?

int a[3]={1,2,3};
    int* iter_rbegin=&a[2];
    int* iter_rend=&a[-1];	
    //physikalisch sowie logisch schon "im siebten kreis der hölle"
    //bloß nicht dereferenzieren!!!

    for(int* i=iter_rbegin; i!=iter_rend; i--){
	std::cout<<*i<<std::endl;
    }

ja, hier klapps... aber physikalisch, sowie logisch zeigt das ding wirklich irgendwohin ins leere...

edit: bzw. nicht "irgendwohin ins leere" sondern nur "iregndwohin", das ist ja das problem

ich raff den unterschied zwischen dem "logisch" und "physikalisch" immer noch nich

CStoll

Da solltest du dir vielleicht mal die reverse_iterator-Klasse(n) ansehen, vielleicht wird dir der Unterschied dann klar

Nochmal langsam: Physikalisch zeigt rend() auf das erste Element des Containers und rbegin() hinter das letzte, logisch verwendet jeder Reverse-Iterator den Wert, der VOR seiner aktuellen Position steht (also rbegin() das letzte Element, rend() undefinierte Speicherbereiche "vor" dem ersten Element).
(ein Iterator "hinter" dem Containerinhalt ist laut Standard erlaubt (nennt sich end()), ein Iterator "vor" dem Containerinhalt ist nicht definiert - deshalb gibt es bei einem Reverse-Iterator diese Unterscheidung zwischen physikalischer und logischer Position.)

Andrey

aaaaaaaaaaaaaaaaaaaaaaaaaaaachhhhhsooooooooooooo!!!
okay, na dann sry für die vielen überflüssigen fragen, mir fehlte es halt n bissl an "allgemeinbildung" was die reverse_iteratoren angeht
danke schön!

dot

(ein Iterator "hinter" dem Containerinhalt ist laut Standard erlaubt (nennt sich end())

jop, nur als ergänzung: der standard garantiert auch für arrays (also nicht nur bei iteratoren), dass es eine gültige operation ist die adresse des 1. elements nach dem letzten element eines arrays zu bestimmen.

camper

dot schrieb:

(ein Iterator "hinter" dem Containerinhalt ist laut Standard erlaubt (nennt sich end())

jop, nur als ergänzung: der standard garantiert auch für arrays (also nicht nur bei iteratoren), dass es eine gültige operation ist die adresse des 1. elements nach dem letzten element eines arrays zu bestimmen.

Vorläufig - bis zur nächsten Version - aber nur per Pointeraddition; also

int a[10];
int* end = a + 10;

dagegen nicht

int* end = &a[ 10 ];

Andrey

im letzten code-schnipsel habe ich aber auch sowas mit

int* rend=&a[-1];

und es hat auch funktioniert... liegt es daran, dass ich einen total veralteten compiler verwende?

end() und rend(): wo wird &quot;leere&quot; garantiert?

end() und rend(): wo wird "leere" garantiert?