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

Sortieren Sie die Elemente nach dem Gruppenwert (wenn es sich um eine Zeiger können Sie dessen Adresse verwenden, andernfalls lexikographisch sortieren die String ). Dann durchlaufen Sie diese sortierte Liste in einer Schleife, wobei Sie immer das erste Element jeder Gruppe nehmen.

Dies dauert etwa

n + n \* log(n)

Ich denke, dies ist eine vernünftige Alternative zwischen der Größe der ausführbaren Datei und der Geschwindigkeit.

Answer 2

Sie können ein Wörterbuch/Hashmap mit Gruppen erstellen und für jede Gruppe einen bool-Wert speichern, der angibt, ob ein Element dieser Gruppe gedruckt wurde oder nicht.

Beispiel-Code:

#include <unordered_map>
#include <string>
#include <iostream>

std::string getGroupForNumber( int num )
{
//
}

int main()
{
    typedef std::tr1::unordered_map< std::string, bool > hashmap;
    hashmap groupsPrinted;

    for( int i = 0 ; i < 100 ; ++i ) {
        if ( groupsPrinted[ getGroupForNumber( i ) ] == false ) {
            groupsPrinted[ getGroupForNumber( i ) ] = true;
            std::cout << i << std::endl;
        }
    }
    return 0;
}

Answer 3

Du hast in der Frage c/c++ geschrieben, also hier ist etwas c-Code. Ein paar Fragen sind in Ordnung. Wird eine Gruppe irgendwann in der Zukunft druckbar? Ist die Artikelliste statisch? Spielt es eine Rolle, welches Element aus einer bestimmten Gruppe Sie drucken?

Ich würde folgendes Konstrukt vorschlagen (mit meinem begrenzten Verständnis des Problems):

Ein Array von Listen.

  typedef struct node{
    void *item; /* this is your item */
    node *next; 
  } node_t;

  typedef struct {
    node_t *my_group;
    int used;
  } group_t;

  static group_t my_items[NUM_OF_GROUPS]; /* this is your ordered by groups list.*/

Noch besser ist es, eine Liste von Listen zu verwenden. group_t wird sein:

typedef struct group{
  node_t *my_group;
  group *next_free;
} group_t;

Answer 4

Wenn Sie die Gruppen von 0 bis 99 nummerieren können, benötigen Sie ein Array von Booleschen Werten oder ein Bitset, wenn Sie optimieren wollen. Setzen Sie das gesamte Array auf 'false'. Setzen Sie arr[groupId] = 'true', nachdem Sie es gedruckt haben, und überprüfen Sie den Wert das nächste Mal vor dem Drucken. Keine STL erforderlich.

Answer 5

Behalten Sie eine std::Menge der Gruppennamen, deren Elemente nicht mehr gedruckt werden sollen.