Die effizienteste Art, Elemente in C/C++ aufzulisten

Question

Ich habe eine Liste mit etwa 100 unsortierten Einträgen. Jedes Element gehört zu einer Gruppe. Die Gruppe, zu der das Element gehört, ist einfach ein Mitglied der Elementklasse.

Mit C/C++ suche ich nach dem effizientesten Weg, die Liste der Elemente zu durchsuchen, zu prüfen, in welcher Gruppe sie sich befinden, und das Element auf dem Bildschirm zu drucken. Hier ist allerdings der Haken. Sobald ein Element aus einer Gruppe auf den Bildschirm gedruckt wurde, möchte ich keine weiteren Elemente aus dieser Gruppe mehr drucken.

Ich verwende einen Pre-STL-Compiler und die Größe der ausführbaren Datei ist kritisch, so dass ich nicht anfangen möchte, meine eigenen Hash-Klassen zu definieren.

Answer 1

Um einige weitere Fragen zu beantworten.

Ist die Artikelliste statisch?

Nein, sie kann jederzeit schrumpfen oder wachsen.

Spielt es eine Rolle, welches Element aus einer einer bestimmten Gruppe Sie drucken?

Vorläufig nicht, nein. Vielleicht in der Zukunft, aber im Moment sollte es ausreichen, den ersten gefundenen Artikel einer eindeutigen Gruppe zu drucken.

Answer 2

Was ist mit Gruppen? Kann man eine neue Gruppe gründen? Und kann eine Gruppe relevant werden, nachdem Sie eines ihrer Mitglieder gedruckt haben?

Answer 3

Die Kosten für die Ausgabe auf dem Bildschirm sind um mehrere Größenordnungen höher als alles andere, was Sie mit den Objekten tun können. Wenn Sie ein Array mit 10 Millionen Objekten in nur wenigen Gruppen haben, dann ist Sortieren keine sinnvolle Option. Wenn die Gruppen durch einen statischen Index (d.h. eine ganze Zahl in einem bestimmten Bereich) identifiziert werden können, genügt es, ein Masken-Array zu verwenden, um anzuzeigen, ob das Objekt gesehen wurde. Wenn die Gruppen komplizierter sind, können Sie die Gruppen, die gesehen wurden, in einer beliebigen Datenstruktur (Hash, Baum, etc.) speichern.