How to interleave two vectors of different sizes?

user_17845255 0
Viewed 76

I have two vectors

vector<int> first_v = {1, 4, 9, 16, 8, 56};
vector<int> second_v = {20, 30};

And the goal is to combine those vectors in specific order like that (basically program first prints one value of the first_v vector and then one value of second_v vector):

Expected Output:
1 20 4 30 9 16 8 56

I'm very close to solution but the problem is that if one vector is shorter than another, then program will print '0'.

Problem output:
1 20 4 30 9 0 16 0

Here is the code I tried to solve this problem

merge_vect(first_v, second_v);

vector<int> merge_vect(const vector<int> & a, const vector<int> & b){
  vector<int> vec(a.size() + b.size());

  for (int i = 0; i < vec.size(); i++){
    cout << a[i] << " ";
    cout << b[i] << " ";
  }  
  return vec;
}

What can I do in order to solve this problem?

vector c++
1 Answers

You could keep one iterator to each vector and add from the vector(s) that have not reached their end() iterator.

Example:

#include <iostream>
#include <vector>

std::vector<int> merge_vect(const std::vector<int>& avec,
                            const std::vector<int>& bvec)
{
    std::vector<int> result;
    result.reserve(avec.size() + bvec.size());

    for(auto ait = avec.begin(), bit = bvec.begin();
        ait != avec.end() || bit != bvec.end();) 
    {
        if(ait != avec.end()) result.push_back(*ait++);
        if(bit != bvec.end()) result.push_back(*bit++);
    }

    return result;
}

int main() {
    std::vector<int> first_v = {1, 4, 9, 16, 8, 56};
    std::vector<int> second_v = {20, 30};

    auto result = merge_vect(first_v, second_v);

    for(auto val : result) std::cout << val << ' ';
}

Output:

1 20 4 30 9 16 8 56

A possible optimization could copy from both vectors for as long as both have elements and then copy the rest from the larger vector in one go:

std::vector<int> merge_vect(const std::vector<int>& avec,
                            const std::vector<int>& bvec)
{
    std::vector<int> result;
    result.reserve(avec.size() + bvec.size());
    auto ait = avec.begin(), bit = bvec.begin();
    
    // copy while both have more elements:
    for(; ait != avec.end() && bit != bvec.end(); ++ait, ++bit) {
        result.push_back(*ait);
        result.push_back(*bit);
    }

    // copy the rest
    if(ait != avec.end()) result.insert(result.end(), ait, avec.end());
    else if(bit != bvec.end()) result.insert(result.end(), bit, bvec.end());

    return result;
}
user_75822470
Related