Fragen zu Iteratoren



  • Hallo,

    ich habe ein paar Fragen bezüglich Iteratoren. Folgender Beispielcode:

    template <typename iterator> void foo(iterator in_start_, iterator in_end_, iterator in_2_start_, iterator out_start_)
    {
    	for (auto it = in_start_; it != in_end_; ++it, ++in_2_start_, ++out_start_) {
    		*out_start_ = *it**in_2_start_;
    	}
    }
    
    int main()
    {
    	std::vector<int> v1 = { 1, 2, 3, 4, 5 };
    	std::vector<int> v2 = { 1, 2, 3, 4, 5 };
    	std::vector<int> result(v1.size());
    
    	foo(v1.begin(), v1.end(), v2.begin(), result.begin()); // Berechnet v1*v2 (Elementweise)
    }
    

    Jetzt meine Fragen:

    • Ist es normal/empfehlenswert immer nur für den ersten iterator sowohl begin als auch end anzugeben? Bei std::copy ist das ja auch so, ist das so gut?
    • Wie bei std::copy muss ja hier auch der result container schon vorinitialisiert sein. Kostet das nicht unnötig Performance wenn ich erst alles per 0 initialisiere und dann nochmal mit den tatsächlichen Werten befülle? Bei vektoren als Parameter würde ich ja einfach reserve und nicht resize aufrufen, aber das geht hier ja nicht, oder?
    • Wie soll man das Ganze elegant machen wenn result sowohl 1- als auch 2-Dimensional sein kann?
    • Die for Schleife ist ja schon ziemlich umfangreich, trotz auto ... kann man das irgendwie eleganter/kürzer machen?
    • Kann man foo nicht einfach das Ergebnis zurückgeben lassen? Also hier einen vector<int> , anstatt einen Rückgabeparameter verwenden zu müssen? Das fände ich auch übersichtlicher...

  • Mod

    Ist es normal/empfehlenswert immer nur für den ersten iterator sowohl begin als auch end anzugeben? Bei std::copy ist das ja auch so, ist das so gut?

    Das ist genau dann der Fall, wenn entweder

    • Die Länge der Range bekannt ist (bspw. copy_n ), oder weil die Länge einer zweiten Range dieselbe sein muss wie die der ersten
    • Die Länge der Range nicht bekannt sein braucht (bspw. output-Parameter wie bei copy )
      Beachte auch Dinge wie std::back_inserter .

    [*] Wie bei std::copy muss ja hier auch der result container schon vorinitialisiert sein. Kostet das nicht unnötig Performance wenn ich erst alles per 0 initialisiere und dann nochmal mit den tatsächlichen Werten befülle? Bei vektoren als Parameter würde ich ja einfach reserve und nicht resize aufrufen, aber das geht hier ja nicht, oder?

    Ja, es geht besser. Mit back_inserter und reserve .

    std::vector<int> result;
        result.reserve( v1.size() );
    
        foo(v1.begin(), v1.end(), v2.begin(), std::back_inserter(result));
    

    Die for Schleife ist ja schon ziemlich umfangreich, trotz auto ... kann man das irgendwie eleganter/kürzer machen?

    template <typename iterator> void foo(iterator in_start_, iterator in_end_, iterator in_2_start_, iterator out_start_)
    {
        std::transform( in_start_, in_end_, in_2_start_, out_start_, std::multiply<>{} );
    }
    

    (ungetestet)



  • Macht deine Funktion nicht genau das gleiche wie std::transform mit std::multiply als funktor?

    Die eleganteste Art fuer das hinten einfuegen ist std::back_inserter.

    Du solltest zwischen Algorithmen (wie die aus der Standardlibrary; sehr generalisiert und arbeiten auf iteratoren) und den normalen Funktionen des Programms (fuehren Aktionen durch und erzeugen Objekte) unterscheiden.

    EDIT: Zu spaet


  • Mod

    happystudent schrieb:

    [*] Ist es normal/empfehlenswert immer nur für den ersten iterator sowohl begin als auch end anzugeben? Bei std::copy ist das ja auch so, ist das so gut?

    Dafür gibt es genau eine Regel und die sollte offensichtlich sein: Nimm, was du brauchst!

    Ist die denn nicht klar, warum copy Anfang und Ende des zu kopierenden Bereichs nimmt, aber nur den Anfang des Ziels? Was würde denn das Ende des Ziels bringen?

    [*] Wie bei std::copy muss ja hier auch der result container schon vorinitialisiert sein. Kostet das nicht unnötig Performance wenn ich erst alles per 0 initialisiere und dann nochmal mit den tatsächlichen Werten befülle? Bei vektoren als Parameter würde ich ja einfach reserve und nicht resize aufrufen, aber das geht hier ja nicht, oder?

    Das ist nicht so. Das wäre nur dann so, wenn du, wie in deiner vorherigen Frage, ein Ende des Zielbereichs angeben würdest. Das ist ein weiterer Grund, wieso dies Unsinn wäre.
    Wenn du hingegen nur den Anfang des Zielbereichs angibst, dann kann ja der Iterator so gebaut sein, dass er bei Bedarf den Container vergrößert (z.B. indem er bei einem vector neue Elemente mittels push_back einfügt). Das tolle an Iteratoren ist schließlich, dass sie nicht nur schnöde Zeiger sind.
    Die Standardbibliothek bietet auch bereits eine Iteratorvorlage, die genau dieses leistet: std::back_inserter.

    [*] Wie soll man das Ganze elegant machen wenn result sowohl 1- als auch 2-Dimensional sein kann?

    Dafür müsste man konkreter wissen, was die Funktion macht. Ist jedenfalls verdächtig, dass sie überhaupt 1D und 2D mit dem gleichen Code bearbeiten kann. Klingt so, als wäre der Algorithmus rein 1D. In dem Fall interessiert die Funktion doch gar nicht, wenn da ein 2D-Container hinter den Iteratoren steht. Und der 2D-Container bietet doch sicher auch einen Iterator (oder du schreibst dir eben einen), der einfach von vorne bis hinten sequentiell durchgeht.

    [*] Die for Schleife ist ja schon ziemlich umfangreich, trotz auto ... kann man das irgendwie eleganter/kürzer machen?

    Das findest du umfangreich? Du kannst das ++ stattdessen in die Rechnung ziehen, dann eben als Postfix.

    [*] Kann man foo nicht einfach das Ergebnis zurückgeben lassen? Also hier einen vector<int> , anstatt einen Rückgabeparameter verwenden zu müssen? Das fände ich auch übersichtlicher...

    Damit wäre doch der ganze Sinn der Iteratoren futsch. Das kann richtig sein, wenn nur vector<int> als Container Sinn macht. Da deine Funktion nur ein abstraktes Beispiel ist, ist das nicht zu beantworten. Aber wenn du Iteratoren nutzt, macht es kaum Sinn, einen konkreten Containertyp vorzugeben.

    Du scheinst den Sinn und die Möglichkeiten des Iteratorkonzepts nicht verstanden zu haben.

    edit: (Zu spät)²



  • SeppJ schrieb:

    Du scheinst den Sinn und die Möglichkeiten des Iteratorkonzepts nicht verstanden zu haben.

    Naja, Sinn ist halt über einen beliebigen container iterieren zu können, oder? Ich dachte halt der Compiler könnte sich ja vielleicht aufgrund des Funktionsaufrufs erschließen dass die übergebenen iteratoren vom Typ std::vector<int>::iterator sind, dann könnte man ja den entsprechenden container auch erstellen. Ist aber ja anscheinend nicht so 😃

    [quote="SeppJ"]Dafür müsste man konkreter wissen, was die Funktion macht. Ist jedenfalls verdächtig, dass sie überhaupt 1D und 2D mit dem gleichen Code bearbeiten kann. Klingt so, als wäre der Algorithmus rein 1D. In dem Fall interessiert die Funktion doch gar nicht, wenn da ein 2D-Container hinter den Iteratoren steht. Und der 2D-Container bietet doch sicher auch einen Iterator (oder du schreibst dir eben einen), der einfach von vorne bis hinten sequentiell durchgeht.[quote]

    Naja, es ist ein physikalisches System, bei dem man die Anzahl der inputs und ouputs konfigurieren kann. Demensprechend soll/muss es mit dem SISO (Single-Input, Single-Output), MISO (Multiple-Input, Single-Output), SIMO und MIMO Fall klarkommen. Mathematisch betrachtet ist ein Input einfach ein Vektor, mehrere Inputs dementsprechend eine Matrix. Mit std::vector würde das zum Beispiel etwa so aussehen:

    int main()
    {
    	std::vector<int> in1 = { 1, 2, 3, 4, 5 };
    	std::vector<int> in2 = { 2, 3, 7, 8, 9 };
    	std::vector<std::vector<int>> inputs = { in1, in2 };
    
    	std::vector<std::vector<int>> outputs = system.do_something(inputs);
    }
    

    Dabei gibt es eben auch den/die Spezialfälle dass inputs oder/und outputs nur einen vector beinhalten. Das würde ich jetzt gerne durch Iteratoren ersetzen um die Algorithmen vom container typ zu entkoppeln.


  • Mod

    Sag mal mehr über do_something. Wie sehen deine 4 Fälle aus? Schreib es mal mit std::vector auf. Die konkrete Rechnung brauchst du nicht zeigen, aber zeig ein Grundgerüst von do_something, welches zeigt, welche Werte mit welchen anderen Werten verrechnet werden (sofern dies überhaupt der Fall ist).

    P.S: Versuch auch unnötige Begriffe zu vermeiden, die nichts zum Inhalt beitragen. Beispielsweise: Was bringt es uns zu wissen, dass es sich um ein "physikalisches System" handelt? Das scheint nirgendwo relevant. Und ich kann mir auch nicht vorstellen, wie solch ein schwammiger Begriff irgendwie relevant werden könnte.



  • SeppJ schrieb:

    Sag mal mehr über do_something. Wie sehen deine 4 Fälle aus? Schreib es mal mit std::vector auf. Die konkrete Rechnung brauchst du nicht zeigen, aber zeig ein Grundgerüst von do_something, welches zeigt, welche Werte mit welchen anderen Werten verrechnet werden (sofern dies überhaupt der Fall ist).

    Ok, hier ein konstruiertes Minimal-Beispiel:

    class physical_system
    {
    private:
    	int get_safe(std::vector<int> const &vec, size_t index)
    	{
    		if (index < 0 || index >= vec.size())
    			return 0;
    		return vec[index];
    	}
    
    public:
    	std::vector<std::vector<int>> do_something(std::vector<std::vector<int>> const &inputs)
    	{
    		if (inputs.size() != 3) // System mit 3 inputs und 2 outputs
    			throw("Error");
    
    		std::vector<int> out_1;
    		std::vector<int> out_2;
    
    		for (size_t i = 0; i < inputs.front().size(); i++) {
    			out_1.push_back(inputs[0][i] + get_safe(inputs[1], i - 1) + inputs[2][i]*inputs[0][i]);
    			out_2.push_back(out_1.back() + get_safe(inputs[1], i - 2));
    		}
    		std::vector<std::vector<int>> outputs = { out_1, out_2 };
    		return outputs;
    	}
    };
    
    int main()
    {
    	std::vector<int> in1 = { 1, 2, 3, 4, 5 };
    	std::vector<int> in2 = { 1, 2, 3, 4, 5 };
    	std::vector<int> in3 = { 1, 2, 3, 4, 5 };
    	std::vector<std::vector<int>> inputs = { in1, in2, in3 };
    
    	physical_system system;
    	std::vector<std::vector<int>> outputs = system.do_something(inputs);
    }
    

    Prinzipiell werden alle inputs miteinander verrechnet, das ist jetzt ein Beispiel mit 3 inputs und 2 outputs. Bei 1 input und 1 output würde das quasi genauso aussehen nur halt mit einer etwas anderen Rechnung in der for Schleife, die dann halt nur inputs[0] benutzen würde.


  • Mod

    Da ist jetzt ja hardcoded, dass es sich um ein System mit 3 inputs und 2 outputs handeln soll. Wenn du das alles in eine Funktion mit Iteratoren packen möchtest, dann muss es zunächst einmal überhaupt möglich sein, alle Situationen in einer Funktion abhandeln zu können (egal ob mit Iterator oder vector).

    Mir fällt an dieser Stelle auch auf, dass deine (inneren) Vectoren immer alle gleich groß sind (damit meine ich nicht, dass sie in allen Beispielen 5 Elemente groß sind, sondern dass alle vectoren in einem Beispiel jeweils gleich groß sind). Ist das ein Zufall oder Absicht? Falls Absicht, dann zweifle ich mal die Wahl von vector<vector> als Datentyp an. vector<vector<int>> ist dafür da, um Listen dieser Art zu speichern:

    1, 2, 3 ,4
    1, 2, 3
    1, 2, 3, 4, 5, 6
    1, 2
    

    Für Matrizen kann man spezialisiertere Strukturen benutzen, bei denen man nicht die Kosten für die Flexibilität des vectors bezahlt. Du sprichst von Matrizen. Falls damit wirklich mathematische Matrizen gemeint sind, dann steht doch von vornherein fest, dass der einzig sinnvolle Datentyp irgendein Matrixtyp ist und die Abstraktion mittels Iteratoren wäre reiner Selbstzweck. Iteratoren sind gut für allgemeine, wiederverwendbare Algorithmen.



  • index < 0 kann nie erfüllt sein weil size_t unsigned ist. Ein Compiler sollte das anmerken.



  • nwp3 schrieb:

    index < 0 kann nie erfüllt sein weil size_t unsigned ist. Ein Compiler sollte das anmerken.

    Ja, war nur schnell als Beispiel geschrieben 😉

    SeppJ schrieb:

    Mir fällt an dieser Stelle auch auf, dass deine (inneren) Vectoren immer alle gleich groß sind (damit meine ich nicht, dass sie in allen Beispielen 5 Elemente groß sind, sondern dass alle vectoren in einem Beispiel jeweils gleich groß sind). Ist das ein Zufall oder Absicht? Falls Absicht, dann zweifle ich mal die Wahl von vector<vector> als Datentyp an.

    Das ist richtig, in echt verwende ich auch eine Matrix Klasse und keinen vector<vector<T>>. Wollte das Beispiel nicht mit sowas überladen.

    SeppJ schrieb:

    Falls damit wirklich mathematische Matrizen gemeint sind, dann steht doch von vornherein fest, dass der einzig sinnvolle Datentyp irgendein Matrixtyp ist und die Abstraktion mittels Iteratoren wäre reiner Selbstzweck. Iteratoren sind gut für allgemeine, wiederverwendbare Algorithmen.

    Ok, also wie soll ich das verstehen... es macht nur für 1-Dimensionale Datenstrukturen Sinn Iteratoren zu verwenden? Wieso ist dieses Konzept nicht auf den 2D Fall übertragbar? Weil ich könnte ja auch ein 2D-Array oder eben doch einen vector<vector<T>> übergeben wollen, oder?


  • Mod

    happystudent schrieb:

    Ok, also wie soll ich das verstehen... es macht nur für 1-Dimensionale Datenstrukturen Sinn Iteratoren zu verwenden?

    Jain. So war das nicht gemeint. Kommt eben drauf an, was ein Algorithmus überhaupt machen soll.

    Wieso ist dieses Konzept nicht auf den 2D Fall übertragbar? Weil ich könnte ja auch ein 2D-Array oder eben doch einen vector<vector<T>> übergeben wollen, oder?

    Ich habe nicht gesagt, dass es nicht möglich ist, aber es steht deiner Beschreibung nach doch schon im Vorhinein fest, dass hier ein bestimmter Matrixtyp zur Anwendung kommt. Schon so Sachen wie dein get_safe oder dein if(size != 3) deuten da drauf hin, dass hier ganz bestimmte Datentypen erwartet werden (und vector<vector> ist es offensichtlich nicht), die ganz bestimmte Anforderungen erfüllen müssen. Ich sehe irgendwie nicht den Sinn, hier abstrakter zu werden. Dies sieht nicht aus wie ein allgemeiner, wieder benutzbarer Algorithmus.

    Falls du das trotzdem unbedingt mit Iteratoren machen möchtest:
    Erste Herausforderung ist, wie schon gesagt wurde, erst einmal die Funktion so zu schreiben, dass du nicht alle Fälle hardcoded hast. Derzeit sieht dein Vorhaben ein wenig so aus, als würdest du eine Sinusfunktion wie folgt schreiben:

    template <typename InputIterator, typename OutputIterator> void sin(InputIterator begin, InputIterator end, OutputIterator out)
    {
      assert(std::distance(begin, end) == 1);
      // ...
    }
    

    Möglich? Ja.
    Sinnvoll? Dieses Beispiel offensichtlich nicht. Deine Problemstellung hat mich bisher auch nicht überzeugt.



  • Hm ok, das klingt logisch. Ich werde das mit den Iteratoren nochmal überdenken, ich dachte halt man sollte quasi immer Iteratoren verwenden^^

    Danke auf jeden Fall für die Antworten 👍


Log in to reply