0

我一直在学习 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;}

卡在这里：在运算符+（合并两个向量）上，运算符-（显示第一个向量上不存在第二个向量的数字），联合，相交。另外，我不知道如何将新向量的对象（第 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){
           }







};
4

2 回答 2

2

如果向量总是排序的，那么可以使用以下算法在 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++;
  }
于 2013-10-16T11:19:09.177 回答
0

如前所述，您希望实现 Set 操作概念。决定是否仍需要保留元素和重复项的原始顺序（如示例输出所示）。如果是这样，请保持您的向量不变，并在操作期间构造临时集（排序的 MyNumber） - 这将是低效的，但有效。为了提高效率，您可能需要更精细的数据结构。否则，只需保持 MyNumber 始终排序并在 find() 中使用二进制搜索。

接下来，从 operator+ 开始 - 按照 operator+= 实现它（类似于 operator=）

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& 但 operator+ 返回 MyNumber

最好不要从 find() 中抛出，因为如果值不在容器中，这不是错误。更好地返回无效索引，如 C 中的负数或 stl 中的 size()。

于 2013-10-16T12:14:15.417 回答