CODEWITHSUNDEEP
c++stl
meguli
meguli

Reputation: 1526

C++ STL Interleave two ranges

I did something to achieve interleaving two ranges. Here is the problem.

Say I have two ranges [a1, b1), call R1 and [a2, b2) call R2. For now, assume their std::distance results are the same, say n. I want to write an algorithm

std::interleave(a1, b1, a2, b2, bool swap)

This will reorder the elements in a way that one element of R2 will be followed an element of R1, through all 2n elements. Depending of the value of swap, it should also be reordered as one element of R1 is followed by an element of R2.

I did this using an additional storage and two for loops. This solution is easy. I could also come up with an in-place solution probably, if I tried a little longer. But what I want is, I want to achieve this thing by assembling algorithms from the STL. How can you solve this problem using STL? It is better if the solution is in-place but I am also open to usage of additional storage, as long as we use algorithms from the STL.

EDIT: The permutation of the elements in the given ranges should not be changed. In other words, this should actually be something like stable_interleave. This is why I couldn't come up with something that uses std::merge.

APPLICATION: One application of this is the conversion of video and image formats from planar to non-planar or semi-planar.

Upvotes: 0

Views: 1399

Answers (1)

user4581301
user4581301

Reputation: 33931

My pitch of using std::merge can fail. I'm not creative enough to see why anyone would write merge so that it could, but it is violating the requirements for Compare as pointed out in the comments below, so someone could.

Regardless, merge is an overkill solution. It is fewer lines of code hiding extra effort because merge's intended usage is for a more complicated job than we do here.

Example:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <list>
#include <deque>

template<typename IN1,
         typename IN2,
         typename OUT>
inline OUT interleave(IN1 it1,
                      IN1 end1,
                      IN2 it2,
                      IN2 end2,
                      OUT out)
{
    // interleave until at least one container is done
    while (it1 != end1 && it2 != end2) 
    {
        // insert from container 1
        *out = *it1;
        out++;
        it1++;
        // insert from container 2
        *out = *it2;
        out++;
        it2++;
    }
    if (it1 != end1) // check and finish container 1
    {
        return std::copy (it1, end1, out);
    }
    else if (it2 != end2)// check and finish container 2
    {
        return std::copy (it2, end2, out);
    }
    return out; // both done
}

int main()
{
    // fill the containers  with numbers
    std::vector<int> in1 = {1,3,5,7,9};
    std::list<int> in2 = {8,6,4,2};

    // construct output container of sufficient size.
    // Could also use empty container and *_inserter
    std::deque<int> out(in1.size() + in2.size());

    // Container-agnostic. reads from vector and list and stores in deque
    interleave(in1.begin(), in1.end(),
               in2.begin(), in2.end(),
               out.begin());
    for (int val: out)
    {
        std::cout << val << ' ';
    }
}

Note: rather than implementing with an option to swap the order of the inputs and making all users of interleave pay for it, the caller should call with the order of input parameters reversed.

Upvotes: 1

Related Questions