[C++] returnen van class

[riezebosch]

Mijn probleem:
Ik maak een variabele (zelfgemaakte class) aan en roep een functie aan om deze te vullen. In deze functie wordt ook een variabele van hetzelfde type aangemaakt en worden een paar bewerkingen hierop uitgevoerd. Vervolgens return ik deze variabele en moet ie gekopieerd worden in de variabele in de main-functie.

Nu het volgende: op het moment dat de functie de variabele moet returnen, wordt door de compiler eerst de destructor van de variabele aangeroepen en daarna pas de kopieerfunctie. In de destructor worden een paar pointers gedelete, wat normaliter ook zo hoort, maar in dit geval dus niet. Hierdoor gaat het kopieren dus mis...

C++:

LinkedList<int> bla()
{
    LinkedList<int> b;

    b.add(1);
    b.add(2);
    b.add(3);

    return b;
}

int main(void)
{
    LinkedList<int> b = bla();

    return 0;
}

Volgens mij is dit een compiler-probleem, en is er dus ook niet zomaar iets aan te doen. Ik kan natuurlijk een pointer naar de functie meegeven zodat er helemaal niets meer gereturned hoeft te worden, maar ik heb liever dat deze manier ook werkt (omdat die in mijn ogen duidelijker is).

Iemand eerder met dit probleem te maken gehad? Of iemand die (nog) meer verstand heeft van (Visual) C++...

[Juicy]

Creeer een nieuwe instantie van een LinkedList in bla mbv new. Gebruik daarna deze pointer om de elementen toe te voegen en retourneer deze pointer.

[BoAC]

Nope dit is een design probleem van jouw

Je maakt een lokale variable die bij het einde van de functie wordt gedestruct.

Oplossing je kan natuurlijk een object van je class aanmaken binnen je functie en de pointer returnen.
Dit object moet je natuurlijk wel deleten na het aanroepen van deze functie

edit:

Was natuurlijk weer te laat

[ Voor 8% gewijzigd door BoAC op 21-07-2003 22:19 ]

[Soultaker]

Juicy en BoAC: allebei fout. Uiteraard zou je ook heapallocatie kunnen gebruiken, maar dat levert een andere situatie op, die hier niet aan de orde is. Stackallocatie zou ook gewoon perfect moeten werken.

TS: om welke compiler gaat en wat gaat er precies mis? Gebruik je precies de code zoals je die hier gegeven hebt?

[riezebosch]

Visual C++ 6.0
Juicy en BoAC: dat zijn dus juist oplossingen die ik niet wil, want anders zou ik ook een pointer als argument mee kunnen geven (wat ook beetje standaard-oplossing is als je met array's e.d. werkt).
En het 'probleem' met de compiler is volgens mij dat ie eerst de destructor aanroept (zoals het ook hoort), en daarna pas gaat kopieren.

[MSalters]

Nee hoor, in de bovenstaande code wordt eerst de copy ctor op b aangeroepen en dan pas de dtor, ook met VC6. Als je iets anders ziet ben je waarschijnlijk de copy ctor van LinkedList vergeten cq. heb je een fout zitten in de signature, dat moet (LinkedList const& rhs) zijn.
Voor alle duidelijkheid, de = die je ziet is geen LinkedList::operator= maar ook de copy ctor.

Nou is de vraag of je Copy On Write gebruikt in Linke List, anders is een container returnen matig efficient (kopieert bv nu 3 ints, maar dat zouden er ook 300000 kunnen zijn).

[riezebosch]

heb idd wel een overloaded operator = gemaakt, maar als ik in debugmode de functie doorloop, wordt echt eerst de ~LinkedList() doorlopen en daarna pas de operator(const &LinkedList).
Copy ctor en dtor zegt me niet zoveel. Zijn dat ook functies die je dan moet overloaden, of zijn dat andere benamingen voor destructor en operator =?

En het idee is dat hij geen clone returned, maar begin- en eindpointer van de list. Ik heb het zo ingebouwd dat de LinkedList bijhoud hoeveel andere LinkedList's naar die betreffende lijst wijzen, en dan wordt in de destructor gecontroleerd of hij de enige is zodat dan pas de elementen verwijderd worden.

[ Voor 6% gewijzigd door riezebosch op 21-07-2003 23:04 ]

[Verwijderd]

riezebosch schreef op 21 July 2003 @ 23:01:
En het idee is dat hij geen clone returned...

Ja dan moet je wel met heapallocatie werken. Zou ik sowieso doen uit efficientie overwegingen. Bij lijsten (die als eigenschap hebben dat ze GROOT kunnen worden) kiest men over het algemeen niet voor stackallocatie, want je wilt niet onnodig data rondpompen.

Verder je copy constructor (als je die verder niet nodig hebt) naar de private sectie moven om dit soort ge-emmer in de toekomst te voorkomen.

[riezebosch]

edit:

Sorry, halverwege actie afgebroken maar blijkbaar toch al in db terechtgekomen...

[ Voor 79% gewijzigd door riezebosch op 21-07-2003 23:18 ]

[riezebosch]

Heapallocatie? Momenteel heb ik het zo gemaakt dat wanneer een lijst aan een ander gekoppeld wordt, er een centrale integer verhoogd wordt. En in de destructor controleer ik of deze 0 is en wordt de lijst leeggegooid, anders wordt deze integer weer met 1 verlaagd.

En de copy-constructor is de ctor?

[farlane]

Volgens mij begrijp je Soultaker niet,

Wat hij probeert te vertellen is dat die toewijzing ( LinkedList a = blah() ) geen operator = aanroept, maar de copy constructor van die LinkedList.

Over het algemeen is het zo dat als je een operator= overload, je ook de copy constructor ( LinkedList ( const LinkedList& ) ) moet overloaden.

[edit]

En de copy-constructor is de ctor?

Nee dus.. de copy contructor neemt een const ref als parameter.
Hij wordt gebruikt bij oa implicite kopieeracties zoals het returnen van een object uit een functie en bij een initialisatie als deze:

C++:

Object a
Object b = a;

Het lijkt alsof er een operator= wordt aangeroepen, maar dat is niet het geval.

[ Voor 40% gewijzigd door farlane op 22-07-2003 00:22 ]

[Soultaker]

Ehm, farlane? Volgens mij had je eerst staat "Volgens mij begrijp je MSalters niet" en dat klopte, want MSalters wees er terecht op dat de copy constructor overloaded moest zijn, om deze constructie te laten werken. (MSalters is de echte C++ expert; ik ben maar een wannabe met wat praktijkervaring )

Ik weet niet waarom je dat in "Volgens mij begrijp je Soultaker niet" hebt veranderd, want mijn reactie was niet direct relevant voor riezebosch.

edit:
Gelijk even een nuttige bijdrage van maken. Je klasse heeft waarschijnlijk de volgende methoden:

C++:

class Voorbeeld
{
public:
    // default constructor (eventueel met argumenten)
    Voorbeeld()
    {
        x = 123;
    }

    // destructor
    ~Voorbeeld()
    {
    }

    // copy constructor
    Voorbeeld(const Voorbeeld& obj)
    {
        x = obj.x;
    }

    // assignment operator
    Voorbeeld& rhs operator=(const Voorbeeld& rhs)
    {
        x = rhs.x;
        return *this;
    }

private:
    int x;
}

De copy constructor wordt gebruikt bij de initialisatie van objecten:

code:

Voorbeeld a;  // default constructor
Voorbeeld b(a);  // copy constructor
Voorbeeld c = a;  // equivalent aan c(a) --> copy constructor

Wat dus van fundamenteel belang is dat op de derde regel ook de copy constructor wordt gebruikt. Als je wil dat de assignment operator wordt gebruikt, kun je dat zo doen:

code:

Voorbeeld d; // default constructor
d = a;  // assignment operator

Maar dit is minder efficient, omdat dan eerst (nodeloos?) de default constructor aangeroepen wordt. Zoals farlane al zei, hoor je de assignment operator en de copy constructor tegelijk te definiëren (omdat het logisch is dat je kunt kopiëren wanneer je kunt toekennen), net zoals het logisch is om de + en - operatoren tegelijk te definiëren. Wil je de definitie achterwege laten, dan is het wel zo netjes om de copy constructor en/of assignment operator private te maken, zodat niet per ongeluk de default copy constructor of assignment operator, die de compiler automatisch genereert als je ze zelf niet definieert, aangeroepen wordt.

Overigens doet de default copy constructor/assignment operator een member-wise copy/assignment; in veel gevallen is dat afdoende, maar voor 'domme' pointer velden doorgaans niet.

[ Voor 71% gewijzigd door Soultaker op 22-07-2003 02:50 ]

[riezebosch]

Heeeelemaal gelijk! Overloaded Copy Constructor gemaakt (had geen idee wat dat inhield, thanks to Google), en nu werkt het perfect. Precies zoals bedoeld (thanks to MSalters).

[riezebosch]

Bij b = a wordt volgens mij wel de overloaded operator = aangeroepen (heb er ff een cout in gezet). En bij b = bla() wordt idd de copy constructor aangeroepen.

Deze is helemaal mooi:

C++:

LinkedList<int> b;
b = bla();

Nu worden zowel de overloade copy constructor alsook de overloaded operator = aangeroepen (blijkt uit de cout's in beide functies)...

[ Voor 109% gewijzigd door riezebosch op 22-07-2003 02:47 ]

[curry684]

riezebosch schreef op 22 July 2003 @ 02:43:
Bij b = a wordt volgens mij wel de overloaded operator = aangeroepen (heb er ff een cout in gezet). En bij b = bla() wordt idd de copy constructor aangeroepen.

Dit hangt van de constructie af:

C++:

Object a; // Default constructor
Object b(a); // Copy constructor
Object c = a; // Copy constructor
b = a; // Operator = omdat B al constructed is

[Soultaker]

Erm... anders zitten jullie even in het holst van de nacht allemaal reacties te typen terwijl ik m'n post zit te editten!

[curry684]

Doen we toch

[Soultaker]

riezebosch schreef op 22 July 2003 @ 02:43:
Deze is helemaal mooi:

C++:

LinkedList<int> b;
b = bla();

Nu worden zowel de overloade copy constructor alsook de overloaded operator = aangeroepen (blijkt uit de cout's in beide functies)...

Ik neem aan dat voor b gewoon de default constructor aangeroepen wordt. De copy constructor wordt waarschijnlijk gebruikt om de return value in de functie bla() te construeren. Ik kan me voorstellen dat Visual C++ in debug mode al die conversies expliciet uitvoert:

C++:

LinkedList<int> bla()
{
    LinkedList<int> b;  // default constructor

    b.add(1);
    b.add(2);
    b.add(3);

    return b; // copy constructor om result value te construeren
}

LinkedList<int> b; // default constructor
b = bla(); // assignment operator

Ik mag trouwens hopen dat Visual C++ al die conversies elimineert in een release build; met GCC kan ik de hele situatie zelf zonder optimalisaties niet nabootsen, want die gebruikt gewoon één variabele. (Blijkbaar mag dat van de C++ specificatie, ondanks dat mijn constructors/destructors echt relevante side effects hebben; curry684 of MSalters weten vast wel hoe dat zit.)

[curry684]

Soultaker schreef op 22 juli 2003 @ 03:08:
Ik mag trouwens hopen dat Visual C++ al die conversies elimineert in een release build; met GCC kan ik de hele situatie zelf zonder optimalisaties niet nabootsen, want die gebruikt gewoon één variabele. (Blijkbaar mag dat van de C++ specificatie, ondanks dat mijn constructors/destructors echt relevante side effects hebben; curry684 of MSalters weten vast wel hoe dat zit.)

Wat officiele specificaties betreft is MSalters de held hiero, maar het lijkt mij op z'n zachtst gezegd onwaarschijnlijk dat non-default constructors weggeoptimaliseerd mogen worden omdat je er zoals je aangeeft side-effects in weg kunt werken. Als het puur default copy-constructors betreft is de optimalisatie geen probleem.

Afaik schrijft de C++ standaard sowieso niets voor wat betreft mogelijke optimalisaties, dat wordt aan de compilerbouwers zelf overgelaten met dien verstande dat de resulterende code uiterlijk hetzelfde resultaat dient te vertonen onder alle compilers: en het lijkt me dat men met deze optimalisatie daartegen zondigt.

[MSalters]

0) ctor is constructor, copy ctor is dus de copy constructor. dtor is idd. de destructor

1) overloaded copy constructors zijn extreem zeldzaam. In de parktijk heb je er maar een, X::X ( X const& rhs). De overloaded variant zou X::X ( X const volatile& rhs) zijn.

2) Ook een user-defined copy ctor mag in sommige situaties weggeoptimaliseerd worden. De gangbare term hiervoor is RVO, return value optimalisation. Een variant is NRVO, Named Return Value Optimalisation. Dit mag ook als er een side-effect is. Bijvoorbeeld een copy ctor die een std::cout<< doet mag ook weggeoptimaliseerd worden. Uiteraard moet de bijbehorende dtor ook worden verwijderd, zodat de ctor/dtor balans behouden blijft.

[MSalters]

riezebosch schreef op 22 juli 2003 @ 02:43:

C++:

LinkedList<int> b;
b = bla();

Nu worden zowel de overloade copy constructor alsook de overloaded operator = aangeroepen (blijkt uit de cout's in beide functies)...

Yep; bla() retourneert mbv de copy ctor en dat wordt weer geassigned aan b. bla() weet nl. niet dat 'ie aan b moet gaan assignen, en dat is ook niet overal het geval, dus bla() moet die kopie wel maken - de LinkedList op de stack van bla() is immers out of scope.

[farlane]

Soultaker schreef op 22 juli 2003 @ 02:37:
Ehm, farlane? Volgens mij had je eerst staat "Volgens mij begrijp je MSalters niet" en dat klopte, want MSalters wees er terecht op dat de copy constructor overloaded moest zijn, om deze constructie te laten werken. (MSalters is de echte C++ expert; ik ben maar een wannabe met wat praktijkervaring )

Dat had ik er idd eerst staan. Vraag ik me af waarom ik dat veranderd heb.

Anyweeyz, misschien had het iets met het tijdstip te maken ?

[Soultaker]

MSalters schreef op 22 juli 2003 @ 10:29:
Ook een user-defined copy ctor mag in sommige situaties weggeoptimaliseerd worden. De gangbare term hiervoor is RVO, return value optimalisation. Een variant is NRVO, Named Return Value Optimalisation. Dit mag ook als er een side-effect is. Bijvoorbeeld een copy ctor die een std::cout<< doet mag ook weggeoptimaliseerd worden. Uiteraard moet de bijbehorende dtor ook worden verwijderd, zodat de ctor/dtor balans behouden blijft.

Aha, dat verklaard een boel. Ik had de volgende testcase gemaakt:

C++:

#include <iostream>
using namespace std;

class Test
{
    public:
        Test() { cout << this << ": constructor" << endl; }
        Test(const Test& t) { cout << this << ": copy constructor" << endl; }
        ~Test() { cout << this << ": destructor" << endl; }
        
        void method() { cout << this << ": method" << endl; }
};

Test func()
{
    Test y;
    y.method();
    return y;
}

int main()
{
    Test x = func();
    x.method();    
    return 0;
}

En ik was wel verbaasd dat GCC daar (zonder optimalisaties!) code van maakte die als volgt runt:

code:

%./test
0xbfbffb6c: constructor
0xbfbffb6c: method
0xbfbffb6c: method
0xbfbffb6c: destructor

Er wordt dus maar één object gebruikt en de copy constructors worden gewoon geëlimineerd. Als het goed is, is dat ook absoluut geen probleem (al met al heeft een default constructor doorgaans meer side effects dan een copy constructor of assignment operator), maar ik moet toch zeggen dat ik niet verwacht had dat zo'n optimalisatie toegestaan zou zijn.

Verder geldt natuurlijk in het algemeen dat alle optimalisaties die de waarneembare werking van het programma niet aantasten toegestaan zijn, maar in deze situatie veranderd ook de uitvoer. Ik vind het wel wat vreemd dat een geldig C++ dus andere uitvoer kan geven, naar gelang welke compiler gebruikt wordt. Maar goed, het is nu eenmaal zo; weer wat om rekening mee te houden.

[MSalters]

Een van de redenen waarom C++ zo snel is is dat er veel aan de compiler wordt overgelaten. sizeof(char*) mag 4 of 8 zijn, net wat de CPU het beste uitkomt. sizeof(wchar_t) idem, dat mag 2 of 4 zijn, afhankelijk of een compiler Unicode versie 2 of 3/4 wil supporten. Print dat en je hebt andere uitvoer.
Het idee is kortom niet dat alle compilers exact dezelfde uitvoer geven; het idee van portabiliteit is dat alle compilers dezelfde uitvoer geven als dat de programmeur alle implementation-defined gedrag mijdt.

[.oisyn]

Verwijderd schreef op 21 July 2003 @ 23:08:
Ja dan moet je wel met heapallocatie werken. Zou ik sowieso doen uit efficientie overwegingen.

Zou ik sowieso niet doen, uit diezelfde efficientie-overwegingen. Bovendien geeft dat een extra verantwoordelijkheid voor de gebruiker van de functie: het geheugen moet immers ook weer vrijgegeven worden. Het alternatief is gewoon een non-const pointer/reference naar een linked list als parameter. De caller kan een lijst meegeven waarin de resultaten moeten komen te staan. Diezelfde caller kan er eveneens voor kiezen de lijst op de stack of op de heap te alloceren.

De caller is verantwoordelijk voor de allocatie, en ook voor de deallocatie. Dat is vanuit design-overwegingen ook een stuk mooier. Bovendien kan er voor een heel ander stuk geheugen worden gekozen dan de stack of de heap. Neem bijvoorbeeld een memory-mapped file (of je daar dit soort objecten in wilt instantieren is een ander verhaal ), of iets dat gewoon een custom memory manager nodig heeft.

Nee, ik vind functies die pointers naar eigen gealloceerd geheugen returnen over het algemeen gewoon evil

Soultaker over gcc

En wat gebeurt er als je func () door een andere translation unit laat compilen? Krijg je dan hetzelfde resultaat?

[MSalters]

.oisyn schreef op 22 July 2003 @ 23:27:
ik vind functies die pointers naar eigen gealloceerd geheugen returnen over het algemeen gewoon evil

std::auto_ptr< > ? Smart pointer met custom deallocator ?

[Soultaker]

.oisyn schreef op 22 juli 2003 @ 23:27:
En wat gebeurt er als je func () door een andere " laat compilen? Krijg je dan hetzelfde resultaat?

Ik heb nu de volgende broncode:

C++:

// a.h
#ifndef A_H_INCLUDED
#define A_H_INCLUDED

class Test
{
    public:
        Test();
        Test(const Test& t);
        ~Test();
 
        void method();
};

#endif // ndef A_H_INCLUDED

C++:

// a.cc
#include "a.h"
#include <iostream>

using namespace std;

Test::Test() { cout << this << ": constructor" << endl; }
Test::Test(const Test& t) { cout << this << ": copy constructor" << endl; }
Test::~Test() { cout << this << ": destructor" << endl; }
void Test::method() { cout << this << ": method" << endl; }

C++:

// b.h
#ifndef B_H_INCLUDED
#define B_H_INCLUDED

#include "a.h"

Test func();

#endif // ndef B_H_INCLUDED

C++:

// b.cc
#include "b.h"

Test func()
{
    Test y;
    y.method();
    return y;
} 

C++:

// c.cc
#include "a.h"
#include "b.h"

int main()
{
    Test x = func();
    x.method();    
    return 0;
}

En ik compileer dit als volgt:

code:

        c++ -O0 -c a.cc -o a.o
        c++ -O0 -c b.cc -o b.o
        c++ -O0 -c c.cc -o c.o
        c++ -O0 -o test a.o b.o c.o

Als ik vervolgens test run, is mijn uitvoer nog steeds hetzelfde, dwz.:

code:

%./test
0xbfbffb64: constructor
0xbfbffb64: method
0xbfbffb64: method
0xbfbffb64: destructor

Dat komt volgens mij omdat die b.cc één compilation unit is en die kan het kopiëren van de lokale variabele y als return value al voorkomen (door gewoon y op de stack te alloceren en te laten staan als return value). Vervolgens gebruikt de main method gewoon de waarde die door func() op de stack geplaatst is als lokale variabele. Hierdoor wordt kopiëren vermeden en zijn alle individuele source files toch correct gecompileerd.

Ik vind het echter wel vreemd dat dit al zo efficiënt gebeurt zonder enige vorm van optimalisatie. Misschien is die -O optie voor het uitvoeren van RTL optimalisaties en worden deze optimalisaties hoe dan ook uitgevoerd door de C++ backend die de RTL code genereert?

edit:
Het is trouwens GCC 3.2.1; ik weet niet of GCC 2.95 op dezelfde manier werkt?

code:

%c++ -v
Using built-in specs.
Configured with: FreeBSD/i386 system compiler
Thread model: posix
gcc version 3.2.1 [FreeBSD] 20021119 (release)

edit2:
Ahhh, als ik -fno-elide-constructors meegeef, werkt het wel zoals verwacht! (Comments door mij toegevoegd.)

code:

%./test
# in func
0xbfbffb10: constructor             # construct y
0xbfbffb10: method          # y.method
0xbfbffb54: copy constructor        # return y 
0xbfbffb10: destructor              # destruct y

# in main
0xbfbffb64: copy constructor        # construct x
0xbfbffb54: destructor              # destruct return value
0xbfbffb64: method                  # x.method
0xbfbffb64: destructor              # destruct x

De GCC documentatie vermeldt echter:

The default behavior (`-fno-elide-constructors') is specified by the draft ANSI C++ standard. If your program's constructors have side effects, using `-felide-constructors' can make your program act differently, since some constructor calls may be omitted.

Allemaal goed en wel, maar blijkbaar wijkt het default gedrag dus af van het in de documentatie beloofde gedrag! Een beetje slordig, of mis ik iets?

[ Voor 32% gewijzigd door Soultaker op 23-07-2003 01:19 ]

[MSalters]

Slordige documentatie, ja. Dat is wel de norm voor GCC. Het gedrag is wel conform de officiele ISO C++ standaard. Jason Merill van het GCC team zit in de C++ commissie, dus die weet heus wel hoe het moet.

[farlane]

Dat kan wel zijn,

maar het default gedrag van gcc is dus kennelijk niet conform de standaard.

[.oisyn]

MSalters schreef op 23 July 2003 @ 00:23:
[...]

std::auto_ptr< > ? Smart pointer met custom deallocator ?

even wat nuanceren: ik had het over kale pointers waar je zelf een delete([]) op moet doen. Dat vind ik evil
Bij smartpointers is het een ander verhaal, omdat je dan al automatisch niet meer verantwoordelijk bent voor de destruction van het object of array
Maar dan moet zo'n smartpointer wel de returnvalue zijn, zodat het gebruik ervan geforceerd wordt, en het geheugen ook automatisch gedelete wordt als je niets met de return value doet

[Soultaker]

farlane schreef op 23 July 2003 @ 11:01:
Dat kan wel zijn, maar het default gedrag van gcc is dus kennelijk niet conform de standaard.

Ik moet zeggen dat ik de standaard niet ken, maar in die documentatie zie ik alleen staan dat "the default behavior (`-fno-elide-constructors') is specified by the draft ANSI C++ standard"; ik weet niet in hoeverre die "draft ANSI C++ standard" verschilt van bestaande ISO/ANSI C++ standaarden. Of is dat hetzelfde?

Overigens krijgt ik met "c++ -pedantic -ansi" ook de geoptimalsieerde uitvoer, dus dat doet vermoeden dat "de standaard" (welke dat dan ook is) die optimalisaties toch niet verbiedt. Het fijne van standaarden is dat erzoveel zijn om uit te kiezen. Dat neemt niet weg dat het gedrag van GCC toch echt afwijkt van het gedocumenteerde gedrag, of ik heb gewoon iets raars in mijn configuratie zitten (maar ik zou dan niet weten wat).

[ Voor 5% gewijzigd door Soultaker op 23-07-2003 15:54 ]

[riezebosch]

Hier het resultaat: http://home.wanadoo.nl/riezebosch/LinkedList.zip.

Het idee is dat de LinkedList een internal iterator heeft, maar dat ook meerdere lijsten naar dezelfde wijzen (als het ware external iterators op elkaar dus...)

Graag commentaar/feedback op de code (ok, punt 1: weinig commentaar...)

[Soultaker]

riezebosch schreef op 23 juli 2003 @ 17:11:
Hier het resultaat: http://home.wanadoo.nl/riezebosch/LinkedList.zip.

Het idee is dat de LinkedList een internal iterator heeft, maar dat ook meerdere lijsten naar dezelfde wijzen (als het ware external iterators op elkaar dus...)

Graag commentaar/feedback op de code (ok, punt 1: weinig commentaar...)

Ik mis het commentaar niet echt, eerlijk gezegd. Misschien één regeltje per attribuut en methode, maar binnen de methoden is commentaar hier echt niet nodig. Verder heb ik wel het een en ander aan commentaar.

Waarom krijgen methoden als add() en mod() een object value (OBJ) mee in plaats van een const reference (const &OBJ)? Nu moet nodeloos een kopie op de stack gemaakt worden, terwijl je die kopiën vervolgens niet wijzigt maar alleen maar aan een nieuw element toekent.

Verder lijkt me dat een Item klasse beter met het object dat er in moet geinstantieerd kan worden, in plaats van dat je eerst een 'leeg' object aanmaakt en daarna het juiste object toekent. Dat is efficiënter en bovendien kun je dan ook objecten zonder default constructor in je LinkedList kwijt, wat nu onmogelijk is.

Overigens vraag ik me af of het nuttig is om de grootte van je linked list op te slaan, als je toch geen indices kan gebruiken om de elementen te benaderen. Het is de vraag of je de grootte vaak nodig hebt (ik denk het niet, namelijk) en dan is het waarschijnlijk efficiënter om de grootte niet in het object te hebben staan (maar dynamisch te berekenen). Heb je er bewust voor gekozen om deze grootte op te slaan? Wat waren de argumenten hiervoor?

Verder heb ik zo m'n twijfels bij de implementatie van je linked list. Als de lijst leeg is, heb je er al twee elementen in staan, die allebei geen objectwaarde hebben. Behalve dat dat nogal zonde is, maakt het het weer onmogelijk om objecten op te slaan in de lijst die geen default constructor hebben. Ik zie grote voordelen van een implementatie op basis van een cyclisch verbonden lijst. Je kunt de drie members, FirstItem, LastItem en CurrentItem, dan simpelweg tot één member (CurrentItem) combineren!

Tenslotte vind ik dat je nogal vreemd geheugenbeheer uitvoert. Je lijstobjecten delen het geheugen van elkaar, zelfs als je naar lijsten gaat het schrijven. Is het niet de bedoeling dat je copy-on-write toepast? Of wil je het echt op deze manier doen? Waarom zou een gebruiker op deze manier met instanties van objecten werken en niet gewoon met references naar objecten?

edit:
Google ownage! Alweer een lange tijd geleden kwam ik dit artikel tegen: Designing A Linked List Class. Het gaat over het ontwerp van een single linked list (zoals die ook in de STL zit). Het mooie van het artikel is dat het niet een korte tutorial is, maar een echte in-depth analyse van de verschillende relevante ontwerpaspecten.

Hoewel copy-on-write niet onder het artikel valt, worden wel andere belangrijke aspecten uitgelicht (zoals const-correctness). Ook worden er nogal wat mogelijke variaties in het ontwerp en de implementatie opgenoemd en geanalyseerd. Al met al dus een uitstekend artikel; een echte aanrader!

[ Voor 13% gewijzigd door Soultaker op 23-07-2003 23:02 ]

[MSalters]

Soultaker schreef op 23 July 2003 @ 15:52:
[...]

Ik moet zeggen dat ik de standaard niet ken, maar in die documentatie zie ik alleen staan dat "the default behavior (`-fno-elide-constructors') is specified by the draft ANSI C++ standard"; ik weet niet in hoeverre die "draft ANSI C++ standard" verschilt van bestaande ISO/ANSI C++ standaarden. Of is dat hetzelfde?

Overigens krijgt ik met "c++ -pedantic -ansi" ook de geoptimalsieerde uitvoer, dus dat doet vermoeden dat "de standaard" (welke dat dan ook is) die optimalisaties toch niet verbiedt. Het fijne van standaarden is dat erzoveel zijn om uit te kiezen. Dat neemt niet weg dat het gedrag van GCC toch echt afwijkt van het gedocumenteerde gedrag, of ik heb gewoon iets raars in mijn configuratie zitten (maar ik zou dan niet weten wat).

"Draft" is engels voor "voorlopige versie", "voorgestelde versie", e.d. Voluit heet dat document de FDIS, Final Draft for International Standard. Dat is dus de laatste publieke werkversie voordat de standaard ingestemd is. Om de standaard door de stemming heen te krijgen zijn er nog wijzigingen doorgevoerd, en blijkbaar is dit er een van. Ik ken ze ook niet allemaal, twee documenten van die dikte vergelijken is een ramp.

De officiele standaard laat het "eliden"van copy constructors (soms) toe. Ik dacht dat dat oook de enige ctors waren die GCC weglaat; ongebruikte objecten hebben dus wel een ctor call. Dwz.

code:

#include "MyClass.h" 
void foo() {
  MyClass doetniks;
}

levert keurig een ctor en een dtor call op (zoals het hoort).

[MSalters]

Soultaker schreef op 23 July 2003 @ 22:50:
edit:
Google ownage! Alweer een lange tijd geleden kwam ik dit artikel tegen: Designing A Linked List Class. Het gaat over het ontwerp van een single linked list (zoals die ook in de STL zit).

Check: "De STL" is een enigzins vaag begrip. Officieel is het een sgi library. Een oudere versie van HP is voorgedragen als onderdeel van de C++ standaard library. In die versie zat nog geen slist (zoals de huidige sgi single-linked list class heet).

Nou maakt dat op zich niet veel uit; de STL (in alle versies, inclusief de Standard Library versie) is uitbreidbaar met andere classes en algoritmes die het CIA model volgen. Een sgi linked list class werkt dus perfect samen met de standaard <algorithm>

[riezebosch]

Weet trouwens ook zelf niet of ik al happy ben met deze implementatie hoor. Was het ff aan het uitproberen. Had eerst alleen linkedlist met external iterator. Maar dit leek me wel handig. Bedant voor je tips trouwens, Soultaker (dat je ff de tijd nam ernaar te kijken).

[riezebosch]

Soultaker:
dat idee van een gesloten ring spreekt me wel aan, heb er ook wel eerder aan gedacht, maar dan kan je toch niet bijhouden of je het kringetje nou al rond bent geweest als je alle elementen keertje langs moet lopen?

De grootte is idd misschien overbodig, want daar gebruik je meestal toch bof() en eof() voor.

En wat bedoel je met copy-on-write? Ik heb juist dat delen van die Count (en Size) gedaan omdat op die manier de destructor weet of ie de elementen ook moet verwijderen.

[Soultaker]

riezebosch schreef op 25 July 2003 @ 12:46:
Soultaker:
dat idee van een gesloten ring spreekt me wel aan, heb er ook wel eerder aan gedacht, maar dan kan je toch niet bijhouden of je het kringetje nou al rond bent geweest als je alle elementen keertje langs moet lopen?

Nee, dat klopt inderdaad. Als je de iterator semantiek wil behouden moet je inderdaad twee pointers gebruiken. (Ik nam alvast een voorschot op de argumenten in het artikel waar ik naar verwees: "There are a few ways to access elements in a list. Bad: A list class could have a notion of a current node.")

In het algemeen zou ik dus aanraden om een losse iterator te definiëren, maar het kan inderdaad ook wel in deze klasse, met een aparte pointer naar het eerste en naar het "huidige" element.

En wat bedoel je met copy-on-write? Ik heb juist dat delen van die Count (en Size) gedaan omdat op die manier de destructor weet of ie de elementen ook moet verwijderen.

Het grote probleem met je huidige implementatie is dat je objecten allemaal dezelfde gegevens gebruiken:

C++:

LinkedList<int> ll1;
ll1.add(1);
ll1.add(2);
ll1.add(3);
LinkedList<int> ll2 = ll1;
ll2.add(4);
ll1.size(); // 4!!

Kortom, als je ll2 construeert uit ll1 en je wijzigt ll2, dan wijzig je ll1 ook. Het idee van object georïenteerd programmeren is dat elk object een eigen identiteit heeft, ongeacht van andere objecten. Als ik een objectwaarde ontvang (bijvoorbeeld als functie argument) dan verwacht ik als programmeur dat alle wijzigingen die ik binnen die functie op het object doe, verdwijnen zodra de functie verlaten wordt. Het object wordt dan immers opgeruimd.

Ik zie dan ook het nut niet van de copy constructor en assignment operator, zoals jij ze nu geïmplementeerd hebt, want ze werken nu exact alsof je refences kopieert. Vergelijk de volgende code met die hierboven:

C++:

LinkedList<int> ll1;
ll1.add(1);
ll1.add(2);
ll1.add(3);
LinkedList<int2> &ll2 = l11;  // let op &!
ll2.add(4);
ll1.size();     // 4!

Het enige verschil is dat jij intern een heleboel overhead hebt met reference counting en het indirect benaderen van velden zoals het aantal elementen.

Wat ik dus wilde zeggen is dat het implementeren van copy semantics (constructor en assignment operator) alleen nuttig is als je ook daadwerkelijk een kopie maakt van de inhoud van het object in kwestie (een zogeheten "deep copy"). De makkelijkste manier is om direct een in de copy constructor (of dus assignment operator, maar die zal ik voor het type-gemak even buiten beschouwing laten ) de hele datastructuur te kopiëren. Dat betekent dat je dan geen reference count hoeft bij te houden.

Copy on write werkt eigenlijk letterlijk zoals de naam suggereert. Als je de copy constructor gebruikt, wordt de onderliggende datastructuur nog niet gekopieerd, maar wordt wel de onderlinge reference count verhoogd. Zodra de onderliggende gegevens echter worden aangepast (met mod() of add() of welke andere methode die de inhoud wijzigt dan ook) dan wordt een onafhankelijke kopie van de gegevens gemaakt. Het gaat er dus om, dat copy on write naar buiten hetzelfde gedrag vertoont als een "domme' implementatie die altijd de inhoud kopieert, behalve dat een implementatie die van copy on write gebruik maakt gemiddeld efficiënter zou kunnen zijn (omdat het kopiëren wordt vermeden als alleen lees-acties uitgevoerd worden op het object), ten koste van wat extra beheer. Of dit in de praktijk ook winst oplevert zou ik zeker in het algemeen niet durven zeggen.

Het eerste deel van een copy on write implementatie heb je al gemaakt (namelijk het verhogen van de reference count). Het tweede deel moet je nog doen, bijvoorbeeld door een methode toe te voegen die het object kan kopiëren. Een stukje voorbeeldcode zegt genoeg:

C++:

private:
void prepareWrite()
{
    if(*Count > 1)
    {
        // Underlying data is shared! Create a copy before modifying it.
        Count = new int(1);
        Size = new int (*Size);
         // TODO: copy internal data structure...
        FirstItem = ...;
        LastItem = ...;
        CurItem = ...;
    }
}

Onder TODO moet je nog wel meer dan die drie regels toevoegen, omdat je niet alleen het eerste, laatste en huidige element, maar ook alle tussenliggende elementen moet kopiëren en bovendien hun referenties moet updaten. Deze methode wordt dan vanuit alle schrijvende methoden (zoals add(), mod(), etc.) aangeroepen, zodat je zeker weet dat je met een onafhankelijke datastructuur werkt.

Copy on write heeft trouwens ook wel wat nadelen die niet direct duidelijk zijn. Omdat objecten hun datastructuren kunnen delen, is het niet direct gegarandeerd dat de datastructuren binnen een enkele thread gebruikt worden, wanneer een object binnen een enkele thread gebruikt wordt. Veel STL containers zijn bijvoorbeeld alleen veilig als ze vanuit verschillende threads gelezen of vanuit één thread geschreven worden; dat is praktisch eigenlijk de enige garantie die je kunt geven zonder (ingewikkelde en kostbare!) locking constructies toe te voegen. Het is duidelijk dat je met copy on write ook tussen objecten gegevens deelt, waardoor het gebruik van twee verschillende objecten in twee verschillende threads niet veilig kan zijn!

Als ik je nu dermate heb ontmoedigd dat je zeker geen copy on write wilt implementeren, dan zou ik willen suggereren om die hele reference counting eruit te gooien, want die vergroot nodeloos de grootte van je objecten in het geheugen, voegt nodeloos extra allocaties en indirectiestappen toe (voor Count en Size), en kost je nodeloos executieprestaties omdat je de reference count up to date moet houden, zonder dat je er verder iets mee doet. Maak dan liever een explicit (!) deep copying constructor (en assignment operator) of maak de copy constructor en assignment operator private en implementeer ze gewoon niet.

[.oisyn]

Soultaker schreef op 25 July 2003 @ 13:38:
In het algemeen zou ik dus aanraden om een losse iterator te definiëren, maar het kan inderdaad ook wel in deze klasse, met een aparte pointer naar het eerste en naar het "huidige" element.

let wel dat, als je de eerste node verwijderd uit de lijst, je alle bestaande iterators invalidate, omdat ze allemaal een ongeldige eerste node hebben

[MSalters]

... en dat is dus een ongebruikelijk gedrag voor list iterators. Wat net zo goed kan is een iterator met pointer naar huidige object+pointer naar list object zelf. Dat list object verandert niet, en kan altijd de huidige eerste node geven.

In de praktijk blijkt dat COW zelden een optimalisatie is. Het is alleen verstandig als uit profilen blijkt dat je veel objecten kopieert en ongewijzigd delete.