Função seqüência-zip para c ++ 11?

99

Com o novo loop for baseado em intervalo, podemos escrever código como

for(auto x: Y) {}

Qual IMO é uma grande melhoria de (por exemplo)

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

Pode ser usado para fazer um loop em dois loops simultâneos, como a zipfunção Pythons ? Para quem não está familiarizado com Python, o código:

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

Dá como saída (1,4) (2,5) (3,6)

Fisgado
fonte
Baseado em intervalo forsó pode ser usado com uma variável, portanto, não. Se você quisesse acessar dois valores ao mesmo tempo, teria que usar algo comostd::pair
Seth Carnegie
4
@SethCarnegie: não diretamente, mas você poderia criar uma zip()função que retorne tuplas e itere sobre a lista de tuplas.
André Caron
2
@ AndréCaron você está certo, meu "não" queria dizer que você não pode usar duas variáveis, não que você não pode iterar em dois containers ao mesmo tempo.
Seth Carnegie
Claramente, for(;;)pode obter esse comportamento, embora longo, então é realmente a questão: É possível para "auto" sobre dois objetos ao mesmo tempo?
Em uma revisão futura (esperançosamente C ++ 17), uma revisão do STL incluirá intervalos . Então view :: zip pode fornecer a solução preferida.
John McFarlane de

Respostas:

88

Aviso: boost::zip_iterator e a boost::combinepartir do Boost 1.63.0 (26 de dezembro de 2016) causará um comportamento indefinido se o comprimento dos contêineres de entrada não for o mesmo (pode falhar ou iterar além do final).


A partir do Boost 1.56.0 (7 de agosto de 2014), você pode usarboost::combine (a função existe em versões anteriores, mas não 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);
    }
}

Isso iria imprimir

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

Em versões anteriores, você mesmo poderia definir um intervalo desta forma:

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

O uso é o mesmo.

Kennytm
fonte
1
você poderia usar isso para classificar? ou seja, std :: sort (zip (a.begin (), ...), zip (a.end (), ...), [] (tup a, tup b) {a.get <0> () > b.get <0> ()}); ?
gnzlbg
@gnzlbg: Não, você não pode .
kennytm
Eu ficaria tentado por optionalelementos de possibilidades de iteração além do fim ...
Yakk - Adam Nevraumont
3
Alguma chance de você fazer isso com std :: make_tuple e std :: tie? Eu estava tentando usar isso enquanto minimizava a dependência do boost, mas não consegui fazer funcionar.
Carneiro
@kennytm alguma ideia de por que eles decidiram ir com UB em vez de apenas terminar no final do grupo mais curto?
Catskul
18

Então eu escrevi este zip antes, quando estava entediado, decidi postar porque é diferente dos outros porque não usa boost e se parece mais com 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;
    }

Exemplo 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
fonte
4
Você deve verificar se algum dos iteradores está no final.
Xeo
1
@Xeo todos os intervalos devem ser do mesmo tamanho que o primeiro ou maior
aaronman
Você pode explicar como [](int i,int j,float k,float l)funciona? Esta é uma função lambda?
Hooked
@Hooked yeah, é um lambda, basicamente funciona, std::for_eachmas você pode usar um número arbitrário de intervalos, os parâmetros no lambda dependem de quantos iteradores você atribui à função
aaronman
1
Uma necessidade comum é compactar intervalos de tamanhos diferentes, ou mesmo com intervalos infinitos.
Xeo
16

Você pode usar uma solução baseada em boost::zip_iterator. Faça uma classe de contêiner falsa mantendo referências a seus contêineres e que retorne zip_iteratordas funções de membro begine end. Agora você pode escrever

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

Implementação de exemplo (teste):

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

Deixo a versão variada como um excelente exercício para o leitor.

Alexandre C.
fonte
3
+1: Boost.Range provavelmente deve incorporar isso. Na verdade, vou enviar-lhes um pedido de recurso sobre isso.
Nicol Bolas
2
@NicolBolas: Você se sai bem. Isso deve ser muito fácil de implementar com boost::iterator_range+ boost::zip_iterator, até mesmo a versão variável.
Alexandre C.
1
Eu acredito que isso nunca vai terminar (e ter um comportamento indefinido) se os intervalos não forem do mesmo tamanho.
Jonathan Wakely
1
boost::zip_iteratornão funciona com intervalos de comprimentos diferentes
Jonathan Wakely
1
Isso também deve funcionar mesmo em c ++ 03 limpo com par em vez de tupla. Ainda assim, isso também criará problemas quando os comprimentos não forem iguais. Algo pode ser feito com o end () tomando o end () correspondente do menor contêiner. Isso parece estar nas especificações, pois estava na pergunta dos OPs.
Paul,
16

std :: transform pode fazer isso 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;

Se a segunda sequência for mais curta, minha implementação parece estar fornecendo valores inicializados padrão.

Venki
fonte
1
Se a 2ª sequência for mais curta, então eu esperaria que fosse UB, pois você estaria iterando no final de b.
Adrian
15

Consulte Recursos <redi/zip.h>para obter uma zipfunção que funciona com base de intervalo fore aceita qualquer número de intervalos, que podem ser rvalues ​​ou lvalues ​​e podem ter comprimentos diferentes (a iteração irá parar no final do intervalo mais curto).

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>() << ' ';

Impressões 0 1 2 3 4 5

Jonathan Wakely
fonte
2
você também pode usar boost/tuple/tuple_io.hppparacout << i;
kirill_igum
Isto é o que funcionou para mim. No entanto, em meu código, tive que usar o equivalente a boost::get<0>(i)e boost::get<1>(i). Não sei por que o exemplo original não pôde ser adaptado diretamente; pode ter a ver com o fato de que meu código faz referências constantes a contêineres.
YitzikC
11

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

A saída:

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

csguth
fonte
@ einpoklum-reinstateMonica agora é!
yuyoyuppe de
6

Encontrei esta mesma pergunta de forma independente e não gostei da sintaxe de nenhuma das opções acima. Portanto, tenho um arquivo de cabeçalho curto que basicamente faz o mesmo que zip_iterator boost, mas tem algumas macros para tornar a sintaxe mais palatável para mim:

https://github.com/cshelton/zipfor

Por exemplo, você pode fazer

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

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

O principal açúcar sintático é que posso nomear os elementos de cada recipiente. Eu também incluo um "mapfor" que faz o mesmo, mas para mapas (para nomear o ".first" e ".second" do elemento).

Cshelton
fonte
Isso é legal! Pode ser necessário um número arbitrário de argumentos, sendo todos aqueles limitados por seus modelos inteligentes a um número finito?
Hooked
Atualmente, ele só lida com até 9 contêineres paralelos. Isso seria simples de avançar. Enquanto as macros variáveis ​​permitem que uma única macro "zipfor" lide com diferentes números de parâmetros, ainda é necessário codificar uma macro separada para cada uma (a ser enviada para). Consulte groups.google.com/forum/?fromgroups=#!topic/comp.std.c/… e stackoverflow.com/questions/15847837/…
cshelton
Ele lida bem com argumentos de tamanhos diferentes? (conforme descrito no OP)
coyotte508
@ coyotte508, ele assume que o primeiro contêiner tem o menor número de elementos (e ignora os elementos extras em outros contêineres). Seria fácil modificar não fazer essa suposição, mas isso iria desacelerar (atualmente, não é mais lento do que escrito à mão) quando o número de elementos corresponder.
cshelton
6
// declare a, b
BOOST_FOREACH(boost::tie(a, b), boost::combine(list_of_a, list_of_b)){
    // your code here.
}
Lula
fonte
6

Se você gosta de sobrecarga do operador, aqui estão três possibilidades. Os dois primeiros estão usando std::pair<>e std::tuple<>, respectivamente, como iteradores; o terceiro estende isso para baseado em alcance for. Observe que nem todo mundo vai gostar dessas definições de operadores, então é melhor mantê-los em um namespace separado e ter um using namespacenas funções (não arquivos!) Onde você gostaria de usá-los.

#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
fonte
3

Para uma biblioteca de processamento de fluxo C ++ que estou escrevendo, procuro uma solução que não dependa de bibliotecas de terceiros e funcione com um número arbitrário de contêineres. Acabei com esta solução. É semelhante à solução aceita que usa boost (e também resulta em comportamento indefinido se os comprimentos do contêiner não forem iguais)

#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
fonte
1
link quebrado ... seria útil se a postagem mostrasse como usá-lo, por exemplo, main ()?
javaLover de
@javaLover: você pode usá-lo da mesma forma que cppitertools na resposta de @knedlsepp. Uma diferença notável é que, com a solução acima, você não pode modificar os contêineres subjacentes, pois operator*for seq::iteratorretorna uma std::tupledas referências const.
winnetou
2

Se você tiver um compilador compatível com C ++ 14 (por exemplo, gcc5), você pode usar zipa cppitertoolsbiblioteca fornecida por Ryan Haining, que parece realmente promissora:

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
fonte
0

Boost.Iterators tem zip_iteratorvocê pode usar (exemplos nos documentos). Não funcionará com range for, mas você pode usar std::for_eache um lambda.

Cat Plus Plus
fonte
Por que não funciona com baseado em intervalo para? Combine-o com Boost.Range e você deve estar definido.
Xeo
@Xeo: Não conheço Range muito bem. Eu acho que você poderia envolver algum clichê e fazê-lo funcionar, mas apenas usando IMO for_eachseria menos incômodo.
Cat Plus Plus
Você quer dizer algo assim não é incômodo 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 de
2
Eu deveria começar uma campanha Lambda não faz std :: for_each útil. :)
UncleBens
2
@Xeo: Essa provavelmente deveria ser uma pergunta separada, mas por que, ah, por quê ??
UncleBens de
-2

Aqui está uma versão simples que não requer reforço. Não será particularmente eficiente, pois cria valores temporários e não generaliza sobre contêineres que não sejam listas, mas não tem dependências e resolve o caso mais comum de compactação.

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

Embora as outras versões sejam mais flexíveis, geralmente o objetivo de usar um operador de lista é criar uma linha simples. Esta versão tem a vantagem de que o caso comum é simples.

Andrew
fonte