Runtime Selection (Virtual Functions)

Runtime selection uses virtual functions to choose algorithms at runtime. The algorithm is selected dynamically from configuration, user input, or other runtime conditions. This approach trades compile-time performance for runtime flexibility.

The approach

In runtime Strategy, algorithms inherit from a common base class with virtual methods:

#include <vector>
#include <memory>
#include <iostream>
#include <algorithm>

// Abstract Strategy base class
class SortStrategy {
public:
    virtual ~SortStrategy() = default;
    virtual void sort(std::vector<int>& data) = 0;
    virtual std::string name() const = 0;
};

// Concrete strategy implementations
class QuickSortStrategy : public SortStrategy {
public:
    void sort(std::vector<int>& data) override {
        std::sort(data.begin(), data.end(),
                  [](int a, int b) { return a < b; });
        std::cout << "Sorted with QuickSort\n";
    }

    std::string name() const override {
        return "QuickSort";
    }
};

class MergeSortStrategy : public SortStrategy {
public:
    void sort(std::vector<int>& data) override {
        std::stable_sort(data.begin(), data.end(),
                        [](int a, int b) { return a < b; });
        std::cout << "Sorted with MergeSort\n";
    }

    std::string name() const override {
        return "MergeSort";
    }
};

class HeapSortStrategy : public SortStrategy {
public:
    void sort(std::vector<int>& data) override {
        std::make_heap(data.begin(), data.end());
        std::sort_heap(data.begin(), data.end());
        std::cout << "Sorted with HeapSort\n";
    }

    std::string name() const override {
        return "HeapSort";
    }
};

// Context class using runtime strategy selection
class DataProcessor {
private:
    std::vector<int> data;
    std::unique_ptr<SortStrategy> strategy;

public:
    DataProcessor(std::unique_ptr<SortStrategy> strategy)
        : strategy(std::move(strategy)) {}

    // Change strategy at runtime!
    void set_strategy(std::unique_ptr<SortStrategy> new_strategy) {
        strategy = std::move(new_strategy);
    }

    void add_data(int value) {
        data.push_back(value);
    }

    void process() {
        if (!strategy) {
            std::cerr << "No strategy set\n";
            return;
        }
        strategy->sort(data);
    }

    void print_data() const {
        for (int value : data) {
            std::cout << value << " ";
        }
        std::cout << "\n";
    }

    std::string current_strategy() const {
        return strategy ? strategy->name() : "None";
    }
};

// Factory function for creating strategies at runtime
std::unique_ptr<SortStrategy> create_strategy(const std::string& name) {
    if (name == "quick") {
        return std::make_unique<QuickSortStrategy>();
    } else if (name == "merge") {
        return std::make_unique<MergeSortStrategy>();
    } else if (name == "heap") {
        return std::make_unique<HeapSortStrategy>();
    }
    return nullptr;
}

// Usage
int main() {
    // Create processor with runtime-selected strategy
    auto processor = std::make_unique<DataProcessor>(
        std::make_unique<QuickSortStrategy>()
    );

    processor->add_data(30);
    processor->add_data(10);
    processor->add_data(20);
    processor->process();
    std::cout << "Using: " << processor->current_strategy() << "\n";
    processor->print_data();

    // Change strategy at runtime
    processor->set_strategy(std::make_unique<MergeSortStrategy>());
    processor->add_data(50);
    processor->add_data(5);
    processor->process();
    std::cout << "Using: " << processor->current_strategy() << "\n";
    processor->print_data();

    // Create strategy from configuration
    std::string config_algorithm = "heap";
    auto from_config = std::make_unique<DataProcessor>(
        create_strategy(config_algorithm)
    );
    from_config->add_data(100);
    from_config->add_data(25);
    from_config->process();

    return 0;
}

Key characteristics

Runtime selection

The algorithm is fixed at execution time:

// Algorithm chosen based on user input or configuration
std::string user_choice = get_user_input();
auto processor = std::make_unique<DataProcessor>(
    create_strategy(user_choice)
);

Virtual function dispatch

Strategy calls go through virtual functions:

void process() {
    // Virtual function call - which sort() is called depends on runtime type
    strategy->sort(data);  // Lookup in vtable, call through pointer
}

Polymorphic container storage

You can store different strategies in the same container:

std::vector<std::unique_ptr<SortStrategy>> strategies;
strategies.push_back(std::make_unique<QuickSortStrategy>());
strategies.push_back(std::make_unique<MergeSortStrategy>());
strategies.push_back(std::make_unique<HeapSortStrategy>());

// Call all strategies
for (auto& strategy : strategies) {
    strategy->sort(data);  // Dynamic dispatch to appropriate implementation
}

Dynamic strategy switching

You can change strategies at runtime:

processor->set_strategy(std::make_unique<MergeSortStrategy>());
processor->process();  // Now uses merge sort

processor->set_strategy(std::make_unique<HeapSortStrategy>());
processor->process();  // Now uses heap sort

Real-world example: compression service

// Strategy base class
class CompressionStrategy {
public:
    virtual ~CompressionStrategy() = default;
    virtual std::vector<uint8_t> compress(const std::string& data) = 0;
    virtual float compression_ratio() const = 0;
};

class GzipStrategy : public CompressionStrategy {
public:
    std::vector<uint8_t> compress(const std::string& data) override {
        // Gzip compression implementation
        return /* compressed data */;
    }

    float compression_ratio() const override { return 0.65f; }
};

class ZstdStrategy : public CompressionStrategy {
public:
    std::vector<uint8_t> compress(const std::string& data) override {
        // Zstandard compression implementation
        return /* compressed data */;
    }

    float compression_ratio() const override { return 0.62f; }
};

class NoCompressionStrategy : public CompressionStrategy {
public:
    std::vector<uint8_t> compress(const std::string& data) override {
        return std::vector<uint8_t>(data.begin(), data.end());
    }

    float compression_ratio() const override { return 1.0f; }
};

// Context
class FileCompressor {
private:
    std::unique_ptr<CompressionStrategy> strategy;

public:
    FileCompressor(std::unique_ptr<CompressionStrategy> strat)
        : strategy(std::move(strat)) {}

    void set_compression_level(int level) {
        // Choose strategy based on level
        if (level == 0) {
            strategy = std::make_unique<NoCompressionStrategy>();
        } else if (level < 8) {
            strategy = std::make_unique<ZstdStrategy>();
        } else {
            strategy = std::make_unique<GzipStrategy>();
        }
    }

    std::vector<uint8_t> compress_file(const std::string& filename) {
        auto content = read_file(filename);
        return strategy->compress(content);
    }

    float get_ratio() const {
        return strategy->compression_ratio();
    }
};

// Usage
int main() {
    auto compressor = std::make_unique<FileCompressor>(
        std::make_unique<ZstdStrategy>()
    );

    // Change compression based on user choice or config
    int user_level = get_compression_level();
    compressor->set_compression_level(user_level);

    auto compressed = compressor->compress_file("data.txt");
    std::cout << "Compression ratio: " << compressor->get_ratio() << "\n";

    return 0;
}

Virtual function overhead

Virtual function calls cost more than direct calls:

// TEMPLATE-BASED (direct call, likely inlined):
template<typename Strategy>
void process(Strategy& strategy) {
    strategy.sort(data);  // Direct call, no indirection
}
// Assembly: jmp <direct_address>

// RUNTIME-SELECTED (virtual function call):
void process() {
    strategy->sort(data);  // Virtual call through vtable
}
// Assembly:
// mov rax, [rdi]      ; load vtable pointer
// mov rax, [rax+X]    ; load function pointer from vtable
// call [rax]          ; call through function pointer

The overhead is typically: - 1-3 CPU cycles for vtable lookup and function pointer call - Branch prediction penalty if call patterns vary - Reduced inlining opportunities (compiler can't inline virtual functions) - Cache pressure from vtable indirection

Benchmark example:

QuickSort (100M integers):
  - Template-based:      1250ms (direct call, inlined)
  - Runtime-selected:    1380ms (virtual call overhead ~10%)
  - Difference:          ~130ms (~10% slower)

Advantages

Runtime flexibility. You can choose the algorithm from runtime conditions.
Dynamic switching. You can change algorithms without recompiling.
Configuration-driven. Strategies can come from config files or the environment.
Homogeneous containers. Different strategies fit in the same collection.
Simpler code generation. There is no template code bloat.
Plugin architecture. Strategies can be loaded from external libraries.
Easier testing. You can mock strategies through inheritance.

Disadvantages

Virtual function overhead. Indirect calls have a cost.
No compiler inlining. Virtual functions cannot be inlined.
Runtime type checking. Null pointers and wrong types are possible.
More objects. Strategy instances need memory allocation.
Less type-safe. Wrong strategy types are caught at runtime, not compile time.
Cache unfriendly. Polymorphic dispatch hurts cache locality.
Potential undefined behavior. A strategy pointer can be null or dangling.

Performance comparison

Aspect	Template-Based	Runtime Selection
Algorithm selection time	Compile-time	Runtime
Function call overhead	0 (inlined)	1-3 CPU cycles
Inlining	✓ Yes	✗ No (usually)
Code bloat	Template instantiation	Minimal
Binary size	Larger (per instantiation)	Smaller
Memory allocation	Stack (compile-time)	Heap (unique_ptr)
Type safety	Compile-time	Runtime
Flexibility	Compile-time algorithms only	Runtime selection
Container homogeneity	Different types	Same type
Cache efficiency	Monomorphic (better)	Polymorphic (worse)

When to use runtime selection

The algorithm must be chosen at runtime
The algorithm depends on configuration, user input, or the environment
You need to switch strategies without recompiling
Different strategy instances must be stored together
You have a plugin architecture where strategies load dynamically
The overhead of virtual function calls is acceptable

For cases where compile-time performance is critical, see Template-Based Strategy (Compile-Time).

Summary

Runtime selection Strategy uses virtual functions for dynamic algorithm dispatch. It gives up the compile-time performance of templates for runtime flexibility and simpler code generation. The 10% figure in the benchmark is an example, not a law. Measure your own loop before you trade flexibility for speed. Choose templates when the algorithm is known at compile time, and virtual functions when it is not.