template pass by value or const reference or...?

Thou shalt not wake the dead, but head a similar problem and here's some example code that shows how to use C++11s type traits to deduce whether a parameter should be passed by value or reference:

#include <iostream>
#include <type_traits>

template<typename key_type>
class example
{
    using parameter_type = typename std::conditional<std::is_fundamental<key_type>::value, key_type, key_type&>::type;

 public:
  void function(parameter_type param)
  {
      if (std::is_reference<parameter_type>::value)
      {
          std::cout << "passed by reference" << std::endl;
      } else {
          std::cout << "passed by value" << std::endl;
      }
  }
};

struct non_fundamental_type
{
    int one;
    char * two;
};

int main()
{
  int one = 1;
  non_fundamental_type nft;

  example<int>().function(one);
  example<non_fundamental_type>().function(nft);

  return 0;
}

Hope it helps others with a similar issue.

Is there a rule of thumb for this?

The same general rules for when to use pass by reference vs. pass by value apply.

If you expect T always to be a numeric type or a type that is very cheap to copy, then you can take the argument by value. If you are going to make a copy of the argument into a local variable in the function anyway, then you should take it by value to help the compiler elide copies that don't really need to be made.

Otherwise, take the argument by reference. In the case of types that are cheap to copy, it may be more expensive but for other types it will be faster. If you find this is a performance hotspot, you can overload the function for different types of arguments and do the right thing for each of them.

I suspect that it can also fail for some specific types

Pass by reference-to-const is the only passing mechanism that "never" fails. It does not pose any requirements on T, it accepts both lvalues and rvalues as arguments, and it allows implicit conversions.