stl: Element in vector finden

freakC++

Hi!

Zunächst muss ich eine kleine Korrektur machen, da meine struct anders aussieht. Ich habe eben einen Denkfehler gemacht. Das zu lösende Problem ist jedoch das gleiche.

struct pixelMatch {
	Feature pixel;
	Feature match;
};

Meine for-Schleifenlösung sieht wie folgt aus:

for(std::vector<pixelMatch>::iterator it1 = pxMatch1.begin(); it1 != pxMatch1.end(); ++it1) {
		for(std::vector<pixelMatch>::iterator it2  = pxMatch2.begin(); it2 != pxMatch2.end(); ++it2) {
			if(isEqual((*it1).pixel, (*it2).match) && isEqual((*it2).pixel,(*it1).match)) {
				_matched1.push_back((*it1).pixel); //in einem anderem vector speichern
				_matched2.push_back((*it2).pixel);
			}
		}
	}

Suchst du sowas?

#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main()
{
	int ar[] = { 1,2,3,4,5,6,7,8,9};
	vector<int> px1(ar,ar+9);

	int ar2[] = { 1,3,8,};
	vector<int> px2(ar2,ar2+3);

	vector<int> res;

	set_intersection( px1.begin(), px1.end(), px2.begin(), px2.end(), back_inserter(res)); // res: 1,3,8
}

dot

Muss für set_intersection der Input nicht sortiert sein?

Grütze.

Aber ja, muss sortiert sein.

dot schrieb:

Muss für set_intersection der Input nicht sortiert sein?

Huch, doch hast Recht. Hab ich meine Werte nun natürlich elegant gewählt.

Decimad schrieb:

Grütze

?

Ich hatte von seinem Algorithmus geschrieben, er sei O(n²). Deshalb Grütze. Könnte ja auch eines davon eine Konstante sein. Ansonsten wäre sortieren zumindest theoretisch trotzdem schneller... irgendwie sowas wollte ich sagen.

Decimad schrieb:

irgendwie sowas wollte ich sagen.

Soweit ich weiss, gibt es keinen Algorithmus in der STL, der O(n·m) oder O(n²) als Komplexität hat. Folglich gibt es für die Schleifenlösung keine direkte Alternative (ausser halt mit Lambdas verschachtelte STL-Algorithmen).

Ich denke aber, dass das Problem von freakC++ schneller lösbar ist. Leider fehlen immer noch ein paar Rahmenbedingungen. (Was wird mit dem Resultat gemacht? Ist pixel oder match eindeutig? Was ist Feature?)

Nein, sowas wollte ich auch gar nicht sagen. Ich wollte ursprünglich nur behaupten dass sortieren + set_intersection schneller wäre und dazu musste ich anschließend bei aktueller Informationslage einfach "Grütze" sagen.

dot

Ich würde sagen, was schneller ist, hängt davon ab, mit wievielen Elementen man es zu tun hat...