3. Sortieren von (int, struct)-Tuppeln

Sortieren von (int, struct)-Tuppeln

  • N

    Hallo c++ler

    Ich arbeite gerade an meinem ersten größeren Projekt in C++ und weiss nicht genau,
    wie ich ein kleines Problem in dieser Sprache loesen kann.
    Es geht darum, dass ich ein struct (cvBox) aus einer Bibliothek (openCV) einsetze. In einer
    meiner Funktionen erstelle ich jetzt unbekannt viele dieser structs und erstelle fuer
    jedes dieser Structs noch eine Bewertung in Form eines ints. Jetzt wuerde ich gerne
    die n besten dieser Structs in einer Liste sammeln.
    Meine erste Idee war die, ein Array of cvBox mit n Eintrügen benutze und ein weiteres, in dem
    ich die Bewertungen speicher. Wenn ich jetzt eine neue cvBox bekomme, kann ich sie passend
    in die Listen eintragen. Problematisch finde ich hier die Einfuegezeit in O(n), da der Algorithmus
    recht häufig aufgerufen wird, und ich Kamerabilder verarbeite, also ein festes Zeitfenster habe.
    Alternativ wollte ich eine einfach verkettete Liste implementieren, da ich hier zwar auch Suchen, dafuer einfach einfüegen kann.
    Da ich aber das Rad nicht noch Mal erfinden wollte, wollte ich euch fragen, ob c++ schon etwas
    in dieser Richtung mit sich bringt. Also im Besten Fall eine Art Dictionary (wie aus Python),
    dem man Tuppe aus Objekten uebergibt und angeben kann, nach welchem Tuppeleintrag sortiert
    werden soll.

    Koennte mir da jemand weiterhelfen?

    0
  • ?

    Da bieten sich natürlich die std::set und std::map-Container beziehungsweise deren multi-Versionen an. Log(n) für einfügen und suchen. Besser gehts ja bis auf konstante Faktoren eigentlich nicht. Beiden kannst du den zu verwendenden Komparator als Template-Argument beifügen (oder einfach durch std:less und entsprechendem operator< realisieren).

    MfG,
    Michael

    0
  • N

    Nikolas schrieb:

    Da ich aber das Rad nicht noch Mal erfinden wollte, wollte ich euch fragen, ob c++ schon etwas
    in dieser Richtung mit sich bringt.

    Guter Ansatz. 🙂

    Also die C++-Standardbibliothek besitzt als Teil der STL einige Container. Eine gute Einführung findest du hier.

    0
  • N

    Das klingt recht optimal 🙂 Danke

    Mal kurz mein Plan:
    Ich nehme ein Multimap aus meinem int als Key und mein Struct als Klasse und lasse den Vergleichsoperator so wie er ist.
    Wenn ich ein neues Objekt einfügen will, bilde ich ein pair aus int und dem struct und benutze insert. Wenn ich jetzt die 5 Objekte mit dem größten Key haben will, benutze ich http://www.cplusplus.com/reference/stl/map/rbegin.html und zähle während der Ausgabe einfach mit.

    klingt das soweit sinnvoll oder hat jemand einen besseren Vorschlag?

    0
  • N

    Nikolas schrieb:

    klingt das soweit sinnvoll oder hat jemand einen besseren Vorschlag?

    Ja, klingt sinnvoll. Das einzige, was mich skeptisch macht, ist die Multimap - kann es bei dir vorkommen, dass mehrere gleiche Schlüssel vorhanden sind? Wenn ja, ist std::multimap angebracht. Wenn nein, reicht auch std::map , die eine eindeutige Schlüssel-Wert-Kombination hat.

    0
  • N

    Ich suche ellipsen in einem Kantenbild. Jede cvBox beschreibt eine Ellipse und die Bewertung besteht aus der Anzahl der Kantenpunkte, die unter dieser Ellipse liegen. (meist so 50-60). Wenn ich 20 Ellipsen in der Liste habe, kann es schon vorkommen, dass ich mehrere Objekte mit gleicher Bewertung habe.
    Danke für den Hinweis 🙂

    0
  • N

    eine kleine Frage hätte ich noch:

    in meinem Buch C/C++ von Kaiser/Kecher steht, dass ich für die Multimenge noch
    # include <set>
    einbinden muss. Wenn ich es damit mache, wird die MultiMap nicht erkannt, wenn ich aber <map> einbinde, funktioniert alles wie oben beschrieben.
    Ist das einfach ein Fehler im Buch oder gibt es da eine andere Erklärung?

    0
  • D

    Nikolas schrieb:

    eine kleine Frage hätte ich noch:

    in meinem Buch C/C++ von Kaiser/Kecher steht, dass ich für die Multimenge noch
    # include <set>
    einbinden muss. Wenn ich es damit mache, wird die MultiMap nicht erkannt, wenn ich aber <map> einbinde, funktioniert alles wie oben beschrieben.
    Ist das einfach ein Fehler im Buch oder gibt es da eine andere Erklärung?

    set musst du include, wenn du std::set benutzen willst und map, wenn du std::map benutzen willst.. 🙂 - So einfach. Wird also ein Fehler im Buch sein. 😉

    0
  • P

    Ist kein Fehler im Buch: Multimenge ist das multiset , und das liegt im <set> header - da du aber keine einfache sondern eine indizierte Menge hast ( multimap ) musst du auch <map> benutzen 😉

    0
  • N

    Ok, dann ist es klar.

    Danke an alle 🙂

    0
Anmelden zum Antworten