algorithm - Finding union of 2 sorted arrays (with duplicates) -

i'm trying find union of 2 sorted arrays (with duplicates) feel i'm not coming elegant code (what have works btw, feel can reduce lines of code). lets have 2 vectors = {1,3,3,4,4,4,5,7} , b = {1,3,3,3,5,5,5,6,8,9} , want store union in vector called unionvector (which 1,3,4,5,6,7,8,9)

here's code:

#include <iostream> #include <vector> using namespace std;  // prints contents of vector void printvector(vector<int> a){   if(a.size() == 0)     return;   else{     for(int = 0; < a.size(); i++)       cout << a[i] << '\t';   }   cout << endl; }  // print union of 2 sorted arrays duplicates void printunion(int *a, int asize, int *b, int bsize){   if(asize == 0 && bsize == 0)     return;   else{      vector<int> unionvector;      int = 0;     int j = 0;     int last = 0;      // insert smaller of first element regardless     if(a[i] < b[j]){       unionvector.push_back(a[i]);       i++;     }     else if (b[j] < a[i]){       unionvector.push_back(b[j]);       j++;     }     else{// both equal numbers        unionvector.push_back(a[i]);       i++;       j++;     }      // traverse both loops 1 increment @ time     while(i < asize && j < bsize){       last = unionvector[unionvector.size() - 1];        if(a[i] < b[j]){         if(last != a[i])           unionvector.push_back(a[i]);         i++; // increment in either case       }       else if(b[j] < a[i]){         if(last != b[j])           unionvector.push_back(b[j]);         j++;       }       else{         // both of numbers equal         if(last != a[i])           unionvector.push_back(a[i]);         i++;         j++;       }     }      // lets if 1 array wasn't complete     while(i < asize){       last = unionvector[unionvector.size() - 1];        if(last != a[i])         unionvector.push_back(a[i]);       i++;     }      while(j < bsize){       last = unionvector[unionvector.size() - 1];        if(last != b[i])         unionvector.push_back(b[j]);       j++;     }      printvector(unionvector);   } }  int main(){   int a[] = {1,3,3,4,4,4,5,7};   int b[] = {1,3,3,3,5,5,5,6,7,7,8,9};    printunion(a,8,b,12);    return 0; } 

thing since there can duplicates check element inserted last element inserted in unionvector. need make sure don't try 'last' element when unionvector empty, thats why i'm inserting 1 element in unionvector anyways. appreciate if can suggest way can check without needing insert 1 element first (i thinking of having flag variable checks if unionvector empty or not, feel messy)

edit 1:

• this isn't homework problem. practising interviews

edit 2:

• i can't use built in functions

edit 3:

• some people getting confused if c++ position. can use language want

if both arrays sorted, it's matter of skipping ahead 1 iterator or other or both if there's match.

so like:

void printunion(int* a, int asize, int* b, int bsize) {     int *aend = + asize, *bend = b + bsize;     std::vector<int> unionvec;      (; != aend; ) {         if (b == bend) {             // copy of             while (a != aend) {                 unionvec.push_back(*a);                 = std::upper_bound(a + 1, aend, *a);             }             break;         }          if (*b < *a) {             unionvec.push_back(*b);             b = std::upper_bound(b + 1, bend, *b);         }          else {             unionvec.push_back(*a);             if (*b == *a) {                 b = std::upper_bound(b + 1, bend, *b);             }             = std::upper_bound(a + 1, aend, *a);         }     }      // copy of b     while (b != bend) {         unionvec.push_back(*b);         b = std::upper_bound(b + 1, bend, *b);     }      printvector(unionvec); } 

if can't use upper_bound directly, implement function yourself. copying implementation this reference:

template<class forwardit, class t> int* upper_bound(int* first, int* last, const int value) {     int* it;     int count = last - first;     int step;      while (count > 0) {         = first;          step = count / 2;          += step;         if (value >= *it) {             first = ++it;             count -= step + 1;         }         else {             count = step;         }     }      return first; } 

or non-binary-search version:

int* upper_bound(int* first, int* last, const int value) {     (; first < last && *first == value; ++first) {         ;     }      return first; } 

now that's pretty verbose, , that's why standard provides algorithm directly set_union:

void printunion(int* a, int asize, int* b, int bsize) {     std::vector<int> unionvec;      // union     std::set_union(a, + asize, b, b + bsize, std::back_inserter(unionvec));      // remove dupes     unionvec.erase(std::unique(unionvec.begin(), unionvec.end()), unionvec.end());      printvector(unionvec); }