STL Elemente finden die eine Bedingung erfüllen

MrPink

Hallo,

ich sitze gerade vor folgendem Problem: Ich habe zwei STL-Vektoren die Pointer auf eigene Klassen (Partikel) enthalten. Der eine Vektor enthält alle Pointer, der andere nur Pointer auf die "aktiven" Elemente.

vector<Particle*> m_Particle;
vector<Particle*> m_ActiveParticle;

Jetzt müssen in regelmäßigen Abständen alle Elemente überprüft werden, ob sie "aktiv" sind und der zweite Vektor mit den aktiven Elementen dementsprechend geupdated werden.
Normalerweise verwende ich for_each, um über container zu iterierene z.B.:

m_ActiveParticle.erase(remove_if(m_ActiveParticle.begin(),m_ActiveParticle.end(),isInActive),m_ActiveParticle.end());

In diesem Fall müsste der Funktor aber einen member haben, der sich merkt, welche Partikel aktiv sind und anschließend diese an m_ActiveParticle übergeben. Die Lösung finde ich irgendwie unschön/unübersichtlich. Alternativ kann ich natürlich eine Iterator-Schleife nutzen abfragen ob das element aktiv ist und entsprechend die Adresse in m_ActiveParticle ablegen. Doch auch diese Lösung finde ich nicht schön.
Ich programmiere nicht so oft C++ und bin deshalb nicht mit allen STL Konstrukten gut vertraut. Wenn da jemand einen guten Tipp hat, wäre ich sehr dankbar! Ich verwende VS2010.

PS: Jedes Partikel hat eine bool Variable m_Aktive, die true oder false ist. Ich hatte mich jedoch dazu entschlossen auf die aktiven Elemente in einem extra Vektor zu verweisen, da auf 50 aktive elemente 5000 inaktive kommen können. Sonst müsste ich anschließend immer über 5000 Partikel iterieren und abfragen, ob es denn aktiv ist.

Viele Grüße

SeppJ

Besteht denn irgendein Zusammenhang, zwischen den vorher aktiven und den nachher aktiven Elementen? So wie du das derzeit formulierst, willst du doch nach deinem Updateschritt alle aktiven Elemente in m_ActiveParticle verwiesen haben, weißt aber nicht, welche Elemente aktiv oder inaktiv geworden sind. Das heißt, du musst sowieso alle Elemente durchgehen und auf Aktivität prüfen, so dass der Schritt zum Entfernen inaktiver Elemente

m_ActiveParticle.erase(remove_if(m_ActiveParticle.begin(),m_ActiveParticle.end(),isInActive),m_ActiveParticle.end());

komplett nutzlos ist.

Das heißt, du machst erst einmal clear() auf m_ActiveParticle, dann gehst du mit copy_if durch alle Elemente von m_Particle und kopierst die Zeiger bei Aktivität des verwiesenen Elementes in m_ActiveParticle.

Ohne C++11 gibt es noch kein copy_if, dieses kannst du dir bei Bedarf trivial selber schreiben:

template<class InputIt, class OutputIt, class UnaryPredicate>
OutputIt copy_if(InputIt first, InputIt last, 
                 OutputIt d_first, UnaryPredicate pred)
{
    while (first != last) {
        if(pred(*first))
            *d_first++ = *first;
         first++;
    }
    return d_first;
}

Alternativ kannst du remove_copy_if benutzen (das gibt's auch in c++98), du musst bloß die Bedingung umkehren (Die Bezeichnung remove_copy_if ist etwas irreführend, es ist eher ein copy_if_not).

MrPink

Danke für die Antwort. Die copy_if Lösung gefällt mir. Zu deiner Frage

Besteht denn irgendein Zusammenhang, zwischen den vorher aktiven und den nachher aktiven Elementen?

Grob sieht der Ablauf so aus, dass in einer Schleife Berechnungen auf allen aktiven Partikeln durchgeführt werden. Dabei kann es vorkommen, dass Partikel am Ende der Berechnung deaktiviert werden - befinden sich aber trotzdem noch in m_ActiveParticles - das ist so vermutlich noch nicht optimal ;-). Dann werdem im nächsten Durchlauf - mit Deiner vorgeschlagenen copy_if Lösung die aktiven Partikel geupdated. Bevor die Berechnung gestartet werden kann müssen allerdings noch einige Voraussetzungen erfüllt sein z.B.:

/*Deactivate and erase particles that are close to the boundary*/
	for_each(m_ActiveParticle.begin(),m_ActiveParticle.end(),m_CheckRange); //deactivates Particle if out of range
	m_ActiveParticle.erase(remove_if(m_ActiveParticle.begin(),m_ActiveParticle.end(),isInActive),m_ActiveParticle.end());

	/*Check for particles at the same pixel location and erase the weaker one*/
	CheckCollision checkCollision(m_ActiveParticle,1);
	for_each(m_ActiveParticle.begin(),m_ActiveParticle.end(),checkCollision); //deactivates Particle if collision
	m_ActiveParticle.erase(remove_if(m_ActiveParticle.begin(),m_ActiveParticle.end(),isInActive),m_ActiveParticle.end());

Aus diesen Zeilen stammt das erase im obigen Post. Momentan initialisiere ich CheckCollision mit den Pointern auf die aktiven Particles, um anschließend mit for_each zu überprüfen, ob zwei Partikel kollidieren. Ist das eine übliche Lösung, um Elemente eines Kontainers gegeneinander zu vergleichen, oder geht das besser? Vielen Dank soweit!

SeppJ

MrPink schrieb:

Ist das eine übliche Lösung, um Elemente eines Kontainers gegeneinander zu vergleichen, oder geht das besser?

Du zeigst zu wenig von deinem Problem und deiner Lösung, um diese Frage beantworten zu können. Alles was wir als Leser sehen können ist, dass du irgendeine Funktion auf irgendeinen Container anwendest. Ja: Das ist üblich, wenn man eine Funktion auf die Elemente eines Containers anwenden möchte . Ob es richtig oder effizient ist, hängt vom restlichen Kontext ab.

Du machst irgendeine Art von Simulation? Deine Beschreibung klingt so, als hättest du noch nie weder von Zelllisten noch von Verletlisten gehört. Vielleicht solltest du dir erst einmal den grundlegenden Algorithmus vornehmen, bevor du darüber nachdenkst, wie du es als C++-Einzeiler aufschreiben kannst.

MrPink

Deine Beschreibung klingt so, als hättest du noch nie weder von Zelllisten noch von Verletlisten gehört

Das stimmt, ich werde mal nachlesen, ob ich das gebrauchen kann.
Bei dem Projekt handelt es sich um ein Tracking Algorithmus, der Partikel in Videos verfolgt und mittels Optimierung die bestmögliche Bewegung ermittelt (jedoch kein Optischer Fluss und nein, OpenCV hilft nicht ;)). Das Projekt umfasst ca 20 Klassen: video, image, optimizer, particle,... Da ich aber alle 2 Jahre hin und wieder mal C++ programmiere, kenne ich mich mit den üblichen Lösungsansätzen nicht so gut aus. Es funktioniert zwar, aber es geht bestimmt besser Danke schon mal für die Tipps soweit! Ich versuche mal meine Frage

Ist das eine übliche Lösung, um Elemente eines Kontainers gegeneinander zu vergleichen, oder geht das besser?

präzieser zu formulieren: Wenn ich einen Container(In diesem Fall einen Vektor) mit Pointern zu Objekten habe (Particle) und ich überprüfen muss, ob es irgendein Tupel in dieser Menge (m_ActiveParticles) gibt, dass eine Bedingung erfüllt (Collision in diesem Fall), wäre die simpelste Umsetzung zwei for-Schleifen zu verschachteln und mit den Iteratoren die Bedingung zu überprüfen. Jetzt habe ich gelesen, dass man in C++ lieber versuchen sollte for_each mit Funktoren zu verwenden. for_each erlaubt mir aber nur über einen Container zu iterieren. Ich muss also einen Funktor erzeugen, der den gleichen Container enthält, um die Elemente gegeneinander auf eine Bedingung zu überprüfen:

vector<Particle*> m_ActiveParticle

CheckCollision checkCollision(m_ActiveParticle,1);
for_each(m_ActiveParticle.begin(),m_ActiveParticle.end(),checkCollision);

in CheckCollision muss ich dann wieder eine for_each Schleife verwenden (Sonst die zweite for-Schleife):

void CheckCollision::operator()(Particle*& particle){
	for_each(m_Particle.begin(),m_Particle.end(),CheckDistance(particle,m_MinDist));
}

Damit das funktioniert muss im Konstruktor von CheckCollicion natürlich m_Particle mit m_ActiveParticle initialisiert werden. Was bedeuted ich muss alle Pointer aus dem Vektor m_ActiveParticles kopieren.
Ist meine Umsetzung eine übliche Vorgehensweise, um zwei verschachtelte for-Schleifen mit for_each umzusetzen? Ich hoffe die Fragestellung nun etwas klarer formuliert zu haben.
Viele Güße!

SeppJ

Wenn ich jedes Element mit jedem anderen Element vergleichen möchte, dann würde ich zwei verschachtelte Schleifen nehmen. Die ganzen algorithms (es gibt ja noch viel mehr als for_each^*) sind schließlich nicht Selbstzweck, sondern vor allem um immer wieder auftauchende Probleme nicht immer wieder auf die gleiche Art und Weise lösen zu müssen, sondern stattdessen einfach die Standardlösung benutzen zu können. Wenn es jedoch darauf hinausläuft, dass man sich wer weiß wie viele Gedanken und Umstände macht, wie man seinen Zweizeiler mit den Algorithms noch eine Stufe abstrakter lösen könnte, dann macht man etwas falsch.

Kurz: Nimm einfach zwei Schleifen. Guck dir eventuell noch range based for und lambda-Ausdrücke an, wenn dir C++11 zur Verfügung steht. Ich denke, diese Konzepte dürften dir auch gefallen.

MrPink

Ok, vielen Dank für die Hilfe.