¿Cuál es la mejor manera de iterar sobre dos o más contenedores simultáneamente?

114

C ++ 11 proporciona varias formas de iterar sobre contenedores. Por ejemplo:

Bucle basado en rango

for(auto c : container) fun(c)

std :: for_each

for_each(container.begin(),container.end(),fun)

Sin embargo, ¿cuál es la forma recomendada de iterar sobre dos (o más) contenedores del mismo tamaño para lograr algo como:

for(unsigned i = 0; i < containerA.size(); ++i) {
  containerA[i] = containerB[i];
}
memecs
fuente
1
¿qué pasa con el transformpresente en #include <algorithm>?
Ankit Acharya
Acerca del ciclo de asignación: si ambos son vectores o similares, utilícelos en containerA = containerB;lugar del ciclo.
emlai
Una pregunta similar: stackoverflow.com/questions/8511035/…
knedlsepp
1
¿Posible duplicado de la función Sequence-zip para c ++ 11?
underscore_d

Respuestas:

53

Bastante tarde para la fiesta. Pero: iteraría sobre índices. Pero no con el forciclo clásico, sino con un forciclo basado en rangos sobre los índices:

for(unsigned i : indices(containerA)) {
    containerA[i] = containerB[i];
}

indiceses una función contenedora simple que devuelve un rango (evaluado con pereza) para los índices. Dado que la implementación, aunque simple, es demasiado larga para publicarla aquí, puede encontrar una implementación en GitHub .

Este código es tan eficiente como usar un forbucle clásico manual .

Si este patrón ocurre con frecuencia en sus datos, considere usar otro patrón que tenga zipdos secuencias y produzca un rango de tuplas, correspondientes a los elementos emparejados:

for (auto& [a, b] : zip(containerA, containerB)) {
    a = b;
}

La implementación de zipse deja como un ejercicio para el lector, pero se deriva fácilmente de la implementación de indices.

(Antes de C ++ 17, tendría que escribir lo siguiente :)

for (auto items&& : zip(containerA, containerB))
    get<0>(items) = get<1>(items);
Konrad Rudolph
fuente
2
¿Hay alguna ventaja de la implementación de sus índices en comparación con boost counting_range? Uno podría simplemente usarboost::counting_range(size_t(0), containerA.size())
SebastianK
3
@SebastianK La mayor diferencia en este caso es la sintaxis: la mía es (afirmo) objetivamente mejor de usar en este caso. Además, puede especificar un tamaño de paso. Consulte la página de Github vinculada, y en particular el archivo README, para ver ejemplos.
Konrad Rudolph
Su idea es muy buena y se me ocurrió el uso de countting_range solo después de verlo: clear upvote :) Sin embargo, me pregunto si proporciona un valor adicional para (re) implementar esto. Por ejemplo, en cuanto al rendimiento. Por supuesto, estoy de acuerdo con una sintaxis más agradable, pero sería suficiente escribir una función de generador simple para compensar este inconveniente.
SebastianK
@SebastianK Admito que cuando escribí el código lo consideré lo suficientemente simple como para vivir aislado sin usar una biblioteca (¡y lo es!). Ahora probablemente lo escribiría como un envoltorio alrededor de Boost.Range. Dicho esto, el rendimiento de mi biblioteca ya es óptimo. Lo que quiero decir con esto es que el uso de mi indicesimplementación produce un resultado del compilador que es idéntico al uso de forbucles manuales . No hay gastos generales de ningún tipo.
Konrad Rudolph
Como utilizo boost de todos modos, sería más simple en mi caso. Ya escribí esta envoltura sobre el rango de impulso: todo lo que necesito es una función con una línea de código. Sin embargo, me interesaría si el rendimiento de los rangos de impulso también es óptimo.
SebastianK
38

Para su ejemplo específico, solo use

std::copy_n(contB.begin(), contA.size(), contA.begin())

Para el caso más general, puede usar Boost.Iterator's zip_iterator, con una pequeña función para hacerlo utilizable en bucles for basados ​​en rangos. En la mayoría de los casos, esto funcionará:

template<class... Conts>
auto zip_range(Conts&... conts)
  -> decltype(boost::make_iterator_range(
  boost::make_zip_iterator(boost::make_tuple(conts.begin()...)),
  boost::make_zip_iterator(boost::make_tuple(conts.end()...))))
{
  return {boost::make_zip_iterator(boost::make_tuple(conts.begin()...)),
          boost::make_zip_iterator(boost::make_tuple(conts.end()...))};
}

// ...
for(auto&& t : zip_range(contA, contB))
  std::cout << t.get<0>() << " : " << t.get<1>() << "\n";

Ejemplo vivo.

Sin embargo, para la generalidad en toda regla, es probable que desee algo más parecido a este , que funcionará correctamente para las matrices y tipos definidos por el usuario que no tienen miembros begin()/ end()pero no tienen begin/ endfunciones en su espacio de nombres. Además, esto permitirá al usuario obtener constacceso específicamente a través de las zip_c...funciones.

Y si eres un defensor de los mensajes de error agradables, como yo, entonces probablemente quieras esto , que verifica si se pasaron contenedores temporales a alguna de las zip_...funciones e imprime un mensaje de error agradable si es así.

Xeo
fuente
1
¡Gracias! Sin embargo, una pregunta, ¿por qué usa auto &&, qué significa &&?
memecs
@memecs: Recomiendo leer esta pregunta , así como esta respuesta mía, que explica un poco cómo se realiza la deducción y el colapso de referencias. Tenga en cuenta que autofunciona exactamente igual que un parámetro de plantilla, y T&&en una plantilla es una referencia universal como se explica en el primer enlace, por auto&& v = 42lo que se deducirá como int&&y auto&& w = v;luego se deducirá como int&. Le permite hacer coincidir lvalues ​​así como rvalues ​​y dejar que ambos sean mutables, sin hacer una copia.
Xeo
@Xeo: ¿Pero cuál es la ventaja de auto && sobre auto & en un bucle foreach?
Viktor Sehr
@ViktorSehr: te permite enlazar elementos temporales, como los producidos por zip_range.
Xeo
23
@Xeo Todos los enlaces a los ejemplos están rotos.
kynan
34

me pregunto por qué nadie mencionó esto:

auto ItA = VectorA.begin();
auto ItB = VectorB.begin();

while(ItA != VectorA.end() || ItB != VectorB.end())
{
    if(ItA != VectorA.end())
    {
        ++ItA;
    }
    if(ItB != VectorB.end())
    {
        ++ItB;
    }
}

PD: si los tamaños del contenedor no coinciden, entonces tendrá que poner el código dentro de las declaraciones if.

Joseph
fuente
9

Hay muchas formas de hacer cosas específicas con varios contenedores, como se indica en el algorithmencabezado. Por ejemplo, en el ejemplo que ha dado, podría usar en std::copylugar de un bucle for explícito.

Por otro lado, no hay ninguna forma incorporada de iterar genéricamente varios contenedores que no sea un bucle for normal. Esto no es sorprendente porque hay muchas formas de iterar. Piense en ello: podría iterar a través de un contenedor con un paso, un contenedor con otro paso; o a través de un recipiente hasta que llegue al final y luego comience a insertar mientras pasa hasta el final del otro recipiente; o un paso del primer recipiente por cada vez que pasa completamente por el otro recipiente y luego comienza de nuevo; o algún otro patrón; o más de dos contenedores a la vez; etc ...

Sin embargo, si quisiera crear su propia función de estilo "for_each" que recorra en iteración dos contenedores solo hasta la longitud del más corto, puede hacer algo como esto:

template <typename Container1, typename Container2>
void custom_for_each(
  Container1 &c1,
  Container2 &c2,
  std::function<void(Container1::iterator &it1, Container2::iterator &it2)> f)
{
  Container1::iterator begin1 = c1.begin();
  Container2::iterator begin2 = c2.begin();
  Container1::iterator end1 = c1.end();
  Container2::iterator end2 = c2.end();
  Container1::iterator i1;
  Container1::iterator i2;
  for (i1 = begin1, i2 = begin2; (i1 != end1) && (i2 != end2); ++it1, ++i2) {
    f(i1, i2);
  }
}

Obviamente puedes realizar cualquier tipo de estrategia de iteraciones que desees de forma similar.

Por supuesto, podría argumentar que simplemente hacer el bucle for interno directamente es más fácil que escribir una función personalizada como esta ... y tendría razón, si solo lo va a hacer una o dos veces. Pero lo bueno es que es muy reutilizable. =)

wjl
fuente
¿Parece que tienes que declarar los iteradores antes del ciclo? Intenté esto: for (Container1::iterator i1 = c1.begin(), Container2::iterator i2 = c2.begin(); (i1 != end1) && (i2 != end2); ++it1, ++i2)pero el compilador grita. ¿Alguien puede explicar por qué esto no es válido?
David Doria
@DavidDoria La primera parte del bucle for es una sola declaración. No puede declarar dos variables de diferentes tipos en la misma declaración. Piense por qué for (int x = 0, y = 0; ...funciona, pero for (int x = 0, double y = 0; ...)no.
wjl
1
.. puede, sin embargo, tener std :: pair <Container1 :: iterator, Container2 :: iterator> its = {c1.begin (), c2.begin ()};
lorro
1
Otra cosa a tener en cuenta es que esto podría hacerse fácilmente variable con C ++ 14typename...
wjl
8

En caso de que necesite iterar simultáneamente sobre 2 contenedores solamente, existe una versión extendida del algoritmo estándar for_each en la biblioteca de rango de impulso, por ejemplo:

#include <vector>
#include <boost/assign/list_of.hpp>
#include <boost/bind.hpp>
#include <boost/range/algorithm_ext/for_each.hpp>

void foo(int a, int& b)
{
    b = a + 1;
}

int main()
{
    std::vector<int> contA = boost::assign::list_of(4)(3)(5)(2);
    std::vector<int> contB(contA.size(), 0);

    boost::for_each(contA, contB, boost::bind(&foo, _1, _2));
    // contB will be now 5,4,6,3
    //...
    return 0;
}

Cuando necesita manejar más de 2 contenedores en un algoritmo, entonces necesita jugar con zip.

czarles
fuente
¡Maravilloso! ¿Como lo encontraste? Parece que no está documentado en ninguna parte.
Mikhail
4

otra solución podría ser capturar una referencia del iterador del otro contenedor en una lambda y usar el operador de incremento posterior en eso. por ejemplo, una copia simple sería:

vector<double> a{1, 2, 3};
vector<double> b(3);

auto ita = a.begin();
for_each(b.begin(), b.end(), [&ita](auto &itb) { itb = *ita++; })

dentro de lambda puede hacer lo que sea itay luego incrementarlo. Esto se extiende fácilmente al caso de múltiples contenedores.

Vahid
fuente
3

Una biblioteca de rango proporciona esta y otras funciones muy útiles. El siguiente ejemplo usa Boost.Range . El rangev3 de Eric Niebler debería ser una buena alternativa.

#include <boost/range/combine.hpp>
#include <iostream>
#include <vector>
#include <list>

int main(int, const char*[])
{
    std::vector<int> const v{0,1,2,3,4};
    std::list<char> const  l{'a', 'b', 'c', 'd', 'e'};

    for(auto const& i: boost::combine(v, l))
    {
        int ti;
        char tc;
        boost::tie(ti,tc) = i;
        std::cout << '(' << ti << ',' << tc << ')' << '\n';
    }

    return 0;
}

C ++ 17 hará que esto sea aún mejor con enlaces estructurados:

int main(int, const char*[])
{
    std::vector<int> const v{0,1,2,3,4};
    std::list<char> const  l{'a', 'b', 'c', 'd', 'e'};

    for(auto const& [ti, tc]: boost::combine(v, l))
    {
        std::cout << '(' << ti << ',' << tc << ')' << '\n';
    }

    return 0;
}
Jens
fuente
Este programa no se compila con g ++ 4.8.0. delme.cxx:15:25: error: no match for 'operator=' (operand types are 'std::tuple<int&, char&>' and 'const boost::tuples::cons<const int&, boost::tuples::cons<const char&, boost::tuples::null_type> >') std::tie(ti,tc) = i; ^
syam
Después de cambiar std :: tie a boost: tie, se compila.
syam
Recibo el siguiente error de compilación para la versión con enlace estructurado (usando MSVC 19.13.26132.0y la versión de Windows SDK 10.0.16299.0): error C2679: binary '<<': no operator found which takes a right-hand operand of type 'const boost::tuples::cons<const char &,boost::fusion::detail::build_tuple_cons<boost::fusion::single_view_iterator<Sequence,boost::mpl::int_<1>>,Last,true>::type>' (or there is no acceptable conversion)
pooya13
los enlaces estructurados no parecen funcionar con boost::combine: stackoverflow.com/q/55585723/8414561
Dev Null
2

También llego un poco tarde; pero puedes usar esto (función variadic estilo C):

template<typename T>
void foreach(std::function<void(T)> callback, int count, ...) {
    va_list args;
    va_start(args, count);

    for (int i = 0; i < count; i++) {
        std::vector<T> v = va_arg(args, std::vector<T>);
        std::for_each(v.begin(), v.end(), callback);
    }

    va_end(args);
}

foreach<int>([](const int &i) {
    // do something here
}, 6, vecA, vecB, vecC, vecD, vecE, vecF);

o esto (usando un paquete de parámetros de función):

template<typename Func, typename T>
void foreach(Func callback, std::vector<T> &v) {
    std::for_each(v.begin(), v.end(), callback);
}

template<typename Func, typename T, typename... Args>
void foreach(Func callback, std::vector<T> &v, Args... args) {
    std::for_each(v.begin(), v.end(), callback);
    return foreach(callback, args...);
}

foreach([](const int &i){
    // do something here
}, vecA, vecB, vecC, vecD, vecE, vecF);

o esto (usando una lista de inicializadores entre llaves):

template<typename Func, typename T>
void foreach(Func callback, std::initializer_list<std::vector<T>> list) {
    for (auto &vec : list) {
        std::for_each(vec.begin(), vec.end(), callback);
    }
}

foreach([](const int &i){
    // do something here
}, {vecA, vecB, vecC, vecD, vecE, vecF});

o puede unir vectores como aquí: ¿Cuál es la mejor manera de concatenar dos vectores? y luego iterar sobre el vector grande.

Szymon Marczak
fuente
0

Aquí hay una variante

template<class ... Iterator>
void increment_dummy(Iterator ... i)
    {}

template<class Function,class ... Iterator>
void for_each_combined(size_t N,Function&& fun,Iterator... iter)
    {
    while(N!=0)
        {
        fun(*iter...);
        increment_dummy(++iter...);
        --N;
        }
    }

Uso de ejemplo

void arrays_mix(size_t N,const float* x,const float* y,float* z)
    {
    for_each_combined(N,[](float x,float y,float& z){z=x+y;},x,y,z);    
    }
user877329
fuente