Why does std::collections::btree_map::Entry::or_default have its own impl section?

help
1

Why is there a distinct impl section for std::collections::btree_map::Entry::or_default

like this:


impl<'a, K, V, A> Entry<'a, K, V, A>
where
    K: Ord,
    V: Default,
    A: Allocator + Clone,
pub fn or_default(self) -> &'a mut V

when ( as I understand it ) a constraint on the function would do? I think it is probably just "random" and "meaningless", but perhaps there is some subtlety to this I don't understand.

( I came across this in my experiment in making my own (equivalent) BTreeMap, my version is here: Entry in btree_experiment - Rust like this:

pub fn or_default(self) -> &'a mut V
where
    V: Default,
2

I don't think there's a difference in this case.

1 Like
3

Thanks! Another curiosity I noticed was this

pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
    K: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

I don't see why K needs to be Ord here. I also don't understand the ?Sized bound on Q ( but maybe there is a good reason for that - actually I think I do understand that now... ok, it allows Q to be unsized ).

4

I believe the K: Ord and Q: Ord bounds are meant to ensure that this requirement from the Borrow trait applies:

Further, when providing implementations for additional traits, it needs to be considered whether they should behave identically to those of the underlying type as a consequence of acting as a representation of that underlying type. Generic code typically uses Borrow<T> when it relies on the identical behavior of these additional trait implementations. These traits will likely appear as additional trait bounds.

In particular Eq, Ord and Hash must be equivalent for borrowed and owned values: x.borrow() == y.borrow() should give the same result as x == y.

The K: Ord bound isn’t very restrictive anyways, since you can’t insert items into the BTreeMap unless K: Ord.

This is particularly useful to allow slice types like str and [T], so you can pass an &str or &[T] to look up items in a BTreeMap<String, _> or BTreeMap<Vec<T>, _>.

1 Like
5

Thanks! I still don't understand it quite, but ok, apparently it means something. I mean... what bad consequence can arise if it is omitted?

6

If K: Ord is omitted, then (a) the BTreeMap must be empty, because there’s no way to insert into it, and (b) if for some reason it was not empty, navigating its entries by borrowing Q from them would not be guaranteed to have any relation to the way they are sorted in the tree.

1 Like
7

Hmm... that seems a little strange. I was just looking here:

and it has this example:

    pub fn get<Q>(&self, k: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized
    {
        // ...
    }

There is no + Hash + Eq on K.

8

True, though in the actual std::collections::HashMap implementation, that is inside of an impl with a K: Eq + Hash bound.

As I said, this is all a bit academic since there is no way to have a populated map if K doesn’t meet the relevant bounds.

1 Like
9

Here is another (to my eyes) peculiarity:

pub fn retain<F>(&mut self, f: F)
where
    K: Ord,
    F: FnMut(&K, &mut V) -> bool,
Retains only the elements specified by the predicate.

from here

I don't see what the K: Ord is for. Retain doesn't involve any comparisons. Unless somehow it allows the closure to do comparisons? But I think it can anyway. Hmm.

10

I agree. As far as I can tell, this K: Ord bound is unnecessary. But as before, it doesn’t make any practical difference because a populated BTreeMap<K, V> always has K: Ord.

11

Since it's come up a few times, I think it's worth pointing out that having or leaving off unnecessary bounds can make a practical difference in some cases. For example I could have a

pub enum GeneralThingDoer<K, V> {
    T(BTreeMap<K, V>),
    M(HashMap<K, V>),
    V(Vec<V>),
}

and then implement methods such that a T variant is only populated if K: Ord + Eq, and an M variant only if K: Hash + Eq, et cetera. But if you require K: Ord + Eq everywhere in your crate (in particular if you require them on the struct definition), then I'll have to include those bounds too -- which is an unwanted restriction given some consumer of my type that never needs to construct the T variant!

Similar thinking can apply to methods, perhaps especially when macros are involved.

On the flip side, adding a trait bound is a breaking change, so removing (or originally not having) the Ord bound somewhere is a promise that you will never require it, modulo a major SemVer bump. So "unnecessary" bounds can be a form of future-proofing.

(This is more sharply relevant to std, which operates under the assumption that there may never be a major version bump, and thus all such promises last forever.)

1 Like
12

Ah, I am wondering if a possible (perhaps inefficient) implementation could repeatedly pop the first element from the BTree, then either discard it or push it into a temporary Vec (depending on the result of f), then at the end re-insert the temporary Vec pairs back into the tree. That would require K: Ord. So the bound is to not preclude this implementation possibility.

But still, the bound could be added when required, and not break anything. I think!

13

Adding bounds is always a breaking change. Hence my last two paragraphs above.

Technically it's breaking even if the function could never be called before.

(That said, sometimes people are willing to make breaking changes if the fallout is small enough.)

1 Like
14

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.