如何创建一个对模板类执行操作的静态模板成员函数？

Question

我正在尝试创建一个通用函数,从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));
}

Answer 1

简答

在头文件中定义函数,最好在类定义中.

答案很长

在.cpp中定义模板函数意味着它不会#include进入任何翻译单元:它只能用于它定义的翻译单元.

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

这种不便有两种解决方法

首先,你可以删除#include "foo.h"从在.cpp并添加另外一个,在结束了的标题:

#include "foo.cpp"

这使您可以一致地组织文件,但不提供单独编译的常见优势(较小的依赖性,更快和更罕见的编译).

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

例如,这可以在.cpp的末尾,以使该函数可用于ints:

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

但是,这假设您只使用模板来保存一些输入,而不是提供真正的通用性.

Answer 2

您可以选择的另一种方法是先std::sort()使用向量,然后使用预先存在的std::unique()函数删除重复项.排序需要O(nlog n)时间,并且在此之后删除重复项只需要O(n)时间,因为所有重复项都出现在单个块中.您当前的"全部与全部"比较算法需要O(n ^ 2)时间.