Elemente aus Vector moven die bestimmte Bedingung erfüllen.



  • Ist bestimmt trivial, aber ich stehe gerade etwas auf dem Schlauch. Ich suche eine elegante Lösung für folgendes Problem: Ich möchte einen Vector nach Elementen durchsuchen die eine bestimmte Bedingung erfüllen, diese entfernen und in einen neuen Vector einfügen. Das soll am besten per move geschehen, da die Objekte teuer zu kopieren sind. hab dafür so direkt keinen Standard-Algorithmus gefunden, was mich wundert, da das doch eigentlich eine sehr gängige Anwendung sein sollte. Vielleicht habe ich das aber auch einfach nur übersehen.



  • sind diese teuer zu kopierenden objekte container? dann würd ich einfach swappen.



  • Es sind keine container im eigentlichen Sinne. Aber wie den swappen und womit? Ich habe ja auf der einen Seite einen vollen Vektor und auf der anderen Seite eine leeren.



  • TNA schrieb:

    Es sind keine container im eigentlichen Sinne. Aber wie den swappen und womit? Ich habe ja auf der einen Seite einen vollen Vektor und auf der anderen Seite eine leeren.

    dann würdest du im leeren vektor hinten einen leeren container pushen und den dann mit dem gewünschten container aus dem vollen vektor swappen.

    eine nicht gerade elegante aber dennoch mögliche idee wäre:
    du hast irgendwo einen pool dieser elemente und speicherst in deinen beiden vektoren lediglich zeiger auf elemente in diesem pool. ist aber nicht wirklich das was man unter speichereffizienz versteht. das kann ich aber auch schlecht beurteilen da ich nicht weiss wie das verhältnis der menge der objekte zu der grösse der objekte ist. wenn du 100 objekte a je 1mb hast, dann fallen die 4 byte pro element nicht auf...



  • asfdlol schrieb:

    TNA schrieb:

    Es sind keine container im eigentlichen Sinne. Aber wie den swappen und womit? Ich habe ja auf der einen Seite einen vollen Vektor und auf der anderen Seite eine leeren.

    dann würdest du im leeren vektor hinten einen leeren container pushen und den dann mit dem gewünschten container aus dem vollen vektor swappen

    Das ist ja in etwa so, als würde ich die Elemente manuell Suchen und dann moven. Das wäre jetzt auch mein naiver Ansatz gewesen. Da stehe ich dann aber noch vor dem Problem, die leeren elemente im ersten vector effizient entfernen zu müssen.

    Ich hatte gehofft, dass es so etwas wie eine Kombination aus std::copy_if und std::remove_if mit move-Semantik geben würde, aber das schein nicht der Fall zu sein.:(



  • Hab nochmal die Referenz durchgeschaut. Wie wäre es mit folgendem: Zuerst alle elemente die verschoben werden sollen per std::partition nach hinten schieben, diese dann per std::move in den neuen vector moven und dann ein range erase auf den hinteren teil des ersten vector. Spricht da etwas gegen?



  • TNA schrieb:

    Hab nochmal die Referenz durchgeschaut. Wie wäre es mit folgendem: Zuerst alle elemente die verschoben werden sollen per std::partition nach hinten schieben, diese dann per std::move in den neuen vector moven und dann ein range erase auf den hinteren teil des ersten vector. Spricht da etwas gegen?

    partition kopiert und verschiebt nicht, damit wirst du teure Kopien auch nicht los. Das ginge dann auch intuitiver durch std::remove_copy_if und erase .



  • DocShoe schrieb:

    partition kopiert und verschiebt nicht, damit wirst du teure Kopien auch nicht los. Das ginge dann auch intuitiver durch std::remove_copy_if und erase .

    std::partition sollte swappen und das wiederum sollte per default moven.



  • otze schrieb:

    std::partition sollte swappen und das wiederum sollte per default moven.

    Exakt, und das ist sehr billig.

    DocShoe schrieb:

    TNA schrieb:

    Hab nochmal die Referenz durchgeschaut. Wie wäre es mit folgendem: Zuerst alle elemente die verschoben werden sollen per std::partition nach hinten schieben, diese dann per std::move in den neuen vector moven und dann ein range erase auf den hinteren teil des ersten vector. Spricht da etwas gegen?

    partition kopiert und verschiebt nicht, damit wirst du teure Kopien auch nicht los. Das ginge dann auch intuitiver durch std::remove_copy_if und erase .

    Abgesehen davon, das dies nicht richtig ist hätte das noch den Nachteil, dass ich nach dem std::remove_copy_if den vector nochmal mit std::remove_if durchgehen muss um die Elemente aus dem ersten vector zu löschen. Auch kann ich bei meiner Lösung für den zweiten vector Speicher reservieren, da ich nach dem std::partition genau weiß wie viele elemente gemoved werden müssen.



  • Eventuell hilft std::move_iterator ... Allerdings könnte der auch zu voreilig moven.



  • Nexus schrieb:

    Eventuell hilft std::move_iterator ... Allerdings könnte der auch zu voreilig moven.

    Ich habe mich heute gefragt, warum es eigentlich keinen move_iterator gibt, aber es gibt ihn tatsächlich :D. Vielen Dank!



  • Mithilfe der move-Iteratoren lässt sich in meiner Lösung das std::move durch eine range Konnstruktor bzw range insert ersetzen, was die Lösung nochmals effizienter macht.


Log in to reply