Aller Dreier aus vector<int> löschen?

Vertexwahn

Danke für die Hilfe wärs mir gleich ansehen

Hab den Code etwas abgeändert - wie macht man das mit iteratorn - ich werde zwar die stl Algorithmen später verwenden, aber um etwas den Umgang mit iteratoren zu lernen wäre es interessant zu wissen wie man das Problem mit Iteratoren löst...

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;

int main()
{
	// Zufallsfunktion initialisieren
	srand(time(0));

	// Zufällig irgendwelche Zahlen ermitteln
	vector<int> Zahlen;
	for(int i = 0; i < 10; i++)
		Zahlen.push_back(rand()%5+1);

	// Zahlen ausgeben
	for(unsigned int i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cout<<"<==================================="<<endl;

	// aller Dreier löschen
	unsigned index = 0;
	while(index != Zahlen.size())
	{
		if(Zahlen[index] == 3)
		{
			vector<int>::iterator dummy = Zahlen.begin() + index;
			Zahlen.erase(dummy);
		}
		else
		{
			index++;
		}
	}

	// Zahlen ausgeben
	for(unsigned int i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cin.get();
}

Maxi

ja, fast... beim vector is das löschen mit iteratoren noch relativ leicht, bei listen hab ichs auch noch nicht richtig hinbekommen

for(int i = 0; i  < v.size(); i++)
{
  if(v[i] == 3)
  {
    v.erase(v.begin()+i);
    i--;
  }
}

GPC

Maxi schrieb:

ja, fast... beim vector is das löschen mit iteratoren noch relativ leicht, bei listen hab ichs auch noch nicht richtig hinbekommen

http://www.c-plusplus.net/forum/viewtopic-var-t-is-144602-and-highlight-is-.html

FireFlow

Du solltest zuerst Zahlen.reserve(10) aufrufen, sonst muss während der Schleife eventuell mehrmals neu allokiert werden.

Das Problem an der Sache bei std::vector ist, dass alle Iteratoren ungültig werden (können) wenn du nur ein Elemnt löscht, daher macht das remove_if auch etwas anderst, kannst dir ja mal eine Implementierung davon anschauen.

Vertexwahn

so gefällts mir schon gut

#include <iostream>
#include <vector>
#include <ctime>
#include <functional>
#include <algorithm>
using namespace std;

bool gleichDrei(int zahl)
{
	if(zahl == 3)
		return true;
	else
		return false;
}

int main()
{
	// Zufallsfunktion initialisieren
	srand(time(0));

	// Zufällig irgendwelche Zahlen ermitteln
	vector<int> Zahlen;
	for(int i = 0; i < 10; i++)
		Zahlen.push_back(rand()%5+1);

	// Zahlen ausgeben
	for(unsigned int i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cout<<"<==================================="<<endl;

	// aller Dreier löschen
    remove_if(Zahlen.begin(), Zahlen.end(), gleichDrei);

	// Zahlen ausgeben
	for(unsigned int i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	//cin.get();
}

Vertexwahn

wieso werden hier die Dreier nicht gelöscht?

#include <iostream>
#include <vector>
#include <ctime>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
	// Zufallsfunktion initialisieren
	srand(time(0));

	// Zufällig irgendwelche Zahlen ermitteln
	vector<int> Zahlen;
	for(int i = 0; i < 10; i++)
		Zahlen.push_back(3/*rand()%5+1*/);

	// Zahlen ausgeben
	for(unsigned int i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cout<<"<==================================="<<endl;

	// aller Dreier löschen
    remove_if(Zahlen.begin(), Zahlen.end(), 
		bind2nd(equal_to<int>(), 3)
	);

	// Zahlen ausgeben
	for(unsigned int i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cin.get();
}

SideWinder

Sieh dir nochmal den Post von FireFlow an. remove_if löscht gar nichts

Wir wollens nicht unnötig in die Länge ziehen: remove_if kopiert die Elemente die gelöscht werden sollen an das Ende der Liste und gibt dir einen Iterator zurück um *ab zurückgegebenen Iterator* zu löschen:

vector<int>::iterator remove_from = remove_if(Zahlen.begin(), Zahlen.end(), 
        bind2nd(equal_to<int>(), 3) 
    ); 

	Zahlen.erase(remove_from,Zahlen.end());

MfG SideWinder

Vertexwahn

remove_if kopiert die Elemente die gelöscht werden sollen an das Ende der Liste und gibt dir einen Iterator zurück

danke für die Hilfe! der Code funktioniert:

#include <iostream>
#include <vector>
#include <ctime>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
	// Zufallsfunktion initialisieren
	srand(time(0));

	// Zufällig irgendwelche Zahlen ermitteln
	vector<int> Zahlen;
	for(int i = 0; i < 10; i++)
		Zahlen.push_back(rand()%5+1);

	// Zahlen ausgeben
	for(unsigned i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cout<<"<==================================="<<endl;

	// aller Dreier löschen
    vector<int>::iterator remove_from = remove_if(Zahlen.begin(), Zahlen.end(),
        bind2nd(equal_to<int>(), 3)
    );

    Zahlen.erase(remove_from,Zahlen.end());

	// Zahlen ausgeben
	for(unsigned i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cin.get();
}

was ich aber nicht verstehe ist - wenn ich das erease weglassen, dann ist die Zahlenliste bei der 2ten ausgabe nicht verändert:

#include <iostream>
#include <vector>
#include <ctime>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
	// Zufallsfunktion initialisieren
	srand(time(0));

	// Zufällig irgendwelche Zahlen ermitteln
	vector<int> Zahlen;
	for(int i = 0; i < 10; i++)
		Zahlen.push_back(rand()%5+1);

	// Zahlen ausgeben
	for(unsigned i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cout<<"<==================================="<<endl;

	// aller Dreier löschen 
    vector<int>::iterator remove_from = remove_if(Zahlen.begin(), Zahlen.end(),
        bind2nd(equal_to<int>(), 3)
    );

    //Zahlen.erase(remove_from,Zahlen.end()); // <- wird jetzt weggelassen

	// Zahlen ausgeben  // 2te Ausgabe
	for(unsigned i = 0; i < Zahlen.size(); i++)
		cout<<Zahlen[i]<<endl;

	cin.get();
}

meiner Erwartung nach müssten doch bei der 2ten Ausgabe die Dreier hinten stehen?

SideWinder

Naja das mit den "die Dreier stehen hinten" scheint nicht ganz zu stimmen. Beim Löschen scheint er alle Elemente die nicht dazugehören durch das nachfolgende Element zu ersetzen. Am Ende bleiben dann die bisher am Ende stehenden Zahlen einfach übrig (sie wurden eh nach vorne kopiert).

Der geht von deinem erase() aus

MfG SideWinder

FireFlow

Vertexwahn schrieb:

meiner Erwartung nach müssten doch bei der 2ten Ausgabe die Dreier hinten stehen?

Ne das mit dem Kopieren von Sidewinder muss nicht stimmen, das ist implementierungsbedingt was an den letzten Stellen dann steht. Aber normalerweise bleibt da einfach das stehen was vorher auch da war, eine 3 dort hinzuschreiben ist ja unnötig.

edit: Das hat man davon wenn man erst noch die Musik anmacht bevor man postet ~~

Werner Salomon

Maxi schrieb:

ja, fast... beim vector is das löschen mit iteratoren noch relativ leicht, bei listen hab ichs auch noch nicht richtig hinbekommen
for(int i = 0; i  < v.size(); i++)
{
  if(v[i] == 3)
  {
    v.erase(v.begin()+i);
    i--;
  }
}

sowas sollte man nie tun. Nicht nur weil es das std::remove_if gibt, sondern auch weil man bei einer Anwendung dieses Algorithmus' auf z.B. diesen Vector

using namespace std;
    vector< int > v( 99999, 3 );
    v[8] = 7;

sein blaues Wunder erleben kann

Gruß
Werner

warum erlebt man dabei sein blaues wunder?

Werner Salomon

Maxi_loggedout schrieb:

warum erlebt man dabei sein blaues wunder?

probier's aus

und danach dann den gleichen vector noch mal mit

v.erase( remove_if( v.begin(), v.end(), bind2nd( equal_to< int >(), 3 ) ), v.end() );

dann merkst Du's deutlich

Gruß
Werner

Vertexwahn

class Edge
		{
		public:
	               ...

		private:
			int    x_min; 
			int    y_min; 	   
			float    x;	   
			float   reciprocalSlope; 				 
			int  	y_max; 

		}; // class Edge

class Polygon
{
...
			bool compareYmax(Edge edge)
			{
				if(scanline == edge.y_max)
					return true;
				else
					false;
			}
...
{
...
// Alle Kanten in der Active Edge Table für die gilt y (scanline) == ymax werden entfernt
vector<Edge>::iterator remove_from = remove_if(ActiveEdgeTable.begin(),
       					  ActiveEdgeTable.end(),
					  compareYmax);  // <- ursache des fehlers

					ActiveEdgeTable.erase(remove_from,ActiveEdgeTable.end());
}
...
}; // class Polygon

der Compiler gibt mir die Fehlermeldung "c:\scanline.h(178) : error C3867: 'Polygon::compareYmax': function call missing argument list; use '&Vertexwahn::Scanline::Polygon::compareYmax' to create a pointer to member
"

warum geht das nicht? ...

Werner Salomon

Vertexwahn schrieb:

// Alle Kanten in der Active Edge Table für die gilt y (scanline) == ymax werden entfernt
vector<Edge>::iterator remove_from = remove_if(ActiveEdgeTable.begin(),
       					  ActiveEdgeTable.end(),
					  compareYmax);  // <- ursache des fehlers

					ActiveEdgeTable.erase(remove_from,ActiveEdgeTable.end());
der Compiler gibt mir die Fehlermeldung "c:\scanline.h(178) : error C3867: 'Polygon::compareYmax': function call missing argument list; use '&Vertexwahn::Scanline::Polygon::compareYmax' to create a pointer to member
"

warum geht das nicht? ...

weil 'compareYmax' kein Funktor oder eine Funktion, sondern eine Methode ist. Korrekt wäre

Polygon poly;
    vector<Edge>::iterator remove_from = remove_if(ActiveEdgeTable.begin(),
        ActiveEdgeTable.end(),
        bind1st( mem_fun( &Polygon::compareYmax ), &poly ) );

oder mit boost

vector<Edge>::iterator remove_from = remove_if(ActiveEdgeTable.begin(),
        ActiveEdgeTable.end(),
        boost::bind( &Polygon::compareYmax, p, _1 ) );

was ist übrigens 'scanline'; mir scheint dass die Methode compareYmax gar keine Member von Polygon benötigt; dann bräuchtest Du sie auch nicht.

Gruß
Werner

Vertexwahn

eigentlich hätte ich gerne so etwas:

vector<Edge>::iterator remove_from = remove_if(ActiveEdgeTable.begin(), 
	   ActiveEdgeTable.end(),  mem_func<bool,Edge>(&Polygon::compareYmax));

hier der ganze code:

#ifndef Scanline_h
#define Scanline_h

#include <vector>
#include <algorithm>
#include <cassert>
#include <functional>
using namespace std;

namespace Vertexwahn
{
	namespace Scanline	
	{
		class Plane3D // Repräsentierte eine Ebene
		{
		public:
			float A,B,C,D;
		}; // class Plane

		class Edge	// Kante eines Polygons. 
			        // Festlegung: Die Eckpunkte einer Kante sind immer ganzzahlig, liegen also genau auf einen Pixel
		{
		public:
			Edge(int x1, int y1, int x2, int y2)
			{
				x_min = x1 > x2 ? x2 : x1;

				y_min = y1 > y2 ? y2 : y1;
				x     = y1 > y2 ? x2 : x1;

				if(y2 == y1)	// bei vertikalen Kannten wird die Steigung auf 0 gesetzt
					reciprocalSlope = 0;
				else
					reciprocalSlope = (x2-x1) / (y2-y1);

				y_max = y1 > y2 ? y1 : y2;

				color = 0xFFFF0000; // rot
			}

			void print()
			{
				cout<<"========================================"<<endl;
				cout<<"y_min          : "<<y_min<<endl;
				cout<<"x              : "<<x<<endl;
				cout<<"reciprocalSlope: "<<reciprocalSlope<<endl;
				cout<<"y_max          : "<<y_max<<endl;
			}

			// zum Sortieren der Kanten nach dem kleinsten y-Wert - das "kleinste" Element ist ganz hinten 
			// im Array zu finden
			bool operator<(const Edge &rhs)
			{
			/*  // alter Code: hier war das kleinste Elment ganz vorn im Array zu finden
			    // wurde aber umgedreht, weil dadurch der Code in der draw Methode einfacher wird
				if(y_min == rhs.y_min)	// haben zwei Kanten den gleichen minimalen y-Wert, so werden sie nach 
				{   
					// aufsteigendem x-Wert sortiert
					return x_min < rhs.x_min;
				}
				else
					return y_min < rhs.y_min;
			*/

				if(y_min == rhs.y_min)	// haben zwei Kanten den gleichen minimalen y-Wert, so werden sie nach 
				{   
					// aufsteigendem x-Wert sortiert
					return x_min > rhs.x_min;
				}
				else
					return y_min > rhs.y_min;
			}

			Edge(const Edge &edge)
			{
				x_min = edge.x_min;
				y_min = edge.y_min;
				x = edge.x;
				reciprocalSlope = edge.reciprocalSlope;
				y_max = edge.y_max;
				color = edge.color;
			}

			Edge& operator=(const Edge &edge)
			{
				x_min = edge.x_min;
				y_min = edge.y_min;
				x = edge.x;
				reciprocalSlope = edge.reciprocalSlope;
				y_max = edge.y_max;
				color = edge.color;

				return *this;
			}

			int getYMax()
			{
				return y_max;
			}

		private:

			int    x_min; // kleinster x-Wert der Kante, wird zum Soriteren der GlobalEdgeTable benötigt

			int    y_min; // kleinster y-Wert der Kante - damit man bestimmen kann wann eine Kante in die 
						   // Active Edge List aufgenommen werden soll
			float    x;	   // Die x-Koordinate des Kantenpunkts mit der kleineren y-Koordinate

			float   reciprocalSlope; // Kehrwert der Steigung (1/slope) zur Berechnung von Schittpunkten mit der Scanline
									 // Für vertikale Kanten wird der Wert 0 angenommen.

			int  	y_max; // größter y-Wert der Kante - damit man bestimmen kann wan die Kante aus der Global bzw. Active
						   // Edge Table gelöscht werden kann

			int		color;	// Farbe des Polygons
			//Plane3D planeequation; // Ebenengleichung zur Bestimmung der Tiefe (für den Z-Buffer)

			friend class Polygon; // die Klasse Polygon soll auf private Datenelmente der Kanten zugreifen dürfen
		}; // class Edge

		//  Verwendetes Koordinatensystem
		//   y+
		//   |
		//   |
		//   | ========  Scanline wird von unten nach oben über das Polygon geschoben
		//   |
		//   0-------x+
		class Polygon
		{
		public:

			void setPixelColor(int x, int y, int color)
			{
			}

			bool compareYmax(Edge edge)
			{
				return scanline == edge.y_max;
			}

			// Methode sollte erste Aufgerufen werden, wenn die GlobalEdgeTable Kanten eines gülitgen Polygons 
			// enthält
			void draw()
			{
				// Polygon soll von unten nach oben gerendert werden - also vom minimalen y-Wert bis maximalen y-Wert

				// ist die GlobalEdgeTable nach y_min sortiert so muss man nur den minimalen y-Wert der ersten Kante
				// ermitteln und erhält so den minimalen y-Wert der Kante. Der Algorithmus wird abgebrochen, wenn
				// die GlobalEdgeTable und die ActiveEdgeTable leer ist. Damit wird der maximale y-Wert des Polygons
				// nicht benötigt.

				// GlobalEdgeTabel sortieren
				sort(GlobalEdgeTable.begin(), GlobalEdgeTable.end());

				// Startwert für die Scanline ist die minimale y-Koordinate des Polygons
				scanline = GlobalEdgeTable.back().y_min;

				// AET cleanen ;)
				ActiveEdgeTable.clear();

				// Solange die ActiveEdgeTable und die GlobalEdgeTable nicht leer sind
				while(!(GlobalEdgeTable.empty() && ActiveEdgeTable.empty()))
				{
					// Alle Kanten werden zur ActiveEdgeTable hinzugefügt und aus der 
					// Global Edgetable entfernt deren minimaler y-Wert mit der Scanline übereinstimmt
					while(!GlobalEdgeTable.empty() && (GlobalEdgeTable.back().y_min == scanline))
					{
						ActiveEdgeTable.push_back(GlobalEdgeTable.back());
						GlobalEdgeTable.pop_back();
					}	

					// Pixel zwischen jeweils zwei Schnittpunkten der AET malen
					Fill();

					// Alle Kanten in der Active Edge Table für die gilt y (scanline) == ymax werden entfernt
					vector<Edge>::iterator remove_from = remove_if(ActiveEdgeTable.begin(), 
																   ActiveEdgeTable.end(), 
																   mem_func<bool,Edge>(&Polygon::compareYmax)); 

					ActiveEdgeTable.erase(remove_from,ActiveEdgeTable.end());

					// continue...

					print();
					int a;
					a++;

				}

				// für die Scanline machen nur ganzzahlige werte sinn... ??? wenn start_y z.B.  2.9 ist wo mit scanline beginnen?
				// 
			}

			// Erwartet das die ActiveEdgeTable sortiert ist nach dem x-Wert und dieser zugleich
			// den Schnittpunkt mit Scanline darstellt
			void Fill()
			{
				// in der Active EdgeTable befindet sich immer eine gerade Anzahl von 
				// Kanten 
				assert(ActiveEdgeTable.size() % 2 == 0);

				for(int i = 0; i < ActiveEdgeTable.size()-1; i++)
				{
					assert(ActiveEdgeTable[i].x < ActiveEdgeTable[i+1].x);
				}

				// Fill Conventions:
				// siehe "Problem beim Füllen von Pixel zwischen zwei Schnittpunkten"
				// an diese Fill Conentions halte ich mich noch nicht - diese Methode sollte jedoch halbwegs zufrieden
				// stellende Ergebnisse liefern - für die Zukunft: Nur linke und untere Ränder zeichnen
				// obere und rechte Ränder werden nicht gezeichnet

				for(int i = 0; i < ActiveEdgeTable.size() / 2; i++)
				{
					DrawHorizontalLine(ActiveEdgeTable[i*2].x,ActiveEdgeTable[i*2+1].x);
				}
			}

			void DrawHorizontalLine(int a, int b)
			{
				assert(a > 0);
				assert(b > 0);
				assert(a < 400);
				assert(b < 400);
			}

			void print()
			{
				sort(GlobalEdgeTable.begin(), GlobalEdgeTable.end());

				// GlobalEdgeTable
				cout<<"GlobalEdgeTable"<<endl;
				for(int i = 0; i < GlobalEdgeTable.size(); i++)
					GlobalEdgeTable[i].print();
				cout<<"ActiveEdgeTable"<<endl;
				for(int i = 0; i < ActiveEdgeTable.size(); i++)
					ActiveEdgeTable[i].print();
			}

			void add(int x1, int y1, int x2, int y2)
			{
				// Horizontale Kanten ignorieren
				if(y1==y2)
					return;

				GlobalEdgeTable.push_back(Edge(x1,y1,x2,y2));
			}
		private:

			vector<Edge> GlobalEdgeTable; // Kantenliste soritiert nach minimalen y-Wert enthalt nur Kanten, die 
			                              // nicht horizontal sind - Kanten werden entfernt, wenn sie in die Active
										  // Edge List übernommen werden

			vector<Edge> ActiveEdgeTable; // Alle Kanten, die die Scanline aktuell schneiden tut ;)

			float scanline;				// y-Koordinaten der Scanline  
		}; // class Polygon

	} // namespace Scanline
} // namespace Vertexwahn

#endif

Aller Dreier aus vector&lt;int&gt; löschen?

Aller Dreier aus vector<int> löschen?