| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
DirectXer
Dark JLI'ler
Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine
|
 Verfasst am: 10.03.2006, 17:09 Titel: Sortieralgo für ne <list> |
 |
|
Hi,
hab mal ne kurze Frage zur std::list. Hab gehört, es gibt in <algorithm> oder so einen Weg, sich selbst eine Sortierfunktion für die Elemente einer Liste zu programmieren, ähnlich wie bei qsort() wo man eine solche angeben muss. Ich brauche das, weil die std::list<>::sort()-Funktion ja nur nach int-Werten sortiert. Kennt einer dazu ein gutes Tutorial, einen Link oder kann das einer schnell erklären? Thx im Voraus
Gruß DXer |
|
| Nach oben |
|
 |
OLiver
Super JLI'ler
Alter: 32
Anmeldedatum: 29.06.2003
Beiträge: 306
Wohnort: Jena
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 17:16 Titel: |
|
|
Reicht da nicht, wenn man den < oder > überläd? Ansonsten guck dir mal Bubble- oder Quicksort an.
_________________
http://www.sieder25.org/ (Siedler 2 - Remake) |
|
| Nach oben |
|
|
David
Super JLI'ler
Alter: 39
Anmeldedatum: 13.10.2005
Beiträge: 315
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 17:25 Titel: |
|
|
Hi!
Doch das reicht:
| CPP: | #include <list>
#include <fstream>
#include <iostream>
class MyInt
{
private:
unsigned long val;
public:
MyInt()
: val( 0 )
{}
MyInt( unsigned long v )
: val( v )
{}
bool operator < ( const MyInt &other )
{
return val < other.val;
}
friend std::ostream &operator<<( std::ostream &o, const MyInt &obj )
{
o << obj.val;
return o;
}
};
int main( int argc, char **argv )
{
std::list< MyInt > l;
l.push_back( MyInt( 10 ) );
l.push_back( MyInt( 60 ) );
l.push_back( MyInt( 20 ) );
l.sort();
for ( std::list< MyInt >::iterator i = l.begin(); i != l.end(); ++i )
{
std::cout << *i << std::endl;
}
l.clear();
return 0;
}
|
Oder:
| CPP: | #include <list>
#include <fstream>
#include <iostream>
class MyInt
{
private:
unsigned long val;
public:
friend bool SortPredicate( const MyInt &, const MyInt & );
MyInt()
: val( 0 )
{}
MyInt( unsigned long v )
: val( v )
{}
friend std::ostream &operator<<( std::ostream &o, const MyInt &obj )
{
o << obj.val;
return o;
}
};
bool SortPredicate( const MyInt &lhs, const MyInt &rhs )
{
return lhs.val < rhs.val;
}
int main( int argc, char **argv )
{
std::list< MyInt > l;
l.push_back( MyInt( 10 ) );
l.push_back( MyInt( 60 ) );
l.push_back( MyInt( 20 ) );
l.sort( SortPredicate );
for ( std::list< MyInt >::iterator i = l.begin(); i != l.end(); ++i )
{
std::cout << *i << std::endl;
}
l.clear();
std::cin.get();
return 0;
}
|
grüße |
|
| Nach oben |
|
|
Patrick
Dark JLI Master
Anmeldedatum: 25.10.2004
Beiträge: 1895
Wohnort: Düren
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 18:58 Titel: |
|
|
DirectXer
Die STL bietet da einen eigenen Sortalgo basiered auf dem BubbleSort, kannst Dir ja sicherlich denken wie lam das ist, da schreibt man sich was eigenes!
Nimm besser Qualität: http://trash.germangamedev.de/heapsort.pdf
OLiver
Und was hat man dann? BubbleSort, einen total lamarschigen Sortalgo und Quicksort? Quicksort mit rekursion, na klasse, bei 22.000 Elementen geht dir so dermaßen das Programm flöten, grandios!
und operator < bzw. > überladen geht nur bei Listen wo man keine Pointer abspeicher, sonst vergleicht man die Pointeradresse.
Besser: Heapsort!
David
Ja reicht NUR bei Listen die keine Pointer managen.
p.s.: Es handelt sich bei dieser Präsentation um eine der viele Gruppenprojektarbeiten, also nix sonderliches. Auch der Code ist nicht mehr aktuell  Aber egal, er läuft und geht ab wie sonst was.
_________________
'Wer der Beste sein will muss nach Perfektion streben und jede Gelegenheit nutzen sich zu verbessern.' - KIA
[ German Game Dev | Boardsuche hilft sehr oft | Google rockt | Wie man Fragen richtig stellt | ICQ#: 143040199 ] |
|
| Nach oben |
|
|
Fallen
JLI MVP
Alter: 40
Anmeldedatum: 08.03.2003
Beiträge: 2860
Wohnort: Münster
Medaillen: 1 (mehr...)
|
| Verfasst am: 10.03.2006, 19:06 Titel: |
|
|
Hoi Patrick, versuche dich mal bitte an einem etwas freundlicherem Ton, wäre der Atmosphäre hier im Forum halt etwas zuträglicher.
Fragen dementsprechend bitte per PM.
_________________
"I have a Core2Quad at 3.2GHz, 4GB of RAM at 1066 and an Nvidia 8800 GTS 512 on Vista64 and this game runs like ass whereas everything else I own runs like melted butter over a smokin' hot 18 year old catholic schoolgirl's arse." |
|
| Nach oben |
|
|
HotAcid
Super JLI'ler
Alter: 42
Anmeldedatum: 04.08.2002
Beiträge: 372
Wohnort: Berlin
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 19:15 Titel: |
|
|
was genau meinst du mit "nicht mehr aktuell"?
_________________
StGB §§ 328 Abs. 2 Pkt 3:
Mit Freiheitsstrafe bis zu fünf Jahren oder mit Geldstrafe wird bestraft, wer eine nukleare Explosion verursacht. |
|
| Nach oben |
|
|
Patrick
Dark JLI Master
Anmeldedatum: 25.10.2004
Beiträge: 1895
Wohnort: Düren
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 19:17 Titel: |
|
|
HotAcid
Halbes Jahr alt (dazu ist der Code in einem Saufgelage entstanden, war net mehr ganz nüchtern  ), an diversen Stellen optimierter, aber sonst noch passabel.
_________________
'Wer der Beste sein will muss nach Perfektion streben und jede Gelegenheit nutzen sich zu verbessern.' - KIA
[ German Game Dev | Boardsuche hilft sehr oft | Google rockt | Wie man Fragen richtig stellt | ICQ#: 143040199 ] |
|
| Nach oben |
|
|
HotAcid
Super JLI'ler
Alter: 42
Anmeldedatum: 04.08.2002
Beiträge: 372
Wohnort: Berlin
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 19:28 Titel: |
|
|
ok, danke 
_________________
StGB §§ 328 Abs. 2 Pkt 3:
Mit Freiheitsstrafe bis zu fünf Jahren oder mit Geldstrafe wird bestraft, wer eine nukleare Explosion verursacht. |
|
| Nach oben |
|
|
DirectXer
Dark JLI'ler
Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 20:00 Titel: |
|
|
@patrick:
danke, genau das was ich suchte. ich benutze nämlich wirklich pointer, mit vererbung und allem un so.
@David und @Oliver
auch danke an euch.
Gruß DXer |
|
| Nach oben |
|
|
Hazel
JLI MVP
Alter: 39
Anmeldedatum: 19.07.2002
Beiträge: 1761
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 21:08 Titel: |
|
|
| Patrick hat Folgendes geschrieben: | DirectXer
Die STL bietet da einen eigenen Sortalgo basiered auf dem BubbleSort, kannst Dir ja sicherlich denken wie lam das ist, da schreibt man sich was eigenes! |
Tut mir leid dich zu korrigieren, aber die STL Leute waren sicher nicht so dämlich Bubblesort zu verwenden... wenn du dir den Code mal anschaust, wirst du feststellen, dass es ein Introsort ist. ;)
_________________
*click* Dabuu!?
Twitter: http://twitter.com/Ollie_R
|
|
| Nach oben |
|
|
Patrick
Dark JLI Master
Anmeldedatum: 25.10.2004
Beiträge: 1895
Wohnort: Düren
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 21:38 Titel: |
|
|
Hazel
Kommt drauf an, vom Standard her ist kein festgelegter Algo dafür benutzt. Generell kann man davon ausgehen das es BubbleSort ist.
_________________
'Wer der Beste sein will muss nach Perfektion streben und jede Gelegenheit nutzen sich zu verbessern.' - KIA
[ German Game Dev | Boardsuche hilft sehr oft | Google rockt | Wie man Fragen richtig stellt | ICQ#: 143040199 ] |
|
| Nach oben |
|
|
Hazel
JLI MVP
Alter: 39
Anmeldedatum: 19.07.2002
Beiträge: 1761
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 23:11 Titel: |
|
|
Keine Ahnung, welche STL du benutzt, aber...
Hab nochmal nachgesehen... STLPort ist auf jeden Fall Introsort(QuickSort der bei zu starker Rekursion auf Heap-Sort ausweicht). Das was bei meinem Visual C++ dabei ist, ist Insertionsort, was garantiert auch kein Bubblesort ist. Arbeite mit Visual C++ .net 2003 aber bis zu neueren Versionen werden sie sicher keinen Rückschritt gemacht haben sondern eher auch auf Introsort umgestiegen sein, wenn überhaupt.
Ich kann mir auch garnicht vorstellen, dass Leute die eine effiziente Template Lib zusammenstellen soetwas hernehmen wie Bubblesort... das hab ich in Klasse 10 an der Schule durchgenommen als einfachsten sortieralgo. Und sogar die einfache C-Funktion sort() benutzt Quicksort für C-Arrays.
_________________
*click* Dabuu!?
Twitter: http://twitter.com/Ollie_R
|
|
| Nach oben |
|
|
Patrick
Dark JLI Master
Anmeldedatum: 25.10.2004
Beiträge: 1895
Wohnort: Düren
Medaillen: Keine
|
|
| Nach oben |
|
|
KI
JLI Master
Alter: 38
Anmeldedatum: 04.07.2003
Beiträge: 965
Wohnort: Aachen
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 23:34 Titel: |
|
|
| Patrick hat Folgendes geschrieben: | Hazel
Frage am Rande, wie kann ein Quicksort einfach mal "mitten drin" auf einen HeapSort zurückgreifen????????????????????? |
Was soll die Frage?
Wahrscheinlich wird die Funktion vorher anhand der Anzahl der zu sortierenden Elemente die effektivste Methode zum Sortieren auswählen.
Man kann ja schon vorher abschätzen, dass die Rekursion bei 10000 Elementen stärker bei Quicksort sein wird, als bei Heapsort. |
|
| Nach oben |
|
|
Patrick
Dark JLI Master
Anmeldedatum: 25.10.2004
Beiträge: 1895
Wohnort: Düren
Medaillen: Keine
|
| Verfasst am: 10.03.2006, 23:38 Titel: |
|
|
KI
Ich rede von "Mitten Drin" nicht vom Anfang an. Und bei Rekursion geht es nicht um die Langsamheit sondern um die Rekursionstiefe.
_________________
'Wer der Beste sein will muss nach Perfektion streben und jede Gelegenheit nutzen sich zu verbessern.' - KIA
[ German Game Dev | Boardsuche hilft sehr oft | Google rockt | Wie man Fragen richtig stellt | ICQ#: 143040199 ] |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Medaillen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
