Vereinen Sie zwei STL-Vektoren mit einem Wechselmuster

Question

Ich habe zwei STL Vektoren A und B und muss sie in einen dritten zusammenführen, wobei die Elemente so sortiert sein sollen, dass jedes n-te Element im Ausgabevektor vom Vektor B stammt. Mein aktueller Code sieht ungefähr so aus:

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

std::vector::const_iterator bIt = b.begin();
for(std::vector::const_iterator aIt = a.begin();
    aIt != a.end(); ++aIt)
{
    c.push_back(*aIt);
    if((c.size() + 1) % STEP == 0)
    {
        c.push_back(*bIt);
        ++bIt; //angenommen, b ist groß genug
    }
}

Der Vektor c sieht jetzt so aus: 4 4 8 4 4 8 ...

Dies funktioniert gut, aber ich frage mich, ob es keine elegantere Lösung gibt. Gibt es einen Weg, einen STL-Algorithmus anstelle meiner selbst geschriebenen Schleifen zu verwenden?

Answer 1

Dies ist zu spezialisiert, um direkt von abgedeckt zu werden. Um die Schleife zu vermeiden, wird ein benutzerdefinierter Iterator benötigt.

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 wenig übertrieben, finde ich.

Answer 2

Ich muss zugeben, dass mir Potatoswatters Lösung ziemlich gut gefällt... ziemlich.

Wie er demonstriert hat, handelt es sich hier nicht um ein Algorithmusproblem, sondern um ein Iterationsproblem. Allerdings passt seine Lösung nicht ganz, weil das Testen des Ende der Iteration sehr schwierig ist: Es 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 ausgedrückt werden, wenn man ein Konzept verwendet, das ziemlich ähnlich zu Iteratoren ist: Ansichten.

Eine Ansicht ist eine Adapter-Schnittstelle über einen oder mehrere Container. Sie enthält tatsächlich nichts (das ist der wichtige Teil). Sie stellt jedoch eine Schnittstelle bereit, die der eines Containers ähnelt, sodass Sie mit den üblichen Idiomen coden können.

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

Zum Beispiel eine sehr einfache Ansicht:

/// Erlaubt nur, einen Bereich des Containers zu sehen:
/// std::vector v(40, 3); // { 3, 3, 3, ... }
/// auto rv = make_range_view(v, 4, 5);
/// rv zeigt die Elemente im Bereich [4,9)
/// Im Debug-Modus wird sichergestellt, dass der Bereich ausreichend groß ist.
template 
class range_view
{
};

Für Ihre Frage sollten Sie eher eine interleave_view erstellen:

/// Ermöglicht das Einflechten von Elementen aus 2 Containern jeweils in ihrem eigenen Tempo
/// std::vector v(40, 3);
/// std::set s = /**/;
/// 
/// auto iv = make_interleave_view(v, 3, s, 1);
/// Nimmt 3 Elemente aus v, dann 1 aus s, dann 3 aus v, usw...
template 
class interleave_view
{
};

Hier wird das Problem des Enditerators irgendwie gemildert, weil wir beide Container kennen und somit in der Lage sind, die Iteratoren selbst zu erstellen und sicherzustellen, dass wir die richtigen Parameter übergeben.

Natürlich kann es etwas mühsamer werden, wenn die Container kein effizientes "size"-Element bieten (list bietet das nicht, es ist O(n)).

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

Beachten Sie, dass in C++0x das interleave_view typischerweise eine unbegrenzte Anzahl von Sequenzen aufnehmen würde.