C++ how to merge, union, intersect two object of Vector into the new third object?

Question

I've been learning about Vector and can't finish some parts. My code and the description on below. The output should be like this :

b1 size = 0
b1 beginning capacity = 10
b1 empty? 1

b2 size = 0
b2 beginning capacity = 10
b2 empty? 1

b1 : []
b2 : [ 2 4 6 8 10 12 14 16 18 20 ]
b1 + b2 : [ 2 4 6 8 10 12 14 16 18 20 ] // not working

b2 duplicate : [ 1 2 2 4 4 6 6 8 8 10 12 14 16 18 20 ] // not working
b2 remove duplicate : [ 1 2 4 6 8 10 12 14 16 18 20 ] // not working

b1 : [ 1 2 3 4 5 6 7 8 9 ]
b1 size : 9
b1 capacity : 10
b2 : [ 1 2 4 6 8 10 12 14 16 18 20 ]
b2 size = 11
b2 capacity = 20

b1+b2 : [ 1 2 3 4 5 6 7 8 9 1 2 4 6 8 10 12 14 16 18 20 ] // nw
b1-b2 : [ 3 5 7 9]                                        // nw
b1 union b2 : [ 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 ]     // nw
b1 intersect b2 : [ 1 2 4 6 8 ]                           // nw

b3+b4 : [ 3 5 7 9 3 5 7 9 ]   // nw
b3-b4 : []                    // nw
b3 union b4 : [ 3 5 7 9 ]     // nw
b3 intersect b4 : [ 3 5 7 9 ] // nw

the skeleton part :

#include RunMyNumber.cpp


int main() {
MyNumber<int> b1;
cout << "b1 size = " << b1.size() << endl;
cout << "b1 beginning capacity = " << b1.capacity() << endl;
cout << "b1 empty? " << b1.empty() << endl << endl;

MyNumber<int> b2;
cout << "b2 size = " << b2.size() << endl;
cout << "b2 beginning capacity = " << b2.capacity() << endl;
cout << "b2 empty? " << b2.empty() << endl << endl;

for(int i=1;i<=10;i++)
{
    b2.push_back(i*2);
}

cout << "b1 : " << b1.toString() << endl;
cout << "b2 : " << b2.toString() << endl;

cout << "b1 + b2 : " << (b1 + b2).toString() << endl << endl;

for(int i=1;i<10;i++)
{
    b1.push_back(i);
}

for(int i=0;i<4;i++){
    b2.duplicate(i+i,1);
}

b2.insert(0,1);
cout << "b2 duplicate : " << b2.toString() << endl;

b2.removeDuplicate();
cout << "b2 remove duplicate : " << b2.toString() << endl << endl;

cout << "b1 : " << b1.toString() << endl;
cout << "b1 size = " << b1.size() << endl;
cout << "b1 capacity = " << b1.capacity() << endl;
cout << "b2 : " << b2.toString() << endl;
cout << "b2 size = " << b2.size() << endl;
cout << "b2 capacity = " << b2.capacity() << endl << endl;

cout << "b1 + b2 : " << (b1 + b2).toString() << endl;
cout << "b1 - b2 : " << (b1 - b2).toString() << endl;
cout << "b1 union b2 : " << b1.myUnion(b2).toString() << endl;
cout << "b1 intersect b2 : " << b1.myIntersect(b2).toString() << endl << endl;

MyNumber<int> b3;
b3 = b1 - b2;

MyNumber<int> b4(b3);
cout << "b3 : " << b3.toString() << endl;
cout << "b4 : " << b4.toString() << endl << endl;

MyNumber<int> b5;
b5 = b3 + b4;
cout << "b3 + b4 : " << b5.toString() << endl;
b5 = b3 - b4;
cout << "b3 - b4 : " << b5.toString() << endl;
cout << "b3 union b4 : " << b3.myUnion(b4).toString() << endl;
cout << "b3 intersect b4 : " << b3.myIntersect(b4).toString() << endl << endl;

return 0;
  }

Here is the code so far :

#include "MyNumber.cpp"
#include <iostream>
#include <string>
#include <sstream>
#include <stdexcept>
#include <algorithm>

using namespace std;

template <typename B>
class MyNumber
{
private :
    static const size_t BEGINNING_CAPACITY =10;
    size_t _capacity;           
    size_t _size;       
    B* _data; // array' element

public :
    // Constructor
    MyNumber<B>() : _capacity(BEGINNING_CAPACITY),
                _size(0),
                    _data(new B[BEGINNING_CAPACITY])
    {}

    //Destructor
    ~MyNumber<B>()
    {
        delete[] _data;
    }

    //Copy Constructor
    MyNumber<B>(const MyNumber<B>& OtherNumber) :
                    _capacity(OtherNumber._capacity),
                    _size(OtherNumber._size),
                    _data(new B[_capacity])
    {
        for(size_t i = 0; i < _size; i++)
            _data[i] = OtherNumber._data[i];
    }

    // template function swap STL algorithm
    void swap(MyNumber<B>& OtherNumber)
    {
        swap(_size, OtherNumber._size);
        swap(_capacity, OtherNumber._capacity);
        swap(_data, OtherNumber._data);
    }

    MyNumber<B>& operator= (const MyNumber<B>& OtherNumber)
    {

        MyNumber<B> copy(OtherNumber);
        exchange(copy);
        return *this;
    }

    // Operator indexing []
    B& operator[] (size_t index)
    {
        if(index < 0 || index >= _size)
        {
            throw out_of_range("Index operator [] out of range");
        }
        return _data[index];
    }

    //Function for adding new element
    void push_back(const B& elemen)
    {
        if(_size == _capacity)
        {
            expand(2 *_capacity);
        }
        _data[_size] = elemen;
        _size++;
    }

    //Function for inserting
    void insert(size_t index, const B& elemen)
    {
        if(index < 0 || index > _size) 
        {
            throw out_of_range("index insert out of range");
        }
        if(_size == _capacity)
        {
            expand(2 * _capacity);
        }

        for(size_t i = _size; i > index; i--)
        {
            _data[i] = _data[i-1];
        }
        _data[index] = elemen;
        _size++;
    }

    //Function for expanding the size of capacity
    void expand(size_t newCapacity)
    {
        _capacity = newCapacity;
        B* newData = new B[newCapacity];
        for(size_t i = 0; i < _size; i++)
            newData[i] = _data[i];
        delete[] _data;
        _data = newData;
    }

    //Funtion for returning capacity
    size_t capacity()
    {
        return _capacity;
    }

    //Function for returning size
    size_t size()
    {
        return _size;
    }

    //Function for checking the vector
    bool empty()
    {
        return _size == 0;
    }

    //Function for representing the vector
    string toString()
    {
        ostringstream oss;
        oss << "[ ";
        for(int i = 0; i < _size; ++i)
            oss << _data[i] << " ";
        oss << "]";
        return oss.str();
    }

    //Function for searching particular element
    int find(const B& elemen){
        for(int i=0;i<_size;i++){
            if(_data[i] == elemen)
                return i;
        }
        string exception = "Data not found!";
        throw exception;}

stuck here : on the operator+ (merge two vectors), operator- (to show the numbers on the first vector that doesn't exist on the second), union, intersect. Also, I don't know how to make new vector's objects( the 3rd and 4th) as the result from the previous operation of b1 and b2.

    MyNumber<B>& operator+ (MyNumber<B>& OtherNumber)
    {auto cmp = [] ( const B& b1, const B& b2 ) { return b1.value() < b2.value() ; } ;
      sort( MyNumber.begin(), MyNumber.end(), cmp ) ; // sort first on ascending v
      sort( OtherNumber.begin(), OtherNumber.end(), cmp ) ; // sort second on ascending v
      merge( MyNumber.begin(), MyNumber.end(), OtherNumber.begin(), OtherNumber.end(),
      back_inserter(b3??), cmp ) ; // merge first and second into third

    // append contents of second to first
      MyNumber.insert( MyNumber.end(), OtherNumber.begin(), OtherNumber.end() ) ;

    // sort first on descending length of str
      sort( MyNumber.begin(), MyNumber.end(),
           [] ( const B& b1, const B& b2 ) { return b1.str().size() > b2.str().size() ; } ) ;

    }

    MyNumber<B>& operator- (MyNumber<B>& OtherNumber)
            {

    }

            void duplicate(size_t index, size_t n)
            {
            }

            void removeDuplicate()
            {
            }
    MyNumber<B>& myUnion(MyNumber<B>& OtherNumber)
    {
        vec_union(MyNumber<B> &, OtherNumber)
        {
            if ( OtherNumber.empty() )
             return MyNumber;

            MyNumber<B>::iterator found = find(MyNumber.begin(), MyNumber.end(), OtherNumber.back());
            if ( found == MyNumber.end() )
             {
                  // all good, element not already in v1, so insert it.
              B value = OtherNumber.back();
              MyNumber.push_back(value);
                  OtherNumber.pop_back(); // remove back element
                  return vec_union(MyNumber, OtherNumber);
             }
             else
            {
                  // element was already in v1, skip it and call vec_union again
            OtherNumber.pop_back(); // remove back element
                return vec_union(MyNumber, OtherNumber);
            }
        }
    }

           MyNumber<B>& myIntersect(MyNumber<B>& OtherNumber){
           }







};

Answer 1

If the vectors are always sorted, then they can be merged in O(N) time using the following algorithm.

Initialize I1 = 0, I2 = 0.

while ( I1 < V1.size() || I2 < V2.size() )
  if ( V1[I1] == V2[I2] ) {
    newVec.push_back( V1[I1] ); // if duplicates are to be entered, then push back twice.
    I1++;
    I2++;
  } else if ( V1[I1] < V2[I2] ) { // or I2 == V2.size()
    newVec.push_back( V1[I1] ); 
    I1++;
  } else { // or I1 == V1.size()
    newVec.push_back( V2[I2] ); 
    I2++;
  }

For subtracting V1 - V2 also, similar algorithm can be applied.
Caveat: I haven't checked either of these algorithms, they may need some debugging or minor tweaks

Initialize I1 = 0, I2 = 0.

while ( I1 < V1.size() ) //|| I2 < V2.size() ) (No need to iterate till end of V2)
  if ( V1[I1] == V2[I2] ) {
    //newVec.push_back( V1[I1] ); // Don't push back if element is common.
    I1++;
    I2++;
  } else if ( V1[I1] < V2[I2] ) { // or I2 == V2.size()
    newVec.push_back( V1[I1] ); 
    I1++;
  } else { // or I1 == V1.size()
    //newVec.push_back( V2[I2] ); 
    I2++;
  }

Answer 2

As discussed, you want to implement Set operations concept. Decide if you still need to preserve original order of elements and duplicates (as your sample output suggests). If so, keep your vector as is, and construct temporary set (sorted MyNumber) during operation - this will be inefficient, but valid. To deal with efficiency you might need more elaborate data structure. Otherwise just keep MyNumber allways sorted and use binary search in find().

Next, as of operator+ - implement it in terms of operator+= (similar to operator=)

MyNumber<B> operator+ (const MyNumber<B>& OtherNumber)
{
  MyNumber<B> result(*this);
  result += OtherNumber;
  return result;
}

Then implement += with push_back

MyNumber<B>& operator+= (MyNumber<B>& OtherNumber)
{
  // todo expand() once
  for (size_t i = 0; i < OtherNumber.size(); ++i)
    push_back(OtherNumber[i]);
  return *this;
}

note that operator+= returns MyNumber& but operator+ returns MyNumber

also it's better not to throw from find(), as it is not an error if value is not in container. Better return invalid index, negative as in C or size() as stl does.