插入任意嵌套的HashMap [英] Insert in arbitrary nested HashMap
问题描述
我想拥有一个数据结构，该结构允许我具有任意嵌套的HashMap.为此，我构建了以下结构:
I want to have a data-structure that allows me to have arbitrary nested HashMap. For that I've constructed the following struct:
struct Database {
children: HashMap<String, Database>,
data: String,
}
要在此结构中插入，我会得到一个键列表和一个要插入的值.例如输入
For inserting in this structure i get a list of keys and a value to insert. So for example for the input
let subkeys = vec!["key1", "key1.1", "key1.1.3"];
let value = "myvalue";
我希望数据库具有此(伪)结构:
I want the database to have this (pseudo) structure:
{
"data" : "",
"children": {
"key1": {
"data" : "",
"children": {
"key1.1": {
"data" : "",
"children" : {
"key1.1.3": {
"data": "myvalue",
"children" : {}
}
}
}
}
}
}
}
然后例如进行第二次插入请求
and then for example for a second insert request
let subkeys = vec!["key1", "key1.1", "key1.1.2"];
let value = "myvalue2";
结构应如下所示(伪):
the structure should look (pseudo) like this:
{
"data" : "",
"children": {
"key1": {
"data" : "",
"children": {
"key1.1": {
"data" : "",
"children" : {
"key1.1.3": {
"data": "myvalue",
"children" : {}
},
"key1.1.2": {
"data": "myvalue2",
"children" : {}
}
}
}
}
}
}
}
所以这是我尝试过的最小的可重现示例(不起作用)游乐场
So here is a minimal reproducible example of what I've tried (not working) playground
use std::collections::HashMap;
struct Database {
children: HashMap<String, Database>,
data: String,
}
fn main()
{
// make a databse object
let mut db = Database {
children: HashMap::new(),
data: "root".to_string(),
};
// some example subkeys
let subkeys = vec!["key1", "key1.1", "key1.1.3"];
// and the value i want to insert
let value = "myvalue";
// a reference to the current HashMap
// initialize with the root
let mut root = &db.children;
// iterate throught subkeys
for subkey in subkeys.iter() {
// match the result of a get request to the hashmap
match root.get::<String>(&subkey.to_string()) {
Some(child) => {
// if the key already exists set the root to the children of the child
root = &child.children;
}
None => {
// if key doesnt exist add it with a ne empty hashmap
let d = Database{children: HashMap::new(), data: "".to_string()};
// set root to this new databse obejct
root = &d.children;
root.insert(subkey.to_string(), d);
}
}
}
}
据我了解，此代码存在问题:
So as I understand it there are to problems with this code:
-
& d.children在match之后被丢弃，因此root的种类"没有价值
&d.childrenget s dropped after thematchand soroot"kind of" has no value
还有 root.insert 似乎是一个问题，因为 root 是& 引用，因此它引用的数据不能被借为可变的`
also the root.insert seems to be a problem because root is a & reference, so the data it refers to cannot be borrowed as mutable`
要使我的代码正常工作并产生如上所示的结果，我需要做些什么.是否可能需要更改我的 struct数据库中的某些内容?
What do I need to do to make my code work and produce results like shown above. Do I maybe need to change something in my struct Database?
推荐答案
首先，对您到目前为止所拥有的内容以及为什么它不起作用进行一些评论. root 必须是可变的引用.注意可变变量( let mut root =& db.children; )和可变引用( let root =& mut db.children; )之间的区别.前者允许变量本身被更改.后者允许更改参考后面的数据.在这种情况下，我们都需要( let mut root =& mut db.children )，因为我们不仅在遍历节点时更改了 root ，而且还修改了每当我们需要插入新节点时，引用后面的数据.
First, some comments on what you have so far and why it doesn't work. root needs to be a mutable reference. Note the distinction between a mutable variable (let mut root = &db.children;) and a mutable reference (let root = &mut db.children;). The former allows the variable itself to be changed. The latter allows the data behind the reference to be changed. In this instance, we need both (let mut root = &mut db.children) because we not only change root as we iterate through the nodes, but we also modify the data behind the reference whenever we need to insert a new node.
相同的内容适用于内部循环中的 d (它必须是一个可变变量)，尽管正如我们将看到的那样，对 d 进行突变并不是真正的我们想要的.
The same thing applies to d in the inner loop (it needs to be a mutable variable), though as we'll see, mutating d isn't really what we want.
// if key doesnt exist add it with a ne empty hashmap
let d = Database{children: HashMap::new(), data: "".to_string()};
// set root to this new databse obejct
root = &mut d.children;
root.insert(subkey.to_string(), d);
暂时忽略这些错误，这段代码应该做什么 ? d 是一个新的 Database ，其中没有真实数据.然后，我们将 root 设置为此新 Database 的子级(空).最后，我们将新的 Database 插入根目录.但是，由于我们在第二步中更改了 root ，因此它不再是父级:我们将 d 作为其自身的子级插入！
Ignoring the errors for a moment, what should this code do? d is a new Database with no real data in it. Then, we set root to be the (empty) set of children of this new Database. Finally, we insert the new Database into root. But since we changed root in the second step, it's no longer the parent: we're inserting d as a child of itself!
我们改为切换后两个步骤的顺序.但是，如果我们仅切换这两行，就会得到错误
We instead want to switch the order of the second two steps. But if we simply switch those two lines, we get the error
error[E0382]: borrow of moved value: `d`
--> src/main.rs:41:24
|
36 | let mut d = Database{children: HashMap::new(), data: "".to_string()};
| ----- move occurs because `d` has type `Database`, which does not implement the `Copy` trait
37 |
38 | root.insert(subkey.to_string(), d);
| - value moved here
...
41 | root = &mut d.children;
| ^^^^^^^^^^^^^^^ value borrowed here after move
因此问题在于，当我们尝试将 root 设置为其子级时， d 不再是局部变量.我们需要 root 作为刚刚插入的值的子级.这类事情的惯用法是 the entry API .它允许我们尝试从 HashMap 中获取一个值，如果找不到该值，则插入一些内容.最相关的是，此插入将返回对该键上现在存在的任何值的可变引用.
So the problem is that d is no longer a local variable when we try to set root to its children. We need root to be the children of the just-inserted value. The usual idiom for this kind of thing is the entry API. It allows us to attempt to get a value from a HashMap and if it's not found, insert something. Most relevantly, this insertion returns a mutable reference to whatever value now resides at that key.
现在该部分看起来像
// if key doesnt exist add it with a new empty hashmap
let d = Database{children: HashMap::new(), data: "".to_string()};
// insert the new database object and
// set root to the hashmap of children
root = &mut root.entry(subkey.to_string()).or_insert(d).children;
此时，我们有一个貌似正常的程序.通过将#[derive(Debug)] 添加到 Database ，我们可以使用 println！("{:#?}，db); .但是，如果我们尝试添加第二个值，则一切都会炸毁，而不是将两个值并排放置，它们最终会出现在数据库的完全独立的分支中.在match语句的 Some(child)分支中注释掉的行.
At this point, we have an apparently working program. By adding a #[derive(Debug)] to Database, we can see what the database looks like with println!("{:#?}, db);. However, if we try to add in the second value, everything blows up. Rather than placing the two values side-by-side, they end up in completely separate branches of the database. This traces back to the commented out lines in the Some(child) branch of the match statement.
我们想将 root 设置为对 child.children 的可变引用，但是即使取消注释该行而没有任何更改也会导致错误，即 root是可变借来的，而在其他地方借来的.问题是我们现在在 root.get(& subkey.to_string())中使用借用.以前，由于我们忽略了 child ，而另一个分支未使用该借用中的任何数据，因此借用可能会立即终止.现在，它必须持续到比赛的整个过程.这样可以防止我们即使在 None 情况下也无法随意借用.
We'd like to set root to a mutable reference to child.children, but even just uncommenting that line without any changes causes the error that root is mutably borrow while borrowed elsewhere. The problem is that we're using the borrow in root.get(&subkey.to_string()) now. Before, since we ignored child and the other branch didn't use any data from that borrow, the borrow could end right away. Now it has to last for the whole duration of the match. This prevents us from borrowing mutably even in the None case.
幸运的是，由于我们使用的是 entry API，因此我们完全不需要此match语句！整个事情可以替换为
Fortunately, since we're using the entry API, we don't need this match statement at all! The whole thing can just be replaced with
let d = Database {
children: HashMap::new(),
data: "".to_string(),
};
// insert the new database object and
// set root to the hashmap of children
root = &mut root.entry(subkey.to_string()).or_insert(d).children;
如果子项集中已经存在该子项，则 root.entry(...).or_insert(...)将指向该现有子项.
If the subkey already exists in the set of children, root.entry(...).or_insert(...) will point to that already existing child.
现在，我们只需要清理代码.由于您已多次使用它，因此建议将在函数中插入键路径的行为分解为因素.我建议您遵循 Database 本身，而不是通过路径遵循 HashMap< String，Database> ，因为这将允许您修改其 data 字段的末尾.为此，我建议使用带有此签名的函数:
Now we just need to clean up the code. Since you're using it more that once, I'd recommend factoring the act of inserting a path of keys into a function. Rather than following the HashMap<String, Database> through the path, I'd recommend following the Database itself, since that will allow you to modify its data field at the end. To that end, I'd suggest a function with this signature:
impl Database {
fn insert_path(&mut self, path: &[&str]) -> &mut Database {
todo!()
}
}
接下来，由于我们只需要在不存在的情况下创建一个新的 Database ( d )，我们可以使用 Entry 的 or_insert_with 方法仅在必要时创建新数据库.当具有创建新数据库的功能时，这是最简单的，因此让我们将#[derive(Default)] 添加到 Database 上的派生列表中.这就是我们的功能
Next, since we only need to create a new Database (d) when one doesn't already exist, we can use Entry's or_insert_with method to create the new database only when necessary. This is easiest when there's a function to create the new database, so let's add #[derive(Default)] to the list of derives on Database. That makes our function
impl Database {
fn insert_path(&mut self, path: &[&str]) -> &mut Self {
let mut root = self;
// iterate throught path
for subkey in path.iter() {
// insert the new database object if necessary and
// set root to the hashmap of children
root = root
.children
.entry(subkey.to_string())
// insert (if necessary) using the Database::default method
.or_insert_with(Database::default);
}
root
}
}
这时，我们应该运行 cargo clippy 来查看是否有任何建议.关于在&& str 上使用 to_string 的一种方法.要解决此问题，您有两种选择.一种，使用其他方法之一将& str s转换为 String s而不是 to_string .第二，在使用 to_string 之前，先取消引用&& str .第二种选择更简单.由于我们要遍历& [& str] (原始的 Vec<& str> :: iter )，因此迭代中的项是& str .剥去多余参考层的惯用方式是使用一种模式来分解项目.
At this point we should run cargo clippy to see if there are any suggestions. There's one about using to_string on &&str. To fix that, you have two choices. One, use one of the other methods for converting &strs to Strings instead of to_string. Two, dereference the &&str before using to_string. This second option is simpler. Since we're iterating over &[&str] (Vec<&str>::iter in your original), the items in the iteration are &&str. The idiomatic way to strip off the extra layer of references is to use a pattern to destructure the items.
for &subkey in path {
^^^ this is new
... // subkey has type &str instead of &&str here
}
我的最后一条建议是将 root 的名称更改为更通用的名称，例如 node .它只是一开始的根源，因此此名称在此之后具有误导性.这是最终的代码以及您的测试游乐场):
My last piece of advice would be to change the name of root to something more generic, like node. It's only the root right at the start, so the name is misleading after that. Here's the final code together with your tests (playground):
use std::collections::HashMap;
#[derive(Default, Debug)]
struct Database {
children: HashMap<String, Database>,
data: String,
}
impl Database {
fn insert_path(&mut self, path: &[&str]) -> &mut Self {
// node is a mutable reference to the current database
let mut node = self;
// iterate through the path
for &subkey in path.iter() {
// insert the new database object if necessary and
// set node to (a mutable reference to) the child node
node = node
.children
.entry(subkey.to_string())
.or_insert_with(Database::default);
}
node
}
}
fn main() {
// make a databse object
let mut db = Database {
children: HashMap::new(),
data: "root".to_string(),
};
// some example subkeys
let subkeys = vec!["key1", "key1.1", "key1.1.3"];
// and the value i want to insert
let value = "myvalue";
let node = db.insert_path(&subkeys);
node.data = value.to_string();
println!("{:#?}", db);
let subkeys = vec!["key1", "key1.1", "key1.1.2"];
let value = "myvalue2";
let node = db.insert_path(&subkeys);
node.data = value.to_string();
println!("{:#?}", db);
}
这篇关于插入任意嵌套的HashMap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
