¿Función de secuencia-zip para c ++ 11?

99

Con el nuevo bucle for basado en rangos podemos escribir código como

for(auto x: Y) {}

Qué IMO es una gran mejora de (por ejemplo)

for(std::vector<int>::iterator x=Y.begin(); x!=Y.end(); ++x) {}

¿Se puede usar para recorrer dos bucles simultáneos, como la zipfunción Pythons ? Para aquellos que no están familiarizados con Python, el código:

Y1 = [1,2,3]
Y2 = [4,5,6,7]
for x1,x2 in zip(Y1,Y2):
    print x1,x2

Da como salida (1,4) (2,5) (3,6)

Enganchado
fuente
El basado en rango forsolo se puede usar con una variable, por lo que no. Si quisiera acceder a dos valores a la vez, tendría que usar algo comostd::pair
Seth Carnegie
4
@SethCarnegie: no directamente, pero podría crear una zip()función que devuelva tuplas e iterar sobre la lista de tuplas.
André Caron
2
@ AndréCaron tiene razón, mi "no" tenía la intención de decir que no puede usar dos variables, no que no pueda iterar sobre dos contenedores a la vez.
Seth Carnegie
Claramente for(;;)puede obtener este comportamiento, aunque sea a largo plazo, por lo que la pregunta es realmente: ¿Es posible "auto" sobre dos objetos a la vez?
En una revisión futura (con suerte C ++ 17), una revisión de STL incluirá rangos . Entonces view :: zip puede proporcionar la solución preferida.
John McFarlane

Respuestas:

88

Advertencia: boost::zip_iterator y a boost::combinepartir de Boost 1.63.0 (26 de diciembre de 2016) causará un comportamiento indefinido si la longitud de los contenedores de entrada no es la misma (puede fallar o iterar más allá del final).


A partir de Boost 1.56.0 (7 de agosto de 2014), puede usarboost::combine (la función existe en versiones anteriores pero no está documentada):

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

int main() {
    std::vector<int> a {4, 5, 6};
    double b[] = {7, 8, 9};
    std::list<std::string> c {"a", "b", "c"};
    for (auto tup : boost::combine(a, b, c, a)) {    // <---
        int x, w;
        double y;
        std::string z;
        boost::tie(x, y, z, w) = tup;
        printf("%d %g %s %d\n", x, y, z.c_str(), w);
    }
}

Esto imprimiría

4 7 a 4
5 8 b 5
6 9 c 6

En versiones anteriores, usted mismo podía definir un rango como este:

#include <boost/iterator/zip_iterator.hpp>
#include <boost/range.hpp>

template <typename... T>
auto zip(T&&... containers) -> boost::iterator_range<boost::zip_iterator<decltype(boost::make_tuple(std::begin(containers)...))>>
{
    auto zip_begin = boost::make_zip_iterator(boost::make_tuple(std::begin(containers)...));
    auto zip_end = boost::make_zip_iterator(boost::make_tuple(std::end(containers)...));
    return boost::make_iterator_range(zip_begin, zip_end);
}

El uso es el mismo.

Kennytm
fuente
1
¿Podrías usar esto para clasificar? es decir, std :: sort (zip (a.begin (), ...), zip (a.end (), ...), [] (tup a, tup b) {a.get <0> () > b.get <0> ()}); ?
gnzlbg
@gnzlbg: No, no puedes .
kennytm
Me sentiría tentado por optionalelementos para posibilidades de iteración más allá del final ...
Yakk - Adam Nevraumont
3
¿Alguna posibilidad de que pueda hacer esto con std :: make_tuple y std :: tie? Estaba tratando de usar esto mientras minimizaba la dependencia del impulso, pero no pude hacerlo funcionar.
Carneiro
@kennytm ¿alguna idea de por qué decidieron ir con UB en lugar de simplemente terminar al final del rango más corto del grupo?
Catskul
18

Así que escribí este zip antes cuando estaba aburrido, decidí publicarlo porque es diferente a los demás en que no usa boost y se parece más a c ++ stdlib.

template <typename Iterator>
    void advance_all (Iterator & iterator) {
        ++iterator;
    }
template <typename Iterator, typename ... Iterators>
    void advance_all (Iterator & iterator, Iterators& ... iterators) {
        ++iterator;
        advance_all(iterators...);
    } 
template <typename Function, typename Iterator, typename ... Iterators>
    Function zip (Function func, Iterator begin, 
            Iterator end, 
            Iterators ... iterators)
    {
        for(;begin != end; ++begin, advance_all(iterators...))
            func(*begin, *(iterators)... );
        //could also make this a tuple
        return func;
    }

Ejemplo de uso:

int main () {
    std::vector<int> v1{1,2,3};
    std::vector<int> v2{3,2,1};
    std::vector<float> v3{1.2,2.4,9.0};
    std::vector<float> v4{1.2,2.4,9.0};
     zip (
            [](int i,int j,float k,float l){
                std::cout << i << " " << j << " " << k << " " << l << std::endl;
            },
            v1.begin(),v1.end(),v2.begin(),v3.begin(),v4.begin());
}
Aaronman
fuente
4
Debe verificar si alguno de los iteradores está al final.
Xeo
1
@Xeo, todos los rangos deben ser del mismo tamaño que el primero o mayor
Aaronman
¿Puedes explicar cómo [](int i,int j,float k,float l)funciona? ¿Es esta una función lambda?
Enganchado el
@Hooked, sí, es una lambda, básicamente funciona, std::for_eachpero puede usar un número arbitrario de rangos, los parámetros en la lambda dependen de la cantidad de iteradores que le dé a la función
Aaronman
1
Una necesidad común es comprimir rangos de diferentes tamaños, o incluso con rangos infinitos.
Xeo
16

Puede utilizar una solución basada en boost::zip_iterator. Cree una clase de contenedor falsa que mantenga referencias a sus contenedores y que regresen zip_iteratorde las funciones miembro beginy end. Ahora puedes escribir

for (auto p: zip(c1, c2)) { ... }

Implementación de ejemplo (prueba):

#include <iterator>
#include <boost/iterator/zip_iterator.hpp>

template <typename C1, typename C2>
class zip_container
{
    C1* c1; C2* c2;

    typedef boost::tuple<
        decltype(std::begin(*c1)), 
        decltype(std::begin(*c2))
    > tuple;

public:
    zip_container(C1& c1, C2& c2) : c1(&c1), c2(&c2) {}

    typedef boost::zip_iterator<tuple> iterator;

    iterator begin() const
    {
         return iterator(std::begin(*c1), std::begin(*c2));
    }

    iterator end() const
    {
         return iterator(std::end(*c1), std::end(*c2));
    }
};

template <typename C1, typename C2>
zip_container<C1, C2> zip(C1& c1, C2& c2)
{
    return zip_container<C1, C2>(c1, c2);
}

Dejo la versión variadic como un excelente ejercicio para el lector.

Alexandre C.
fuente
3
+1: Boost.Range probablemente debería incorporar esto. De hecho, les enviaré una solicitud de función sobre esto.
Nicol Bolas
2
@NicolBolas: Lo haces bien. Esto debería ser bastante fácil de implementar con boost::iterator_range+ boost::zip_iterator, incluso la versión variadic.
Alexandre C.
1
Creo que esto nunca terminará (y tendrá un comportamiento indefinido) si los rangos no tienen la misma longitud.
Jonathan Wakely
1
boost::zip_iteratorno funciona con rangos de diferentes longitudes
Jonathan Wakely
1
Esto también debería funcionar incluso en limpio c ++ 03 con par en lugar de tupla. Aún así, esto también creará problemas cuando las longitudes no sean iguales. Se puede hacer algo con end () tomando el correspondiente end () del contenedor más pequeño. Esto parece estar en la especificación como lo fue en la pregunta de OP.
Paul
16

std :: transform puede hacer esto trivialmente:

std::vector<int> a = {1,2,3,4,5};
std::vector<int> b = {1,2,3,4,5};
std::vector<int>c;
std::transform(a.begin(),a.end(), b.begin(),
               std::back_inserter(c),
               [](const auto& aa, const auto& bb)
               {
                   return aa*bb;
               });
for(auto cc:c)
    std::cout<<cc<<std::endl;

Si la segunda secuencia es más corta, mi implementación parece estar dando valores inicializados predeterminados.

Venki
fuente
1
Si la segunda secuencia es más corta, entonces esperaría que esto sea UB, ya que estaría iterando al final de b.
Adrian
15

Consulte <redi/zip.h>una zipfunción que funcione con range-base fory acepte cualquier número de rangos, que pueden ser rvalues ​​o lvalues ​​y pueden tener diferentes longitudes (la iteración se detendrá al final del rango más corto).

std::vector<int> vi{ 0, 2, 4 };
std::vector<std::string> vs{ "1", "3", "5", "7" };
for (auto i : redi::zip(vi, vs))
  std::cout << i.get<0>() << ' ' << i.get<1>() << ' ';

Huellas dactilares 0 1 2 3 4 5

Jonathan Wakely
fuente
2
también puede utilizar boost/tuple/tuple_io.hppparacout << i;
kirill_igum
Esto es lo que funcionó para mí. Sin embargo, en mi código tuve que usar el equivalente de boost::get<0>(i)y boost::get<1>(i). No estoy seguro de por qué la muestra original no se pudo adaptar directamente, podría tener que ver con el hecho de que mi código toma referencias constantes a los contenedores.
YitzikC
11

Con range-v3 :

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

namespace ranges {
    template <class T, class U>
    std::ostream& operator << (std::ostream& os, common_pair<T, U> const& p)
    {
      return os << '(' << p.first << ", " << p.second << ')';
    }
}

using namespace ranges::v3;

int main()
{
    std::vector<int> a {4, 5, 6};
    double b[] = {7, 8, 9};
    std::cout << view::zip(a, b) << std::endl; 
}

La salida:

[(4, 7), (5, 8), (6, 9)]

csguth
fuente
@ einpoklum-reinstateMonica ahora lo es!
Yuyoyuppe
6

Me encontré con esta misma pregunta de forma independiente y no me gustó la sintaxis de ninguno de los anteriores. Entonces, tengo un archivo de encabezado corto que esencialmente hace lo mismo que boost zip_iterator pero tiene algunas macros para hacer que la sintaxis sea más aceptable para mí:

https://github.com/cshelton/zipfor

Por ejemplo, puedes hacer

vector<int> a {1,2,3};
array<string,3> b {"hello","there","coders"};

zipfor(i,s eachin a,b)
    cout << i << " => " << s << endl;

El principal azúcar sintáctico es que puedo nombrar los elementos de cada contenedor. También incluyo un "mapfor" que hace lo mismo, pero para mapas (para nombrar el ".first" y ".second" del elemento).

cshelton
fuente
¡Esto es genial! ¿Puede tomar un número arbitrario de argumentos si todos los que se limitan a un número finito por su ingeniosa creación de plantillas?
Enganchado
Actualmente solo maneja hasta 9 contenedores paralelos. Eso sería sencillo de avanzar. Mientras que las macros variadic permiten que una sola macro "zipfor" maneje diferentes números de parámetros, uno todavía tiene que codificar una macro separada para cada uno (para ser enviado a). Ver groups.google.com/forum/?fromgroups=#!topic/comp.std.c/… y stackoverflow.com/questions/15847837/…
cshelton
¿Maneja bien argumentos de diferente tamaño? (como se describe en el OP)
coyotte508
@ coyotte508, asume que el primer contenedor tiene la menor cantidad de elementos (e ignora los elementos adicionales en otros contenedores). Sería fácil modificarlo para no hacer esta suposición, pero eso lo ralentizaría (actualmente no es más lento que el escrito a mano) cuando el número de elementos coincida.
cshelton
6
// declare a, b
BOOST_FOREACH(boost::tie(a, b), boost::combine(list_of_a, list_of_b)){
    // your code here.
}
calamar
fuente
6

Si le gusta la sobrecarga del operador, aquí tiene tres posibilidades. Los dos primeros utilizan std::pair<>y std::tuple<>, respectivamente, como iteradores; el tercero extiende esto al rango basado for. Tenga en cuenta que no a todo el mundo le gustarán estas definiciones de los operadores, por lo que es mejor mantenerlas en un espacio de nombres separado y tener una using namespaceen las funciones (¡no en archivos!) Donde le gustaría usarlas.

#include <iostream>
#include <utility>
#include <vector>
#include <tuple>

// put these in namespaces so we don't pollute global
namespace pair_iterators
{
    template<typename T1, typename T2>
    std::pair<T1, T2> operator++(std::pair<T1, T2>& it)
    {
        ++it.first;
        ++it.second;
        return it;
    }
}

namespace tuple_iterators
{
    // you might want to make this generic (via param pack)
    template<typename T1, typename T2, typename T3>
    auto operator++(std::tuple<T1, T2, T3>& it)
    {
        ++( std::get<0>( it ) );
        ++( std::get<1>( it ) );
        ++( std::get<2>( it ) );
        return it;
    }

    template<typename T1, typename T2, typename T3>
    auto operator*(const std::tuple<T1, T2, T3>& it)
    {
        return std::tie( *( std::get<0>( it ) ),
                         *( std::get<1>( it ) ),
                         *( std::get<2>( it ) ) );
    }

    // needed due to ADL-only lookup
    template<typename... Args>
    struct tuple_c
    {
        std::tuple<Args...> containers;
    };

    template<typename... Args>
    auto tie_c( const Args&... args )
    {
        tuple_c<Args...> ret = { std::tie(args...) };
        return ret;
    }

    template<typename T1, typename T2, typename T3>
    auto begin( const tuple_c<T1, T2, T3>& c )
    {
        return std::make_tuple( std::get<0>( c.containers ).begin(),
                                std::get<1>( c.containers ).begin(),
                                std::get<2>( c.containers ).begin() );
    }

    template<typename T1, typename T2, typename T3>
    auto end( const tuple_c<T1, T2, T3>& c )
    {
        return std::make_tuple( std::get<0>( c.containers ).end(),
                                std::get<1>( c.containers ).end(),
                                std::get<2>( c.containers ).end() );
    }

    // implement cbegin(), cend() as needed
}

int main()
{
    using namespace pair_iterators;
    using namespace tuple_iterators;

    std::vector<double> ds = { 0.0, 0.1, 0.2 };
    std::vector<int   > is = {   1,   2,   3 };
    std::vector<char  > cs = { 'a', 'b', 'c' };

    // classical, iterator-style using pairs
    for( auto its  = std::make_pair(ds.begin(), is.begin()),
              end  = std::make_pair(ds.end(),   is.end()  ); its != end; ++its )
    {
        std::cout << "1. " << *(its.first ) + *(its.second) << " " << std::endl;
    }

    // classical, iterator-style using tuples
    for( auto its  = std::make_tuple(ds.begin(), is.begin(), cs.begin()),
              end  = std::make_tuple(ds.end(),   is.end(),   cs.end()  ); its != end; ++its )
    {
        std::cout << "2. " << *(std::get<0>(its)) + *(std::get<1>(its)) << " "
                           << *(std::get<2>(its)) << " " << std::endl;
    }

    // range for using tuples
    for( const auto& d_i_c : tie_c( ds, is, cs ) )
    {
        std::cout << "3. " << std::get<0>(d_i_c) + std::get<1>(d_i_c) << " "
                           << std::get<2>(d_i_c) << " " << std::endl;
    }
}
lorro
fuente
3

Para una biblioteca de procesamiento de flujo de C ++ que estoy escribiendo, estaba buscando una solución que no se base en bibliotecas de terceros y funcione con una cantidad arbitraria de contenedores. Terminé con esta solución. Es similar a la solución aceptada que usa boost (y también da como resultado un comportamiento indefinido si las longitudes del contenedor no son iguales)

#include <utility>

namespace impl {

template <typename Iter, typename... Iters>
class zip_iterator {
public:
  using value_type = std::tuple<const typename Iter::value_type&,
                                const typename Iters::value_type&...>;

  zip_iterator(const Iter &head, const Iters&... tail)
      : head_(head), tail_(tail...) { }

  value_type operator*() const {
    return std::tuple_cat(std::tuple<const typename Iter::value_type&>(*head_), *tail_);
  }

  zip_iterator& operator++() {
    ++head_; ++tail_;
    return *this;
  }

  bool operator==(const zip_iterator &rhs) const {
    return head_ == rhs.head_ && tail_ == rhs.tail_;
  }

  bool operator!=(const zip_iterator &rhs) const {
    return !(*this == rhs);
  }

private:
  Iter head_;
  zip_iterator<Iters...> tail_;
};

template <typename Iter>
class zip_iterator<Iter> {
public:
  using value_type = std::tuple<const typename Iter::value_type&>;

  zip_iterator(const Iter &head) : head_(head) { }

  value_type operator*() const {
    return value_type(*head_);
  }

  zip_iterator& operator++() { ++head_; return *this; }

  bool operator==(const zip_iterator &rhs) const { return head_ == rhs.head_; }

  bool operator!=(const zip_iterator &rhs) const { return !(*this == rhs); }

private:
  Iter head_;
};

}  // namespace impl

template <typename Iter>
class seq {
public:
  using iterator = Iter;
  seq(const Iter &begin, const Iter &end) : begin_(begin), end_(end) { }
  iterator begin() const { return begin_; }
  iterator end() const { return end_; }
private:
  Iter begin_, end_;
};

/* WARNING: Undefined behavior if iterator lengths are different.
 */
template <typename... Seqs>
seq<impl::zip_iterator<typename Seqs::iterator...>>
zip(const Seqs&... seqs) {
  return seq<impl::zip_iterator<typename Seqs::iterator...>>(
      impl::zip_iterator<typename Seqs::iterator...>(std::begin(seqs)...),
      impl::zip_iterator<typename Seqs::iterator...>(std::end(seqs)...));
}
foges
fuente
1
enlace roto ... sería útil si la publicación muestra cómo usarlo, por ejemplo, main ()?
javaLover
@javaLover: puede usarlo de la misma manera que cppitertools en la respuesta de @ knedlsepp. Una diferencia notable es que con la solución anterior no puede modificar los contenedores subyacentes, ya que operator*for seq::iteratordevuelve una std::tuplede las referencias constantes.
winnetou
2

Si tiene un compilador compatible con C ++ 14 (por ejemplo, gcc5), puede usarlo zipproporcionado en la cppitertoolsbiblioteca por Ryan Haining, que parece realmente prometedor:

array<int,4> i{{1,2,3,4}};
vector<float> f{1.2,1.4,12.3,4.5,9.9};
vector<string> s{"i","like","apples","alot","dude"};
array<double,5> d{{1.2,1.2,1.2,1.2,1.2}};

for (auto&& e : zip(i,f,s,d)) {
    cout << std::get<0>(e) << ' '
         << std::get<1>(e) << ' '
         << std::get<2>(e) << ' '
         << std::get<3>(e) << '\n';
    std::get<1>(e)=2.2f; // modifies the underlying 'f' array
}
knedlsepp
fuente
0

Boost.Iterators tiene zip_iteratorque puede usar (ejemplos en los documentos). No funcionará con range for, pero puedes usar std::for_eachy lambda.

Gato Plus Plus
fuente
¿Por qué no funciona con el rango basado en? Combínelo con Boost.Range y debería estar listo.
Xeo
@Xeo: No conozco muy bien a Range. Supongo que podría involucrar algo de repetición y hacer que funcione, pero en mi opinión, usarlo for_eachsería menos complicado.
Cat Plus Plus
¿Quiere decir que algo como esto no es una molestia std::for_each(make_zip_iterator(make_tuple(Y1.begin(), Y2.begin())), make_zip_iterator(make_tuple(Y1.end(), Y2.end())), [](const tuple<int, int>& t){printf("%d %d\n", get<0>(t), get<1>(t)); });?
UncleBens
2
Debo iniciar una campaña Lambda Does Not Make std :: for_each útil. :)
UncleBens
2
@Xeo: Esta probablemente debería ser una pregunta separada, pero ¿por qué, oh, por qué?
UncleBens
-2

Aquí hay una versión simple que no requiere impulso. No será particularmente eficiente ya que crea valores temporales y no generaliza sobre contenedores que no sean listas, pero no tiene dependencias y resuelve el caso más común de compresión.

template<class L, class R>
std::list< std::pair<L,R> >  zip(std::list<L> left, std::list<R> right)
{
auto l = left.begin();
auto r = right.begin();
std::list< std::pair<L,R> > result;
  while( l!=left.end() && r!=right.end() )
    result.push_back( std::pair<L,R>( *(l++), *(r++) ) );
  return result;
}

Aunque las otras versiones son más flexibles, a menudo el objetivo de utilizar un operador de lista es hacer una simple línea. Esta versión tiene la ventaja de que el caso común es simple.

Andrés
fuente