Jaki jest najlepszy sposób na jednoczesne iterowanie w dwóch lub więcej kontenerach

114

C ++ 11 zapewnia wiele sposobów iteracji po kontenerach. Na przykład:

Pętla oparta na zakresie

for(auto c : container) fun(c)

std :: for_each

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

Jednak jaki jest zalecany sposób iteracji na dwóch (lub więcej) kontenerach tego samego rozmiaru, aby osiągnąć coś takiego:

for(unsigned i = 0; i < containerA.size(); ++i) {
  containerA[i] = containerB[i];
}
memeki
źródło
1
co z transformprezentem w #include <algorithm>?
Ankit Acharya
O pętli przypisania: jeśli oba są wektorami lub podobnymi, użyj containerA = containerB;zamiast pętli.
emlai
Podobne pytanie: stackoverflow.com/questions/8511035/…
knedlsepp
1
Możliwy duplikat funkcji Sequence-zip dla języka C ++ 11?
underscore_d

Odpowiedzi:

53

Raczej późno na przyjęcie. Ale: chciałbym iterować po indeksach. Ale nie z klasyczną forpętlą, ale zamiast tego z forpętlą opartą na zakresie na indeksach:

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

indicesto prosta funkcja opakowująca, która zwraca (leniwie oceniany) zakres indeksów. Ponieważ implementacja - choć prosta - jest trochę za długa, aby ją tutaj opublikować, możesz znaleźć implementację na GitHub .

Ten kod jest tak samo wydajny, jak użycie ręcznej, klasycznej forpętli.

Jeśli ten wzorzec często występuje w danych, rozważ użycie innego wzorca, który zipskłada się z dwóch sekwencji i tworzy zakres krotek odpowiadających sparowanym elementom:

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

Implementację zippozostawia się czytelnikowi jako ćwiczenie, ale łatwo wynika z implementacji indices.

(Przed C ++ 17 musiałbyś zamiast tego napisać:)

for (auto items&& : zip(containerA, containerB))
    get<0>(items) = get<1>(items);
Konrad Rudolph
źródło
2
Czy jest jakaś przewaga implementacji indeksów w porównaniu do zwiększenia counting_range? Można by po prostu użyćboost::counting_range(size_t(0), containerA.size())
SebastianK
3
@SebastianK Największą różnicą w tym przypadku jest składnia: moja jest (twierdzę) obiektywnie lepsza w tym przypadku. Ponadto możesz określić rozmiar kroku. Przykłady można znaleźć na połączonej stronie Github, aw szczególności w pliku README.
Konrad Rudolph
Twój pomysł jest bardzo fajny i wymyśliłem użycie counting_range dopiero po obejrzeniu go: wyczyść upvote :) Zastanawiam się jednak, czy daje to dodatkową wartość do (ponownego) wdrożenia tego. Np. Jeśli chodzi o wydajność. Oczywiście ładniejsza składnia, zgadzam się, ale wystarczyłoby napisać prostą funkcję generatora, aby zrekompensować tę wadę.
SebastianK
@SebastianK Przyznaję, że pisząc kod uznałem za dość proste, aby żyć w izolacji bez korzystania z biblioteki (i tak jest!). Teraz prawdopodobnie zapisałbym to jako opakowanie wokół Boost.Range. To powiedziawszy, wydajność mojej biblioteki jest już optymalna. Rozumiem przez to, że użycie mojej indicesimplementacji daje dane wyjściowe kompilatora, które są identyczne z użyciem ręcznych forpętli. Nie ma żadnych kosztów ogólnych.
Konrad Rudolph
Ponieważ i tak używam boostu, w moim przypadku byłoby to prostsze. Napisałem już to opakowanie wokół zakresu doładowania: potrzebuję tylko funkcji z jedną linią kodu. Byłbym jednak zainteresowany, czy wydajność zakresów doładowania również jest optymalna.
SebastianK
38

Aby uzyskać konkretny przykład, po prostu użyj

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

W bardziej ogólnym przypadku możesz użyć Boost.Iterator zip_iterator, z małą funkcją, dzięki której można go używać w pętlach opartych na zakresie. W większości przypadków zadziała to:

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

Przykład na żywo.

Jednak dla pełnowymiarową genericity, prawdopodobnie chcesz coś bardziej jak ten , który będzie działał prawidłowo dla tablic i typów zdefiniowanych przez użytkownika, które nie mają elementu begin()/ end()ale nie mają begin/ endfunkcje w ich nazw. Pozwoli to również użytkownikowi uzyskać konkretny constdostęp za pośrednictwem zip_c...funkcji.

A jeśli jesteś zwolennikiem ładnych komunikatów o błędach, tak jak ja, prawdopodobnie chcesz tego , który sprawdza, czy jakiekolwiek tymczasowe kontenery zostały przekazane do którejkolwiek z zip_...funkcji, i wyświetla ładny komunikat o błędzie, jeśli tak.

Xeo
źródło
1
Dzięki! Jedno pytanie, dlaczego używasz auto &&, co to znaczy &&?
memecs
@memecs: Zalecam przeczytanie tego pytania , a także mojej odpowiedzi, która wyjaśnia, w jaki sposób odbywa się dedukcja i zwijanie odniesienia. Zauważ, że autodziała dokładnie tak samo jak parametr szablonu, aw T&&szablonie jest uniwersalnym odniesieniem, jak wyjaśniono w pierwszym linku, więc auto&& v = 42zostanie wydedukowany jako, int&&a auto&& w = v;następnie zostanie wydedukowany jako int&. Pozwala dopasować lvalues, a także rvalues ​​i pozwolić, aby oba były zmienne, bez tworzenia kopii.
Xeo,
@Xeo: Ale jaka jest przewaga auto && nad auto & w pętli foreach?
Viktor Sehr
@ViktorSehr: Umożliwia powiązanie z elementami tymczasowymi, takimi jak te produkowane przez zip_range.
Xeo,
23
@Xeo Wszystkie linki do przykładów są uszkodzone.
kynan
34

zastanawiam się, dlaczego nikt o tym nie wspomniał:

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

PS: jeśli rozmiary kontenerów nie są zgodne, będziesz musiał umieścić kod w instrukcjach if.

Józef
źródło
9

Istnieje wiele sposobów wykonywania określonych czynności z wieloma kontenerami, jak podano w algorithmnagłówku. Na przykład w podanym przykładzie możesz użyć std::copyzamiast jawnej pętli for.

Z drugiej strony nie ma żadnego wbudowanego sposobu na generalne iterowanie wielu kontenerów poza zwykłą pętlą for. Nie jest to zaskakujące, ponieważ istnieje wiele sposobów iteracji. Pomyśl o tym: możesz iterować przez jeden kontener jednym krokiem, jeden kontener drugim krokiem; lub przez jeden pojemnik, aż dotrze do końca, a następnie zacznij wkładać, przechodząc do końca drugiego pojemnika; lub jeden krok pierwszego pojemnika za każdym razem, gdy całkowicie przejdziesz przez drugi pojemnik, a następnie zacznij od nowa; lub inny wzór; lub więcej niż dwa pojemniki jednocześnie; itp ...

Jeśli jednak chcesz stworzyć własną funkcję w stylu „for_each”, która iteruje przez dwa kontenery tylko do długości najkrótszego, możesz zrobić coś takiego:

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

Oczywiście w podobny sposób możesz stworzyć dowolną strategię iteracji.

Oczywiście możesz argumentować, że po prostu wykonanie wewnętrznej pętli for bezpośrednio jest łatwiejsze niż napisanie niestandardowej funkcji, takiej jak ta ... i miałbyś rację, jeśli zamierzasz to zrobić tylko jeden lub dwa razy. Ale fajną rzeczą jest to, że jest to wielokrotnego użytku. =)

wjl
źródło
Wygląda na to, że musisz zadeklarować iteratory przed pętlą? Próbowałem tego: for (Container1::iterator i1 = c1.begin(), Container2::iterator i2 = c2.begin(); (i1 != end1) && (i2 != end2); ++it1, ++i2)ale kompilator krzyczy. Czy ktoś może wyjaśnić, dlaczego to jest nieważne?
David Doria
@DavidDoria Pierwsza część pętli for to pojedyncza instrukcja. Nie możesz zadeklarować dwóch zmiennych różnych typów w tej samej instrukcji. Zastanów się, dlaczego for (int x = 0, y = 0; ...działa, ale for (int x = 0, double y = 0; ...)nie.
wjl
1
.. możesz jednak mieć std :: pair <Container1 :: iterator, Container2 :: iterator> its = {c1.begin (), c2.begin ()};
lorro
1
Inną rzeczą, na którą należy zwrócić uwagę, jest to, że można to łatwo zmienić w typename...
wariadikę za
8

W przypadku, gdy potrzebujesz iterować jednocześnie tylko na 2 kontenerach, istnieje rozszerzona wersja standardu algorytmu for_each w bibliotece zakresu boost, np .:

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

Kiedy musisz obsłużyć więcej niż 2 pojemniki w jednym algorytmie, musisz bawić się zipem.

carles
źródło
Wspaniale! Jak znalazłeś? Wydaje się, że nie jest to nigdzie udokumentowane.
Michaił
4

innym rozwiązaniem mogłoby być przechwycenie referencji iteratora drugiego kontenera w lambdzie i użycie do tego operatora postinkrementacji. na przykład prosta kopia to:

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

wewnątrz lambdy możesz zrobić cokolwiek, itaa następnie ją zwiększyć. To łatwo rozciąga się na skrzynię z wieloma kontenerami.

Vahid
źródło
3

Biblioteka zakresów zapewnia tę i inne bardzo pomocne funkcje. Poniższy przykład używa Boost.Range . Rangev3 Erica Nieblera powinien być dobrą alternatywą.

#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 uczyni to jeszcze lepszym dzięki powiązaniom strukturalnym:

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
źródło
Ten program nie kompiluje się z 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
Po zmianie std :: tie na boost: tie, skompilowano.
syam
Otrzymuję następujący błąd kompilacji dla wersji z powiązaniem strukturalnym (przy użyciu wersji MSVC 19.13.26132.0i 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
strukturalne powiązania wydają się nie działać z boost::combine: stackoverflow.com/q/55585723/8414561
Dev Null
2

Jestem trochę spóźniony; ale możesz użyć tej (funkcji wariadycznej w stylu 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);

lub to (używając pakietu parametrów funkcji):

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

lub to (używając listy inicjalizującej w nawiasach klamrowych):

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

lub możesz łączyć wektory, jak tutaj: Jaki jest najlepszy sposób łączenia dwóch wektorów? a następnie iteruj po dużym wektorze.

Szymon Marczak
źródło
0

Oto jeden wariant

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

Przykładowe użycie

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