その理解でいいだろ。
lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())
は対応するイテレータがそれぞれ参照している要素をoperator<で比較していく。
mapのイテレータが参照しているのはpair<key_type,mapped_type>。
pair<first_type,second_type> x,y に対して x < y が真になるのは
x.first < y.first または !(y.first < x.first) && x.second < y.second が真になるとき。