サイトが見当たらなかったので、使用してるSTLのソースを参考にしてみると良いかも

こんな感じに：
template <class T> struct less_key2 {
bool operator()(const T& s1,const T& s2) const { return s1.first < s2.first && s1.second < s2.second; }
};
typedef std::pair<std::string,int> Key2;
std::map<Key2,int,less_key2<Key2> > a;