Boucle basée sur la plage inverse C ++ 11

321

Existe-t-il un adaptateur de conteneur qui inverserait la direction des itérateurs afin que je puisse itérer sur un conteneur en sens inverse avec une boucle basée sur une plage?

Avec des itérateurs explicites, je convertirais ceci:

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

en cela:

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

Je veux convertir ceci:

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

pour ça:

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

Existe-t-il une telle chose ou dois-je l'écrire moi-même?

Alex B
la source
17
Un adaptateur de conteneur inversé semble intéressant, mais je pense que vous devrez l'écrire vous-même. Nous n'aurions pas ce problème si le comité Standard se dépêchait et adaptait les algorithmes basés sur la plage au lieu d'itérateurs explicites.
deft_code
4
@deft_code: "au lieu de?" Pourquoi voudriez-vous vous débarrasser des algorithmes basés sur les itérateurs? Ils sont bien meilleurs et moins verbeux pour les cas où vous n'itérez pas de beginà endou pour traiter les itérateurs de flux et similaires. Les algorithmes de plage seraient formidables, mais ils ne sont vraiment que du sucre syntaxique (à l'exception de la possibilité d'une évaluation paresseuse) sur les algorithmes d'itérateur.
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; };Il peut être amélioré (ajout de constversions, etc.) mais cela fonctionne: vector<int> v {1, 2, 3}; reverse_adapter<decltype(v)> ra; for (auto& i : ra) cout << i;impressions321
Seth Carnegie
10
@SethCarnegie: Et pour ajouter une belle forme fonctionnelle: template<typename T> reverse_adapter<T> reverse_adapt_container(T &c) {return reverse_adapter<T>(c);}Donc, vous pouvez simplement utiliser for(auto &i: reverse_adapt_container(v)) cout << i;pour itérer.
Nicol Bolas
2
@CR: Je ne pense pas que cela devrait signifier cela, car cela le rendrait indisponible en tant que syntaxe concise pour les boucles où l'ordre est important. OMI, la concision est plus importante / utile que votre sens sémantique, mais si vous n'appréciez pas la concision de votre guide de style peut lui donner l'implication que vous voulez. C'est un peu ce à quoi cela parallel_forservirait, avec une condition encore plus stricte «Je me fiche de l'ordre», si elle était incorporée dans la norme sous une forme ou une autre. Bien sûr, il pourrait aussi avoir un sucre syntaxique basé sur la plage :-)
Steve Jessop

Réponses:

230

En fait , Boost avoir un tel adaptateur ne: 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
la source
91

En fait, en C ++ 14, cela peut être fait avec très peu de lignes de code.

C'est une idée très similaire à la solution de @ Paul. En raison de choses manquantes dans C ++ 11, cette solution est un peu gonflée (plus la définition des odeurs std). Grâce à C ++ 14, nous pouvons le rendre beaucoup plus lisible.

L'observation clé est que les boucles for basées sur la plage fonctionnent en s'appuyant sur begin()et end()pour acquérir les itérateurs de la plage. Grâce à ADL , on n'a même pas besoin de définir leur custom begin()et end()dans l'espace de noms std ::.

Voici une solution d'échantillon très simple:

// -------------------------------------------------------------------
// --- 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 }; }

Cela fonctionne comme un charme, par exemple:

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;
}

imprime comme prévu

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

NOTE std::rbegin() , std::rend()et std::make_reverse_iterator()ne sont pas encore implémentés dans GCC-4.9. J'écris ces exemples selon la norme, mais ils ne compileraient pas en g ++ stable. Néanmoins, l'ajout de stubs temporaires pour ces trois fonctions est très simple. Voici un exemple d'implémentation, certainement pas complet mais qui fonctionne assez bien dans la plupart des cas:

// --------------------------------------------------
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
la source
35
Quelques lignes de code? Pardonnez-moi, mais c'est plus de dix :-)
Jonny
4
En fait, c'est 5-13, selon la façon dont vous comptez les lignes:) Les solutions de contournement ne devraient pas être là, car elles font partie de la bibliothèque. Merci de me rappeler, btw, cette réponse doit être mise à jour pour les versions récentes du compilateur, où toutes les lignes supplémentaires ne sont pas nécessaires du tout.
Prikso NAI
2
Je pense que vous avez oublié forward<T>dans votre reverseimplémentation.
SnakE
3
Hm, si vous mettez cela dans un en-tête, vous êtes using namespace stddans un en-tête, ce qui n'est pas une bonne idée. Ou est-ce que je manque quelque chose?
estan
3
En fait, vous ne devriez pas écrire "en utilisant <n'importe quoi>;" à la portée du fichier dans un en-tête. Vous pouvez améliorer ce qui précède en déplaçant les déclarations using dans la portée de la fonction pour begin () et end ().
Chris Hartman
23

Cela devrait fonctionner en C ++ 11 sans boost:

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
la source
58
L'IIRC ajoutant quoi que ce soit à l'espace de noms std est une invitation à l'échec épique.
BCS
35
Je ne suis pas sûr de la signification normative de "échec épique", mais la surcharge d'une fonction dans l' stdespace de noms a un comportement indéfini selon 17.6.4.2.1.
Casey
9
C'est apparemment en C ++ 14 , sous ce nom.
HostileFork dit de ne pas faire confiance au SE
6
@MuhammadAnnaqeeb Le malheur est que cela se heurte exactement. Vous ne pouvez pas compiler avec les deux définitions. De plus le compilateur n'est pas nécessaire d'avoir la définition pas être présent en C ++ 11 et apparaissent uniquement sous C ++ 14 (la spécification ne dit rien sur ce qui est pas dans le std :: espace de noms, tout ce qui est). Donc, ce serait un échec de compilation très probable sous un compilateur C ++ 11 conforme aux normes ... beaucoup plus probable que si c'était un nom aléatoire qui n'était pas en C ++ 14! Et comme souligné, c'est un "comportement indéfini" ... donc ne pas compiler n'est pas la pire des choses.
HostileFork dit de ne pas faire confiance au SE
2
@HostileFork Il n'y a pas de collision de noms, make_reverse_iteratorn'est pas dans l' stdespace de noms, donc il ne se heurtera pas à sa version C ++ 14.
Paul Fultz II
11

Est-ce que ça marche pour toi:

#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
la source
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);
}

par exemple:

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
la source
1
pouvez-vous expliquer plus en détail votre réponse?
Mostafiz
ceci est un tamplate de classe C ++ 11 à boucle de base inversée
Khan Lau
4

Si vous pouvez utiliser la gamme v3 , vous pouvez utiliser l'adaptateur de plage inverse ranges::view::reversequi vous permet de visualiser le conteneur en sens inverse.

Un exemple de travail minimal:

#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;
}

Voir DEMO 1 .

Remarque: Selon Eric Niebler , cette fonctionnalité sera disponible en C ++ 20 . Cela peut être utilisé avec l'en- <experimental/ranges/range>tête. Ensuite, la fordéclaration ressemblera à ceci:

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

Voir DEMO 2

PW
la source
Mise à jour: l' ranges::viewespace de noms a été renommé ranges::views. Alors, utilisez ranges::views::reverse.
nac001
2

Si vous n'utilisez pas C ++ 14, je trouve ci-dessous la solution la plus simple.

#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}; }

Démo .
Cela ne fonctionne pas pour les conteneurs / types de données (comme le tableau), qui n'ont pas de begin/rbegin, end/rendfonctions.

iammilind
la source
0

Vous pouvez simplement utiliser BOOST_REVERSE_FOREACHce qui se répète en arrière. Par exemple, le 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;
}

génère la sortie suivante:

4

3

2

1

0
Catriel
la source