3. Bestimmter Wert schon im vector enthalten?

Bestimmter Wert schon im vector enthalten?

  • P

    Danke erstmal.

    @CStoll: Was muss ich einbinden um find() nutzen zu können?

    @Ponto: Hast Du vielleicht noch ein wenig mehr Input für mich?

    Gruß
    Patrick

    0
  • P

    PACoSys schrieb:

    @Ponto: Hast Du vielleicht noch ein wenig mehr Input für mich?

    Nicht wirklich. Es hängt vom Anwendungsfall ab. Aber generell geht es so:

    Header:

    #include <algorithm>

    Sortieren:

    std::sort(vec.begin(), vec.end());

    Ist der Wert schon drin?

    if (std::binary_search(vec.begin(), vec.end(), 5)) {
... 
}
    0
  • C

    PACoSys schrieb:

    Danke erstmal.

    @CStoll: Was muss ich einbinden um find() nutzen zu können?

    Den Header <algorithm>

    @Ponto: Hast Du vielleicht noch ein wenig mehr Input für mich?

    find() sucht linear, benötigt also (im worst case und im Durchschnitt) eine Laufzeit von O(n). binary_search() verwendet eine binäre Suche und kommt damit auf eine Laufzeit von O(log n) - allerdings erwartet es, daß die Eingabefolge sortiert ist (wenn du die Daten öfter änderst als suchst, lohnt sich das nicht, weil du jedes Mal neu sortieren müsstest).

    0
  • P

    Um heraus zu bekommen, ob ein Wert gefunden wurde, muss ich doch nur mit dem end des vectors vergleichen oder nicht. Komischerweise wird aber kein Eintrag gefunden. In dem vector stehen Pointer auf Point-Objekte und ich habe den == Operator für diese überschrieben (siehe Code). Heißt das im vorliegenden Fall, dass die Koordinaten unterschiedlich sind? Wenn ich sie mir mit cout anzeigen lassen sehe ich nur 4 Nachkommastellen und die sind gleich.

    bool operator == (const Point & crP2) const { return ((x == crP2.GetX()) && (y == crP2.GetY()) && (z == crP2.GetZ())); }

    if (find(rPoints.begin(), rPoints.end(), pPoint) == rPoints.end())
{
	rPoints.push_back(pPoint);
}

    Gruß
    Patrick

    0
  • M

    Du hast Pointer im vector? Dann werden die auch verglichen und nicht deine Point-Objekte.

    0
  • R

    btw. vielleicht solltest du eher ein std::set als ein std::vector benutzen.

    0
  • S

    Kann man nicht, falls es pointer sind, eine eigene Vergleichsfunktion schreiben, die eben erst dereferenziert und dann vergleicht und diese dann an find übergeben?

    template<class T>
struct PointerVergleich{
    bool operator()(const T*& l,const T*& r){
        return (*l)==(*r);
};

    so in der Art, bin mir aber recht unsicher, ob ich das jetzt richtig geschrieben hab... bitte korrigieren wenn falsch.

    EDIT: falls du nie gleichen Elemente im Container haben willst, nimm wie gesagt std::set.

    0
  • L

    Shinja schrieb:

    Kann man nicht, falls es pointer sind, eine eigene Vergleichsfunktion schreiben, die eben erst dereferenziert und dann vergleicht und diese dann an find übergeben?

    Operatoren die sich ausschließlich auf eingebaute Typen (und nichts anderes sind Pointer) beziehen lassen sich nicht überladen.

    0
  • S

    Siehe oben, ich meinte nicht überladen vom operator==. Würde es wie oben geschrieben nicht gehen? (den Functor dann halt an find übergeben)

    0
  • C

    find() kannst du keinen zusätzlichen Funktor übergeben. Aber die Lösung geht schon in die richtige Richtung - nimm find_if().

    0
  • L

    Der Funktor stand vorhin noch nicht da 😉
    Ja, das sollte gehen.

    EDIT: Siehe CStoll.

    0
  • S

    Ich weisz, sry, hab den gleich danach hinzugefügt. Aber hier antworten die Leute einfach zu schnell, hehe.

    Achja, find_if() war's, sry. Hatte ich mal wieder vergessen.

    0
  • P

    Erstmal danke für Eure zahlreichen Antworten.

    Habe es so probiert:

    if (find_if(rPoints.begin(), rPoints.end(), ComparePoint(pPoint)) == rPoints.end())
{
	//create new point
}

    und

    class ComparePoint
{
public:
	bool operator () (const Point *& crLhs, const Point *& crRhs)
	{
		return (*crLhs) == (*crRhs);
	}
};

    Ich bekomme jetzt beim Compilieren folgenden Fehler: "'<function-style-cast>': 'Point *' kann nicht in 'ComparePoint' konvertiert werden".

    Gruß
    Patrick

    0
  • C

    Ja, Funktoren sind kompliziert 😉 find_if() erwartet eine Funktion/Funktor, die mit einem Parameter aufgerufen werden kann und einen bool zurückgibt - den Vergleich mußt du in deinem op() erledigen:

    struct ComparePoints : public unary_function<Point*,bool>
{
  //Ctor - legt Vergleichwert fest
  ComparePoints(Point* tgt) : m_tgt(tgt) {}

  //op() - vergleicht übergebenen Wert mit Vergleichswert
  bool operator() (Point* akt)
  { return *akt == *m_tgt; }
private:
  Point* m_tgt;
};

...
if (find_if(rPoints.begin(), rPoints.end(), CompairPoint(pPoint)) == rPoints.end())
{
    //create new point
}

    (PS: Zeiger sind klein genug, um sie per Value übergeben zu können - da ist die Übergabe als const-Referenz überflüssig ;))

    0
  • P

    Danke funktioniert super. Eine Sache noch. Könnt Ihr Euch folgenden Code mal bitte ansehen und mir schreiben, ob Optimierungen möglich sind (ganz bestimmt sind welche möglich). Außerdem habe ich die Vermutung, dass ich da ein Speicherloch programmiert habe. In Kommentaren gibt es noch eine zweite Variante, die funktioniert aber nicht, da man Iteratoren nicht dereferenzieren kann.

    // Create new point.
Point * pPoint = new Point(x, y, z);

// If the point does not exist already then create a new one.
//vector<Point *>::iterator iter = find_if(rPoints.begin(), rPoints.end(), ComparePoint(pPoint)); // version 2
//if (iter == rPoints.end()) // version 2
if (find_if(rPoints.begin(), rPoints.end(), ComparePoint(pPoint)) == rPoints.end()) // version 1
{
	cout << " not found!!!" << endl;
	// Point does not exist already.
	pPoint->SetIndex(rPoints.size());

	rPoints.push_back(pPoint);
}
else
{
	// Delete pPoint because of memory leak??? But it is needed below again!!!
	cout << " found." << endl;
}

// Memorize point index for neighborhoods.
//int index = (*iter)->GetIndex(); // version 2
int index = (*find_if(rPoints.begin(), rPoints.end(), ComparePoint(pPoint)))->GetIndex(); // version 1

    Gruß
    Patrick

    0
  • C

    Die beste Optimierung: Verwende keine Zeiger, wenn es nicht nötig ist (d.h. wenn keine echten Gründe dagegen sprechen, solltest du du einen vector<Point> verwenden - dann erübrigt sich auch die Speicherveraltung und das Gebastel mit dem Functor).

    Ansonsten: Ja, im else-Zweig solltest du das per new angelegte Objekt wieder freigeben. Und die Suche solltest du nur einmal durchführen und dir das Ergebnis dann merken (die Lösung "version 2" solltest du auf jeden Fall verwenden - im else-Zweig noch ergänzt um ein iter = rPoints.end()-1; ).

    0
  • P

    Variante 2 würde ich ja gerne verwenden, aber Iteratoren können nicht dereferenziert werden.

    Ohne Pointer geht es glaube ich nicht. Mal ein Wenig mehr zum Hintergrund: Ich schreibe mir ein Programm, welches aus einer Datei Flächen einliest. Jede Fläche besteht aus Drahtgittern, diese wiederum aus Kanten und die sind dann durch ihre Anfangs- und Endpunkte beschrieben. Beim Einlesen muss ich mir eine Topologie aufbauen, so dass ich hinterher weiß welche Punkte benachbart sind, welche Punkte zu welchem Drahtgitter gehören und welche Punkte zu einer Fläche gehören. Nachdem ich die Daten eingelesen habe, will ich die Punkte so sortieren, dass die Punkte, die den Rand der Fläche beschreiben in einer bestimmten Reihenfolge sind. Nun hatte ich mir folgendes überlegt:

    Klasse Face:
    - hat einen vector mit allen Punkten => vector<Point *>
    - hat einen vector mit allen Drahtgittern => vector<Wire *>

    Klasse Wire:
    - hat einen vector mit den sortierten Indizes der zugehörigen Punkte => vector<int>

    Klasse Point:
    - Koordinaten => double x, double y und double z
    - Pointer auf Nachbarn (jeweils zwei) => Point * pN0 und Point * pN1

    Beim Einlesen erstelle ich für jede Fläche eine Instanz der Klasse Face, in dieser wird die Methode processFace() aufgerufen. processFace() erstellt für jedes Drahtgitter der Fläche eine Instanz der Klasse Wire, in der dann wiederum processWire() aufgerufen wird. processWire() ruft für jede Kante des Drahtgitters processEdge() auf. processEdge() ist der Kern, hier werden die Instanzen der Point Klasse erstellt, wobei nur ein neuer Punkt erstellt werden soll, wenn nicht schon ein Punkt mit den selben Koordinaten existiert.

    Kann man, dass ohne Pointer umsetzen?

    Gruß
    Patrick

    0
  • A

    Ja, kann man ohne Pointer umsetzen. Solange du ohne Polymorphie auskommst. Und das scheint bei deiner Point und Wire Klasse der Fall zu sein. Probier es doch einfach mal ohne Pointer! (du bist in der C++-Welt!) Der Code wird dadurch sogar kürzer.

    0
  • C

    PACoSys schrieb:

    Variante 2 würde ich ja gerne verwenden, aber Iteratoren können nicht dereferenziert werden.

    Wer erzählt denn sowas? Klar können Iteratoren dereferenziert werden, andernfalls wären sie ziemlich nutzlos.

    0
  • P

    CStoll schrieb:

    Wer erzählt denn sowas?

    Die Microsoft Visual C++ Debug Library. Ich kann das Projekt compilieren und ausführen, aber an dem Punkt wo ich den Iterator dereferenziere bekomme ich eine schicke Fehlermeldung:

    Debug Assertion Failed!

    Program: ...
    File: ...
    Line: ...

    Expression: vector iterator not dereferencable

    For information on how your program can cause an assertion
    failure, see the Visual C++ documentation on asserts.

    @Artchi: Wo speichere ich dann meine Punkte, ich dachte die müsste ich mir mit Pointern merken?! Insbesondere die Nachbarschaft, bisher speichere ich mir einen Pointer, aber aus einem vector<Point> bekomme ich keinen Pointer.

    Gruß
    Patrick

    0
Anmelden zum Antworten