I’d not go that far. For many computations about term sets ordered sets are a good solution. For example, below is a perfectly sensible way to find out which variables are shared between T1 and T2. Vars is also an ordered set, but one should simply consider it a list unless it is certain nothing touches the variables.
shared_variables(T1, T2, Vars) :-
term_variables(T1, V1), sort(V1, SV1),
term_variables(T2, V2), sort(V2, SV2),
ord_intersection(SV1, SV2, Vars).
For short, ordered sets, library(assoc) and library(rbtress), etc. are perfect with variables as long as one is certain the set of elements/keys is not instantiated during the relevant part of the computation.
Note that attributed variables can be a good alternative for reasoning about variables.