std::multimap::insert langsam?



  • Hallo,

    Ich habe einen Renderer (in C++/DX) geschrieben und benutze zum Rendern eine RenderQueue. Die RenderQueue besteht aus mehreren RenderQueueGroups und jeder Group kann man nun Renderables (etwas das sich zeichnen lässt) hinzufügen. Die Methode sieht so aus:

    void RenderQueueGroup::addRenderable(Renderable* renderable, unsigned int priority) {
       mRenderablesPriority.insert( std::pair<uint, Renderable*>(priority, renderable) );
      //testVector.push_back( std::pair<uint, Renderable*>(priority, renderable) );
    }
    

    Jedes Renderable hat eine Priorität, mit der man die Reihenfolge des Zeichnens festlegen kann. Meine Datenstruktur mRenderablesPriority ist vom Typ std::multimap<unsigned int, Renderable*>. Ich verwende multimap, weil mehrere Renderables ruhig die gleiche Priorität haben dürfen. Das Problem ist nun: Das insert() in die map ist offenbar sehr langsam. Zu Testzwecken habe ich mal der Klasse den Member testVector hinzufügt (Typ std::vector< std::pair<uint,Renderable*> > ). testVector ist quasi die Multimap per Hand nachgebaut. Wenn ich jetzt das insert() in die multimap auskommentiere und stattdessen den vector benutze (und diesen dann am Ende per sort() sortiere. Die multimap wird ja automatisch sortiert, der vector nicht), dann steigen meine fps von 1500 auf 2000.

    Ist das normal, dass insert() so teuer ist? Benutze ich insert() falsch? Sollte ich jetzt einfach meine "per Hand" Lösung nehmen? (Also ein vector mit einem pair und am Ende per Hand mittels sort() sortieren)?



  • Du könntest auch eine klassische Priority Queue einsetzen. Also entweder std::priority_queue nutzen, oder wenn dir die zu unflexibel ist, selbst eine mit den STL-Algorithmen make_heap() , push_heap() , pop_heap() nachbauen...



  • Eine multimap ist eine Struktur, die nicht dafür ausgelegt wurde, einmal aufgebaut, benutzt und sofort wieder abgebaut zu werden. Die Map ist ein klassisches Wörterbuch, bei dem du ein Objekt unter einem bestimmten Schlüssel wieder finden kannst. Das ist wohl etwas, was du in deiner Aufgabe nicht brauchst. Zusätzlich ist die Map enorm gut, wenn du einzelne Schlüssel wieder entfernen musst.

    Insofern ist es verständlich dass der vector mit anschließender Sortierung für den von dir geschilderten Zweck schneller ist. Bei ihm würde es dich stattdessen richtig teuer kommen, wenn du zwischenzeitlich Objekte entfernst, oder in die Mitte einfügen würdest.

    Du brauchst offensichtlich nur eine sortierte Liste: Nimm Vector. Map macht zu viel, und ist deswegen natürlich auch langsamer.


Anmelden zum Antworten