为迭代器实现泛型方法的正确方法

Question

假设我想做这样的事情（这只是一般想法的一个例子）：

class AbstractSortingMethod
{
     public:
     template<class iterator>
     virtual void Sort(iterator begin, iterator end) = 0;
};

这在 C++ 中显然是非法的。

实现相同目标的正确设计是什么？

我知道我可以模板化 class 而不是模板化方法，但这不允许类型推导，除非我实现某种类似工厂的方法。

另一件事是 - 我是否应该 "blindly trust" 作为模板参数传递的类型是迭代器？

根据评论中的要求：

可能还有很多其他（甚至更好）的例子，但这就是我现在想到的。

让我们想象一个程序，它应该在许多不同容器的上下文中对许多不同排序方法的性能进行基准测试。

有一个类似于 SortingMethodTest 的 class，它将未排序的数据保存在许多不同的容器（如列表、常规数组和向量等）中。我们将排序方法仿函数传递给它，它继承自本文前面提到的 AbstractSortingMethod 之类的东西 post。基准程序如下所示：

遍历所有容器 -> startTimer() -> 将给定容器的迭代器传递给排序方法运行它 -> stopTimer() -> 记录时间 -> 继续

Answer 1

loop over all containers -> startTimer() -> pass the iterators of given container to sorting method and run it -> stopTimer() -> record time -> continue

基于此，你要的是模板，而不是多态。您需要一个采用排序算法和一对迭代器的函数模板：

template <class Algorithm, class Range>
void time_sort(Algorithm algo, Range&& range)
{
    using std::begin;
    using std::end;

    // start timer
    algo(begin(first), end(last));
    // stop timer
    // do stuff with the difference
}

然后你只需编写一堆不同的函数对象来实现你想要计时的各种类型。这个的标准库版本是这样的：

struct StdSort {
    template <class Iterator>
    void operator()(Iterator first, Iterator last) {
        std::sort(first, last);
    }
};

然后您将使用该函数模板，例如：

time_it(StdSort{}, gimme_vector<int>());
time_it(StdSort{}, gimme_list<Foo>());

如果您想测试新的排序算法，只需创建一个新类型：

struct MergeSort {
    template <class Iterator>
    void operator()(Iterator first, Iterator last) {
        // ...
    }
};

struct WhosebugSort {
    template <class Iterator>
    void operator()(Iterator first, Iterator last) {
        // see xkcd 1185
    }
};

并将其作为第一个参数传入。冲洗并重复。

time_sort(MergeSort{}, gimme_vector<int>());
time_sort(WhosebugSort{}, gimme_list<Foo>());

为迭代器实现泛型方法的正确方法

Proper way of implementing generic methods for iterators

c++

oop

templates

virtual-functions