Funkcja sekwencji-zip dla C ++ 11?

100

Dzięki nowej pętli for opartej na zakresach możemy pisać kod podobny do

for(auto x: Y) {}

Która IMO jest ogromnym ulepszeniem (np.)

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

Czy można go użyć do zapętlenia dwóch równoczesnych pętli, jak zipfunkcja Pythona ? Dla osób niezaznajomionych z Pythonem kod:

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

Daje jako wyjście (1,4) (2,5) (3,6)

Haczykowaty
źródło
Oparta na zakresie formoże być używana tylko z jedną zmienną, więc nie. Jeśli chcesz uzyskać dostęp do dwóch wartości naraz, musisz użyć czegoś takiego jakstd::pair
Seth Carnegie,
4
@SethCarnegie: nie bezpośrednio, ale możesz wymyślić zip()funkcję, która zwraca krotki i iteruje listę krotek.
André Caron,
2
@ AndréCaron masz rację, moje „nie” miało oznaczać, że nie możesz używać dwóch zmiennych, a nie że nie możesz iterować po dwóch kontenerach naraz.
Seth Carnegie,
Oczywiste for(;;)jest, że można uzyskać takie zachowanie, choć na dłuższą metę, więc jest tak naprawdę pytanie: Czy jest możliwe, aby „automatycznie” nad dwoma obiektami naraz?
W przyszłej wersji (miejmy nadzieję, że C ++ 17), przegląd STL będzie obejmował zakresy . W takim przypadku view :: zip może zapewnić preferowane rozwiązanie.
John McFarlane

Odpowiedzi:

89

Ostrzeżenie: boost::zip_iterator a boost::combineod Boost 1.63.0 (26 grudnia 2016 r.) Spowoduje niezdefiniowane zachowanie, jeśli długość kontenerów wejściowych nie jest taka sama (może się zawiesić lub iterować poza końcem).


Począwszy od Boost 1.56.0 (7 sierpnia 2014 r.) Możesz użyćboost::combine (funkcja istnieje we wcześniejszych wersjach, ale nie jest udokumentowana):

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

To by się wydrukowało

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

We wcześniejszych wersjach można było samodzielnie zdefiniować zakres w następujący sposób:

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

Użycie jest takie samo.

kennytm
źródło
1
czy możesz użyć tego do sortowania? tj. std :: sort (zip (a.begin (), ...), zip (a.end (), ...), [] (tup a, tup b) {a.get <0> () > b.get <0> ()}); ?
gnzlbg
@gnzlbg: Nie, nie możesz .
kennytm
Chciałbym być kuszony przez optionalelementy do możliwości past-the-end iteracji ...
Yakk - Adam Nevraumont
3
Czy możesz to zrobić za pomocą std :: make_tuple i std :: tie? Próbowałem tego użyć, minimalizując zależność doładowania, ale nie mogłem sprawić, by działało.
Carneiro,
@kennytm masz jakiś pomysł, dlaczego zdecydowali się na UB zamiast po prostu kończyć na końcu najkrótszego zakresu z paczki?
Catskul,
18

Więc napisałem ten plik zip wcześniej, kiedy się nudziłem, zdecydowałem się go opublikować, ponieważ różni się od innych, ponieważ nie używa boost i wygląda bardziej jak stdlib c ++.

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

Przykładowe zastosowanie:

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
źródło
4
Powinieneś sprawdzić, czy którykolwiek z iteratorów jest na końcu.
Xeo
1
@Xeo wszystkie zakresy powinny mieć taki sam rozmiar jak pierwszy lub większy
aaronman
Czy możesz wyjaśnić, jak to [](int i,int j,float k,float l)działa? Czy to jest funkcja lambda?
Hooked
@Hooked yeah to lambda, w zasadzie działa tylko, std::for_eachale możesz użyć dowolnej liczby zakresów, parametry w
lambdzie
1
Częstą potrzebą jest spakowanie zakresów o różnej wielkości lub nawet nieskończonych zakresów.
Xeo,
18

std :: transform może to zrobić trywialnie:

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;

Jeśli druga sekwencja jest krótsza, moja implementacja wydaje się podawać domyślne zainicjalizowane wartości.

Venki
źródło
1
Jeśli druga sekwencja jest krótsza, spodziewałbym się, że jest to UB, tak jak byś iterował na końcu b.
Adrian
16

Możesz skorzystać z rozwiązania opartego na boost::zip_iterator. Utwórz fałszywą klasę kontenera zachowującą odwołania do kontenerów i zwracającą się zip_iteratorz funkcji begini endskładowych. Teraz możesz pisać

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

Przykładowa implementacja (prosimy o przetestowanie):

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

Wersję wariadyczną pozostawiam czytelnikowi jako doskonałe ćwiczenie.

Alexandre C.
źródło
3
+1: Boost.Range prawdopodobnie powinien to uwzględniać. Właściwie to zostawię im prośbę o dodanie funkcji.
Nicol Bolas,
2
@NicolBolas: Dobrze sobie radzisz. Powinno to być dość łatwe do zaimplementowania z boost::iterator_range+ boost::zip_iterator, nawet w wersji wariadycznej.
Alexandre C.
1
Uważam, że to się nigdy nie zakończy (i będzie miało niezdefiniowane zachowanie), jeśli zakresy nie będą tej samej długości.
Jonathan Wakely
1
boost::zip_iteratornie działa z zakresami o różnych długościach
Jonathan Wakely
1
Powinno to również działać nawet w czystym c ++ 03 z parą zamiast krotki. Jednak będzie to również powodować problemy, gdy długości nie są równe. Coś można zrobić z końcówką end (), biorąc odpowiednią końcówkę end () najmniejszego pojemnika. Wydaje się, że jest to zgodne ze specyfikacją, tak jak w przypadku pytań dotyczących PO.
Paul
15

Patrz <redi/zip.h>na zipfunkcję, która współpracuje z zakresu bazy fori przyjmuje dowolną liczbę przedziałów, które mogą być rvalues lub lwartościami i może mieć różną długość (będzie iteracji zatrzymuje się na koniec krótkim zasięgu).

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

Wydruki 0 1 2 3 4 5

Jonathan Wakely
źródło
2
możesz również użyć boost/tuple/tuple_io.hppdocout << i;
kirill_igum
To właśnie zadziałało dla mnie. Jednak w moim kodzie musiałem użyć odpowiednika boost::get<0>(i)i boost::get<1>(i). Nie jestem pewien, dlaczego oryginalna próbka nie mogła zostać dostosowana bezpośrednio, może to mieć związek z faktem, że mój kod stale odwołuje się do kontenerów.
YitzikC
11

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

Wyjście:

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

csguth
źródło
@ einpoklum-reinstateMonica teraz jest!
yuyoyuppe
6

Natknąłem się na to samo pytanie niezależnie i nie podobała mi się składnia żadnego z powyższych. Mam więc krótki plik nagłówkowy, który zasadniczo robi to samo, co przyspieszenie zip_iterator, ale ma kilka makr, aby uczynić składnię bardziej przyjemną dla mnie:

https://github.com/cshelton/zipfor

Na przykład możesz to zrobić

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

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

Głównym cukrem syntaktycznym jest to, że mogę nazwać elementy z każdego pojemnika. Dołączam również „mapfor”, które robi to samo, ale dla map (aby nazwać „.first” i „.second” elementu).

cshelton
źródło
To jest fajne! Czy może zająć dowolna liczba argumentów, czy wszystkie te są ograniczone przez twoje sprytne szablony do skończonej liczby?
Hooked
Obecnie obsługuje do 9 równoległych kontenerów. To byłoby łatwe do zrobienia. Podczas gdy makra wariadyczne pozwalają na użycie jednego makra „zipfor” do obsługi różnej liczby parametrów, nadal trzeba kodować osobne makro dla każdego (do wysłania). Zobacz groups.google.com/forum/?fromgroups=#!topic/comp.std.c/… i stackoverflow.com/questions/15847837/…
cshelton
Czy dobrze radzi sobie z argumentami o różnej wielkości? (jak opisano w PO)
coyotte508
@ coyotte508 zakłada, że ​​pierwszy kontener ma najmniejszą liczbę elementów (i ignoruje dodatkowe elementy w innych kontenerach). Byłoby łatwo zmodyfikować, aby nie przyjmować tego założenia, ale spowolniłoby to (obecnie nie jest wolniejsze niż napisane ręcznie), gdy liczba elementów się zgadza.
cshelton
6
// declare a, b
BOOST_FOREACH(boost::tie(a, b), boost::combine(list_of_a, list_of_b)){
    // your code here.
}
kałamarnica
źródło
6

Jeśli lubisz przeciążanie operatorów, oto trzy możliwości. Pierwsze dwa używania std::pair<>i std::tuple<>odpowiednio jako iteratorami; trzecia rozszerza to na podstawie zakresu for. Zauważ, że nie każdemu spodobają się te definicje operatorów, więc najlepiej trzymać je w oddzielnej przestrzeni nazw i mieć using namespacew funkcjach (nie plikach!), W których chciałbyś ich używać.

#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
źródło
3

W przypadku biblioteki przetwarzania strumieniowego C ++, którą piszę, szukałem rozwiązania, które nie opiera się na bibliotekach innych firm i działa z dowolną liczbą kontenerów. Skończyło się na tym rozwiązaniu. Jest podobny do przyjętego rozwiązania, które wykorzystuje doładowanie (a także powoduje niezdefiniowane zachowanie, jeśli długości kontenerów nie są równe)

#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)...));
}
mgły
źródło
1
link uszkodzony ... przydałby się, gdyby post pokazuje, jak go używać, np. main ()?
javaLover
@javaLover: możesz go używać w taki sam sposób, jak cppitertools w odpowiedzi @ knedlsepp. Jedną zauważalną różnicą jest to, że w powyższym rozwiązaniu nie można modyfikować podstawowych kontenerów, ponieważ operator*for seq::iteratorzwraca a std::tuplez odwołań do const.
winnetou
2

Jeśli masz kompilator zgodny z C ++ 14 (np. Gcc5), możesz użyć zipdostarczonego w cppitertoolsbibliotece przez Ryana Haininga, który wygląda naprawdę obiecująco:

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
źródło
0

Boost.Iterators ma, zip_iteratorktórego możesz użyć (przykłady w dokumentacji). Nie będzie działać z zakresem dla, ale możesz użyć std::for_eachi lambda.

Cat Plus Plus
źródło
Dlaczego nie będzie działać z opcją opartą na zakresie? Połącz to z Boost.Range i powinieneś być ustawiony.
Xeo,
@Xeo: Nie znam zbyt dobrze Range. Wydaje mi się, że mógłbyś zaangażować trochę schematu i sprawić, by działał, ale samo użycie IMO for_eachbyłoby mniej kłopotliwe.
Cat Plus Plus
Masz na myśli coś takiego nie jest uciążliwe: 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
Powinienem rozpocząć kampanię Lambda nie tworzy std :: for_each Useful. :)
UncleBens
2
@Xeo: To prawdopodobnie powinno być osobne pytanie, ale dlaczego, och, dlaczego?
UncleBens
-2

Oto prosta wersja, która nie wymaga doładowania. Nie będzie szczególnie wydajne, ponieważ tworzy wartości tymczasowe i nie generalizuje innych kontenerów niż listy, ale nie ma żadnych zależności i rozwiązuje najczęstszy przypadek kompresowania.

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

Chociaż inne wersje są bardziej elastyczne, często celem użycia operatora listy jest stworzenie prostego jednowierszowego. Ta wersja ma tę zaletę, że typowy przypadek jest prosty.

Andrzej
źródło