在vector c++中实现一个操作符函数

Question

嗨，我想为我的向量类实现一个操作符函数。

函数应该接受两个预先排序的向量v1和v2作为运算符的形参。operator函数返回一个Vector对象，该对象将v2中所有在v1中常见的元素从v1中移除。

例如v3 = v1 - v2;式中v1 = {2,8,12,17,22}， v2 ={17,18,22,30}。

因此v3应该是{2,8,12}。

我已经尝试过这个代码，它不显示我想要的，当我试图显示什么是在v3它显示{2,8,12,17,22}。有人能帮忙吗?或者解释我需要实现什么算法才能使其工作

template<class T>
MyVector<T> operator-(MyVector<T>& v1,MyVector<T>& v2)
{
MyVector<T> v3;
T temp;
for(int i=0;i<v1.getCount();i++)
{
temp = v1.at(i);
if(!v2.Find(temp))
{
v3.push_back(temp);
}
}
return v3;
}

使用的向量函数

template <class T>
bool MyVector<T>::Find(T& element)
{
while(start != end)
{
if(*start==element)
{
return true;
}
start++;
}
return false;
}
template <class T>
void MyVector<T>::push_back(const T& element)
{
if(count == (capacity - 1))
{
MyVector::resize(capacity * 2); //double the size of vector
}
*end = element; //add the element to the back of the vector
end++;  //move the vector end pointer by 1
count++; //+1 to the current size of the vector
}

Answer 1

我可以建议使用std::set_difference吗?

vector v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
vector v2 = {1, 3, 5, 7, 9};
vector<int> v3;
std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));
// v3 now contains {2, 4, 6, 8}

https://godbolt.org/z/n4oKqq

Answer 2

可以用O(n + m)代替上面提供的O(n x m)解决方案，如下所示:

int i=0, j=0;    
while(i < v1.getCount() && j < v2.getCount()) {
if(v1.at(i) == v2.at(j)) {
i++;
j++;
} else if(v1.at(i) < v2.at(j)) {
v3.push_back(v1.at(i));
i++;
} else {
j++;
}
}    

while(i < v1.getCount()) {  // push back any remaining elements
v3.push_back(v1.at(i));
i++;
}

---

注意:从问题来看，不清楚每个向量的值是否唯一，以及如何处理重复的值。

例如，输入

v1={1, 3, 7, 7, 7, 7, 8, 8}

v2={2, 4, 7, 7, 9}

上述解决方案将产生

v3={1, 3, 7, 7, 8, 8}.

---

如果这不是你想要的，那么你可能需要添加一些以下内容:

• 为v1和v2添加while循环，以在处理之前根除重复项:

  while(i < v1.getCount() && j < v2.getCount()) {
  while((i+1) < v1.getCount() && v1.at(i) == v1.at(i+1))
  i++;
  while((j+1) < v2.getCount() && v2.at(j) == v2.at(j+1))
  j++;
  // ...
  }
  while(i < v1.getCount()) {
  while((i+1) < v1.getCount() && v1.at(i) == v1.at(i+1))
  i++;
  // ...
  }
  

  result:v3={1, 3, 8}

• 检查v3，如果最后一个元素与你试图push_back()的元素相同。

  result:v3={1, 3, 7, 8}

• 使用std::unordered_set<T>来存储在v1和v2中发现的重叠元素，并为v1中遇到的每个后续元素做find()，以检查它过去是否有重叠元素。

  std::unordered_set<>在搜索元素时的平均时间复杂度为0(1)，但这当然会使用额外的辅助空间。

  result:v3={1, 3, 8, 8}

• 合并前面两个项目符号点

  result:v3={1, 3, 8}

有许多方法可以解决这个问题，这取决于您期望作为输出的内容。