Welche Datenstruktur?



  • Hallo,

    ich bin auf der Suche nach der richtigen Datenstruktur. Was ich brauche: Eine Liste von Objekten vom Typ Core*, wobei jeder Core eine Order (Integer) hat. Die Core* sollen aufsteigend nach ihrer Order in der Liste sein.

    Beispiel:

    datastruct.addCore(c1, 2);
    datastruct.addCore(c2, 2);
    datastruct.addCore(c3, 1);
    datastruct.addCore(c4, 10);
    datastruct.addCore(c5, 33);
    

    Nach diesem Code soll die Datenstruktur so gefüllt sein:

    [(1, c3), (2, c1), (2, c2), (10, c4), (33, c5)]
    

    Sprich die Cores sind alle in der Struktur, sortiert nach ihrer Order. Core4 (c4) ist zB. vor c5, da c4 eine Order von 10 hat und c5 von 33.

    Welche STL Datenstruktur eignet sich da am besten?



  • Wenn du erst hinzufügst und erst dann eine sortierte Liste haben möchtest bietet sich std::vector<std::pair<int, Core*> > an . Erst alles hinzufügen, dann std::sort aufrufen. Schneller gehts nicht.

    Willst du, dass auch zwischen den einzelnen addCore aufrufen die Liste sortiert ist, brauchst du eine std::map<int, Core*> .

    Bzw. wenn du immer nur am kleinsten Element interessiert bist, dann ist std::priority_queue<std::pair<int, Core*> > etwas für dich.



  • std::map?



  • Kellerautomat schrieb:

    std::map?

    Wenn, dann std::multimap. Ich würd aber auch eher std::priority_queue verwenden, wenn das reicht.


Log in to reply