在使用 operator+ 连接两个向量之前，从 <T> 类型的向量中删除索引

Question

我的函数接受 2 个向量，比较每个向量中的元素是否重复。如果找到重复项，我想从第二个向量中删除该元素。

调用擦除方法时出现编译器错误。我相信这是因为 Vector<T> 与 vector<int>::iterator 不是同一类型，但我不确定如何解决此问题。

有人可以建议我如何解决这个问题吗？

template <typename T>
std::vector<T> operator+(const std::vector<T>& v1, const std::vector<T>& v2)
{
    typename std::vector<T> newVectorOne = v1;
    typename std::vector<T> newVectorTwo = v2;
    for (std::vector<int>::const_iterator i = newVectorOne.begin(); i != newVectorOne.end(); i++)
    {
        for (std::vector<int>::const_iterator j = newVectorTwo.begin(); j != newVectorTwo.end(); j++)
        {
            if (*i == *j)
            {
                newVectorTwo.erase(newVectorTwo.begin() + j); //error here
            }
        }
    }
    newVectorOne += NewVectorTwo;
    return newVectorOne;
}

错误日志：

1>------ Build started: Project: Assignment2, Configuration: Debug Win32 ------
1>main.cpp
1>c:\users\rm\documents\comp3512_2\assignments\assignment2\assignment2.h(67): error C2678: binary '+': no operator found which takes a left-hand operand of type 'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>' (or there is no acceptable conversion)
1>        with
1>        [
1>            _Ty=int
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.11.25503\include\vector(332): note: could be 'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>> std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>::operator +(int) const'
1>        with
1>        [
1>            _Ty=int
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.11.25503\include\vector(361): note: or       'std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>> std::operator +<std::_Vector_val<std::_Simple_types<_Ty>>>(int,std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>)'
1>        with
1>        [
1>            _Ty=int
1>        ]
1>c:\program files (x86)\microsoft visual studio17\community\vc\tools\msvc.11.25503\include\vector(243): note: or       'std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>> std::operator +<std::_Vector_val<std::_Simple_types<_Ty>>>(int,std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>)'
1>        with
1>        [
1>            _Ty=int
1>        ]
1>c:\users\rm\documents\comp3512_2\assignments\assignment2\assignment2.h(67): note: while trying to match the argument list '(std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>, std::_Vector_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>)'
1>        with
1>        [
1>            _Ty=int
1>        ]
1>c:\users\rm\documents\comp3512_2\assignments\assignment2\main.cpp(36): note: see reference to function template instantiation 'std::vector<int,std::allocator<_Ty>> operator +<int>(const std::vector<_Ty,std::allocator<_Ty>> &,const std::vector<_Ty,std::allocator<_Ty>> &)' being compiled
1>        with
1>        [
1>            _Ty=int
1>        ]
1>Done building project "Assignment2.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Answer 1

问题是您在这一行将两个迭代器加在一起：

newVectorTwo.erase(newVectorTwo.begin() + j); //error here

这样的操作不存在：您只需要一个递增和取消引用的迭代器，或者一个递增的整数偏移量，在需要删除时将其转换为迭代器。以后一种解决方案为模板，您可以更改外部循环，使 j 为 size_t 并从 0 变为 newVectorTwo.size()（不包括）。

请记住 erase 也会使迭代器在处和擦除点之后失效，因此如果它实际上擦除任何内容（除了最后一个元素，因为在这种情况下循环会在之后立即退出） - 所以使用 j 作为递增迭代器的方法通常不会像你所拥有的那样工作。在 vector 中使用索引解决了这个问题：除了由 begin().

创建的临时迭代器之外，您根本没有对迭代器的引用

性能

对于任何显着大小的向量，您的解决方案的性能都将非常差。两个嵌套循环和 erase 调用使其成为 O(n^3) 解决方案（更具体地说 O(m*n^2) 如果 v1 和 v2 的大小为 m 和 n 分别）。

一个更简单的解决方案是创建 newVectorTwo 最初为空，然后添加每个元素 push_back 这是 而不是 重复，而不是试图从完全填充的向量中删除重复项。此 push_back 在 O(1) 摊销时间内运行，这将减少到 O(n^2)。您也可以去掉 newVectorTwo 并将元素直接附加到 newVectorOne 和 return 上。不过，您需要更改最外层迭代以使用索引，以避免迭代器失效。

如果您想要预期的 O(n)（实际上是 O(n + m)）解决方案，您可以使用 v1 的内容填充 std::unordered_map 并将其用于查找，而不是使用两个嵌套循环。

在使用 operator+ 连接两个向量之前，从 <T> 类型的向量中删除索引

remove index from vector of type <T> before concatenating two vectors with operator+

c++

vector

erase

性能