Implementing Strategy Pattern with Polymorphism/Templates

1. The Problem: When One Algorithm Doesn't Fit All

Imagine you are developing different types of robots. Each robot needs to perform actions like search(), attack(), and defend(). You might initially use inheritance to define different robot types based on their primary behavior, for example, a LinearSearchRobot and a SpiralSearchRobot.

But what happens when you need to combine different attack and defend behaviors? You quickly run into the "class explosion" problem we saw with the Decorator pattern, where you need classes like LinearSearchPinchAttackRunDefendRobot, SpiralSearchPunchAttackHideDefendRobot, etc. The inheritance hierarchy becomes a rigid, unmaintainable web of combined behaviors.

This inflexibility highlights the need for a better design. We need to vary the algorithms independently from the Robot object that uses them.

2. The Solution: Encapsulating Algorithms

The Strategy pattern addresses this by defining a family of algorithms, encapsulating each one, and making them interchangeable. The pattern has two main participants:

1. Context: The class that needs to perform an algorithm (e.g., our Robot class). It maintains a reference to a Strategy object.
2. Strategy: An interface that defines the common signature for all supported algorithms.
3. Concrete Strategy: A specific implementation of an algorithm (e.g., LinearSearch, PinchAttack).

The Context delegates the work to its Strategy object instead of implementing the behavior itself.

This design allows the algorithm to be selected and swapped at runtime, independently from the client using the Context.

3. Implementation 1: Runtime Polymorphism

The classic implementation of the Strategy pattern uses runtime polymorphism via inheritance and virtual functions. Let's see how the Robot example is refactored using this approach.

The video's implementation uses raw pointers, which raises ownership questions. In modern C++, we'd manage the strategy objects' lifetimes with smart pointers. Here is a more robust implementation for a sorting context, using std::shared_ptr.

Under the Hood: The Cost of Runtime Polymorphism

Your interest in low-level mechanics is key here. While flexible, this approach has performance implications you should be aware of:

1. Vtable Overhead: The call strategy->sort(data) is a virtual function call. This involves:

   • Dereferencing the object's vptr to find the vtable.
   • Indexing into the vtable to get the function address.
   • Calling the function via that address (an indirect function call).
     This is more work than a direct function call and can hinder branch prediction.

2. Optimization Barrier: Because the exact function being called is unknown at compile time, the compiler cannot perform optimizations like inlining. The virtual call acts as an "optimization barrier."

3. Memory Management: Using std::shared_ptr is safe but introduces its own overhead. Every time a shared_ptr is copied (e.g., passed by value), its internal reference count must be atomically updated. These atomic operations can be surprisingly expensive, especially in multi-threaded contexts, as they require synchronization across CPU cores.

4. Implementation 2: Compile-Time Polymorphism (Policy-Based Design)

What if you know which algorithm you need at compile time? C++ templates offer a powerful and highly efficient alternative. This variation of the Strategy pattern is commonly known as Policy-Based Design.

Instead of an inheritance hierarchy, you pass the strategy (now called a "policy") as a template parameter.

Here is the core idea:

// A policy is just a class with a static method. No virtual functions!
struct AscendingSortPolicy {
    template <typename T>
    static void sort(std::vector<T>& data) {
        std::sort(data.begin(), data.end());
    }
};

// The Context is now a template, parameterized by the policy.
template <typename T, typename SortingPolicy>
class PolicyBasedContainer {
    // ...
    void sort() {
        // Direct, compile-time call to the policy's method.
        SortingPolicy::sort(data);
    }
    // ...
};

// Usage: The type itself defines the strategy.
PolicyBasedContainer<int, AscendingSortPolicy> myContainer;

Under the Hood: The Power of Static Polymorphism

This approach has significant advantages that align with your goal of understanding high-performance C++:

1. No Runtime Overhead: The call SortingPolicy::sort(data) is resolved at compile time. There is no vptr, no vtable, and no indirect function call.
2. Compiler Optimization: Since the compiler knows exactly which function is being called, it can inline the call, effectively replacing the function call with the function's body. This eliminates function call overhead entirely and opens the door for further optimizations across the function boundary.
3. No Pointer Indirection: The context object doesn't need to store pointers to strategies, simplifying memory layout and management.

The primary trade-off is the loss of runtime flexibility. The algorithm is "baked in" to the type at compile time. You cannot change the sorting policy of a PolicyBasedContainer<int, AscendingSortPolicy> object at runtime.

5. Other C++ Alternatives

Modern C++ provides even more tools that can be used to implement strategy-like behavior:

• std::function: A type-erased wrapper that can hold any callable entity (function pointers, lambdas, functors). This allows for runtime flexibility without a rigid inheritance hierarchy. It combines the flexibility of runtime polymorphism with the convenience of not needing a base class. However, it has its own overhead, including potential heap allocation for the wrapped callable. The final segment of the "C++ - strategy" video (LINK from 09:20) demonstrates this approach.

• std::variant and std::visit: For a closed set of strategies, std::variant provides a type-safe union to hold one of the strategy types by value. This can be more cache-friendly than pointer-based approaches. std::visit provides a way to perform an operation on the currently active type. The "Rethink Polymorphism in C++" video (LINK, from 51:37) introduces this as a powerful alternative to traditional polymorphism.

#include <iostream>
#include <string>
#include <memory>

// Strategy Interface
class IFormatStrategy {
public:
    virtual ~IFormatStrategy() = default;
    virtual std::string format(const std::string& data) const = 0;
};

// Concrete Strategies
class JsonStrategy : public IFormatStrategy {
public:
    std::string format(const std::string& data) const override {
        return "{ \"data\": \"" + data + "\" }";
    }
};

class XmlStrategy : public IFormatStrategy {
public:
    std::string format(const std::string& data) const override {
        return "<data>" + data + "</data>";
    }
};

// Context
class Serializer {
private:
    std::unique_ptr<IFormatStrategy> strategy_;
public:
    // Strategy can be changed at runtime
    void setStrategy(std::unique_ptr<IFormatStrategy> strategy) {
        strategy_ = std::move(strategy);
    }

    std::string serialize(const std::string& data) {
        if (!strategy_) throw std::runtime_error("Strategy not set!");
        return strategy_->format(data);
    }
};

#include <iostream>
#include <string>

// Policies (no common base class or virtual functions)
struct JsonFormatPolicy {
    static std::string format(const std::string& data) {
        return "{ \"data\": \"" + data + "\" }";
    }
};

struct XmlFormatPolicy {
    static std::string format(const std::string& data) {
        return "<data>" + data + "</data>";
    }
};

// Templated Context
template <typename FormatPolicy>
class Serializer {
public:
    std::string serialize(const std::string& data) {
        return FormatPolicy::format(data);
    }
};

Conclusion

We've seen that the Strategy pattern is a fundamental tool for creating flexible and maintainable systems by decoupling an object from the algorithms it uses.

Key Takeaways:

• Intent: To define a family of algorithms, encapsulate each one, and make them interchangeable.
• Runtime Polymorphism (Classic Strategy):
  • Mechanism: Inheritance and virtual functions.
  • Pros: Highly flexible; strategies can be swapped at any time.
  • Cons: Incurs runtime overhead from virtual dispatch, can be an optimization barrier, and may involve performance costs from memory management (e.g., atomic operations in shared_ptr).
• Compile-Time Polymorphism (Policy-Based Design):
  • Mechanism: Templates.
  • Pros: Extremely performant due to compile-time resolution, enabling inlining and other optimizations.
  • Cons: Inflexible at runtime; the strategy is fixed when the code is compiled.

Understanding the trade-offs between these two powerful C++ implementation techniques is crucial for writing code that is not only well-designed but also highly performant.

Next Lesson Preview:
In our next lesson, we will cover the Observer pattern. We'll shift our focus from structuring an object's internal behavior to managing communication between objects. The Observer pattern provides a clean way for an object (the "subject") to notify a list of other objects (the "observers") about state changes, without being tightly coupled to them. This is fundamental to building reactive and event-driven systems.