Как создать статическую функцию-член шаблона, которая выполняет действия над классом шаблона? - PullRequest
Новая
       9

Как создать статическую функцию-член шаблона, которая выполняет действия над классом шаблона?

25 голосов
/ 28 января 2009

Я пытаюсь создать универсальную функцию, которая удаляет дубликаты из 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);
}

Я получаю ошибку компоновщика, но он компилируется нормально. Есть идеи, что я делаю не так?

ОБНОВЛЕНИЕ: Основываясь на ответе Ираимбиланья, я пошел и переписал код. Однако на тот случай, если кто-то хочет, чтобы рабочий код выполнял функцию 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 во втором цикле.

ОБНОВЛЕНИЕ 2:

Я видел, что этот вопрос получил еще один голос, поэтому решил обновить его с помощью лучшего алгоритма, использующего некоторые достоинства C ++ 14. Мой предыдущий работал только в том случае, если тип, сохраненный в векторе, реализовал оператор == и требовал кучу копий и ненужных сравнений. И, оглядываясь назад, нет необходимости делать его членом класса. Этот новый алгоритм учитывает пользовательский предикат сравнения, сокращает пространство сравнения при обнаружении дубликатов и делает значительно меньшее количество копий. Имя было изменено на 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));
}

Ответы [ 6 ]

31 голосов
/ 28 января 2009

Короткий ответ

Определите функцию в заголовке, предпочтительно внутри определения класса.

Длинный ответ

Определение функции шаблона внутри .cpp означает, что она не получит #include d в любых единицах перевода: она будет доступна только той единице перевода, в которой она определена.

Следовательно, RemoveVectorDuplicates должно быть определено в заголовке, так как это единственный способ, которым компилятор может заменить текстовые аргументы шаблона текстом, следовательно создает экземпляр шаблона, создавая пригодный для использования класс.

Есть два способа обойти это неудобство

Сначала , вы можете удалить #include "foo.h" из .cpp и добавить еще один, в end заголовка : 

#include "foo.cpp"

Это позволяет вам систематизировать файлы последовательно, но не дает обычных преимуществ раздельной компиляции (меньшие зависимости, более быстрая и редкая компиляция).

Второй , вы можете просто определить функцию шаблона в .cpp и явно создать ее экземпляр для всех типов, с которыми она будет когда-либо использоваться.

Например, это может идти в конце .cpp, чтобы сделать функцию пригодной для использования с int s: 

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

Тем не менее, предполагается, что вы используете шаблоны только для того, чтобы сохранить некоторую типизацию, а не для обеспечения подлинности.

5 голосов
/ 29 января 2009

Один из возможных вариантов - сначала std::sort() вектор, а затем использовать существующую функцию std::unique() для удаления дубликатов. Сортировка занимает время O (nlog n), а удаление дубликатов занимает всего O (n), так как все дубликаты появляются в одном блоке. Ваш текущий алгоритм сравнения "все против всех" занимает время O (n ^ 2).

2 голосов
/ 28 января 2009

Вы не можете реализовать функцию шаблона в файле .cpp. Полная реализация должна быть видна везде, где она создается.

Просто определите функцию внутри определения класса в заголовке. Это обычный способ реализации шаблонных функций.

1 голос
/ 29 января 2009

Я предлагаю использовать более «общий» подход, вместо передачи контейнера просто получите два итератора.

Что-то вроде этого: remove_duplicates (сначала это, это последнее), и он вернет итератор, так что вы можете вызвать как удалить: 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;
}
0 голосов
/ 28 января 2009

Я не думаю, что код компилируется ....

vectorToUpdate.erase, где std :: vector * vectorToUpdate .... кто-нибудь еще замечает, что есть *, где должен быть символ &? этот код определенно не компилируется. если вы собираетесь использовать указатель на вектор, вы должны использовать «->» вместо «.» Я знаю, что на самом деле это немного придирчиво, но указывает на то, что компилятору даже не нужен ваш код ...

0 голосов
/ 28 января 2009

Независимо от вашей проблемы (которая уже была объяснена), почему эта статическая функция, а не находится глобально в пространстве имен? Это было бы немного C ++ - ier.

...