[C++]STL list.sort() laat elementen weg?

[Verwijderd]

Ik heb een programma geschreven die pixels (van een BMP) in een list inlaadt namelijk in de volgende lijst:

code:

     std::list<Pixel> lijst_van_pixels;

Vervolgens wordt deze lijst gesorteerd m.b.h.v. het ingebouwde sort() functie:

code:

lijst_van_pixels.sort();

Echter dan gebeurd er iets raars, er "verdwijnen" elementen uit deze lijst??? Het lijkt mij stug dat sort() elementen verwijderd? Die hoort toch enkel te sorteren.

Toch is dit zo want:

code:

    std::cout << lijst_van_pixels.size() << endl;   //DEBUG
    lijst_van_pixels.sort();
    std::cout << lijst_van_pixels.size() << endl;   //DEBUG

geeft als output:

code:

156332
25260

Nu lijkt mij dit erg raar, en het is ook erg lastig omdat daarna die lijst niet meer weggeschreven kan worden zoals het moet immers ze is kleiner geworden wat zorgt voor memory leaks.

Ik heb zelf een lijst (een template) geschreven met dezelfde mogelijkheden (push, pop, sort etc...) en daar werkt dat wel mee. Nu wou ik ook de STL-faciliteiten gebruiken i.p.v. mijn eigen template en dat werkt niet???

Ik zou dus erg graag weten wat ik fout doe hier.

[curry684]

Lijkt erop dat ie duplicates elimineert?

[Verwijderd]

curry684 schreef op 10 juni 2004 @ 13:01:
Lijkt erop dat ie duplicates elimineert?

Dat dacht ik eerst ook maar dat is niet zo, immers mijn testbeeld bevat maar 5 kleuren.

[.oisyn]

Verwijderd schreef op 10 juni 2004 @ 12:54:
Nu lijkt mij dit erg raar, en het is ook erg lastig omdat daarna die lijst niet meer weggeschreven kan worden zoals het moet immers ze is kleiner geworden wat zorgt voor memory leaks.

Hoe kom je erbij dat er memory leaks zijn? Dat de lijst kleiner is geworden betekent niet automatisch dat er nog niet vrijgegeven geheugen los loopt. Tenzij jij expliciet geheugen alloceert in een Pixel en dat niet vrijgeeft op het moment dat ie gedestruct wordt natuurlijk, maar dan is het je eigen schuld

Ik heb zelf een lijst (een template) geschreven met dezelfde mogelijkheden (push, pop, sort etc...) en daar werkt dat wel mee. Nu wou ik ook de STL-faciliteiten gebruiken i.p.v. mijn eigen template en dat werkt niet???

Ik zou dus erg graag weten wat ik fout doe hier.

Je doet niets fout, het zou gewoon niet mogen gebeuren
Welke compilerversie gebruik je?

(En trouwens, hoe ziet je Pixel er precies uit?)

[ Voor 3% gewijzigd door .oisyn op 10-06-2004 13:14 ]

[Verwijderd]

Je doet niets fout, het zou gewoon niet mogen gebeuren
Welke compilerversie gebruik je?

(En trouwens, hoe ziet je Pixel er precies uit?)

Ik gebruik MS Visual C++ 6.0 onder win2000

en een Pixel bestaat uit 3 kleuren:

code:

byte red;
byte green;
byte blue;

met byte gewoon een unsigned char.

In mijn klasse pixel zijn ook nog eens 2 operatoren gedefinieerd nl. > en < dan. Echter je doet mij aan iets denken, heeft sort() horend bij list ook de operator == nodig of niet? In mijn zelfgeschreven template had ik dat niet nodig en was enkel < en > noodzakelijk als operator maar misschien dat deze STL-functie dat wel nodig heeft.
Ik zet het er even bij, als het werkt of niet laat ik iets weten. Andere tips ook welkom. (niet dus)

Uiteraard zijn er nog allerlei andere functies gedefinieerd zoals hier in de header te zien:

code:

/*De klasse Pixel*/
#ifndef PIXEL_H
#define PIXEL_H

#include "datatypes.h"

class Pixel {
    private:
        //data
        byte red;
        byte green;
        byte blue;

    public:
        //constructie elementen:
        Pixel();                        //lege constructor
        Pixel(byte r, byte g, byte b);  //constructor met elementen
        Pixel(const Pixel &p);          //copy-constructor
        ~Pixel();           //destructor

        //Setters:
        void setRed(byte r);
        void setGreen(byte g);
        void setBlue(byte b);
        void setCollor(byte r, byte g, byte b);

        //Getters:
        byte getRed();
        byte getGreen();
        byte getBlue();

        //Operatoren:
        bool operator>(Pixel& y) const;
        bool operator<(Pixel& y) const;
        bool operator==(Pixel& y) const;
};
#endif

EDIT:
Het werkt nog niet , ondanks de == operator, deze is dus niet noodzakelijk voor het sort()

[ Voor 44% gewijzigd door Verwijderd op 10-06-2004 13:24 ]

[.oisyn]

sort heeft alleen de < nodig, maar dat is het punt niet. Hij zou niet zomaar elementen mogen verwijderen uit de list aan de hand van een comparison operator. Ik neem aan dat je niet in de constructors of de destructor Pixels gaat toevoegen of verwijderen uit de lijst?

Het enige wat ik me kan bedenken is dat het gewoon komt omdat templates in MSVC++ 6.0 (en dus de STL implementatie) gewoon gaar zijn. Ik zou echt aanraden om over te stappen naar MSVC++ 7.1. Heb je de laatste service pack (SP6) trouwens wel?

[Verwijderd]

.oisyn schreef op 10 juni 2004 @ 13:30:
sort heeft alleen de < nodig, maar dat is het punt niet. Hij zou niet zomaar elementen mogen verwijderen uit de list aan de hand van een comparison operator. Ik neem aan dat je niet in de constructors of de destructor Pixels gaat toevoegen of verwijderen uit de lijst?

Nee dat gebeurd uiteraard niet, want deze lijst is enkel in de sorteerfunctie geldig:

code:

void Beeld::sorteer() {
    std::list<Pixel> lijst_van_pixels;
    for(int i=0;i<ih.biHeight;i++) {
        for(int j=0;j<ih.biWidth;j++) {
            lijst_van_pixels.push_back(getPixel(j,i));
        }
    }
    std::cout << lijst_van_pixels.size() << endl;   //DEBUG
    lijst_van_pixels.sort();
    std::cout << lijst_van_pixels.size() << endl;   //DEBUG
    for(int l=0;l<ih.biHeight;l++) {
        for(int k=0;k<ih.biWidth;k++) {
            drawPixel(lijst_van_pixels.back(),k,l);
            lijst_van_pixels.pop_back();
        }
    }
}

die "image" is een 2dimensionele deque waar dus uiteraard niet aan geraakt wordt. En de constructors en destructors van de Pixel doen ook enkel wat ze moeten doen nl.:

code:

Pixel::Pixel() {
    red=0;
    green=0;
    blue=0;
}

Pixel::Pixel(byte r, byte g, byte b) {
    red=r;
    green=g;
    blue=b;
}

Pixel::Pixel(const Pixel &p) {
    red = p.red;
    green = p.green;
    blue = p.blue;
}

Pixel::~Pixel() {
    //alle dynamisch aangemaakte dingen hier verwijderen!
}

Pixel::Pixel(int waarde) {
    red=waarde;
    green=waarde;
    blue=waarde;
}

Het enige wat ik me kan bedenken is dat het gewoon komt omdat templates in MSVC++ 6.0 (en dus de STL implementatie) gewoon gaar zijn. Ik zou echt aanraden om over te stappen naar MSVC++ 7.1. Heb je de laatste service pack (SP6) trouwens wel?

Zou dat echt aan het gaar zijn van list.sort() liggen dan, ik kan dat haast niet geloven... Anderzijds het moet haast wel, want mijn eigen template:

code:

template <class Item>
class LIFO {
    private:
        struct node {
            Item item;
            node *next;
            node(Item x, node *t) {
                item = x;
                next = t;
            }
        };
        typedef node *link;
        link head;

    public:
        LIFO() {head = NULL;}

        ~LIFO() {           //moet er zijn en wordt aanroepen wanneer out-of-scope!!!
            while(head!=NULL) {
                link t = head->next;
                delete head;
                head = t;               
            }
        }

        void push(Item x) {
            head = new node(x,head);    //knoop dynamisch aangemaakt!
        }

        Item pop() {
            Item v = head->item;
            link t = head->next;
            delete head;
            head = t;
            return v;
        }

        int isLeeg() {
            if(head==NULL)
                return 1;   //1 bij lege lijst
            else
                return 0;   //0 bij lijst waar nog Items inzitten
        }

        void sorteer() {
            node head_b(0,NULL);    //niet dynamisch aanmaken van een knoop
            link u,x,t,b=&head_b;
            
            int tijd = time(NULL);
            if(!isLeeg()) {
                //insertionsort algoritme
                for(t=head;t!=NULL;t=u) {
                    u=t->next;
                    for(x=b;x->next!=NULL;x=x->next)
                        if(x->next->item < t->item)
                            break;
                    t->next = x->next;
                    x->next = t;
                }
                head=b->next;
                std::cout << "Lijst werd gesorteerd in " << time(NULL)-tijd << " seconden." << endl;
            } else  {
                std::cout << "Een lege lijst kan men niet sorteren..." << endl;
                exit(0);
            }
        }
};

deze werkt wel perfect.

Euh jah nieuwe versie van visual C++ ofzo da zal wel niet komen, ben maar student en eigenlijk geen MSVC++ programmer. Maar mag ik je anders om een gunst vragen, als ik je nou de hele source doormail (gezipt) zou je dan es willen zien of het bij jou wel werkt?

[ Voor 8% gewijzigd door Verwijderd op 10-06-2004 13:41 ]

[.oisyn]

Ok heb het even getest, het ligt idd gewoon aan MSVC++ 6.0 (ik heb hier SP5 overigens, misschien dat het in SP6 gefixed is)

C++:

#include <list>
#include <iostream>
#include <stdlib.h>

int main ()
{
    std::list<int> l;

    for (int i = 0; i < 100000; i++)
        l.push_front (rand () % 1000);

    std::cout << l.size () << std::endl;
    l.sort ();
    std::cout << l.size () << std::endl;
}

MSVC++ 6.0 SP5:

100000
1696

MSVC++ 7.1:

100000
100000

Het ligt niet aan duplicates, ik heb het ook getest met 10000 elementen en minder, en toen ging het wel goed

[.oisyn]

Ah, er is ook een knowledge base artikel over
http://support.microsoft....aspx?scid=kb;en-us;240014

SYMPTOMS
If a list has over 32K elements, list::sort removes the elements.
Please refer to the Sample Program in the MORE INFORMATION section for details.

RESOLUTION
The bug is in the header file <list>.

In the sort() function:

C++:

   if (_I == _MAXN)
    //_A[_I].merge(_X); /* remove this line and add the line below*/ 
    _A[_I - 1].merge(_X);

In the sort(_Pr3 _Pr) function :

C++:

   if (_I == _MAXN)
    //_A[_I].merge(_X, _Pr); /* remove this line and add the line below*/ 
    _A[_I - 1].merge(_X, _Pr);

If you are sorting through a list larger than 32K, increasing _MAXN from 15 to 25 would improve the performance.

NOTE: Since the resolution involves modifying a system header file, extreme care should be taken to make sure nothing else is changed in the header file. Microsoft is not responsible for any problems resulting due to unwanted changes to the system header files.

STATUS
Microsoft has confirmed that this is a bug in the Microsoft products that are listed at the beginning of this article.

This problem was corrected in Microsoft Visual C++ .NET.

[Verwijderd]

Heel erg bedankt, dus het ligt niet aan mij en inderdaad bij mij geeft ie ook 1696 als output bij het door jou geteste programma.

En lucky me met een kleiner prentje werkt het inderdaad

[ Voor 21% gewijzigd door Verwijderd op 10-06-2004 13:58 ]

[MSalters]

Als je toch bezig bent, er zijn meer bugs in de STL van VC6: headers istream, xstring, vector, xlocale, xtree, xmemory, string, sstream, memory, algorithm, fstream, deque en dus ook list bevatten bugs. Nieuwe versies zijn op dinkumware.com te krijgen

[^Mo^]

Dat is toch eigenlijk ook fout, ze laten deze bug dus gewoon in VC++ 6.0 zitten?

[MSalters]

Ja, er waren juridische redenen voor. In VC7.0 is het gefixt, MS stak het ook niet onder stoelen of banken, Dinkumware (de auteurs van de STL bij MSVC4+) had de fix online staan. Kortom, mogelijkheden genoeg om er iets aan te doen.