BTreeMap constant time first/last iterators

libs
34

I guess nothing more recent? I suppose even doing Entry optimally for HashMap remains hard enough ala https://github.com/rust-lang/rfcs/pull/1769 and [Pre-RFC] Abandonning Morals In The Name Of Performance: The Raw Entry API so traits might only help when you've lots of code that does not require optimization.

As an aside, an optimal entries (plural) interface for a cuckoo tables looks nothing like the entry interface for a hash map. Insertion into cuckoo tables has only four-ish placement options, so you handle indexes into the table which possibly change during actual insertion:

pub struct Entries<'table,KO,V,H: CuckooHasher> {
    table: RefCell<&'table mut CuckooTable<KO,V,H>>
}
pub struct IndexFetch<'table,KO,V,H: CuckooHasher> {
    entries: Entries<'table,KO,V,H: CuckooHasher>,
    index: H::Index,
    key: H::Key,
}
pub struct IndexInsert<'table,KO,V,H: CuckooHasher> {
    fetch: IndexFetch,
    key_owned: KO,
}

As for owned vs borrowed key issues, cuckoo tables should've an owned key that appears inside the table, and a separate ephemeral aka borrowed key that appears only during hashing, and does not even appear in the cuckoo table's type.