Elemente in std::vector vergleichen

playking21

Guten Tag,
ich habe einen std::vector, in dem alle Elemente untereinander verglichen werden müssen. Es wäre ja ziemlich langsam, wenn ich einfach mit 2 Iteratoren durch den Vektor iterieren würde, denn dann würde ich ja nicht nur das 1. Element mit dem 2. Element vergleichen, sondern auch das 2. mit dem 1. Das will ich vermeiden.
Hoffe ihr könnt mir da nen Algorithmus geben, habe es nämlich nicht hinbekommen, den selber zu schreiben.
Mit freundlichen Grüßen,
playking21

Nexus

Willst du jedes Element mit jedem vergleichen? Das ist immer noch langsam (quadratische Laufzeit), aber sähe so aus:

for (auto first = c.begin(); first != c.end(); ++first)
{
	for (auto second = std::next(first); second != c.end(); ++second)
	{
		doSomething(*first, *second);
	}
}

Je nachdem, was du tun willst, kannst du durch vorheriges Sortieren o.Ä. viel effizienter arbeiten. Also beschreib vielleicht mal dein Problem.

playking21

Ok, also eigentlich geht es darum, dass ich einen Vector habe, in dem Objekte gespeichert sind, die eine Kollision haben können. Habe ich jetzt zum Beispiel zwei Objekte(A und B), muss ich ja nur die Kollision zwischen A und B prüfen.

prüfeKollision(a, b);

Mit deinem Lösungsvorschlag, hätte ich ja das Problem, dass er die Funktion 2-mal aufruft(oder?)

prüfeKollision(a, b);
prüfeKollision(b, a);

icarus2

Nein, der Code von Nexus prüft nichts doppelt, siehe auto second = std::next(first) in der inneren for-Schleife.

Eventuell ist es mit Indizes etwas einfacher zu verstehen. Mit Indizes (anstatt Iteratoren) wäre es

for ( int i = 0; i < m; ++i )
{
  for ( int j = i + 1; j < n; ++j )
  {
    // ...
  }
}

Offensichtlich gilt stets j > i und deswegen wird nichts doppelt überprüft.

playking21

Danke für eure Hilfe