[C++/STL/Visual studio 6] std::sort probleem

[12_0_13]

Ik probeer in C++ in visual studie 6 mbv de STL (std::sort()) een lijst te sorteren, maar ik krijg allemaal errors naar mijn hoofd, in C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\algorithm.

Kan iemand mij misschien vertellen of het aan mij ligt of aan VC++ ?

dit is in kort wat ik wil:

C++:

class Node
{
public:
    double currentDistance;
    typedef std::auto_ptr<Node> Ptr;
};

std::list<Node::Ptr> nodes;

class CloserNode
{
public: 
    bool operator () (const Node::Ptr &x, const Node::Ptr &y) 
    {
        return (x->currentDistance < y->currentDistance);
    }
};


std::sort(nodes.begin(), nodes.end(), CloserNode() );

[whoami]

Altijd handig als je verteld welke errors je krijgt...

[AaroN]

Geef eens de exacte foutmeldingen..?

... code lijkt mij namelijk wel te kloppen

[ Voor 44% gewijzigd door AaroN op 20-04-2004 11:01 . Reden: grrr, 1 sec te laat :) ]

[Verwijderd]

Je gebruikt auto_ptrs in je comparator CloserNode, terwijl std::list en std::sort iterators en references gebruiken, maar geen auto_ptrs.

C++:

typedef std::list<Node> nodes;

class CloserNode
{
public:    
    bool operator () (const Node& x, const Node& y)  const
    {
        return (x.currentDistance < y.CurrentDistance);
    }
}; 

edit:
Containers van auto_ptrs is een grote don''t (ik verkeek me op je code).

[ Voor 35% gewijzigd door Verwijderd op 20-04-2004 11:11 . Reden: toevoeging ]

[farlane]

Het probleem is dat aut_ptr de 'reference' naar je object overdragen tijdens bijvoorbeeld een copy operation ( welke optreedt bij bijvoorbeeld een push_back() ). auto_ptr willen zogezegd exclusive bezit hebben van het object.

[12_0_13]

Eeerm ik snap het niet helemaal meer:

* waarom mag ik geen auto_ptr gebruiken? Ik wil namelijk niet steeds een heel object moeten copieeren als ik push_back doe... Het is juist de bedoeling dat de auto_ptr in de list eigenaar is van het object.

Verder ben ik erachter dat list sorteert op een andere manier, namelijk

C++:

typedef std::list<Node::Ptr>        NodeListT;
typedef NodeListT::iterator     NodeListIterator;

class CloserNode
{

public: 
    bool operator() (NodeListIterator const & x, NodeListIterator const & y) 
    {
        return true; //(x->currentDistance < y->currentDistance);
    }
};

nodes.sort(CloserNode());

Maar daar kan je weer geen functor aan meegeven.. lastig hoor.

De error die ik nu krijg:

C:\DeskEYE\src\test\SOMTest.cpp(91) : error C2664: 'void __thiscall std::list<class std::auto_ptr<class Node>,class std::allocator<class std::auto_ptr<class Node> > >::sort(struct std::greater<class std::auto_ptr<class Node> >)' : cannot convert par
ameter 1 from 'class CloserNode' to 'struct std::greater<class std::auto_ptr<class Node> >'
No constructor could take the source type, or constructor overload resolution was ambiguous

[ Voor 67% gewijzigd door 12_0_13 op 20-04-2004 11:57 ]

[Verwijderd]

Het punt is dat je een lijst van auto_ptr maakt, dat gaat altijd fout. Opties:
1) Maak een lijst van "naakte" (C) pointers (slechte optie)
2) Schrijf zelf een (reference counting) smartpointer voor je Node objecten
3) Gebruik een smart_ptr uit een library als Boost (beste optie)

[farlane]

12_0_13 schreef op 20 april 2004 @ 11:41:
Eeerm ik snap het niet helemaal meer:

* waarom mag ik geen auto_ptr gebruiken?

Heb je de reply van mietje en van mij gelezen dan ?

[12_0_13]

farlane schreef op 20 april 2004 @ 12:25:
[...]


Heb je de reply van mietje en van mij gelezen dan ?

Ja dat heb ik gelezen, alleen WAAROM het niet mag is me nog niet duidelijk. Ik wil juist graag het ownership van de objecten die met "new" zijn gemaakt overgeven aan de lijst. Ik gebruik auto-pointers omdat ik dan niet meer hoef na te denken over het deleten ervan. Zit ik nou heel erg fout te denken?

Ik doe dit:

C++:

Node::Ptr n (new Node);
nodes.push_back(n);

Dat zou er toch voor moeten zorgen dat de auto-pointer in de lijst ownerhsip krijgt over de new Node die is gemaakt?

En heeft iemand miscshien dan een goed voorbeeld over hoe je een list kan sorten met een zelfgemaakte comperator?

[ Voor 4% gewijzigd door 12_0_13 op 20-04-2004 12:40 ]

[Verwijderd]

Een auto_ptr is niet reference counting, als je een auto_ptr assigned aan een andere auto_ptr dan is die laatste auto_ptr meteen de eigenaar van het (Node) object. Zelfs al krijg je een lijst van auto_ptrs syntactisch aan het werken, dan doet die lijst semantisch nog niet wat jij wilt:

C++:

struct Node {
    int x;
}; 

typedef std::auto_ptr<Node>   stupid_ptr;
typedef std::list<stupid_ptr> stupid_list;

void my_funky_func(stupid_list& l)
{
    stupid_ptr p= l.back();
    return;
    // het laatste element in de lijst is nu gewist, want p is eigenaar
    // van dat element en gaat out of scope
}

[curry684]

Je gebruikt een auto_ptr voor iets waar ie niet voor bedoeld is: garbage collection. Om te bereiken wat je wilt zul je echt zelf een simpel referencecounting mechanisme moeten schrijven, of goed aanleren om destructors goed in te vullen. Het staat je bijvoorbeeld vrij om van std::vector een template te inheriten die alleen pointers opslaat en bij destructie een delete over al die pointers gooit. Iets als dit:

C++:

template <typename t_Class>
class MyDeletingVector : public std::vector<t_Class*>
{
...
};

Ik zou echter in jouw geval een gewone vector gebruiken ipv dit soort hacks, maar da's een tweede...

[12_0_13]

Verwijderd schreef op 20 april 2004 @ 12:51:
Een auto_ptr is niet reference counting, als je een auto_ptr assigned aan een andere auto_ptr dan is die laatste auto_ptr meteen de eigenaar van het (Node) object. Zelfs al krijg je een lijst van auto_ptrs syntactisch aan het werken, dan doet die lijst semantisch nog niet wat jij wilt:

C++:

void my_funky_func(stupid_list& l)
{
    stupid_ptr p= l.back();
    return;
    // het laatste element in de lijst is nu gewist, want p is eigenaar
    // van dat element en gaat out of scope
}

Dat snap ik wel. Ik zou dat dan ook niet zo doen maar met een stupid_list::iterator. Zo traverseer je door de lijst en kan je member functies uitvoeren op de nodes door de iterator te derefencen (als dat zo heet dan). Die assignment zoals jij voorstelt komt nooit voor.

Btw ik heb de code al omgeschreven naar een versie zonder auto_ptrs, en de kopieen maar op de koop toe genomen. Verder heb ik voor de list sort een manier gevonden, door de operator < te overriden kan je sort zonder functors schrijven. Mooi vind ik dat niet echt trouwens.

@curry: Ik snap je, maar ivm met perfomance is een vector niet zo handig, er wordt namelijk heel wat gedelete en ge-insert en een vector is dan toch langzamer dacht ik.

[ Voor 13% gewijzigd door 12_0_13 op 20-04-2004 13:42 ]

[_Squatt_]

12_0_13 schreef op 20 april 2004 @ 13:38:
Verder heb ik voor de list sort een manier gevonden, door de operator < te overriden kan je sort zonder functors schrijven. Mooi vind ik dat niet echt trouwens.

Waarom niet? Ik vind dat juist een van de mooie dingen aan operator overloading. Het wordt pas lelijk als je operator<() overload om iets geheel anders te doen dan 2 objecten vergelijken.

Overigens zou de CloserNode die mietje in zijn eerste reply geeft volgens mij gewoon moeten werken als functor voor een std::list<Node>.

@curry: Ik snap je, maar ivm met perfomance is een vector niet zo handig, er wordt namelijk heel wat gedelete en ge-insert en een vector is dan toch langzamer dacht ik.

Je kunt wat curry684 voorstelt ook doen met een std::list, of een andere container.

[MSalters]

Ben ik nou heel erg blond als ik zeg dat dit ook niet werkt omdat std::sort op random-access iterators werkt, en std::list::iterator alleen maar bidirectioneel is?

Bovendien is het kopieren van een double sneller dan het kopieren van een smart pointer, dus de hele boost::smart_ptr/std::auto_ptr noodzaak ontgaat me.

[MSalters]

curry684 schreef op 20 april 2004 @ 13:36:
Je gebruikt een auto_ptr voor iets waar ie niet voor bedoeld is: garbage collection. Om te bereiken wat je wilt zul je echt zelf een simpel referencecounting mechanisme moeten schrijven, of goed aanleren om destructors goed in te vullen. Het staat je bijvoorbeeld vrij om van std::vector een template te inheriten die alleen pointers opslaat en bij destructie een delete over al die pointers gooit. Iets als dit:

C++:

template <typename t_Class>
class MyDeletingVector : public std::vector<t_Class*>
{
...
};

Ik zou echter in jouw geval een gewone vector gebruiken ipv dit soort hacks, maar da's een tweede...

code:

MyDeletingVector V( new t_Class );
V.erase(); // OOPS

En dan is de eerste regel ook al een _oops. (Niet exception-safe)

[curry684]

MSalters schreef op 20 april 2004 @ 15:18:
[...]

code:

MyDeletingVector V( new t_Class );
V.erase(); // OOPS

En dan is de eerste regel ook al een _oops. (Niet exception-safe)

erase kun je net als de destructor overriden Toegegeven, aggregaten is netter dan inheritance, omdat je anders hopeloos de mist in gaat zodra iemand het ding z'n ancestor methods gaat benaderen.

Maar ik zei dan ook niet dat ik de methode aanraadde voor alle gevallen maar dat het in dit specifieke geval een voorbeeld was van een potentiele oplossing. Ik gebruik zelf ook tig keer liever echte referencecounting smart pointers De correcte methode in dit geval lijkt me gewoon een std::list oid, ik zie echt het nut van die pointers niet voor een object dat alleen een double bevat...

[12_0_13]

_Squatt_ schreef op 20 april 2004 @ 14:17:
[...]
Waarom niet? Ik vind dat juist een van de mooie dingen aan operator overloading. Het wordt pas lelijk als je operator<() overload om iets geheel anders te doen dan 2 objecten vergelijken.

Ik niet. Want als ik met functors werk kan ik makkelijk een andere functie gebruiken, en operator-overlaoding is niet aan te passen op runtime.

Ik heb bijvoorbeeld 3 distance functies, maar ik kan er nu maar 1 gebruiken omdat ik de operator maar 1 keer kan overloaden.

edit: ach dat is natuurlijk ook niet waar, want ik bereken de distance al ergens anders.. nouja. ik heb het e.e.a. nu aan het werk, en het werkt ok!

[ Voor 13% gewijzigd door 12_0_13 op 20-04-2004 15:47 ]

[Verwijderd]

MSalters schreef op 20 april 2004 @ 15:16:
Ben ik nou heel erg blond als ik zeg dat dit ook niet werkt omdat std::sort op random-access iterators werkt, en std::list::iterator alleen maar bidirectioneel is?

Klopt, maar hij was er al achter dat hij std::list::sort gebruiken moest. Het erge is dat we vervolgens vrolijk doorbakkelijen over comparators/functors

Bovendien is het kopieren van een double sneller dan het kopieren van een smart pointer, dus de hele boost::smart_ptr/std::auto_ptr noodzaak ontgaat me.

Ik ging er vanuit dat er meer in die Node zou zitten dan alleen een double, anders ontgaat de noodzaak tot encapsulation me in dit geval een beetje

[MSalters]

Sorry voor de iewat late response, maar ik moest dit even op m'n werk checken. Het probleem is (uiteraard) VC6. std::list::sort accepteert inderdaad een function object. Omdat dat een templated type moet zijn, en std::list een class template is, is std::list<T>::sort<Compare> dus een member template van een template. Dat is te moeilijk voor VC6. De alternatieve implementatie is VC6 is simpelweg void list::sort(std::greater<T> pr); wat feitelijk betekent dat je alleen met std::less en std::greater kunt sorteren.

Oplossing: gebruik een gesupporte versie van VC.