Dynamisches Klassen Array sortieren: Mit Vectoren oder Container implementieren?

mireiner

Hallo!

Da ich bislang noch nicht mit Vectoren oder Containern gearbeitet habe, bräuchte ich einmal Anfänger Anschubhilfe für eine sicher einfache Aufgabe.

Gegeben ist folgendes Klassen Array:

class
{
public:
double Laenge;
int Num
int Lage;
} Teil[1];

1. Dem Array sollen später eine unterschiedliche Anzahl von Elementen hinten angefügt werden. Das Array soll sich dann automatisch vergrößern. Die maximale Größe des Arrays ist ca. Teil[30].
2. Das Klassen Array soll dann nach Größe des Klassenelements "Laenge" sortiert werden.
3. Löschen einzelner Elemente wird nicht benötigt.

Wie läßt sich die Aufgabe am einfachsten mit der C++ oder der C++ STL lösen?
Das ganze sollte schnell sein, weil es oft ausgeführt wird.

Grüße,
Bernd

Columbo

struct Data
{
    double Laenge;
    int Num
    int Lage;
}; 
Data d;
// [...]

std::vector<Data> vec; // benötigt den Header <vector>
vec.push_back({ 0.4, 7, 9 });
vec.push_back(d);
// [...] weitere Elemente mittels push_back hinten einfügen

// Sortieren - benötigt den Header <algorithm>
std::sort( std::begin(vec), std::end(vec), []( Data const& lhs, Data const& rhs ){ return lhs.Laenge < rhs.Laenge; } );
// Alternativ: Eigenen Funktor implementieren

mireiner

Hallo Arcoth,

vielen Dank für die Antwort!

Bei der Lösung mit Vektoren hatte ich gleich mehrere Blackouts. Den Operator, als auch den Header <algorithm> hatte ich vergessen. Der Operator ist nun in der Klasse implementiert. Funktioniert super und ist genial einfach!

class Teil {
public:
double dLaenge;
int nNum;
int nLage;

bool operator < (const Teil & rhs) const { return dLaenge < rhs.dLaenge; }
};

Grüße,
Bernd

mireiner

Beim Versuch den Klassen Vector einmal nach "dLaenge" und ein anderes Mal nach "nNum" zu sortieren, komme ich nicht weiter:

#include <vector>
#include <algorithm>

class Teil {
public:
double dLaenge;
int nNum;
int nLage;
bool operator < (const Teil & rhs) const { return dLaenge < rhs.dLaenge; }
};

bool MyDataSortPredicate(const Teil& lhs, const Teil& rhs)
{
return lhs.nNum < rhs.nNum;
}

int main()
{
std::vector <Teil> MyTeil;
MyTeil.push_back( { 1.1, 2, 3} );
MyTeil.push_back( { 5.2, 5, 1} );
MyTeil.push_back( { 4.1, 9, 4} );

// Funktioniert, es wird "dLaenge" sortiert
std::sort(MyTeil.begin(), MyTeil.end());

// error C3867: Dem Funktionsaufruf fehlt die Argumentliste. Verwenden Sie "&MyDataSortPredicate", um einen Zeiger auf den Member zu erstellen.
std::sort(MyTeil.begin(), MyTeil.end(), MyDataSortPredicate);
}

An der Stelle komme ich nicht weiter. Vielleicht ist der Weg aber eh falsch?

Wie kann mehr als ein Klassenelement sortiert werden?

Nathan

Ja, sort einen Functor geben, wie Arcoth ds gezeigt hat.
Das ist einfach irgendeine Funktion mit der selben Signatur wie operator<, aber man kann sie ja beliebig nennen.
Er hat das jetzt mit einem Lambda, d.h. einer anonymen Funktion, gemacht.

SeppJ

Das hat erst einmal mit vectoren übrigens nichts zu tun. std::sort kann alles sortieren, was irgendwie mit einem Index angesprochen werden kann. Und es kann dazu jedes beliebiger Kriterium benutzen, was du programmieren kannst. Es ist bloß die Standardvorgabe, dass nach dem Operator< sortiert wird. Zur Auswahl des Sortierkriteriums dient der dritte Parameter.
Referenzen mit Beispielen:
http://www.cplusplus.com/reference/algorithm/sort
http://en.cppreference.com/w/cpp/algorithm/sort
Wie du siehst, ist selbst die Art, wie das Sortierkriterium übergeben wird offen gehalten, es muss bloß irgendetwas sein, was zwei der zu sortierenden Objekte nehmen kann und dann einen Wahrheitswert zurück gibt, ob das erste Element "kleiner" ist als das zweite (wobei man frei wählen kann, was "kleiner" bedeuten soll). Das können freie Funktionen, Memberfunktionen, Funktoren (funktionsartige Objekte) oder Lambda-Ausdrücke sein (eine Art Minifunktor).

mireiner schrieb:

bool operator < (const Teil & rhs) const { return dLaenge < rhs.dLaenge; }
bool operator < (const Teil & rhs) const { return nNum < rhs.nNum; }
...

Der Operator wird aber vermutlich nur einmal überladen werden können, oder?

"Überladung" heißt, dass man eine Funktion mehrmals definiert, aber mit anderen Parametern. Das heißt, man kann schon einen Operator mehrmals überladen, die erste Überladung ist ja naturgemäß bereits eine weitere Definition einer Funktion, die es längst gibt (hier: Der normale Operator< zum Vergleich von Zahlen). Operatoren sind auch nur ganz normale Funktionen mit Syntaxzucker.
Mit diesem Wissen sollte klar sein, dass dein Code so nicht gehen kann, denn das ist ja eine mehrfache Definition ein und der selben Funktion, eines Operators<, der ein Member von Teil ist und rechtsseitig ein const Teil& nimmt. Funktionen darf man aber nicht mehrfach definieren. Wie sollten sie auch unterschieden werden? Was würdest du dir vorstellen, welche Variante bei einem Aufruf genommen wird? Normalerweise würde dies anhand der Parameter entschieden, aber hier wäre ja alles gleich.

mireiner

Hallo Zusammen,

danke für die Antworten, die sich mit meinem geänderten Posting wohl überschnitten haben. Ich habe es jetzt so hinbekommen:

class Teil
public:
double Laenge
int Num;
int Lage;
};

int main()
{
std::vector <Teil> MyTeil;

MyTeil.push_back({...});
MyTeil.push_back({...});
....

// Sortiert nach "Laenge"
std::sort(std::begin(MyTeil), std::end(MyTeil), [](Teil const& lhs, Teil const& rhs){ return lhs.Laenge < rhs.Laenge; });

// Sortiert nach "Num"
std::sort(std::begin(MyTeil), std::end(MyTeil), [](Teil const& lhs, Teil const& rhs){ return lhs.nNum < rhs.nNum; });
}

Wie läßt sich der functor in die Klasse integrieren? So dass folgender Aufruf genügt:
std::sort(std::begin(MyTeil), std::end(MyTeil), functor);

SeppJ

mireiner schrieb:

Wie läßt sich der functor in die Klasse integrieren? So dass folgender Aufruf genügt:
std::sort(std::begin(MyTeil), std::end(MyTeil), functor);

Du hast doch gar keinen Funktor, bist du sicher, dass du wirklich willst, wonach du fragst? Das sind doch quasi freie Funktionen, ohne inneren Zustand, und das ist auch passend so. Mach eventuell eine statische Klassenmethode daraus, wenn du es unbedingt als Teil deiner Klasse haben möchtest. Das geht dann immer noch so, wie bei einer freien Funktion.

Wutz

Gar nicht.
Statt das sort nach jedem Ändern des vector explizit aufrufen zu müssen, nimm besser set . Dort kannst du gleich bei der Definition deine Vergleichsfunktion angeben, set sortiert damit immer aufsteigend.
Der gesamte Inhalt ist nach jedem Ändern des set ( insert , erase ) sofort automatisch sortiert, und somit natürlich viel angenehmer als das vector / sort Gefrickel.

mireiner

Habs jetzt hinbekommen:

class Teil
public:
double Laenge
int Num;
int Lage;
};

struct cmpL{
bool operator()(const psort &a, const psort &b){return (a.dLaenge < b.dLaenge);}
} compareLaenge;

struct cmpN{
bool operator()(const psort &a, const psort &b){return (a.nNum < b.nNum);}
} compareNum;

int main()
{
std::vector <Teil> MyTeil;

MyTeil.push_back({...});
MyTeil.push_back({...});
....

// Sortiert nach "Laenge"
std::sort(std::begin(MyTeil), std::end(MyTeil), compareLaenge);

// Sortiert nach "Num"
std::sort(std::begin(MyTeil), std::end(MyTeil), compareNum);

Vielen Dank an alle!

P.S.: Das "set" werde ich mir auch einmal anschauen.