Liste nach unterschiedlichen Eigenschaften sortieren

[Dirty Oerti]

Tag!

Mir kam gerade so ein Einfall, wie man denn eine Liste sortieren könnte, und zwar nach unterschiedlichen Eigenschaften. Ich weiß nicht ob es das Konzept schon gibt, aber ich leg mal meine Überlegungen dar^^

Als Beispiel:

Unsere Mitgliederliste kann man ja nach Name, Beiträge, Angemeldet seit, etc sortieren.
Ich weiß jetzt nicht, wie das im Falle unserer Mitgliederliste nun genau gemacht wird, aber ich würde das so machen:

Alle Elemente (=Mitglieder) in eine verkettete Liste packen. Da in dem Beispiel jetzt Mitglieder erst in diese Liste eingereiht werden, wenn sie sich auch anmelden (logisch...), ist die Liste praktisch schon nach einer Eigenschaft sortiert:
Angemeldet seit.

Um das Ganze nicht zu abstrakt zu halten, hier mal ein bisschen Beispielcode in C++:

Code: Alles auswählen

struct Element {
   string Name;
   struct Datum Anmeldedatum;
   unsigned int Beiträge;
}

Das ist natürlich noch keine verkettete Liste. Die Erweiterung dazu kommt nun:

Code: Alles auswählen

struct Element {
   string Name;
   struct Datum Anmeldedatum;
   unsigned int Beiträge;
   struct Element *Danach_Angemeldet;
   struct Element *Davor_Angemeldet;
}

Ich benutze eine doppelt verkettete Liste, um evtl auch "andersrum sortieren" zu können.

Jetzt wollen wir natürlich noch nach dem Namen sortieren können:

Code: Alles auswählen

struct Element {
   string Name;
   struct Datum Anmeldedatum;
   unsigned int Beiträge;
   struct Element *Danach_Angemeldet;
   struct Element *Davor_Angemeldet;

   struct Element *Name_weiter_unten_im_ABC;
   struct Element *Name_weiter_oben_im_ABC;
}

Wieder eine doppelte Liste, um auch von Z nach A sortieren zu können.
Jetzt noch die Anzahl der Beiträge:

Code: Alles auswählen

struct Element {
   string Name;
   struct Datum Anmeldedatum;
   unsigned int Beiträge;
   struct Element *Danach_Angemeldet;
   struct Element *Davor_Angemeldet;

   struct Element *Name_weiter_unten_im_ABC;
   struct Element *Name_weiter_oben_im_ABC;

   struct Element *Mehr_Beitraege;
   struct Element *Weniger_Beitraege;
}

Jetzt braucht man noch einen Pointer auf die Startpunkte und Endpunkte der jeweiligen Listen.
Wobei man diese Pointer eigentlich nicht brauchen würde, so geht es aber schneller, da man nicht jedesmal den Anfangs/Endpunkt suchen muss.

Code: Alles auswählen

struct Element *Anmeldungsdatum_Start;
struct Element *Anmeldungsdatum_Ende;

struct Element *ABC_Start;
struct Element *ABC_Ende;

struct Element *Beitragsanzahl_Start;
struct Element *Beitragsanzahl_Ende;

Wie man jetzt ein Element einfügt:

Zuerst einmal hängt man das Element ganz hinten an die Liste Anmeldungsdatum. Das Element ist ja das, das als letztes hinzugefügt wurde.
Man nimmt also das Element Anmeldungsdatum_Ende und trägt bei Danach_Angemeldet das neue Element ein.
Beim neuen Element trägt man bei Davor_Angemeldet das Element Anmeldungsdatum_Ende ein.
Jetzt setzt man Anmeldungsdatum_Ende auf das neue Element.

So ähnlich funktioniert das auch mit den anderen Elementen:

Nur muss man hier darauf achten, die Elemente gleich sortiert einzufügen.
Ein Beispiel:

Das neue Element (der neue Benutzer) hat 5 Beiträge (ist jetzt unlogisch, aber egal).
Dann sucht man in der Liste Beitragsanzahl solange, bis man das erste Element mit 5 Beiträgen gefunden hat.
Vor dieses setzt man dann das neue Element in die Liste ein.
Wie das geht dürfte eigentlich klar sein.
Einfach wieder die Zeiger in den Elementen davor und dahinter und im neuen Element anpassen.
Diesesmal muss man aber (logischerweise) die Zeiger der Liste Beitragsanzahl hernehmen.

So.
Ich hoffe das hilft irgendwem vielleicht.

Achja: Gibt es das schon?
Hättet ihr Verbesserungen vorzuschlagen?

MfG
Daniel

[AnGaiNoR]

Ich glaube es gibt schon gute Konzepte für Listen.

Deins hat folgendene Vorteile:

• • Das Sortieren geht schnell, weils ja schon sortiert ist.
  • Man könnte auch ganz leicht noch ein paar Features hinzuimplementieren, z.B. eine verbesserte Suchfunktion

Aber es hat auch einige Nachteile:

• • Das Löschen / Hinzufügen von Elementen wird mit zunehmender Eigenschaftszahl kompliziert.
  • Du verbrauchst pro Eigenschaft 8/16 Byte mehr, nur für die Zeiger (Na gut, das ist eigentlich egal)

Alles in allem ein gutes Konzept, man kann aber auch die schon gegebenen verwenden.

[fat-lobyte]

Ist nicht so schlecht die Idee.
Das hat allerdings die eben genannten nachteile.

Ich würde das ganze allerdings so lösen:

Das ist unser Element.

Code: Alles auswählen

struct Element {
   string Name;
   struct Datum Anmeldedatum;
   unsigned int Beitraege;
}

Das ist unsere verkettete Liste. Sie ist vom typ std::list<> und eine double linked list, aus der Standard template library

Code: Alles auswählen

#include <list>

std::list<Element> members;

Um das ganze zu sortieren, füttern wir das ganze an den std::sort() algorithmus:

Code: Alles auswählen

std::sort(members.begin(), members.end(), nach_name);
std::sort(members.begin(), members.end(), nach_beitraege);
std::sort(members.begin(), members.end(), nach_anmeldedatum);

Wobei das dritte Argument Funktionsobjekte sind, die so aussehen:

Code: Alles auswählen

struct NachName {
    bool operator() (const Element& a, const Element& b)
    { 
        return a.Name < b.Name; // operator< ist für std::strings bereits überladen
    }
} nach_name;

struct NachBeitraege {
    bool operator() (const Element& a, const Element& b)
    { 
        return a.Beitraege < b.Beitraege;
    }
} nach_beitraege;

struct NachAnmeldedatum {
    bool operator() (const Element& a, const Element& b)
    { 
        return a.Anmeldedatum < b.Anmeldedatum;  // operator< müsste man fürs datum auch überladen
    }
} nach_anmeldedatum; 

[fat-lobyte]

So, jetzt hab ichs mal Praktisch probiert und bin draufgekommen, dass std::sort nicht mit std::list funktioniert.
Klar, in einer Liste kann man nicht beliebig herumspringen. Wenn man stattdessen vector nimmt funktionierts super.

hier das listing für das komplette demoprogramm:

Code: Alles auswählen

#include <iostream>
#include <ctime>

#include <string>
#include <vector>
#include <algorithm>



// das eigentliche element
struct Element {
    std::string Name;
    time_t Anmeldedatum;
    unsigned int Beitraege;
};


// hilfsklasse zum anzeigen
struct ElementPrinter {
    void operator() (const Element& e)
    {
        std::cout<<"Name: "<<e.Name
                <<"; Angemeldet seit: "<<e.Anmeldedatum
                <<"; Betraege: "<<e.Beitraege<<'\n';
    }
};



// die sortierklassen
struct NachName {
    bool operator() (const Element& a, const Element& b)
    {
        return a.Name < b.Name; // operator< ist für std::strings bereits überladen
    }
};

struct NachBeitraege {
    bool operator() (const Element& a, const Element& b)
    {
        return a.Beitraege < b.Beitraege;
    }
};

struct NachAnmeldedatum {
    bool operator() (const Element& a, const Element& b)
    {
        return a.Anmeldedatum < b.Anmeldedatum;  // operator< müsste man fürs datum auch überladen
    }
}; 


int main()
{
    Element member1 = {"joe", 20080702, 10};
    Element member2 = {"hank", 20080707, 4};
    Element member3 = {"will", 19930116, 283};
    
    std::vector<Element> members;

    // elemente hinzufuegen
    members.push_back(member1);
    members.push_back(member2);
    members.push_back(member3);


    

    // nach Name sortieren
    std::sort(members.begin(), members.end(), NachName());

    // liste ausgeben
    std::cout<<"Nach Name sortiert:\n";
    std::for_each(members.begin(), members.end(), ElementPrinter());

    // nach Anmeldedatum sortieren
    std::sort(members.begin(), members.end(), NachAnmeldedatum());

    // liste ausgeben
    std::cout<<"Nach Anmeldedatum sortiert:\n";
    std::for_each(members.begin(), members.end(), ElementPrinter());

    // nach Beitraegen sortieren
    std::sort(members.begin(), members.end(), NachBeitraege());

    // liste ausgeben
    std::cout<<"Nach Beitraegen sortiert:\n";
    std::for_each(members.begin(), members.end(), ElementPrinter());

                       
    return 0;
}

[AnGaiNoR]

Naja, dann benutzt du aber eine "normale Liste". Ich denke, dass eher eine Liste gedacht war, die durch die Verkettungen schon automatisch sortiert war, und nicht immer umsortiert werden muss

[Dirty Oerti]

Aber es hat auch einige Nachteile:

• • Das Löschen / Hinzufügen von Elementen wird mit zunehmender Eigenschaftszahl kompliziert.
  • Du verbrauchst pro Eigenschaft 8/16 Byte mehr, nur für die Zeiger (Na gut, das ist eigentlich egal)

Alles in allem ein gutes Konzept, man kann aber auch die schon gegebenen verwenden.

Wieso wird Löschen/Hinzufügen kompliziert?
Du musst nur ein Element suchen, das eine gewisse Eigenschaft hat (nämlich die gleiche oder eine ähnlich wie das einzufügende), und dieser Vorgang geht schnell (zur Not noch eine Liste "darüberschalten"). Und sehr viel mehr ist dann ja nicht mehr zu tun.
Ein paar Zeiger ändern und fertig..

Ist nicht so schlecht die Idee.
Das hat allerdings die eben genannten nachteile.

Ich würde das ganze allerdings so lösen:

Das ist unser Element.

Code: Alles auswählen

struct Element {
   string Name;
   struct Datum Anmeldedatum;
   unsigned int Beitraege;
}

Das ist unsere verkettete Liste. Sie ist vom typ std::list<> und eine double linked list, aus der Standard template library

Code: Alles auswählen

#include <list>

std::list<Element> members;

Standard template libary => nein.
Sinn und Zweck ist ja einen eigenen Algorithmus zu verwenden und nicht einen schon vorgefertigten klug anzuwenden

Naja, dann benutzt du aber eine "normale Liste". Ich denke, dass eher eine Liste gedacht war, die durch die Verkettungen schon automatisch sortiert war, und nicht immer umsortiert werden muss

Bingo!

Sinn bzw Idee hinter diesem Algorithmus ist die Tatsache, dass diese Liste nicht sortiert werden muss, da sie automatisch schon sortiert ist.
Und es soll eben nichts vorgefertigtes verwendet werden.