You have a const problem.
You are not passing a const object to apply_visitor - so object members will not be passed. Therefore, in your case, this is string& - a reference to the type of string. This template is suitable for him:
template<typename T> bool operator()(T &other) const
So he is selected. This function is not an exact match - it is skipped:
bool operator()(const string &other) const
Of course, if you provide this statement:
bool operator()(string &other) const
then it will be selected, since a function without a template is considered before the template.
So, the solution: either provide a method in your visitor that accepts a link to the string (not const) - or use the option const const ...
The first solution is to remove const from the string statement:
bool operator()( string &other) const
The second solution is to pass the const object:
const MyVariant& cv = v; apply_visitor(StartsWith("123"), cv);
The third solution is to add a const specifier for the common visitor:
template<typename T> bool operator()(const T &other) const
The solutions of the 1st and 3rd are better than the 2nd - you must go through the consecutive visitor of your option, const is of great importance when the compiler must select the appropriate function.