Iterando el vector C ++ desde el final hasta el principio

¿Es posible iterar un vector desde el final hasta el principio?

for (vector<my_class>::iterator i = my_vector.end();
        i != my_vector.begin(); /* ?! */ ) {
}

O es que solo es posible con algo así:

for (int i = my_vector.size() - 1; i >= 0; --i) {
}

La mejor forma es:

for (vector<my_class>::reverse_iterator i = my_vector.rbegin(); 
        i != my_vector.rend(); ++i ) { 
} 

rbegin()Fui rend()especialmente diseñado para ese propósito. (Y sí, incrementar a lo reverse_interatormueve hacia atrás).

Ahora, en teoría, su método (usando begin()/ end()& --i) funcionaría, std::vectorel iterador es bidireccional, pero recuerde, end()no es el último elemento, es uno más allá del último elemento, por lo que tendría que disminuir primero, y está terminado cuando llegue begin(), pero aún debe realizar el procesamiento.

vector<my_class>::iterator i = my_vector.end();
while (i != my_vector.begin())
{
     --i;
    /*do stuff */

} 

ACTUALIZACIÓN: Aparentemente fui demasiado agresivo al reescribir el for()bucle en un while()bucle. (La parte importante es que --iestá al principio).

Si tiene C ++ 11, puede hacer uso de auto.

for (auto it = my_vector.rbegin(); it != my_vector.rend(); ++it)
{
}

El "patrón" bien establecido para la iteración inversa a través de rangos cerrados-abiertos tiene el siguiente aspecto

// Iterate over [begin, end) range in reverse
for (iterator = end; iterator-- != begin; ) {
  // Process `*iterator`
}

o, si lo prefieres,

// Iterate over [begin, end) range in reverse
for (iterator = end; iterator != begin; ) {
  --iterator;
  // Process `*iterator`
}

Este patrón es útil, por ejemplo, para la indexación inversa de una matriz utilizando un índice sin signo

int array[N];
...
// Iterate over [0, N) range in reverse
for (unsigned i = N; i-- != 0; ) {
  array[i]; // <- process it
}

(Las personas no familiarizadas con este patrón menudo insiste en usar firmado entero tipos de indexación de matrices específicamente porque creen erróneamente que los tipos sin signo son de alguna manera "inservibles" para la indexación inversa)

Se puede utilizar para iterar sobre una matriz utilizando una técnica de "puntero deslizante".

// Iterate over [array, array + N) range in reverse
for (int *p = array + N; p-- != array; ) {
  *p; // <- process it
}

o se puede usar para la iteración inversa sobre un vector utilizando un iterador ordinario (no inverso)

for (vector<my_class>::iterator i = my_vector.end(); i-- != my_vector.begin(); ) {
  *i; // <- process it
}

Comenzando con c ++ 20, puede usar un std::ranges::reverse_viewy un bucle for basado en rango:

#include<ranges>
#include<vector>
#include<iostream>

using namespace std::ranges;

std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for(auto& i :  views::reverse(vec)) {
    std::cout << i << ",";
}

O incluso

for(auto& i :  vec | views::reverse)

Desafortunadamente, en el momento de escribir este artículo (enero de 2020), ningún compilador importante implementa la biblioteca de rangos, pero puede recurrir a los rangos-v3 de Eric Niebler :

#include <iostream>
#include <vector>
#include "range/v3/all.hpp"

int main() {

    using namespace ranges;

    std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(auto& i :  views::reverse(vec)) {
        std::cout << i << ",";
    }

    return 0;
}

rend() / rbegin()Iteradores de usuario :

for (vector<myclass>::reverse_iterator it = myvector.rbegin(); it != myvector.rend(); it++)

template<class It>
std::reverse_iterator<It> reversed( It it ) {
  return std::reverse_iterator<It>(std::forward<It>(it));
}

Luego:

for( auto rit = reversed(data.end()); rit != reversed(data.begin()); ++rit ) {
  std::cout << *rit;

Alternativamente en C ++ 14 simplemente haga:

for( auto rit = std::rbegin(data); rit != std::rend(data); ++rit ) {
  std::cout << *rit;

En C ++ 03/11 la mayoría de contenedores estándar tienen una .rbegin()y .rend()método también.

Finalmente, puede escribir el adaptador de rango de la backwardssiguiente manera:

namespace adl_aux {
  using std::begin; using std::end;
  template<class C>
  decltype( begin( std::declval<C>() ) ) adl_begin( C&& c ) {
    return begin(std::forward<C>(c));
  }
  template<class C>
  decltype( end( std::declval<C>() ) ) adl_end( C&& c ) {
    return end(std::forward<C>(c));
  }
}

template<class It>
struct simple_range {
  It b_, e_;
  simple_range():b_(),e_(){}
  It begin() const { return b_; }
  It end() const { return e_; }
  simple_range( It b, It e ):b_(b), e_(e) {}

  template<class OtherRange>
  simple_range( OtherRange&& o ):
    simple_range(adl_aux::adl_begin(o), adl_aux::adl_end(o))
  {}

  // explicit defaults:
  simple_range( simple_range const& o ) = default;
  simple_range( simple_range && o ) = default;
  simple_range& operator=( simple_range const& o ) = default;
  simple_range& operator=( simple_range && o ) = default;
};
template<class C>
simple_range< decltype( reversed( adl_aux::adl_begin( std::declval<C&>() ) ) ) >
backwards( C&& c ) {
  return { reversed( adl_aux::adl_end(c) ), reversed( adl_aux::adl_begin(c) ) };
}

y ahora puedes hacer esto:

for (auto&& x : backwards(ctnr))
  std::cout << x;

que creo que es bastante bonito.

Utilice iteradores inversos y recorra de rbegin()arend()

Aquí hay una implementación súper simple que permite el uso de para cada construcción y se basa solo en la biblioteca estándar C ++ 14:

namespace Details {

    // simple storage of a begin and end iterator
    template<class T>
    struct iterator_range
    {
        T beginning, ending;
        iterator_range(T beginning, T ending) : beginning(beginning), ending(ending) {}

        T begin() const { return beginning; }
        T end() const { return ending; }
    };

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// usage:
//  for (auto e : backwards(collection))
template<class T>
auto backwards(T & collection)
{
    using namespace std;
    return Details::iterator_range(rbegin(collection), rend(collection));
}

Esto funciona con cosas que proporcionan rbegin () y rend (), así como con matrices estáticas.

std::vector<int> collection{ 5, 9, 15, 22 };
for (auto e : backwards(collection))
    ;

long values[] = { 3, 6, 9, 12 };
for (auto e : backwards(values))
    ;

Si puede usar The Boost Library, existe Boost.Range que proporciona el reverseadaptador de rango al incluir:

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

Luego, en combinación con el forbucle de rango de C ++ 11 , puede escribir lo siguiente:

for (auto& elem: boost::adaptors::reverse(my_vector)) {
   // ...
}

Dado que este código es más breve que el que usa el par de iteradores, puede ser más legible y menos propenso a errores, ya que hay menos detalles a los que prestar atención.

Me gusta el iterador al revés al final de Yakk: la respuesta de Adam Nevraumont, pero parecía complicado para lo que necesitaba, así que escribí esto:

template <class T>
class backwards {
    T& _obj;
public:
    backwards(T &obj) : _obj(obj) {}
    auto begin() {return _obj.rbegin();}
    auto end() {return _obj.rend();}
};

Puedo tomar un iterador normal como este:

for (auto &elem : vec) {
    // ... my useful code
}

y cámbielo a esto para iterar al revés:

for (auto &elem : backwards(vec)) {
    // ... my useful code
}

usa este código

//print the vector element in reverse order by normal iterator.
cout <<"print the vector element in reverse order by normal iterator." <<endl;
vector<string>::iterator iter=vec.end();
--iter;
while (iter != vec.begin())
{
    cout << *iter  << " "; 
    --iter;
}

Como no quiero introducir una nueva sintaxis de C ++ similar a la de un alienígena, y simplemente quiero construir sobre las primitivas existentes, los siguientes fragmentos parecen funcionar:

#include <vector>
#include <iostream>

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

    // iterate forward
    for (it = arr.begin(); it != arr.end(); it++) {
        std::cout << *it << " ";
    }

    std::cout << "\n************\n";
 
    if (arr.size() > 0) {
        // iterate backward, simple Joe version
        it = arr.end() - 1;
        while (it != arr.begin()) {
            std::cout << *it << " ";
            it--;
        }
        std::cout << *it << " ";
    } 

    // iterate backwards, the C++ way
    std::vector<int>::reverse_iterator rit;
    for (rit = arr.rbegin(); rit != arr.rend(); rit++) {
        std::cout << *rit << " ";
    }

    return 0;
}