25

我正在尝试创建一个从 std::vector 中删除重复项的通用函数。因为我不想为每个向量类型创建一个函数，所以我想让它成为一个模板函数，可以接受任何类型的向量。这是我所拥有的：

//foo.h

Class Foo {

template<typename T>
static void RemoveVectorDuplicates(std::vector<T>& vectorToUpdate);

};

//foo.cpp

template<typename T>
void Foo::RemoveVectorDuplicates(std::vector<T>& vectorToUpdate) {
for(typename T::iterator sourceIter = vectorToUpdate.begin(); (sourceIter != vectorToUpdate.end() - 1); sourceIter++) {
        for(typename T::iterator compareIter = (vectorToUpdate.begin() + 1); compareIter != vectorToUpdate.end(); compareIter++) {
            if(sourceIter == compareIter) {
                vectorToUpdate.erase(compareIter);
            }
        }
    }
}

//SomeOtherClass.cpp

#include "foo.h"

...

void SomeOtherClass::SomeFunction(void) {
    std::vector<int> myVector;

    //fill vector with values

    Foo::RemoveVectorDuplicates(myVector);
}

我不断收到链接器错误，但它编译得很好。关于我做错了什么的任何想法？

更新：根据 Iraimbilanja 给出的答案，我去重写了代码。但是，以防万一有人想让工作代码执行 RemoveDuplicates 函数，这里是：

//foo.h

Class Foo {

    template<typename T>
    static void RemoveVectorDuplicates(T& vectorToUpdate){
        for(typename T::iterator sourceIter = vectorToUpdate.begin(); sourceIter != vectorToUpdate.end(); sourceIter++) {
            for(typename T::iterator compareIter = (sourceIter + 1); compareIter != vectorToUpdate.end(); compareIter++) {
            if(*sourceIter == *compareIter) {
                compareIter = vectorToUpdate.erase(compareIter);
            }
        }
    }
};

事实证明，如果我在签名中指定 std::vector，迭代器将无法正常工作。所以我不得不采用更通用的方法。此外，当擦除 compareIter 时，循环的下一次迭代会产生指针异常。擦除后 compareIter 的后减量可以解决该问题。我还修复了迭代器比较和第二个循环中 compareIter 初始化中的错误。

更新 2：

我看到这个问题又得到了赞成票，所以我想用一个更好的算法来更新它，这个算法使用了一些 C++14 的优点。我的前一个只有在向量中存储的类型实现 operator== 并且它需要一堆副本和不必要的比较时才有效。而且，事后看来，没有必要让它成为一个类的成员。这种新算法允许自定义比较谓词，在发现重复项时缩小比较空间，并显着减少副本数量。名称已更改为erase_duplicates更好地符合 STL 算法命名约定。

template<typename T>
static void erase_duplicates(T& containerToUpdate) 
{
    erase_duplicates(containerToUpdate, nullptr);
}

template<typename T>
static void erase_duplicates(T& containerToUpdate, 
  std::function<bool (typename T::value_type const&, typename T::value_type const&)> pred) 
{
    auto lastNonDuplicateIter = begin(containerToUpdate);
    auto firstDuplicateIter = end(containerToUpdate);
    while (lastNonDuplicateIter != firstDuplicateIter) {
        firstDuplicateIter = std::remove_if(lastNonDuplicateIter + 1, firstDuplicateIter, 
            [&lastNonDuplicateIter, &pred](auto const& compareItem){
            if (pred != nullptr) {
                return pred(*lastNonDuplicateIter, compareItem);
            }
            else {
                return *lastNonDuplicateIter == compareItem;
            }
        });
        ++lastNonDuplicateIter;
    }
    containerToUpdate.erase(firstDuplicateIter, end(containerToUpdate));
}
4

6 回答 6

33

简答

在头文件中定义函数，最好在类定义中。

长答案

在 .cpp 中定义模板函数意味着它不会#included 进入任何翻译单元：它只对定义它的翻译单元可用。

因此RemoveVectorDuplicates必须在头文件中定义，因为这是编译器可以文本替换模板参数的唯一方法，从而实例化模板，生成可用的类。

对于这种不便，有两种解决方法

首先，您可以从 .cpp 中删除并在标题末尾#include "foo.h"添加另一个：

#include "foo.cpp"

这使您可以一致地组织文件，但不提供单独编译的通常优势（更小的依赖项，更快和更少的编译）。

其次，您可以在 .cpp 中定义模板函数，并为所有将要使用的类型显式实例化它。

例如，这可以放在 .cpp 的末尾以使该函数可与ints 一起使用：

template void Foo::RemoveVectorDuplicates(std::vector<int>*);

但是，这假设您只使用模板来节省一些输入，而不是提供真正的通用性。

于 2009-01-28T19:30:04.767 回答
5

您可以选择的一种方法是首先std::sort()使用向量，然后使用预先存在的std::unique()函数删除重复项。排序需要 O(nlog n) 时间，之后删除重复项只需要 O(n) 时间，因为所有重复项都出现在一个块中。您当前的“all-vs-all”比较算法需要 O(n^2) 时间。

于 2009-01-29T04:39:46.810 回答
2

您不能在 .cpp 文件中实现模板函数。完整的实现必须在任何实例化的地方都可见。

只需在标题中的类定义内定义函数即可。这是实现模板函数的常用方法。

于 2009-01-28T19:26:28.987 回答
1

我建议使用更“通用”的方法，而不是传递一个容器，只接收两个迭代器。

像 It remove_duplicates(It first, It last) 这样的东西，会返回一个迭代器，所以你可以像 remove: 一样调用v.erase(remove_duplicates(v.begin(), v.end()), v.end())。

template <typename It>
It remove_duplicate(It first, It last)
{
  It current = first;
  while(current != last) {
    // Remove *current from [current+1,last)
    It next = current;
    ++next;
    last = std::remove(next, last, *current);
    current = next;
  }
  return last;
}
于 2009-01-28T22:04:24.457 回答
0

与您的问题无关（已经解释过），为什么这是一个静态函数而不是全局驻留在命名空间中？这将有点 C++-ier。

于 2009-01-28T19:48:31.623 回答
0

我不认为代码编译....

vectorToUpdate.erase where std::vector* vectorToUpdate.... 有没有其他人注意到应该有 & 的地方有 *？该代码绝对没有被编译。如果要使用指向向量的指针，则必须使用“->”而不是“。” 我知道这实际上有点挑剔，但它指出编译器甚至不关心你的代码......

于 2009-01-28T20:00:47.387 回答