Having multiple BTree indexers to a Vec now that BTrees don't support custom comparison functionality

help
1

I have a Vec<Person>, V. Persons will be pushed to V, though never popped from. However, a Person's details may be modified.

V can grow quite large, and I would like to keep indexers to Persons based on their .FirstName (String) and .LastName (String). I will store these indexers for both fields in two BTrees.

I also want to iterate through V in V's order, and in that case I want to be able to see their FirstName and LastName immediately. So it is crucial that FirstName and LastName are stored in Persons themselves.

Now, since it would be quite wasteful to have a String copy for each FirstName and LastName, I want to store the index of a Person in V in these BTrees instead.

This would be doable if BTrees allowed custom comparator Fns. Eg. for FirstName it would look like:

|left : &usize, right : &usize| {
    V[*left].FirstName.cmp(&V[*right].FirstName)
}

But BTrees don't have this functionality.

In similar cases, a wrapper type has been suggested for a custom std::cmp::Ord implementation. But in my case, this can't be solved with wrapper types since these comparisons also require an external argument: &V.

I also can't simply make these BTree element values (index, &V), since V would then be shared-referenced, meaning its mutability is locked.

What options remain?

2

Would iddqd be what you're looking for?

3

One option would be something like this:

struct Person {
    first_name: Arc<str>,
    last_name: Arc<str>,
    ...
}

struct PersonStore {
    people: Vec<Person>,
    fname_idx: BTreeMap<Arc<str>, BTreeSet<usize>>,
    lname_idx: BTreeMap<Arc<str>, BTreeSet<usize>>
}
2 Likes
4

Maps where keys are borrowed from values.

The OP wants to borrow keys from a separate Vec, so I don't see how that would work. An implementation of IdHashItem for example would need to store a reference to the Vec.

Also, the maps are all hashed, rather than ordered by their keys like BtreeMap.

5

It would be replacing the OP's Vec. Though yes, only the IdOrdMap would provide the ordering, but then only allow a single key.

Nonetheless, the underlying implementation might be worth a look, it directly uses a hashbrown::HashTable, allowing all sorts of things to be built on top.

1 Like
6

I see. That could work if other access via Vec index is not needed.