Шаблоны будут иметь немного меньшие потери производительности для времени выполнения (меньше косвенных обращений, меньше вызовов, больше встроенных оптимизаций), но заставят вас понести очень высокий штраф за время компиляции ...
Я думаю, что для этой цели интерфейсы лучше (пока у нас нет концепций в C ++ 0x TR1) ... если только вы не можете замедлить некоторый "код узкого места". Интерфейсы более динамичны и переключаемы во время выполнения.
Помните, что вы можете создать свой класс с объектами внедрения по умолчанию (реальными), но у вас могут быть фабрики, которые внедряют фиктивные объекты в ваши тесты ... вам даже не нужно создавать подклассы.