Werbung

  1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

[C++ Quicktip] Iterieren in Zweierpärchen

Über konsekutive Paare in einem Container iterieren.

  1. -AB-
    Programmiersprache(n):
    C++
    Und wieder ein winziger Quicktip - da Iterieren in verschiedenen Varianten wohl meine Kernkompetenz ist, ist das auch heute mal wieder Thema :)

    Es geht 1) um folgendes: Angenommen, ich habe einen Container mit Elementen, aber eigentlich interessiert mich, was *zwischen* diesen Elementen ist - sagen wir, ich interessiere mich für die jeweilige Differenz (diskrete Ableitung) einer Reihe von Zahlen:

    Code (C++):
    Quelltext kopieren
    1. std::vector<int> data = {1, 6, 4, 8, 3, 9, 12};
    Der für uns interessante Fall könnte jetzt sein, dass zwei aufeinanderfolgende Elemente eine Differenz von >5 haben.

    std::for_each oder std::accumulate hilft uns hier nicht weiter, wir müssen eine Schleife schreiben:

    Code (C++):
    Quelltext kopieren
    1. //variant: skip first element
    2. for(std::size_t i = 1; i<data.size();++i)
    3. {
    4.     if(abs(data[i] - data[i-1]) > 5)
    5.         //interesting case!
    6.     //...
    7. }
    Oder, wenn man keinen random access hat:
    Code (C++):
    Quelltext kopieren
    1. auto iter = data.begin();
    2. const auto end = data.end();
    3. while(iter != end)
    4. {
    5.     auto prev = iter++;
    6.     if(iter != end)
    7.     {
    8.         if(abs(*iter - *prev) > 5)
    9.             //interesting case!
    10.     }
    11. }
    Beide Schleifen dienen grad nur der Demonstration. Etwaige Fehler verdeutlichen nur, wie schnell man hier einen one-off Error einbauen kann, den Fall "leeres Set" oder "nur ein Element" kann man auch vergessen, usw.

    Also doch lieber eine Funktion, die genau das tut, was wir wollen:
    Code (C++):
    Quelltext kopieren
    1. std::vector<int> data = {1, 6, 4, 8, 3, 9, 12};
    2.  
    3. for_each_overlapping_pair(data.begin(), data.end(),
    4.                             [](int a, int b)
    5.                             {
    6.                                 if(abs(a - b) > 5)
    7.                                     //interesting case!
    8.                             }
    9.                           );
    Fehlerpotential ist praktisch auf 0 gesunken, man kann die Funktion kaum falsch bedienen - auch die Bedeutung ist gleich viel klarer, man will nicht einfach nur irgendwie iterieren und irgendwelche Elemente vergleichen, sondern interessiert sich immer nur für (a, b)-Pärchen. Die Parameter des Lambdas (oder übergebener Funktion) geben auch gleich an, ob die Elemente eventuell verändert werden - oder ob sie eher const sind.

    Eine Funktion dieser Art hätte ich vor ein paar Jahren mal gebraucht, als ich über Streckenabschnitte zwischen Wegpunkten iteriert habe. Der Code war schon kompliziert genug, dann zusätzlich noch Schleifenbedingungen zu bedenken musste nicht sein...

    Dieses war der erste Streich, der andere Fall 2) ist der, wenn wir hintereinander jeweils 2 zueinander passende Elemente in einem Container haben, also z.B. begin/end-Pärchen oder untere und obere Grenzen für numerische Reihen, ... Eigentlich ein Designfehler, und man sollte die zueinander gehörenden Objekte z.B. in ein std::pair stecken, aber die Möglichkeit hat man ja nicht immer.

    Code könnte z.B. so aussehen:
    Code (C++):
    Quelltext kopieren
    1. std::vector<int> data = {1, 6, 4};
    2. std::vector<int> moreData = {3, 4, 5};
    3.  
    4. std::vector<std::vector<int>::iterator> concat = {data.begin(), data.end(), moreData.begin(), moreData.end()};
    5.  
    6. for_each_pair(concat.begin(), concat.end(),
    7.                         [](auto begin, auto end)
    8.                         {
    9.                             std::for_each(begin, end, [](auto obj){std::cout << obj;});
    10.                         }
    11.                     );
    Ist natürlich bisschen aus der Luft gegriffen, wie gesagt: eigentlich sollte man solchen Code refactoren und die beiden zueinander gehörenden Elemente auch in eine Datenstruktur packen. Aber da ich den anderen Fall schon hatte, hab ich auch gleich diese Funktion geschrieben.

    Implementation gibts natürlich auch:
    Code (C++):
    Quelltext kopieren
    1. #include <iterator>
    2.  
    3. ///iterates over a container, calls an arbitrary action with each 2 consecutive (but not overlapping) elements, {1, 2, 3, 4} -> {1, 2}, {3, 4}
    4. template <typename ForwardIterator, typename Action>
    5. typename std::enable_if<std::is_base_of<std::forward_iterator_tag, typename ForwardIterator::iterator_category>::value, Action>::type
    6. for_each_pair(ForwardIterator first, ForwardIterator last, Action action)
    7. {
    8.     while(first != last)
    9.     {
    10.         ForwardIterator second{first};
    11.         ++second;
    12.  
    13.         if(second != last)
    14.             action(*first, *second);
    15.         else
    16.             break;
    17.  
    18.         first = ++second;
    19.     }
    20.  
    21.     return std::move(action);
    22. }
    23.  
    24. ///iterates over a container, calls an arbitrary action with each 2 consecutive (including overlapping) elements, {1, 2, 3, 4} -> {1, 2}, {2, 3}, {3, 4}
    25. template <typename ForwardIterator, typename Action>
    26. typename std::enable_if<std::is_base_of<std::forward_iterator_tag, typename ForwardIterator::iterator_category>::value, Action>::type
    27. for_each_overlapping_pair(ForwardIterator first, ForwardIterator last, Action action)
    28. {
    29.     if(first != last)
    30.     {
    31.         ForwardIterator second{first};
    32.         ++second;
    33.  
    34.         while(second != last)
    35.         {
    36.             action(*first, *second);
    37.  
    38.             first = second;
    39.             ++second;
    40.         }
    41.     }
    42.  
    43.     return std::move(action);
    44. }

    Bei Fragen, Verbesserungsvorschlägen, oder zum munteren Plaudern: Oben auf "Diskussion" gehen und sich einfach mal alles von der Seele schreiben :)