vector<bool> og pointers

Tags:    c++

Hej udviklere,
jeg har en templated klasse 'Grid<T>' der arver fra std::vector<T> (det er reelt en 2d-vector, og arver altså faktisk fra std::vector<std::vector<T> > ).
For at kunne bruge STL <algorithm>'er på min container, har jeg lavet en iterator ('class Grid<T>::iterator : public std::iterator<std::bidirectional_iterator_tag, T>'), der kan gå igennem mit Grid fra .begin() til .end().
Problemet er: når jeg laver et Grid<bool> (dvs T = bool) giver min iterator mig problemer med compileren (MinGW). Jeg får:
Fold kodeboks ind/udKode 

der så vidt jeg kan gennemskue fortæller mig at jeg ikke må dereferere en pointer til en bool i en std::vector.
Jeg dereferer pointeren her (linie 38 i GeoMap.cpp):
Fold kodeboks ind/udKode 

Linie 239 i Grid.h, hvor iterator operationen defineres, ser således ud:
Fold kodeboks ind/udKode 


Det ser jo tilforladeligt ud, og fungerer for alle andre typer. Jeg går ud fra at problemet er at vector<bool> er implementeret som bits, for at gøre den mere effektiv. Jeg kunne godt tænke mig at udnytte denne effektivitet, da jeg har nogle tusind potentielle Grid<bool> objekter i spil, à et par tusind felter hver - lige nu bruger jeg <int>, men det går langsomt og tager hukommelse.
Spørgsmålet er: kan jeg implementere min iterator (eller gøre noget andet smart), så jeg ikke får <bool> problemet?
Tak,



Indlæg senest redigeret d. 15.10.2008 12:19 af Bruger #8249
8 svar postet i denne tråd vises herunder
0 indlæg har modtaget i alt 0 karma
Sorter efter stemmer Sorter efter dato
Jeg er ikke sikker på at jeg helt forstår din kode.
Jeg har prøvet at reproducere problemet, men uden held. Kunne du prøve at poste et minimalt, men komplet, eksempel der viser problemet?



Jeg er ikke sikker på at jeg helt forstår din kode.

Uha, det lyder ikke godt at du ikke forstår min kode. Jeg er 100% selvlært programmør, så jeg laver formentlig en masse vrøvl.

Jeg formoder der er min loadSQSfile() der virker uigennemskuelig. Jeg er nødt til at læse et filformat der ser således ud:

'Worldmap.sqs'
Fold kodeboks ind/udKode 

og den lille funktion var måden jeg fandt ud af at gøre det på. Det er imidlertid ikke kun den funktion der gør vrøvl. Hvis jeg udkommenterer den kommer der fejlmeldinger initieret andre steder fra, bla. inde fra <algorithm>. Fælles for dem alle er at de brokker sig over dereferingen af iteratoren når T = bool.
Det mindste eksempel jeg lige umiddelbart kan reducere det til ser således ud:

Fold kodeboks ind/udKode 

Det åbner den lille Worldmap.sqs fil foroven. Nedarv fra Grid<bool> for at reproducere problemet.
Tak fordi du gider kigge på det (du må endelig også sige til hvis min kode kan gøres mere forståelig).



Indlæg senest redigeret d. 16.10.2008 14:29 af Bruger #8249
Du burde kunne løse problemet ved at lave operatoren om til:

Fold kodeboks ind/udKode 


Det kræver at du bruger den som:
*(*iter) = bool(c-48);

At jeg ikke forsod din kode skyldes mere denne kommentar:

jeg har en templated klasse 'Grid<T>' der arver fra std::vector<T> (det er reelt en 2d-vector, og arver altså faktisk fra std::vector<std::vector<T> > ).




Indlæg senest redigeret d. 16.10.2008 23:12 af Bruger #4996
Jeg er desværre ikke sikker på at det løser problemet. I den konkrete funktion kan jeg bruge
*(*iter) = bool (c-48);
men jeg ville gerne have at min iterator opførerer sig som en STL iterator; for eksempel implementerer jeg en constructor fra en anden Grid klasse, der kan kopiere en GeoMap, med:
Fold kodeboks ind/udKode 

der giver samme problem.
Ideen er at jeg gerne vil kunne bruge STL algoritmerne til at foretage forskellige operationer med på denne måde (jeg forestiller mig at det er mere elegant). Men det fungerer desværre ikke hvis man skal dereferere dobbelt.



PS: her er sammenhængen for kodestumpen:
Fold kodeboks ind/udKode 




Indlæg senest redigeret d. 17.10.2008 10:40 af Bruger #8249
Jeg er bange for at det er en "no can't do" :-(

Problemet er at man ikke kan adressere de enkelte bits i en std::vector<bool> på samme måde som havde det været chars. Bits har ikke adresser, så man kan ikke returnere en T& fra operator* og modificere bitten på den måde, for man har brug for mere information en blot en reference.

Så hvis du vil bruge std algoritmer bliver du nok nødt til at bruge en std::vector<char>

Se også: http://www.gotw.ca/publications/N1185.pdf



Jeg er bange for at det er en "no can't do" :-(

OK, det var jeg også begyndt at blive bange for, men det var fedt at få det afklaret. Jeg holder fast i min kode som den er :-) Det er ærgerligt, jeg synes ellers også at bit-operationer er sådan en elegant form for programmering.
Og tak for den interessante reference. Sådan som jeg læser den, ser det faktisk ud som om en vector<bool> ikke er hurtigere end en vector<char>; i R (det programmeringssprog jeg bruger til dataanalyse) er bitvise vektorer 32 gange så hurtige (på 32 bit) - da det tilsyneladende ikke gælder for C++ er jeg godt tilfreds med at lægge mit <bool> forsøg på hylden.



Indlæg senest redigeret d. 17.10.2008 13:48 af Bruger #8249
Der er alt mulig grund til at tro at en vector<bool> er en del langsommere, til nogle opgaver, end vector<char>
At læse og sætte enkelte værdier, med f.eks. operator= vil være langsommere, da der skal udføres bit-shift og maskering.

Men vector<bool> fylder mindre, og bør derfor være hurtigere at kopiere.



Hmm jeg kan se at performance er en hel videnskab :)
Jeg bruger assignment og dereferering betragteligt mere end kopiering, så det lyder som om vector<char> er det rette valg.
Nu du gør opmærksom på det kan jeg selvfølgelig godt se at vector<char> er et mere oplagt valg en vector<int> - jeg tror jeg var kommet til at glemme at char ikke kun er til bogstavtegn.
Nu har jeg ændret koden til vector<char> og har følelsen af at det nok er det mest optimale.
Jeg er dog lidt bekymret, da jeg hidtil har brugt værdien '-9999' til at beskrive et manglende data punkt. Med vector<char> må jeg bruge '255', og det er garanteret sådan noget der vil give mig problemer før eller siden... - det problem var selvfølgelig endnu vanskeligere med vector<bool> hvor jeg havde måttet finde en hel tredje måde at gøre det på.
Ak ja, der er ingen der har sagt at programmering skal være let - men nu blev jeg da meget klogere på vector<T>! ;)



Indlæg senest redigeret d. 20.10.2008 10:21 af Bruger #8249
t