lawZ lawZ - 4 years ago 86
C++ Question

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

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 Source

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++;
  }
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download