Специализация шаблонного класса, где аргументом шаблона является другой шаблон

Да, вы можете специализированно определить класс следующим образом:

template <>
template <typename T, typename S>
class MyTemplateClass<SomeRandomClass<T, S>>
{
    void DoSomething(SomeRandomClass<T, S>& t) { /* что-то */ }
};

Однако нельзя специализированно определить только метод-член, поскольку специальная настройка осуществляется для всего класса в целом, и вам необходимо определить новый класс. Тем не менее, вы можете сделать так:

template <>
template <typename T, typename S>
class MyTemplateClass<SomeRandomClass<T, S>>
{
    void DoSomething(SomeRandomClass<T, S>& t);
};

template <>
template <typename T, typename S>
void MyTemplateClass<SomeRandomClass<T, S>>::DoSomething(SomeRandomClass<T, S>& t)
{
    // что-то
}

Это позволяет разделить объявление и определение метода.

Все, что вам нужно сделать, это использовать шаблоны для того, что вы хотите оставить общим. Взяв ваш начальный код:

template<typename T, typename S>
void MyTemplateClass< SomeRandomClass<T,S> >::DoSomething(SomeRandomClass<T,S> & t)
{
    // здесь происходит что-то специализированное
}

ИЗМЕНЕНИЕ:

Если вы хотите оставить общим только часть SomeRandomClass, вы можете сделать это следующим образом:

template<typename T>
void MyTemplateClass< SomeRandomClass<T,int> >::DoSomething(SomeRandomClass<T,int> & t)
{
    // здесь происходит что-то специализированное
}

Таким образом, вы можете гибко настраивать свой код в зависимости от того, какие части ваших классов вам нужно обобщить.

Правка: это правильный ответ на другой вопрос.

Использование типа T дважды немного запутывает, поскольку они компилируются отдельно и не связаны между собой.

Вы можете перегрузить метод так, чтобы он принимал параметр-шаблон:

template <typename T>
class MyTemplateClass
{
    void DoSomething(T& t) { }

    template <typename U, typename V>
    void DoSomething(SomeRandomClass<U, V>& r) { }
};

Это связывает U и V в новом методе с T' и S' в SomeRandomClass. В такой конфигурации U или V могут быть того же типа, что и T, но это необязательно. В зависимости от вашего компилятора, вы сможете сделать следующее:

MyTemplateClass<string> mine;
SomeRandomClass<int, double> random;

// Примечание: не обращайте внимания на неконстантную ссылку на строковый литерал здесь...
mine.DoSomething("hello world");
mine.DoSomething(random);

При этом будет выбрана перегруженная версия с шаблоном, и вам не придется явно указывать типы.

Правка:

Если вы хотите сделать это с помощью специальной реализации шаблона, это не повлияет на перегрузку DoSomething. Если вы специализирован свой класс следующим образом:

template <>
class SomeRandomClass<int, double>
{
    // что-то здесь...
};

то перегрузка выше с радостью «съест» эту специализированную реализацию. Просто убедитесь, что интерфейсы специализированного шаблона и стандартного шаблона совпадают.

Если вы хотите специализированный DoSomething, который принимает определенную пару типов для SomeRandomClass, тогда вы уже потеряли обобщенность... вот что такое специализация.

Если вы хотите использовать шаблонную структуру в качестве аргумента шаблона (с намерением использовать её внутри), не специализируя её, вы можете воспользоваться концепцией SFINAE. Вот пример, который добавляет тип в кортеж, принимая структуру-шаблон, которая будет использоваться в качестве условия:

template<typename Tuple, typename T, template<typename> class /*SFINAEPredicate*/>
struct append_if;

template<typename T, template<typename> class SFINAEPredicate, typename ... Types>
struct append_if<std::tuple<Types...>, T, SFINAEPredicate>
{
    using type = typename std::conditional<SFINAEPredicate<T>::value,
            std::tuple<Types..., T>, std::tuple<Types...>>::type;
};

// Использование
using tuple_with_int = append_if<std::tuple<>, int, std::is_fundamental>::type;

Данный подход может быть использован начиная с C++11. В вашем коде SFINAEPredicate — это шаблонная структура, например, std::is_fundamental, которая проверяет, является ли переданный тип фундаментальным. Если это так, тип T будет добавлен в результирующий кортеж std::tuple, иначе будет возвращён кортеж без изменений.