stl: Element in vector finden

freakC++

Hallo zusammen,

ich habe zwei vector px1 und px2 vom Typ "pixelIndex":

struct pixelIndex {
	unsigned char value;
	int x;
	int y;
};

vector<pixelIndex> px1;
vector<pixelIndex> px2;

Jetzt iteriere ich über px1 und möchte für jedes Element aus px1 wissen, ob es ein Element in px2 gibt, das denselben "value" hat.

Ich kenne die stl-Methode "find", aber momentan sehe ich keine Anwendung, da ich ein Element suche, das ein bestimmtes Attribut hat.

Könnt ihr mir helfen, dieses Problem schön zu lösen (Ich könnte es auch durch zwei normale for-Schleife lösen, doch ist es mir daran gelegen, mich mehr in die STL einzuarbeitetn und schöneres C++ zu produzieren :))

Vielen Dank

Nathan

Vielleicht mismatch?

Eher set_union.

PS @freakC++: Zeig uns mal, wie das mit den 2 for-Schleifen aussehen würde, sonst ist das für uns ein Rätselraten, was du eigentlich willst.

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...