C++ 使用继承来调整算法

Question

由于 Dijkstra 算法和 Prim 算法非常相似，我想创建一个基本算法类(我将其称为“Greedy”或其他名称)，然后我想继承 Greedy 并根据类。

我认为归结为这一点。我想重用大部分算法，但调整一两个操作。

class BaseAlg
{
public:
    BaseAlg(std::vector<int> data)  //constructor sums a vector and stores result
    {
        int accum = 0;
        for (unsigned int i = 0; i < data.size(); ++i)
            accum += data[i];
        result = accum;
    }

protected:
    int result;
};

class Alg1  //A second, similar algorithm
{
public:
    Alg1(std::vector<int> data)
    {
        //I want to reuse BaseAlg except use *= instead of +=; 
    }
};

因此，一种方法是只有一个类 (BaseAlg) 并向该类的构造函数添加一个“选择器”值。我会打开该选择器值并在不同情况下执行 += 或 *= 。我觉得应该有一种方法可以通过继承来实现这种重用，因为 Greedy 和 Prim 以及 Greedy 和 Dijkstra 之间存在“是一种”关系。但我不太明白。有什么想法吗？

Answer 1

你应该为这种“重用但也不是真正的继承”使用模板。

例如，在您的情况下，基本上可以归结为:

template<class Op, class Iter, class T> T reduce(const Op & op, Iter begin, Iter end, T init = T()) {
    T accum = init;
    for(Iter i = begin; i != end; ++i)
        accum = Op(accum, *i);
    return accum;
}

然后你可以像这样使用它:

std::vector<int> data; // fill data
int sum = reduce(add<int>, data.begin(), data.end());
int prod = reduce(mul<int>, data.begin(), data.end(), 1);

你需要像这样定义 add 和 mult 的地方:

template<class T> T add(T a, T b) { return a + b; }
template<class T> T mult(T a, T b) { return a * b; }

现在，正如 Jerry Coffin 指出的那样，这只是为了说明目的，使用 STL，您可以简单地执行以下操作:

#include <functional>
#include <numeric>
int sum = std::accumulate(data.begin(), data.end(), 0, std::plus<int>);