Hi Adam,
I'm personally all for option 2, as it is something I had proposed at some point. It feels much more natural to me, and more aligned with our usual traits-based approach. I understand it may prevent users from specifying different behaviors (i.e. different translators) for the same type, but I consider that an edge case and there are workarounds.
As for option 4, I see the analogy but I would argue that in the STL you don't really need a map if you have non-indexable values to store. You'll simply make them indexable (i.e. define operator<()) to use them in a set. A map is more for when the key can't be derived from the value at all.
Bruno