How do I use a custom comparator function with BTreeSet?

Question

In C++, it is possible to customize the code std::set uses to sort its arguments. By default it uses std::less, but that can be changed with the Compare template parameter.

Rust's BTreeSet uses the Ord trait to sort the type. I don't know of a way to override this behavior -- it's built into the type constraint of the type stored by the container.

However, it often makes sense to build a list of items that are sorted by some locally-useful metric that nevertheless is not the best way to always compare the items by. Or, suppose I would like to sort items of a used type; in this case, it's impossible to implement Ord myself for the type, even if I want to.

The workaround is of course to build a plain old Vec of the items and sort it afterward. But in my opinion, this is not as clean as automatically ordering them on insertion.

Is there a way to use alternative comparators with Rust's container types?

Answer 1

Custom comparators currently do not exist in the Rust standard collections. The idiomatic way to solve the issue is to define a newtype:

struct Wrapper(Wrapped);

You can then define a custom Ord implementation for Wrapper with exactly the semantics you want.

Furthermore, since you have a newtype, you can also easily implement other traits to facilitate conversion:

• convert::From can be implemented, giving you convert::Into for free
• ops::Deref<Target = Wrapped> can be implemented, reducing the need for mapping due to auto-deref

Note that accessing the wrapped entity is syntactically lightweight as it's just two characters: .0.