Ordered Keys and Values

Every key K in a BTreeMap<K, V> and every element T in a BTreeSet<T> must implement the total ordering trait std::cmp::Ord (along with PartialOrd, Eq, and PartialEq).

Required Trait Hierarchy for Ordered Keys

PartialEq ──> Eq ──┐
                   ├──> Ord   (Required by BTreeMap<K, V> and BTreeSet<T>)
PartialOrd ────────┘

1. Strict total order: For any two keys a and b, a.cmp(&b) must return Ordering::Less, Ordering::Equal, or Ordering::Greater consistently (antisymmetric, transitive, and total).
2. Ord and PartialOrd consistency: a.partial_cmp(&b) must equal Some(a.cmp(&b)). Violating this contract (for example, by writing a buggy manual PartialOrd that disagrees with Ord) can cause BTreeMap searches and tree rebalancing to fail or panic.
3. Key immutability: Just as HashMap keys must not mutate their hashed fields while stored in the map, BTreeMap keys must never mutate fields that affect Ord via interior mutability (Cell / RefCell) while stored in the tree.

Custom Composite Key Ordering (Lexicographical vs. Custom Ord)

Applying #[derive(PartialEq, Eq, PartialOrd, Ord)] compares struct fields top-to-bottom. Placing the most significant sorting field first gives you multi-column sorting automatically:

use std::collections::BTreeMap;

// Orders by `priority` ascending first, then by `seq_id` ascending on ties:
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct JobKey {
    priority: u8,
    seq_id: u64,
}

fn main() {
    let mut jobs = BTreeMap::new();
    jobs.insert(JobKey { priority: 2, seq_id: 105 }, "index_search");
    jobs.insert(JobKey { priority: 1, seq_id: 102 }, "payment_webhook");
    jobs.insert(JobKey { priority: 1, seq_id: 101 }, "auth_check");

    for (key, name) in &jobs {
        println!("prio={}, seq={} -> {name}", key.priority, key.seq_id);
    }
}

prio=1, seq=101 -> auth_check
prio=1, seq=102 -> payment_webhook
prio=2, seq=105 -> index_search

Reversing Key Order or Wrapping Floats

• Descending key order: Wrap the key (or a specific field inside a key struct) in std::cmp::Reverse<K> so BTreeMap<Reverse<K>, V> sorts keys from largest to smallest.
• Floating-point keys: Because f64 does not implement Ord (NaN != NaN), wrap f64 in a newtype that delegates Ord::cmp to f64::total_cmp:

use std::cmp::Ordering;
use std::collections::BTreeSet;

#[derive(Debug, Clone, Copy)]
struct TotalF64(f64);

impl PartialEq for TotalF64 {
    fn eq(&self, other: &Self) -> bool {
        self.0.total_cmp(&other.0) == Ordering::Equal
    }
}

impl Eq for TotalF64 {}

impl PartialOrd for TotalF64 {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for TotalF64 {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.total_cmp(&other.0)
    }
}

fn main() {
    let thresholds = BTreeSet::from([TotalF64(2.5), TotalF64(-1.0), TotalF64(0.5)]);
    for TotalF64(val) in &thresholds {
        print!("{val} ");
    }
    println!();
}

-1 0.5 2.5