C ++ 11 Reverse Range-basierte For-Loop

321

Gibt es einen Containeradapter, der die Richtung der Iteratoren umkehrt, damit ich mit einer bereichsbasierten for-Schleife in umgekehrter Reihenfolge über einen Container iterieren kann?

Mit expliziten Iteratoren würde ich Folgendes konvertieren:

for (auto i = c.begin(); i != c.end(); ++i) { ...

das sehr gut finden:

for (auto i = c.rbegin(); i != c.rend(); ++i) { ...

Ich möchte dies konvertieren:

for (auto& i: c) { ...

dazu:

for (auto& i: std::magic_reverse_adapter(c)) { ...

Gibt es so etwas oder muss ich es selbst schreiben?

Alex B.
quelle
17
Ein Reverse-Container-Adapter klingt interessant, aber ich denke, Sie müssen ihn selbst schreiben. Wir hätten dieses Problem nicht, wenn sich das Standardkomitee beeilen und bereichsbasierte Algorithmen anstelle expliziter Iteratoren anpassen würde.
Deft_code
4
@deft_code: "statt?" Warum sollten Sie iteratorbasierte Algorithmen loswerden wollen? Sie sind viel besser und weniger ausführlich für Fälle, in denen Sie nicht von beginbis iterieren end, oder für den Umgang mit Stream-Iteratoren und dergleichen. Bereichsalgorithmen wären großartig, aber sie sind wirklich nur syntaktischer Zucker (mit Ausnahme der Möglichkeit einer verzögerten Bewertung) gegenüber Iteratoralgorithmen.
Nicol Bolas
17
@deft_code template<typename T> class reverse_adapter { public: reverse_adapter(T& c) : c(c) { } typename T::reverse_iterator begin() { return c.rbegin(); } typename T::reverse_iterator end() { return c.rend(); } private: T& c; };Es kann verbessert werden (Hinzufügen von constVersionen usw.), aber es funktioniert: vector<int> v {1, 2, 3}; reverse_adapter<decltype(v)> ra; for (auto& i : ra) cout << i;Drucke321
Seth Carnegie
10
@ SethCarnegie: Und um eine schöne funktionale Form hinzuzufügen: template<typename T> reverse_adapter<T> reverse_adapt_container(T &c) {return reverse_adapter<T>(c);}Dann können Sie einfach for(auto &i: reverse_adapt_container(v)) cout << i;zum Iterieren verwenden.
Nicol Bolas
2
@CR: Ich denke nicht, dass es das bedeuten sollte , weil das es als prägnante Syntax für Schleifen, bei denen die Reihenfolge eine Rolle spielt, nicht verfügbar machen würde. IMO ist die Prägnanz wichtiger / nützlicher als Ihre semantische Bedeutung, aber wenn Sie die Prägnanz von c nicht schätzen, kann Ihr Styleguide sie beliebig implizieren. Das ist parallel_forgenau das, wofür es wäre, mit einer noch stärkeren Bedingung "Es ist mir egal, welche Reihenfolge", wenn es in irgendeiner Form in den Standard aufgenommen würde. Natürlich könnte es auch einen Range-basierten syntaktischen Zucker geben :-)
Steve Jessop

Antworten:

230

Eigentlich hat Boost einen solchen Adapter : boost::adaptors::reverse.

#include <list>
#include <iostream>
#include <boost/range/adaptor/reversed.hpp>

int main()
{
    std::list<int> x { 2, 3, 5, 7, 11, 13, 17, 19 };
    for (auto i : boost::adaptors::reverse(x))
        std::cout << i << '\n';
    for (auto i : x)
        std::cout << i << '\n';
}
kennytm
quelle
90

Tatsächlich kann dies in C ++ 14 mit sehr wenigen Codezeilen durchgeführt werden.

Dies ist eine sehr ähnliche Idee wie die Lösung von @ Paul. Aufgrund von Dingen, die in C ++ 11 fehlen, ist diese Lösung etwas unnötig aufgebläht (plus Definition in Standardgerüchen). Dank C ++ 14 können wir es viel lesbarer machen.

Die wichtigste Beobachtung ist, dass bereichsbasierte for-Schleifen funktionieren, indem sie sich auf die Iteratoren des Bereichs verlassen begin()und diese end()erfassen. Dank ADL muss man nicht einmal ihre benutzerdefinierten begin()und definierenend() im std :: Namespace definieren.

Hier ist eine sehr einfache Beispiellösung:

// -------------------------------------------------------------------
// --- Reversed iterable

template <typename T>
struct reversion_wrapper { T& iterable; };

template <typename T>
auto begin (reversion_wrapper<T> w) { return std::rbegin(w.iterable); }

template <typename T>
auto end (reversion_wrapper<T> w) { return std::rend(w.iterable); }

template <typename T>
reversion_wrapper<T> reverse (T&& iterable) { return { iterable }; }

Das funktioniert wie ein Zauber, zum Beispiel:

template <typename T>
void print_iterable (std::ostream& out, const T& iterable)
{
    for (auto&& element: iterable)
        out << element << ',';
    out << '\n';
}

int main (int, char**)
{
    using namespace std;

    // on prvalues
    print_iterable(cout, reverse(initializer_list<int> { 1, 2, 3, 4, }));

    // on const lvalue references
    const list<int> ints_list { 1, 2, 3, 4, };
    for (auto&& el: reverse(ints_list))
        cout << el << ',';
    cout << '\n';

    // on mutable lvalue references
    vector<int> ints_vec { 0, 0, 0, 0, };
    size_t i = 0;
    for (int& el: reverse(ints_vec))
        el += i++;
    print_iterable(cout, ints_vec);
    print_iterable(cout, reverse(ints_vec));

    return 0;
}

druckt wie erwartet

4,3,2,1,
4,3,2,1,
3,2,1,0,
0,1,2,3,

HINWEIS std::rbegin() , std::rend()und std::make_reverse_iterator()ist noch nicht in GCC-4.9 implementiert. Ich schreibe diese Beispiele gemäß dem Standard, aber sie würden nicht in stabilem g ++ kompiliert. Das Hinzufügen temporärer Stubs für diese drei Funktionen ist jedoch sehr einfach. Hier ist eine Beispielimplementierung, die definitiv nicht vollständig ist, aber in den meisten Fällen gut genug funktioniert:

// --------------------------------------------------
template <typename I>
reverse_iterator<I> make_reverse_iterator (I i)
{
    return std::reverse_iterator<I> { i };
}

// --------------------------------------------------
template <typename T>
auto rbegin (T& iterable)
{
    return make_reverse_iterator(iterable.end());
}

template <typename T>
auto rend (T& iterable)
{
    return make_reverse_iterator(iterable.begin());
}

// const container variants

template <typename T>
auto rbegin (const T& iterable)
{
    return make_reverse_iterator(iterable.end());
}

template <typename T>
auto rend (const T& iterable)
{
    return make_reverse_iterator(iterable.begin());
}
Prikso NAI
quelle
35
Wenige Codezeilen? Verzeih mir, aber das ist über zehn :-)
Jonny
4
Tatsächlich ist es 5-13, abhängig davon, wie Sie Zeilen zählen :) Die Workarounds sollten nicht vorhanden sein, da sie Teil der Bibliothek sind. Vielen Dank, dass Sie mich daran erinnert haben, dass diese Antwort für aktuelle Compilerversionen aktualisiert werden muss, bei denen nicht alle zusätzlichen Zeilen benötigt werden.
Prikso NAI
2
Ich denke, Sie haben forward<T>in Ihrer reverseImplementierung vergessen .
SnakE
3
Hm, wenn Sie dies in einen Header einfügen, befinden Sie sich using namespace stdin einem Header, was keine gute Idee ist. Oder fehlt mir etwas?
Estan
3
Eigentlich sollten Sie nicht "using <anything>;" schreiben. im Dateibereich in einem Header. Sie können das oben Gesagte verbessern, indem Sie die using-Deklarationen in den Funktionsbereich für begin () und end () verschieben.
Chris Hartman
23

Dies sollte in C ++ 11 ohne Boost funktionieren:

namespace std {
template<class T>
T begin(std::pair<T, T> p)
{
    return p.first;
}
template<class T>
T end(std::pair<T, T> p)
{
    return p.second;
}
}

template<class Iterator>
std::reverse_iterator<Iterator> make_reverse_iterator(Iterator it)
{
    return std::reverse_iterator<Iterator>(it);
}

template<class Range>
std::pair<std::reverse_iterator<decltype(begin(std::declval<Range>()))>, std::reverse_iterator<decltype(begin(std::declval<Range>()))>> make_reverse_range(Range&& r)
{
    return std::make_pair(make_reverse_iterator(begin(r)), make_reverse_iterator(end(r)));
}

for(auto x: make_reverse_range(r))
{
    ...
}
Paul Fultz II
quelle
58
IIRC, das dem Namespace std etwas hinzufügt, ist eine Einladung zum epischen Scheitern.
BCS
35
Ich bin mir nicht sicher über die normative Bedeutung von "epischem Fehler", aber das Überladen einer Funktion im stdNamespace hat gemäß 17.6.4.2.1 ein undefiniertes Verhalten.
Casey
9
Es ist in C ++ 14 anscheinend unter diesem Namen.
HostileFork sagt, vertraue SE
6
@ MuhammadAnnaqeeb Das Unglückliche ist, dass dies genau kollidiert. Sie können nicht mit beiden Definitionen kompilieren. Außerdem muss der Compiler nicht haben, dass die Definition unter C ++ 11 nicht vorhanden ist und nur unter C ++ 14 angezeigt wird (die Spezifikation sagt nichts darüber aus, was nicht im std :: -Namensraum enthalten ist, nur was ist). Dies wäre also ein sehr wahrscheinlicher Kompilierungsfehler unter einem standardkonformen C ++ 11-Compiler ... viel wahrscheinlicher als wenn es ein zufälliger Name wäre, der nicht in C ++ 14 enthalten wäre! Und wie bereits erwähnt, handelt es sich um "undefiniertes Verhalten". Das Nichtkompilieren ist also nicht das Schlimmste, was es tun könnte.
HostileFork sagt, vertraue SE
2
@HostileFork Es gibt keine Namenskollision, make_reverse_iteratorbefindet sich nicht im stdNamespace, sodass es nicht zu Konflikten mit der C ++ 14-Version kommt.
Paul Fultz II
11

Geht das für dich:

#include <iostream>
#include <list>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator_range.hpp>

int main(int argc, char* argv[]){

  typedef std::list<int> Nums;
  typedef Nums::iterator NumIt;
  typedef boost::range_reverse_iterator<Nums>::type RevNumIt;
  typedef boost::iterator_range<NumIt> irange_1;
  typedef boost::iterator_range<RevNumIt> irange_2;

  Nums n = {1, 2, 3, 4, 5, 6, 7, 8};
  irange_1 r1 = boost::make_iterator_range( boost::begin(n), boost::end(n) );
  irange_2 r2 = boost::make_iterator_range( boost::end(n), boost::begin(n) );


  // prints: 1 2 3 4 5 6 7 8 
  for(auto e : r1)
    std::cout << e << ' ';

  std::cout << std::endl;

  // prints: 8 7 6 5 4 3 2 1
  for(auto e : r2)
    std::cout << e << ' ';

  std::cout << std::endl;

  return 0;
}
Arlen
quelle
7
template <typename C>
struct reverse_wrapper {

    C & c_;
    reverse_wrapper(C & c) :  c_(c) {}

    typename C::reverse_iterator begin() {return c_.rbegin();}
    typename C::reverse_iterator end() {return c_.rend(); }
};

template <typename C, size_t N>
struct reverse_wrapper< C[N] >{

    C (&c_)[N];
    reverse_wrapper( C(&c)[N] ) : c_(c) {}

    typename std::reverse_iterator<const C *> begin() { return std::rbegin(c_); }
    typename std::reverse_iterator<const C *> end() { return std::rend(c_); }
};


template <typename C>
reverse_wrapper<C> r_wrap(C & c) {
    return reverse_wrapper<C>(c);
}

z.B:

int main(int argc, const char * argv[]) {
    std::vector<int> arr{1, 2, 3, 4, 5};
    int arr1[] = {1, 2, 3, 4, 5};

    for (auto i : r_wrap(arr)) {
        printf("%d ", i);
    }
    printf("\n");

    for (auto i : r_wrap(arr1)) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}
Khan Lau
quelle
1
Können Sie bitte Ihre Antwort näher erläutern?
Mostafiz
Dies ist eine Reverse Range-Base-Schleife C ++ 11 Klasse Tamplate
Khan Lau
4

Wenn Sie Range v3 verwenden können , können Sie den Reverse Range Adapter verwendenranges::view::reverse , mit dem Sie den Container in umgekehrter Reihenfolge anzeigen können.

Ein minimales Arbeitsbeispiel:

#include <iostream>
#include <vector>
#include <range/v3/view.hpp>

int main()
{
    std::vector<int> intVec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    for (auto const& e : ranges::view::reverse(intVec)) {
        std::cout << e << " ";   
    }
    std::cout << std::endl;

    for (auto const& e : intVec) {
        std::cout << e << " ";   
    }
    std::cout << std::endl;
}

Siehe DEMO 1 .

Hinweis: Laut Eric Niebler ist diese Funktion in C ++ 20 verfügbar . Dies kann mit dem <experimental/ranges/range>Header verwendet werden. Dann forsieht die Aussage folgendermaßen aus:

for (auto const& e : view::reverse(intVec)) {
       std::cout << e << " ";   
}

Siehe DEMO 2

PW
quelle
Update: Der ranges::viewNamespace wurde in umbenannt ranges::views. Also, benutze ranges::views::reverse.
nac001
2

Wenn ich C ++ 14 nicht benutze, finde ich unten die einfachste Lösung.

#define METHOD(NAME, ...) auto NAME __VA_ARGS__ -> decltype(m_T.r##NAME) { return m_T.r##NAME; }
template<typename T>
struct Reverse
{
  T& m_T;

  METHOD(begin());
  METHOD(end());
  METHOD(begin(), const);
  METHOD(end(), const);
};
#undef METHOD

template<typename T>
Reverse<T> MakeReverse (T& t) { return Reverse<T>{t}; }

Demo .
Es funktioniert nicht für Container / Datentypen (wie Array), die keine begin/rbegin, end/rendFunktionen haben.

iammilind
quelle
0

Sie können einfach verwenden, BOOST_REVERSE_FOREACHwas rückwärts iteriert. Zum Beispiel der Code

#include <iostream>
#include <boost\foreach.hpp>

int main()
{
    int integers[] = { 0, 1, 2, 3, 4 };
    BOOST_REVERSE_FOREACH(auto i, integers)
    {
        std::cout << i << std::endl;
    }
    return 0;
}

generiert die folgende Ausgabe:

4

3

2

1

0
Catriel
quelle