Elemente eines Vectors zusammenfassen

Mister Wing

Hallo,

folgendes Szenario. Ich habe einen Vector der mit Objekten belegt ist.

Hierbei möchte ich jeweils die y addieren zueinander deren x gleich ist. Der Vector ist auch bereits vorsortiert. So soll es aussehen.

Mein Implementierung is twie folgt.

#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;

struct point
{
	int x;
	int y;
};

int main(array<System::String ^> ^args)
{
        //Punkte anlegen
	point a,b,c,d,e,e1,e2,f,g,h,i;

	a.x = 1; a.y = 2;
	b.x = 1; b.y = 3;
	c.x = 4; c.y = 5;
	d.x = 6; d.y = 12;
	e.x = 9; e.y = 1;
	e1.x = 9; e1.y = 4;
	e2.x = 9; e2.y = 8;
	f.x = 10;f.y = 4;
	g.x = 11;g.y = 7;
	h.x = 14;h.y = 12;
	i.x = 14;i.y = 15;

        //Vector anlegen und mit Punkten füllen
	vector<point> vec;

	vec.push_back(a);vec.push_back(b);vec.push_back(c);
	vec.push_back(d);vec.push_back(e);vec.push_back(e1);
	vec.push_back(e2);vec.push_back(f);vec.push_back(g);
	vec.push_back(h);vec.push_back(i);

	point curr, next;

	vector<point>::iterator iter;
	for( iter = vec.begin() ; iter != vec.end()-1 ; iter++ )
	{
		curr = *iter;
		next = *(++iter);

		if ( curr.x == next.x )
		{				
			point temp;

			temp.x = curr.x;

			temp.y = curr.y + next.y;

			iter = vec.erase(--iter);
			iter = vec.erase(iter);

			vec.insert(iter,temp);		
		}
		else			
			--iter;
	}

   return 0;
}

Leider veursacht der Code einen Programmabsturz. Wo liegt der Fehler?

Simon2

Mister Wing schrieb:

...

int main(array<System::String ^> ^args)

...

Das ist ziemlich sicher kein C++.

Im Folgenden rede ich nur über C++ - wenn Du was Anderes programmierst, gilt das vielleicht nicht mehr:

Ich würde das gar nicht "auf dem Vektor" machen, sondern mir eine passende Kopie erzeugen.
Vollziehe Deinen Algorithmus doch mal "auf dem Papier" nach - vA die Positionen und Gültigkeiten (merke: erase() und insert() verändern die Gültigkeiten von Iteratoren !) von "iter".
sollen wirklich nur aufeinanderfolgende Gleichartige bearbeitet werden ?
Folgendes berücksichtigt Dein Algorithmus z.B. nicht:

Du kannst das Suchen auch von einer map<int, int> abnehmen lassen:

map<int,int> m;
for(vector<point>::const_iterator i=vec.begin(); i!=vec.end(), ++i) {
   m[i->x] += i->y;
}
// -> in ergebnisVec kopieren
vector<point> erg;
for(map<int,int>::const_iterator i=m.begin(); i!=m.end(), ++i) {
   erg.push_back(point(i->first, i->second)); // entsprechenden Ctor vorausgesetzt
}

Falls point keinen entsprechenden Ctor hat: entweder den oder eine make_point()-Funktion schreiben ...

da es std::pair gib, brauchst Du eigentlich kein eigenes "point-Struct".
Das Konstrukt (*i). funktioniert zwar, aber ich persönlich finde -> schöner und übersichtlicher ... (ist aber nur eine Randbemerkung)

Gruß,

Simon2.

asc

zu spät...

Mister Wing

Danke für den alternativen Vorschlag. Das war aber nicht meine Frage.
Vielmehr wollte ich den Fehler in meinem Code wissen. In meinem Programm ist die Struktur komplexer. Am Ende will ich gleichartige Objekte fidnen nach bestimtmen Kriterien und dessen Elemente zusammenfassen. Das addieren war nur ein Beispiel, damit das Prinzip klar wird. Und in welcher Sprche programmiere ich gerade, weil du meintest das ist ganz sicher kein C++ ?!

jencas

Manipulationen an Iteratoren einer for-Schleife sollte man nur vornehmen, wenn man weiss, was man macht. Hast Du Dir den Inhalt von iter am Ende des ersten Schleifendurchlaufs schon mal im Debugger angeschaut? Tipp: Bau Dir lieber einen zweiten vector für die Ergebnisse auf, dann kannst Du Dir den ganzen Kuddelmuddel mit den Manipulationen am Iteratoren ersparen. Und noch ein Tipp: auch structs können Konstruktoren haben. Damit könntest Du die Initialisierung des Vectors vereinfachen auf z.B.:

vec.push_back(point(1, 2));
vec.push_back(point(1, 3));
...

Tanren

So sollte es gehen

vector<point>::iterator read,write; 
    point temp;
    temp.x = vec.begin()->x;
    temp.y = 0;
    point prev = *(vec.begin());
    for(read = write = vec.begin(); read != vec.end(); read++){
        if(read->x != prev.x){
            *write++ = temp;
            temp = *read;
        }else{
            temp.y += read->y;
        }
        prev = *read;
    }
    *write++ = temp;
    vec.erase(write,vec.end());

Simon2

Mister Wing schrieb:

...Vielmehr wollte ich den Fehler in meinem Code wissen. ...

Da hast Du vermutlich nur meinen Code angesehen und meine Anmerkungen zu "den Fehler(n) in meinem Code" sind ein wenig untergegangen: Veränderungen an Vectoren machen Iteratoren ungültig! (nicht jede, aber einige und in Deinem Fall auf jeden Fall)
Spätestens beim insert() sollte das klar sein, wenn Du Dir die üblichste Implementierung eines std::vector ansiehst:
- Er hält intern ein Array (mit new[] angelegt, vielleicht bis zu einem Schwellwert auf dm Stack), das bis zu einer gewissen Größe "Reserve" bietet
- Ist diese aufgebraucht, muss er ein neues anlegen und kopieren ... und dieses liegt an einer anderen Stelle im Speicher!!
- Zeiger (und Iteratoren halten intern Speicher und verhalten sich nach Außen auch so wie welche), die noch auf den alten Speicherbereich verweisen, sollte man natürlich nicht mehr verwenden.

Ja - man hätte die Sprache so definieren können, dass Iteratoren "mit umziehen". Aber es ist nunmal nicht so (und man hatte auch gute Gründe dafür)..

Eine Lösung (die auch ich schon vorgeschlagen habe): Eine Kopie erstellen.

Mister Wing schrieb:

...
Am Ende will ich gleichartige Objekte fidnen nach bestimtmen Kriterien und dessen Elemente zusammenfassen...

Einer map kannst Du vollkommen frei definieren, wann sie ihre Objekte als "gleichartig" betrachtet und mit einer entsprechenden Überladung des operator+=() kannst Du auch frei definieren, was Du als "zusammenfassen" verstanden haben möchtest ....
Damit ist mein Code sehr viel allgemeingültiger, als er Dir vielleicht vorkommt.
Aber selbst ohne diesen "syntaktischen Zucker" bleibt map eine mächtige Waffe im "Suchen/Ergänzen"-Krieg ... da kann man viel Aufwand/Fehler/Ärger sparen, wenn man das nutzt.

Andere wichtige Waffen findest Du in <algorithm> ...
diese ganze "manuelle Schleiferei" (mit ihren tausend "off-by-one"-, "ungültige-Iteratoren"- und Verschachtelungsfehlermöglichkeiten) kann man sich größtenteils sparen.

@"Kein C++":
+ Das Zeichen "^" bedeutet in C++ "binäres XOR"
+ "array" ist kein vordefinierter Datentyp
+ die o.a. Signatur von main() ist in C++ nicht gültig.
Der Rest würde aber als C++ durchgehen.

Gruß,

Simon2.

LordJaxom

Leider veursacht der Code einen Programmabsturz. Wo liegt der Fehler?

Wenn Du die letzten beiden Elemente prüfst, steht curr auf 14/12, und iter auf 14/15. Dann löscht Du diese beiden Elemente, wodurch iter auf end() steht (das dem gelöschten folgende Element ist end()). Die Fortsetzung der for-Schleife zählt iter dann nochmal hoch (erster Fauxpas, end() darf nicht inkrementiert werden). Damit wird die Bedingung iter == end()-1 nie erreicht.

EDIT:
Die Sachen von Simon2 kommen noch erschwerend hinzu. Tipp: Auch insert() liefert einen Iterator zurück.

Dravere

Mister Wing schrieb:

Und in welcher Sprche programmiere ich gerade, weil du meintest das ist ganz sicher kein C++ ?!

Nur um diese Frage auch noch zu beantworten: Sehr wahrscheinlich C++/CLI. Das ist eine Kombination aus C++ und dem .Net Framework von Microsoft. Wir haben sogar ein Extra Forum dafür:
http://www.c-plusplus.net/forum/viewforum-var-f-is-58.html

Ist aber definitiv kein Standard-C++.

Grüssli

asc

Mister Wing schrieb:

Und in welcher Sprche programmiere ich gerade, weil du meintest das ist ganz sicher kein C++ ?!

Das ist C++/CLI nicht C++.

int main(array<System::String ^> ^args) // <-- System::String, "^" sind kein C++

Entweder hast du ausversehen den falschen Projekttyp gewählt, oder du verwendest bewusst C++/CLI. Unter dem Visual C++ musst du "Win32 Konsolenanwendung" auswählen (Nichts mit CLR oder ähnlich).

cu André

Mister Wing

@Tanren Dein Algo funktioniert super. Danke!

Werde aber trotzdem auch noch mal die anderen Alternativen versuchen.

Thread closed() !

Jester

Simon2 schrieb:

Einer map kannst Du vollkommen frei definieren, wann sie ihre Objekte als "gleichartig" betrachtet und mit einer entsprechenden Überladung des operator+=() kannst Du auch frei definieren, was Du als "zusammenfassen" verstanden haben möchtest ....

Das mit der map funktioniert aber nur, wenn man bereit ist, den zusätzlichen O(log n)-Faktor zu bezahlen.

Hier würde ich tatsächlich einfach manuell -- so wie von tanren vorgeschlagen -- drüberlaufen. Allerdings würde ich das in eine Funktion mit Iteratoren Interface packen.

Simon2

Jester schrieb:

...
Das mit der map funktioniert aber nur, wenn man bereit ist, den zusätzlichen O(log n)-Faktor zu bezahlen....

Das stimmt natürlich.

Aber ich bin auch erstmal von eher wenigen Daten ausgegangen, bei denen die Entwicklungs-/Wartungszeit eine größere Rolle spielt als Laufzeitordnungen.

... und auch ansonsten würde ich immer erstmal unter den Std-Algos schauen, bevor ich mich an "handgemachte" Schleifen setze. Der Ansatz hält erstmal die Entwicklungszeit (besonders bzgl. Fehlersuche) klein und wenn später tatsächlich Laufzeitprobleme zu beheben sind, kann man immer noch gezielt optimieren...
Wer andersherum immer zuerst eine eigene Schleife für Standardaufgaben baut (von trivialen mal abgesehen), verpulvert eine Menge Zeit/Schweiß.

Gruß,

Simon2.

Jester

Simon2 schrieb:

... und auch ansonsten würde ich immer erstmal unter den Std-Algos schauen, bevor ich mich an "handgemachte" Schleifen setze.

Das ist sicher oft eine gute Idee. Allerdings ist es gerade hier so, dass aus mehreren Datensätzen einer werden soll. Die Standard-Funktionen bieten so etwas afaik aber nicht: Es gibt die normalen copy/transform-Sachen, die ein Element auf ein anderes Abbilden, Varianten wie transform_if bzw. das nicht existierende copy_if, die aus einem Element 0 oder 1 machen und Varianten, die alles auf ein Element eindampfen (accumulate/min_element und Konsorten). Dazwischen gibt es meines Wissens nicht. Daher muß man hier wohl oder übel selbst Hand anlegen.

Simon2

Jester schrieb:

...Allerdings ist es gerade hier so, dass aus mehreren Datensätzen einer werden soll. Die Standard-Funktionen bieten so etwas afaik aber nicht: ...

Da hast Du schon Recht.

Ich habe den gewünschten Algorithmus' auch ein wenig anders interpretiert - nämlich ohne vorherige Sortierung (die Mr. Wing anscheinend voraussetzte, ich aber wohl in seiner Schilderung übersehen habe).

Dadurch kam es halt zu dem

Jester schrieb:

...zusätzlichen O(log n)-Faktor ...

Den hatte Mr Wing schon in die Sortierung gesteckt (Vorteil könnte natürlich sein, dass er diese Sortierung direkt in den Vektoren auch später noch verwenden könnte) ...

Gruß,

Simon2.

Werner Salomon

Unabhängig vom ursprünglichen Problem von Mister Wing, frage ich mich bei solchen Anforderungen immer, wie man es den im Sinne von STL und C++-like machen könnte. Simon2 äußerte bereits das Bedürfnis, einen Algorithmus aus dem Standard zu nutzen. Wenn es schon keinen passenden gibt, so kann man sich auch selber einen schnitzen.

'condense' fast alle aufeinanderfolgenden Elemente bei denen pred(*i,*(i+1)) true ist mit merge zu einem zusammen und gibt schließlich den Iterator hinter dem zuletzt zusammengefassten Element zurück (ähnlich wie remove_if).

template< typename I, typename P, typename M >
I condense( I first, I last, P pred, M merge )
{
    if( first == last )
        return last;
    for( I src = first; ++src != last; )
    {
        if( pred( *first, *src ) )
        {
            *first = merge( *first, *src );
        }
        else
        {
            *++first = *src;
        }
    }
    return ++first;
}

Auch bei der kleinsten anzunehmenden struct kann man immer einen Konstruktor und einen Ausgabe-operator vorsehen - und sei es nur für Debug-Zwecke. Zusätzlich spendiere ich hier einen operator+ - ich unterstelle mal, dass es sich bei 'point' nicht(!) um eine Koordinate im 2D handelt. Somit wird nur der y-Wert addiert. Dann erhält man das aufgeblasene point:

#include <cassert>
#include <iostream>
#include <boost/operators.hpp> // addable

struct point : public boost::addable< point >
{
    point() : x(0), y(0) {}
    point( int x_, int y_ ) : x(x_), y(y_) {}
    point& operator+=( const point& b )
    {
        assert( x == b.x );
        y += b.y;
        return *this;
    }
    int x;
    int y;
};
std::ostream& operator<<( std::ostream& out, const point& pnt )
{
    return out << pnt.x << " " << pnt.y;
}

Ausgerüstet mit diesem Handwerkszeug ist der Rest fast Formsache:

#include <algorithm>    // copy
#include <functional>   // plus
#include <iostream>
#include <iterator>     // ostream_iterator
#include <vector>

#include <boost/bind.hpp>

// struct point und Algorithmus condense s.o.

int main()
{
    using namespace std;
    vector< point > vec;
    vec.push_back( point( 1, 2 ) );
    vec.push_back( point( 1, 3 ) );
    vec.push_back( point( 4, 5 ) );
    vec.push_back( point( 6, 12 ) );
    vec.push_back( point( 9, 1 ) );
    vec.push_back( point( 9, 4 ) );
    vec.push_back( point( 9, 8 ) );
    vec.push_back( point( 10, 4 ) );
    vec.push_back( point( 11, 7 ) );
    vec.push_back( point( 14, 12 ) );
    vec.push_back( point( 14, 15 ) );

    vec.erase( condense( vec.begin(), vec.end(), 
        boost::bind( &point::x, _1 ) == boost::bind( &point::x, _2 ), plus< point >() ), 
        vec.end() );
    copy( vec.begin(), vec.end(), ostream_iterator< point >( cout << "x y\n", "\n" ) );
    return 0;
}

Das Programm generiert die von Mister Wing im Original Thread gewünschte Ausgabe.

Gruß
Werner