C++如何合併，聯合，將Vector的兩個對象相交成新的第三個對象？

Question

我一直在學習Vector，無法完成一些部分。我的代碼和下面的描述。 輸出應該是這樣的：

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 

框架部分：

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

這是迄今爲止代碼：

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

困在這裏：在運營商+ （合併兩個向量），operator-（顯示第一個向量上不存在的數字），union，intersect。另外，我不知道如何創建新的矢量對象（第3和第4）作爲b1和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

如果矢量總是排序，那麼它們可以在O（N）時間內使用以下算法進行合併。

初始化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++; 
    } 

對於減去V1 - V2也，類似的算法可以應用。
警告：我沒有檢查任何這些算法，他們可能需要一些調試或小的調整

初始化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

如前所述，要實施Set操作概念。決定是否仍然需要保留元素和副本的原始順序（如您的示例輸出所示）。如果是這樣，保持你的向量，並在操作過程中構造臨時集合（排序的MyNumber） - 這將是低效的，但是有效的。要處理效率問題，您可能需要更復雜的數據結構。否則，只需保留MyNumber allways排序並在find（）中使用二進制搜索。

接着，作爲操作者的+ - 實現它在操作者而言+ =（類似於操作者=）

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

然後實現+ =含的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; 
} 

注意，operator + =返回mynumber的&但是運算符+返回MyNumber

也最好不要從find（）中拋出，因爲如果值不在容器中，它不是錯誤。更好地返回無效索引，如C中的負數或size（）與stl一樣。