Why is BTreeSet defined this way?

help
1

Something I don't understand ( there is so much I don't understand )...

BTreeSet is defined like this:

pub struct BTreeSet<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
> {
    map: BTreeMap<T, SetValZST, A>,
}

https://doc.rust-lang.org/src/alloc/collections/btree/set.rs.html#78-81

SetValZST is defined here:

where it explains:

/// Zero-Sized Type (ZST) for internal `BTreeSet` values.
/// Used instead of `()` to differentiate between:
/// * `BTreeMap<T, ()>` (possible user-defined map)
/// * `BTreeMap<T, SetValZST>` (internal set representation)
#[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Hash, Clone, Default)]
pub(super) struct SetValZST;

But isn't the definition (of map) private? Does it somehow "leak" even though it is private?

2 Likes
2

SetValZST was added for clearer panic messages for BTreeSet.

7 Likes
3

I see (sort of). It does seem like the "proper" fix might be to fix whatever is generating the panic message, although I can see this might be a reasonable temporary solution.

4

I find the fix rather elegant, to be honest. Great use of specialization, which std is allowed to use. The only other options I can think of how to implement this would be to pass the is_set flag as argument (I haven't checked how long the call-chain from BTreeSet::range down to NodRef::search_tree_for_bifurcation is) or implement BTreeSet not as a BTreeMap with no values (which sounds like a lot of duplicated code no one would like to maintain).

1 Like
5

I didn't understand is_set either and still don't! Sure, I expect BTreeSet to be a wrapper around BTreeMap, although the public methods are somewhat different.

6

Oh, I think I can see now what is going on, roughly. I get it.

I think my implementation will have a private method of BTreeMap, which is a bit more straight-forward. This is too clever for me!