Merge two STL vectors with an alternation pattern

Question

I have two STL vectors A and B and need to merge them into a third one, where the elements should be ordered in a way, that every nth element in the output vector should be of vector B. My current code looks something like this:

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

The vector c now looks like: 4 4 8 4 4 8 ...

This works fine, but I'm curious if there isn't a more elegant solution. Is there any way use a STL algorithm instead of my hand-written loops?

Answer 1

This is too specialized to be covered directly by <algorithm>. Avoiding the loop will require a custom iterator.

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

A little excessive, I think.

Answer 2

I must admit I quite like Potatoswatter solution... quite.

As he demonstrated, this is not an issue of algorithm, but of iteration. However his solution does not quite fit the bill because testing for the end of the iteration is very difficult: it requires much care in the preparation of the containers and the creation of the iterators to avoid undefined behavior.

I think the problem could be much better expressed using a concept that is quite similar to iterators: views.

A view is an Adapter interface over one or several containers. It doesn't actually contain anything itself (that's the important part). It does however exposes an interface similar to that of a container so that you can code with the usual idioms.

The beautiful things about views, is that you can often compose them.

For example, one very simple view:

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

For your question, you would rather create an 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
{
};

Here the issue of the end iterator is somehow alleviated because we know both containers and thus we are able to create the iterators ourselves, ensuring we pass the proper parameters.

Of course it can become a bit more tedious if the containers do not offer an efficient "size" member (list doesn't, it's O(n)).

The general principle however is that a view gives you more control (and allows more checks), and is safer to use because you control precisely the creation of the iterators.

Note that in C++0x the interleave_view would typically accomodate an unbounded number of sequences.

Answer 3

I'm sorry for posting my answer in here, but since I posted without a real registration I'm not able to reply or comment anymore.

At first to the comments. @DyP: In general my example is as I expect the code. The only change I've made is that, if vector b has too few elements, I'd start again, though in reality, this usually won't be the case. So I intend to stop on a.end(), regardless of how many b elements are left.

@AndreyT: Since this was only a minimal example there was no error checking for better readability.

Now to the answers: @Potatoswatter: Though your solution is, as you already wrote, a little excessive I thank you for your custom iterator example. It's a nice STL training. And most importantly you clarified my merge operation in reality is just an alternative iteration pattern.

@DyP: Your solutions seems to be what I thought might be a "STL-like solution". It helps to hide away the actual iteration code and make the actual merge call readable.

Thank you both for your answers, and again, I'm sorry to post my answer here instead of the comments.