使用 C++ 模板切换策略/算法

Question

我有一个 C++ class 可以用于线性或二进制搜索。

目前我有额外的成员变量显示要使用的搜索。

我知道如何使用类似 Java 的虚函数（策略模式或模板方法）进行搜索，
但我很好奇在编译时使用模板<> 完成此操作的最佳做法是什么？

当前（简化）代码如下所示：

int MyArray::lookup(const String &key) const{
    if (lookupMethod == LINEAR_SEARCH)
        return lookupLinearSearch(key);
    else
        return lookupBinarySearch(key);
}

Answer 1

您可以使用模板特化，前提是 lookupMethod 在编译时已知。例如，您可以这样做：

template <int METHOD> 
int MyArray::lookup(const String& key); // Not implemented
template<>
int MyArray::lookup<LINEAR_SEARCH>(const String& key) {
    return lookupLinearSearch(key);
}

template<>
int MyArray::lookup<BINARY_SEARCH>(const String& key) {
    return lookupBinarySearch(key);
}

Answer 2

如果您愿意始终承诺在编译时使用哪种策略，您可以这样做：

enum class METHOD {LINEAR_SEARCH, BINARY_SEARCH};

template <METHOD M>
int MyArray::lookup(const String & key) {
    if (M == METHOD::LINEAR_SEARCH)
        return lookupLinearSearch(key);
    else
        return lookupBinarySearch(key);
}

Answer 3

最明显的方法是将策略封装在类型中并将 lookup() 实现为函数模板：

namespace searchStrategy {
    struct linearSearch {
        static auto lookup(const MyArray& a, const String &key)
        -> int {
            return a.lookupLinearSearch(key);
        };
    };

    struct binarySearch {
        static auto lookup(const MyArray& a, const String &key)
        -> int {
            return a.lookupBinarySearch(key);
        };
    };
}

class MyArray {
    public:
        template <typename LookupStrategy>
        auto lookup(const String &key) const
        -> int {
            return LookupStrategy::lookup(*this, key);
        };
};

// ...
auto myArray = MyArray{};
mArray.lookup<searchStrategy::binarySearch>("asdf"s);

或者，您可以专门化模板并将策略类型仅用作标签：

namespace searchStrategy {
    struct linearSearch {};    
    struct binarySearch {};
}

class MyArray {
    public:
        template <typename LookupStrategy>
        int lookup(const String &key) const;
        template <>
        int lookup<searchStrategy::linearSearch>(const String &key) const {
            return lookupLinearSearch(key);
        };
        template <>
        int lookup<searchStrategy::binarySearch>(const String &key) const {
            return lookupBinarySearch(key)
        };
};


// ...
auto myArray = MyArray{};
mArray.lookup<searchStrategy::binarySearch>("asdf"s);

现在您可能更愿意不必定义模板参数，而是使用函数参数。你甚至不需要模板，只需要方法重载：

namespace searchStrategy {
    struct LinearSearchT {};    
    struct BinarySearchT {};
    static const LinearSearchT linearSearch;
    static const BinarySearchT binarySearch;
}

class MyArray {
    public:
        int lookup(const String &key,
                   const searchStrategy::linearSearchT strategy) const {
            return lookupLinearSearch(key);
        };
        int lookup(const String &key,
                   const searchStrategy::binarySearchT strategy) const {
            return lookupBinarySearch(key)
        };
};


// ...
auto myArray = MyArray{};
mArray.lookup("asdf"s, searchStrategy::binarySearch);

看起来像是动态选择策略，但实际上是静态的。你不能这样做：

mArray.lookup("asdf"s, (someReason) ?
                           searchStrategy::binarySearch :
                           searchStrategy::linearSearch);

在那种情况下你必须写

if( someReason )
    mArray.lookup("asdf"s, searchStrategy::binarySearch);
else
    mArray.lookup("asdf"s, searchStrategy::linearSearch);

注意：此答案中的所有代码都未经测试。它将包含错误。

使用 C++ 模板切换策略/算法

using C++ templates to switch strategies / algorithms

c++

templates

strategy-pattern