[C++|STL] Hoe testen of Iterator laatste element is

[^Mo^]

Hoi,

Ik heb de volgende code die gebruikt maakt van een stl list met als template element een pair:

C++:

for( DimensionsList::const_iterator Iter = DimensionsLst.begin(); Iter != DimensionsLst.end(); Iter++)
{
    if( ((Iter->first >= inoutWidth) && (Iter->second >= inoutHeight)) || (Iter == (DimensionsLst.end() - 1)))
    {
        inoutWidth = Iter->first;
        inoutHeight = Iter->second;
        break;
    }
}

Nu wil ik dus de laatste loop, mocht er niks eerder gevonden zijn, dus alsnog iets doen.

Nu kan ik volgens mij niet op end() testen aangezien deze iterator voorbij het laatste element is. Ik wilde dus Iter + 1, of end() - 1 proberen om dit te kunnen testen, echter Visual C++ 6.0 geeft dan de volgende fout:

code:

error C2678: binary '-' : no operator defined which takes a left-hand operand of type 'class std::list<struct std::pair<unsigned long,unsig
ned long>,class std::allocator<struct std::pair<unsigned long,unsigned long> > >::iterator' (or there is no acceptable conversion)

Kortom, hoe kan ik kijken of de huidige iterator het laatste element is? Ik kan uiteraard een teller bijhouden, maar via de iterator is natuurlijk netter (en sneller)

[Soultaker]

Een forward iterator kun je alleen maar verhogen. Je kunt ze gelukkig wel kopiëren, dus zoiets moet wel werken:

C++:

DimensionsList::const_iterator Next = Iter;
++Next;
if(Next == DimensionsLst.end())
{
    // blabla
}

Zelf zou ik de hele lus dan wat anders schrijven:

C++:

for( DimensionsList::const_iterator
         Iter = DimensionsLst.begin(),
         Next = Iter;
     Next++ != DimensionsLst.end(); Iter = Next )
{
  // hier kun je Iter en Next (== Iter + 1) gebruiken
}

(Onhandige naamgeving van variabelen hou je er op na trouwens; DimensionList (het type) en DimensionLst (de instantie) zijn nauwelijks van elkaar te onderscheiden.)

[ Voor 18% gewijzigd door Soultaker op 03-02-2005 16:49 ]

[bigbeng]

Hoewel C++ niet tot mijn core programmeertalen behoort, toch een poging tot een antwoord.

Kun je niet eenvoudig een boolean voor de loop initialiseren op false en die binnen de if op true zetten. Vervolgens na de loop checken of ie false is en zo ja, speciale handelingen verrichten.
Misschien kan het eenvoudiger met een check, maar dit is de methode die ik o.h.a. toepas en die werkt.

[^Mo^]

Ik heb de loop herschreven, en het werkt als een dolle! Dank je

[bigbeng]

Niet om het een of het ander, maar is Soultaker's oplossing niet een mug doden met een nucleaire bom (ik zocht even een stevige metafoor , nofi )?
Nog los van het feit dat de for loop instantiering wordt verkracht (of zit ik ernaast), wordt er elke loop een extra check uitgevoerd (tegenover 1 check aan het einde van mijn oplossing) en wordt er een extra iterator gebruikt (die vast wel meer geheugen gebruikt dan een boolean). Dit lijkt me niet efficient.

edit:

Wat natuurlijk wel zo is, is dat Soultaker's oplossing de vraag tot op de letter beantwoord, terwijl ik een aantal extra aannames doe over wat de TS wil. AAI

[ Voor 18% gewijzigd door bigbeng op 03-02-2005 17:06 ]

[MSalters]

De iterator in kwestie heet std::list::rbegin( ), reverse begin
Je hebt echter geen iterator nodig, want er is ook gewoon een back( ) element.
Het grote probleem is natuurlijk, wat doe je als de list leeg is?

[MSalters]

Soultaker schreef op donderdag 03 februari 2005 @ 16:48:
Een forward iterator kun je alleen maar verhogen. Je kunt ze gelukkig wel kopiëren

Ten eerste is een list iterator een bidirectional iterator. Verhogen kan alleen met ++, verlagen kan met --, en +1 werkt niet omdat +10 dan ook zou werken (random access).

Ten tweede is je text iets bedriegelijk: "alleen verhogen" suggereert dat er niks anders mogelijk is. Dat is niet waar, je kunt een forward iterator ook verlagen door een lagere iterator te assignen. Dat werkt niet voor output iterators (zoals bijvoorbeeld een ostream_iterator), maar wel bij bijvoorbeeld single-linked list iterators.

[Soultaker]

Met verhogen bedoel ik inderdaad het gebruik van de increment operators. Logisch dat je een bidirectionele operator ook kan verlagen, maar dat doet er niet aan af dat je er geen plus of min op kunt gebruiken als het geen random access iterator is (daar ging het feitelijk om). Bovendien was het uit de context niet duidelijk wat voor type er gebruikt werd; uit niets blijkt dat het om een double linked list gaat en niet om een single linked list ofzo.

Verder vind ik dat je een forward iterator toch echt niet kan verlagen. Wat jij doet is er een andere, 'lagere' iterator overheen kopiëren. Dat is heel wat anders, omdat je die 'lagere' iterator niet kunt vinden als je alleen de originele iterator hebt. Als operatie op de originele iterator bestaat het verlagen dus gewoon niet.

[ Voor 21% gewijzigd door Soultaker op 03-02-2005 17:36 ]

[MSalters]

Je kunt het wel vinden, maar 't is toch niet zo. De relevante functie is operator=, en een Forward Iterator moet die aanbieden (als member). En dat is dus wel degelijk een verschil met de Output Iterator categorie. Die iterator hoeft geen assignment te hebben.

Zoiets is relevant als je probeert een iterator te definieren op een single-linked list met een "current position". Met zo'n class kun je de current position alleen 1 vooruit schuiven. Dan zou je zeggen dat je een forward iterator voor zo'n class kunt definieren, maar dat valt dus tegen: je krijgt de assignment niet geimplementeerd omdat je niet terug kunt.

[Soultaker]

MSalters schreef op donderdag 03 februari 2005 @ 18:07:
Je kunt het wel vinden, maar 't is toch niet zo.

Wat is dat nu weer voor raar argument? Ofwel het is een interpretatiekwestie van het concept 'verlagen' en dan kun je moeilijk stellen dat het niet zo 'is', ofwel het is duidelijk gedefinieerd wat verlagen is en dan moet je me daar op wijzen. Dit is een argument van "ik ben het niet met je eens dus wat jij zegt klopt niet".

De relevante functie is operator=, en een Forward Iterator moet die aanbieden (als member). En dat is dus wel degelijk een verschil met de Output Iterator categorie. Die iterator hoeft geen assignment te hebben.

Dat klopt helemaal maar dat kan ik ook in een willekeurige specificatie lezen. operator= is de assignment operator en wij hebben het over een
Operator= is de assignment operator. Het gaat niet om het toekennen van waarden (assignment) maar om het verlagen (decrement). Er is een hele duidelijke decrement operator (twee zelfs) en een type dat die niet heeft kun je wat mij betreft niet verlagen.

[Knorrend_varken]

Mischien niet helemaal on topic, maar is het niet beter om de end() iterator buiten de for loop te bepalen?

[ Voor 10% gewijzigd door Knorrend_varken op 03-02-2005 21:46 ]

[.oisyn]

Och, het is een temporary die in de meeste gevallen toch wel weggeoptimized wordt, mede omdat begin en end in constante tijd werken.

Wel is het handig om ++iterator te doen ipv iterator++, scheelt een onnodige copy.

[Soultaker]

.oisyn schreef op donderdag 03 februari 2005 @ 21:55:
Och, het is een temporary die in de meeste gevallen toch wel weggeoptimized wordt, mede omdat begin en end in constante tijd werken.

Wel is het handig om ++iterator te doen ipv iterator++, scheelt een onnodige copy.

Hmz, geldt daar niet hetzelfde voor, dat dat in 99% van de gevallen wel weggeoptimaliseerd wordt? (Je gebruikt de return value toch niet, en ik neem aan dat die operators meestal gewoon inline gedeclareerd zijn.)

Verder doe ik zelf uit principe ook altijd ++i (zelfs als het bijvoorbeeld om simpele integers gaat) maar goed.

[ Voor 10% gewijzigd door Soultaker op 04-02-2005 01:51 ]

[MSalters]

Soultaker schreef op donderdag 03 februari 2005 @ 19:25:
[...]
Wat is dat nu weer voor raar argument? Ofwel het is een interpretatiekwestie van het concept 'verlagen' en dan kun je moeilijk stellen dat het niet zo 'is', ofwel het is duidelijk gedefinieerd wat verlagen is en dan moet je me daar op wijzen. Dit is een argument van "ik ben het niet met je eens dus wat jij zegt klopt niet".

Ok: de relevante term is "single pass" in 24.1.1/3 Input iterators en 24.1.2/2 Output Iterators, een consequentie en "multi pass" in 24.1.3/2 Forward Iterators.
( uit C++98, C++0x gaat waarschijnlijk I/O en traversal scheiden )

[.oisyn]

Soultaker schreef op vrijdag 04 februari 2005 @ 01:50:
[...]

Hmz, geldt daar niet hetzelfde voor, dat dat in 99% van de gevallen wel weggeoptimaliseerd wordt? (Je gebruikt de return value toch niet, en ik neem aan dat die operators meestal gewoon inline gedeclareerd zijn.)

Heb het even getest voor een std::map (die heeft ingewikkelde in-/decrement operators) onder VC7.1. De postfix versie maakt intern gebruik van de prefix versie, en het wordt idd compleet weggeoptimized. Zelfs als je de returnvalue aan een andere iterator assignt; dan doet ie de assignment eerst, en vervolgens de increment. Het maakt dus idd geen reet uit

Ik heb ook meteen even iterator != map::end() getest, en het enige wat er gebeurt is een pointer comparison van de member van de iterator tegen een member van de map. Een mov, een cmp en een conditional jump dus . Geldt ook voor de reverse iterators.