Yes, the coffee is bitter. Drink it down. The real bitterness will come when it wakes you up enough to contemplate your failures.
- Existential Comics
Here are some ways in which the current map APIs suck, and potentially make your program Slower And Therefore Terrible:
- Entry requires an owned key upfront, even if all you have is a borrowed key and the entry is occupied
- You can't memoize hashes (easily)
- We require K: Eq + Hash to insert keys, like cowards
- Having to make wrapper types to do custom search logic is annoying
There have been many attempts to variously resolve these issues, by myself and others. These attempts have failed because they have tried to achieve goals like "ergonomics", "safety", and "basic decency". Today we abandon these goals and just solve the dang problem, allowing our users to write abominations like:
let borrowed_key = ...;
let entry = map.raw_entry()
.hash_with(|_| borrowed_key.get_memoized_hash())
.search_with(|k| borrowed_key.field == k.field);
match entry {
Vacant(entry) => { entry.insert(borrowed_key.clone(), val) }
Occupied(entry) => { entry.insert(val) }
}
Here is the API:
pub struct RawEntryBuilder<'a, K: 'a, V: 'a, S: 'a>;
pub struct RawEntryBuilderHashed<'a, K: 'a, V: 'a>;
pub enum RawEntry<'a, K: 'a, V: 'a> {
Occupied(RawOccupiedEntry<'a, K, V>),
Vacant(RawVacantEntry<'a, K, V>),
}
pub struct RawOccupiedEntry<'a, K: 'a, V: 'a>;
pub struct RawVacantEntry<'a, K: 'a, V: 'a>;
pub struct RawImmutableEntryBuilder<'a, K: 'a, V: 'a, S: 'a>;
pub struct RawImmutableEntryBuilderHashed<'a, K: 'a, V: 'a>;
impl<K, V, S> HashMap<K, V, S> {
/// Creates a raw entry builder for the HashMap.
///
/// Raw entries provide the lowest level of control for searching and
/// manipulating a map. They must be manually initialized with hash and
/// then manually searched. After this, insertions into the entry also
/// still require an owned key to be provided.
///
/// Raw entries are useful for such exotic situations as:
///
/// * Hash memoization
/// * Deferring the creation of an owned key until it is known to be required
/// * Using a HashMap where the key type can't or shouldn't be hashed and/or compared
///
/// Unless you are in such a situation, higher-level and more foolproof APIs like
/// `entry` should be preferred.
fn raw_entry(&mut self) -> RawEntryBuilder<K, V, S>;
/// Creates a raw immutable entry builder for the HashMap.
///
/// This is useful for
/// * Hash memoization
/// * Querying a HashMap where the key type can't or shouldn't be hashed and/or compared
///
/// Unless you are in such a situation, higher-level and more foolproof APIs like
/// `entry` should be preferred.
///
/// Immutable raw entries have very limited use; you might instead want `raw_entry`.
fn raw_entry_immut(&self) -> RawImmutableEntryBuilder<K, V, S>;
}
impl<'a, K, V, S> RawEntryBuilder<'a, K, V, S>
where S: BuildHasher,
{
/// Initializes the raw entry builder with the hash of the given query value.
fn hash_by<Q: ?Sized>(self, k: &Q) -> RawEntryBuilderHashed<'a, K, V>
where Q: Hash;
/// Initializes the raw entry builder with the hash yielded by the given function.
fn hash_with<F>(self, func: F) -> RawEntryBuilderHashed<'a, K, V>
where F: FnOnce(S::Hasher) -> u64;
/// Searches for the location of the raw entry with the given query value.
fn search_by<Q: ?Sized>(self, k: &Q) -> RawEntry<'a, K, V>
where K: Borrow<Q>,
Q: Eq + Hash;
}
impl<'a, K, V> RawEntryBuilderHashed<'a, K, V>
{
/// Searches for the location of the raw entry with the given query value.
///
/// Note that it isn't required that the query value be hashable, as the
/// builder's hash is used.
fn search_by<Q: ?Sized>(self, k: &Q) -> RawEntry<'a, K, V>
where K: Borrow<Q>,
Q: Eq;
/// Searches for the location of the raw entry with the given comparison function.
///
/// Note that mutable access is given to each key that is visited, because
/// this land is truly godless, and *someone* might have a use for this.
fn search_with<F: ?Sized>(self, func: F) -> RawEntry<'a, K, V>
F: FnMut(&mut K) -> bool;
}
impl<'a, K, V> RawEntry<'a, K, V> {
// At this point, basically an Entry except `insert` APIs take a `K` as well.
}
// raw_entry_immut is basically exactly the same except:
/// Searches for the location of the raw entry with the given comparison function.
///
/// If the location is empty, None is returned as nothing useful can be done in
/// this case.
fn search_with<F: ?Sized>(self, func: F) -> Option<(&'a K, &'a V)>
where F: FnMut(&K) -> bool; // Only immutable access to F!
The API for BTreeMap is much the same except everything about hashing is removed. It's possible it would also just support prev()/next() on entries, in which case a Real immutable entry type would be necessary. At that point we may also wish to swap the API naming polarity back to the typical raw_entry + raw_entry_mut scheme.
I started implementing this on HashMap and it seems like we're mostly already setup for it. The only kinda annoying thing is exposing the keys mutably during search for RawEntryBuilder, but I'm pretty sure this just means copy-pasting search_hashed_nonempty to add some mut's and being sad.
But it's also aesthetically displeasing to use an unsafe API when a safe one is possible!