Se ho ben capito quello che intendi, tu vuoi ordinare il vector che contiene tutte le parole che iniziano con una data lettera. Allora potresti evitare del tutto la push_back ed inserire direttamente la parola nella posizione corretta. Quindi scorri il vector (tramite un iteratore) e sfrutti il metodo insert.