Impl red-black tree

[zzwxh]

members dont change their address when edit the rbtree
pseudo code：

let mut map = RBTree::<String,i32>::new();
map.insert("foo".to_string(),1);
map.insert("bar".to_string(),2);
let foo:&mut i32 = map.get_mut("foo").unwrap();
let bar:&mut i32 = map.get_mut("bar").unwrap();
*foo;
*bar;

this code should compile sucess
if the pointers are available after edit the rbtree

[H2CO3]

It is unclear what you are asking. There's not enough context to know what RBTree is and where it's from, or if there's an actual problem you are trying to solve. If you have trouble expressing yourself in English clearly, you might want to ask for help from someone.

[steffahn]

Editing a search tree can, in principle, change the address of members. E.g. if a member is removed, its address changes (since it no longer exists at all).

Your example code however shows an example that would be more of a library limitation. It’s not a compiler limitation and the code should not compile: This is because the compiler can’t know that get_mut doesn’t modify the tree structure, or that the two keys you’re looking up are definitely different, both of which are conditions that ensure that the two mutable references from the get_mut could, in principle, exist in parallel.

APIs such as HashMap are in the process of getting new API to actually allow this particular use-case. It’s unstable in std, but already available e.g. for hashbrown::HashMap: hashbrown::HashMap::get_many_mut.

One reason why such API is not already long established is that for the general case of allowing 2, 3, 4, 5, or any constant number of places to be accessed in the map data structure in parallel, you would’ve needed a lot of different functions, or ad-hoc trait infrastructures with many separate (or macro-generated) impls, before the introduction of const generics to stable Rust last year started off all kinds of new API development which was eventually also allowing functions like this to be implemented.

If the crate that implements RBTree also were to add a similar API, then you could use it roughly as follows:

let mut map = RBTree::<String,i32>::new();
map.insert("foo".to_string(),1);
map.insert("bar".to_string(),2);
let [foo, bar] = map.get_many_mut(["foo", "bar"]).unwrap();
*foo;
*bar;