Scalanie dwóch wektorów STL z układem naprzemiennym

Question

Mam dwa wektory STL A i B i trzeba je połączyć w trzeci, gdzie elementy należy uporządkować w taki sposób, aby każdy n-ty element wektora wyjściowego wektor B. Mój obecny kod wygląda mniej więcej tak:

std::vector<int> a(10, 4); 
std::vector<int> b(10, 8); 
std::vector<int> c; 
static const std::size_t STEP(3); 

std::vector<int>::const_iterator bIt = b.begin(); 
for(std::vector<int>::const_iterator aIt = a.begin(); 
    aIt != a.end(); ++aIt) 
{ 
    c.push_back(*aIt); 
    if((c.size() + 1) % STEP == 0) 
    { 
     c.push_back(*bIt); 
     ++bIt; //assume b is large enough 
    } 
} 

wektor c teraz wygląda: 4 4 8 4 4 8 ...

działa to dobrze, ale jestem ciekaw, czy istnieje nie jest bardziej eleganckim rozwiązaniem. Czy istnieje sposób użycia algorytmu STL zamiast moich ręcznie pisanych pętli?

Answer 1

Jest to zbyt specjalistyczna funkcja, aby można ją było bezpośrednio chronić przez <algorithm>. Unikanie pętli wymaga niestandardowego iteratora.

template< typename I1, typename I2 > 
struct interleave_iterator 
    : std::iterator< forward_iterator_tag, typename I1::value_type > { 
    using typename I1::value_type; 

    I1 i1; 
    I2 i2; 
    size_t cnt, stride; 

    interleave_iterator(I1 in1, I2 in2, size_t in_stride=0, size_t in_off=0) 
     : i1(in1), i2(in2), cnt(in_off), stride(in_stride) {} 

    value_type &operator*() const { return cnt? * i1 : * i2; } 
    interleave_iterator &operator++() { 
     if (++ cnt == stride) { 
      cnt = 0; 
      ++ i2; 
     } else ++ i1; 
     return *this; 
    } 
    value_type *operator->() const 
     { return cnt? i1.operator->() : i2.operator->(); } 

    interleave_iterator &operator++(int) 
     { interleave_iterator r = *this; ++ *this; return r; } 

    friend bool operator== 
     (interleave_iterator const &lhs, interleave_iterator const &rhs) 
     { return lhs.i1 == rhs.i1 && lhs.i2 == rhs.i2; } 
    friend bool operator!= 
     (interleave_iterator const &lhs, interleave_iterator const &rhs) 
     { return ! (lhs == rhs); } 
}; 

Trochę przesadzam, tak myślę.

Answer 2

Muszę przyznać, że całkiem lubię rozwiązanie Potatoswatter ... całkiem.

Jak zademonstrował, nie jest to kwestia algorytmu, ale iteracji. Jednak jego rozwiązanie nie pasuje do rachunku, ponieważ testowanie dla iteracji end jest bardzo trudne: wymaga dużej ostrożności przy przygotowywaniu pojemników i tworzeniu iteratorów, aby uniknąć nieokreślonego zachowania.

Myślę, że problem mógł być znacznie lepiej wyrażony za pomocą koncepcji, która jest dość podobna do iteratorów: widoków.

Widok to interfejs adaptera na jeden lub kilka kontenerów. W rzeczywistości nie zawiera niczego samego (to jest ważna część). Ma jednak interfejs podobny do interfejsu kontenera, dzięki czemu można kodować za pomocą zwykłych idiomów.

Piękne rzeczy na temat widoków, to fakt, że często można je komponować.

Na przykład, jeden bardzo prosty widok:

/// Only allow to see a range of the container: 
/// std::vector<int> v(40, 3); // { 3, 3, 3, ... } 
/// auto rv = make_range_view(v, 4, 5); 
/// rv exposes the elements in the range [4,9) 
/// in debug mode, asserts that the range is sufficiently large 
template <typename Container> 
class range_view 
{ 
}; 

Na pytanie, czy raczej stworzyć interleave_view:

/// Allow to interleave elements of 2 containers each at its own pace 
/// std::vector<int> v(40, 3); 
/// std::set<int> s = /**/; 
/// 
/// auto iv = make_interleave_view(v, 3, s, 1); 
/// Takes 3 elements from v, then 1 from s, then 3 from v, etc... 
template <typename C1, typename C2> 
class interleave_view 
{ 
}; 

Tutaj kwestia iteratora końcowego jest w jakiś sposób złagodzony, ponieważ wiemy, Oba pojemniki i dzięki temu jesteśmy w stanie samodzielnie tworzyć iteratory, zapewniając odpowiednie parametry.

Oczywiście może stać się nieco bardziej żmudny, jeśli pojemniki nie oferują wydajnego elementu "rozmiaru" (list nie, to O (n)).

Ogólna zasada jest taka, że ​​widok zapewnia większą kontrolę (i pozwala na więcej sprawdzeń) i jest bezpieczniejszy w użyciu, ponieważ dokładnie kontrolujesz tworzenie iteratorów.

Należy zauważyć, że w C++ 0x typ interleave_view byłby typowy dla nieograniczonej liczby sekwencji.