алгоритм — дизайн класса C ++: ковариантность
Я хочу реализовать ряд алгоритмов, которые работают на графике и возвращают оценки для пар узлов, указывающих, похожи ли эти узлы. Алгоритмы должны работать на одной паре узлов и на всех возможных парах узлов. В последнем случае коллекция / матрица должна быть возвращена.
Алгоритмы происходят из
class SimilarityAlgorithm {
public:
Base(const Graph& G);
virtual double run(node u, node v) = 0; // indices for nodes in the graph
virtual ScoreCollection& runAll() = 0;
}
Теперь алгоритмы различаются по использованию памяти. Некоторые алгоритмы могут быть симметричными, а оценки для (u, v) и (v, u) идентичны. Это требует разных типов ScoreCollection, которые должны быть возвращены. Примером может служить разреженная матрица и треугольная матрица, которые оба являются производными от ScoreCollection,
Это будет сводиться к ковариантным типам возврата:
class SpecificAlgorithm : SimilarityAlgorithm {
public:
double run(node u, node v);
// The specific algorithm is symmetric and thus uses a symmetric matrix to save memory
SymmetricScoreCollection& runAll();
}
- Является ли этот подход подходящим решением для этой проблемы?
- Должен ли быть представлен тот факт, что все коллекции реализованы в виде матриц?
Решение
Ваш дизайн кажется подходящим для проблемы, которую вы описываете.
Проблема:
Тем не менее, есть проблема с вашим SpecificAlgorithm : runAll() не возвращает тот же тип, что и виртуальная функция базового класса. Поэтому он не будет вызываться (или, скорее всего, ваш код не будет компилироваться из-за отсутствия виртуальной функции).
Решение:
Используйте также полиморфный подход для ScoreCollection, сделав SymmetricScoreCollection производный класс ScoreCollection :
class SymetricScoreCollection: public ScoreCollection {
//define the member functions to access the values virtual
...
};
class SpecificAlgorithm : public SimilarityAlgorithm {
public:
double run(node u, node v);
// The specific algorithm is symmetric and thus uses a symmetric matrix to save memory
ScoreCollection& runAll();
};
На самом деле это приложение шаблон фабричного метода, со следующими ролями:
- Схожесть Алгоритм это фабрика,
- SpecificAlgorithm — конкретный завод
- ScoreCollection — это продукт
- SymetricScoreCollection — это конкретный продукт
Дополнительное замечание:
Возврат ссылки на ScoreCollection от runAll() приносит некоторые риски. предполагать sa это конкретный алгоритм.
В следующем заявлении:
ScoreCollection sc = sa.runAll();
sa.runAll() возвращает ссылку на SymetricScoreCollection, но он скопирует указанный объект в sc, сделав его ScoreCollection. нарезка происходит, и полиморфизм не будет работать.
Однако следующее утверждение будет успешным:
ScoreCollection& rsc = sa.runAll();
потому что rsc является ссылкой, и он все равно будет ссылаться на оригинал SymetricScoreCollection объект, возвращенный sa.runAll()и все будет работать как задумано.
Вы видите, что очень легко иметь незамеченные ошибки при возврате ссылок. Я бы предложил вернуть указатель вместо ссылки.
Другие решения
detector