CODEWITHSUNDEEP
c++templatesstrategy-pattern
Nick
Nick

Reputation: 10559

using C++ templates to switch strategies / algorithms

I have a C++ class that might work with linear or binary search.

Currently I have additional member variable that show what search to be used.

I know how I can do the search with Java-like virtual functions (strategy pattern or template method),
but I am curious what is best practice this to be done compile time with templates<>?

Current (simplified) code looks like this:

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

Upvotes: 1

Views: 788

Answers (3)

cdonat
cdonat

Reputation: 2822

The most obvious way is to encapsulate the strategies in types and implement lookup() as a function template:

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);

Alternatively you can specialize the template and use the strategy type as tag only:

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);

Now you might prefer to not have to define the template parameters, but use a function parameter instead. You don't even need templates for that, but just method overloading:

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);

Looks like dynamically choosing the strategy, but is static. You can not do something like this:

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

In that case you'd have to write

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

Beware: all code in this answer is untested. It will contain bugs.

Upvotes: 4

Nir Friedman
Nir Friedman

Reputation: 17714

If you are willing to always commit to which strategy you are going to use at compile time, you can do this:

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);
}

Upvotes: -1

SergeyA
SergeyA

Reputation: 62613

You can use template specialization, provided lookupMethod is known at compile time. For example, you can do it like this:

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);
}

Upvotes: 1

Related Questions