Merge two alternating STL vectors

Question

I have two vectors STL A and B and you need to combine them into a third one, where the elements must be ordered so that every n-th element in the output vector is a vector B. My current code looks something like:

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

Vector c now looks like this: 4 4 8 4 4 8 ...

This works great, but I'm curious if there is a more elegant solution. Is there a way to use the STL algorithm instead of my handwritten loops?

Answer 1

It is too specialized to be directly covered by <algorithm> . To avoid a loop, a custom iterator is required.

 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 bit excessive, I think.

Answer 2

I have to admit that I really like the Potatoswatter solution ... quite.

As he demonstrated, this is not an algorithm problem, but an iteration. However, its solution is not entirely suitable for the bill, because testing for the end iteration is very difficult: it requires great care when preparing containers and creating iterators to avoid undefined behavior.

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

A view is an adapter interface through one or more containers. It actually contains nothing (which is an important part). However, it does provide an interface similar to the container interface, so you can encode regular idioms.

The great things about looks are 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 better 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 problem of the final iterator is somehow facilitated, because we know both containers and, thus, we can create iterators ourselves, ensuring the transfer of the correct parameters.

Of course, this can become a little more tedious if the containers do not have an effective member of the "size" ( list not, this is O (n)).

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

Note that in C ++ 0x interleave_view will usually contain an unlimited number of sequences.