Zusammenführen zweier STL-Vektoren mit einem Wechselmuster

Question

Ich habe zwei STL-Vektoren A und B und muss sie zu einem dritten zusammenführen, wobei die Elemente so geordnet werden sollen, dass jedes n-te Element im Ausgangsvektor zu Vektor B gehört. Mein aktueller Code sieht etwa so aus:

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

Der Vektor c sieht nun wie folgt aus: 4 4 8 4 4 8 ...

Das funktioniert gut, aber ich bin neugierig, ob es nicht eine elegantere Lösung gibt. Gibt es eine Möglichkeit, einen STL-Algorithmus anstelle meiner handgeschriebenen Schleifen zu verwenden?

Answer 1

Dies ist zu speziell, um direkt von <algorithm> . Um die Schleife zu vermeiden, ist ein eigener Iterator erforderlich.

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

Ein bisschen übertrieben, finde ich.

Answer 2

Ich muss zugeben, dass ich die Potatoswatter-Lösung ziemlich mag... ziemlich.

Wie er zeigte, ist dies keine Frage des Algorithmus, sondern der Iteration. Seine Lösung ist jedoch nicht ganz passend, da die Prüfung auf die end der Iteration ist sehr schwierig: Sie erfordert viel Sorgfalt bei der Vorbereitung der Container und der Erstellung der Iteratoren, um undefiniertes Verhalten zu vermeiden.

Ich denke, das Problem könnte viel besser mit einem Konzept ausgedrückt werden, das den Iteratoren sehr ähnlich ist: Ansichten.

Eine Ansicht ist eine Adapterschnittstelle über einen oder mehrere Container. Sie enthält eigentlich selbst nichts (das ist der wichtige Teil). Sie stellt jedoch eine Schnittstelle zur Verfügung, die der eines Containers ähnelt, so dass Sie mit den üblichen Idiomen programmieren können.

Das Schöne an Ansichten ist, dass man sie oft selbst zusammenstellen kann.

Ein Beispiel: eine sehr einfache Ansicht:

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

Für Ihre Frage würden Sie lieber eine 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
{
};

Hier wird das Problem des End-Iterators etwas entschärft, da wir beide Container kennen und somit in der Lage sind, die Iteratoren selbst zu erstellen, wobei wir sicherstellen, dass wir die richtigen Parameter übergeben.

Natürlich kann es etwas mühsamer werden, wenn die Container kein effizientes "Größen"-Mitglied bieten ( list nicht, ist es O(n)).

Das allgemeine Prinzip ist jedoch, dass eine Ansicht Ihnen mehr Kontrolle gibt (und mehr Prüfungen ermöglicht) und sicherer zu verwenden ist, weil Sie die Erstellung der Iteratoren genau kontrollieren.

Beachten Sie, dass in C++0x die interleave_view würde in der Regel eine unbegrenzte Anzahl von Sequenzen aufnehmen können.