11

我有一个结构Foo

struct Foo {
    v: String,
    // Other data not important for the question
}

我想处理一个数据流并将结果保存到该字段上并Vec<Foo>为此创建一个索引。Vec<Foo>Foo::v

我想使用 aHashMap<&str, usize>作为索引,键在哪里,&Foo::v值是 中的位置Vec<Foo>,但我愿意接受其他建议。

我想尽可能快地处理数据流,这不需要做两次明显的事情。

例如,我想:

  • String每个数据流读取只分配一次
  • 不要搜索索引两次,一次是检查键不存在,一次是插入新键。
  • 不要使用Rcor增加运行时间RefCell

借用检查器不允许此代码:

let mut l = Vec::<Foo>::new();
{
    let mut hash = HashMap::<&str, usize>::new();
    //here is loop in real code, like: 
    //let mut s: String; 
    //while get_s(&mut s) {
    let s = "aaa".to_string();
    let idx: usize = match hash.entry(&s) { //a
        Occupied(ent) => {
            *ent.get()
        }
        Vacant(ent) => {
            l.push(Foo { v: s }); //b
            ent.insert(l.len() - 1);
            l.len() - 1
        }
    };
    // do something with idx
}

有多个问题:

  1. hash.entry借用钥匙,所以s必须有一个“更大”的生命周期hash
  2. 我想s在 (b) 行移动,而我在 (a) 行有一个只读引用

那么我应该如何在没有额外调用String::clone或调用HashMap::get后调用的情况下实现这个简单的算法HashMap::insert呢?

4

3 回答 3

10

一般来说,你试图完成的事情是不安全的,Rust 正确地阻止了你做你不应该做的事情。对于一个简单的例子为什么,考虑一个Vec<u8>. 如果向量具有一项且容量为一项,则向向量添加另一个值将导致重新分配和复制向量中的所有值,从而使对向量的任何引用无效。这将导致索引中的所有键都指向任意内存地址,从而导致不安全的行为。编译器会阻止这种情况。

这种情况下,编译器不知道但程序员不知道的两条额外信息:

  1. 还有一个额外的间接性——String是堆分配的,因此将指针移动到该堆分配并不是真正的问题。
  2. String永远不会改变。如果是,那么它可能会重新分配,从而使引用地址无效。使用 aBox<[str]>而不是 aString将是通过类型系统强制执行此操作的一种方法。

在这种情况下,使用unsafe代码是可以的,只要您正确记录为什么它不是不安全的

use std::collections::HashMap;

#[derive(Debug)]
struct Player {
    name: String,
}

fn main() {
    let names = ["alice", "bob", "clarice", "danny", "eustice", "frank"];

    let mut players = Vec::new();
    let mut index = HashMap::new();

    for &name in &names {
        let player = Player { name: name.into() };
        let idx = players.len();

        // I copied this code from Stack Overflow without reading the prose
        // that describes why this unsafe block is actually safe
        let stable_name: &str = unsafe { &*(player.name.as_str() as *const str) };

        players.push(player);
        index.insert(idx, stable_name);
    }

    for (k, v) in &index {
        println!("{:?} -> {:?}", k, v);
    }

    for v in &players {
        println!("{:?}", v);
    }
}

但是,我的猜测是您不希望在您的main方法中使用此代码,而是希望从某个函数中返回它。这将是一个问题,因为您很快就会遇到为什么我不能在同一个结构中存储一个值和对该值的引用?.


老实说,有些代码风格不太适合 Rust 的限制。如果你遇到这些,你可以:

  • 确定 Rust 不适合您或您的问题。
  • 使用unsafe代码,最好是经过彻底测试并且只公开一个安全的 API。
  • 研究替代表示。

例如,我可能会重写代码以使索引成为键的主要所有者:

use std::collections::BTreeMap;

#[derive(Debug)]
struct Player<'a> {
    name: &'a str,
    data: &'a PlayerData,
}

#[derive(Debug)]
struct PlayerData {
    hit_points: u8,
}

#[derive(Debug)]
struct Players(BTreeMap<String, PlayerData>);

impl Players {
    fn new<I>(iter: I) -> Self
    where
        I: IntoIterator,
        I::Item: Into<String>,
    {
        let players = iter
            .into_iter()
            .map(|name| (name.into(), PlayerData { hit_points: 100 }))
            .collect();
        Players(players)
    }

    fn get<'a>(&'a self, name: &'a str) -> Option<Player<'a>> {
        self.0.get(name).map(|data| Player { name, data })
    }
}

fn main() {
    let names = ["alice", "bob", "clarice", "danny", "eustice", "frank"];

    let players = Players::new(names.iter().copied());

    for (k, v) in &players.0 {
        println!("{:?} -> {:?}", k, v);
    }

    println!("{:?}", players.get("eustice"));
}

或者,如制作使用项目字段作为键的查找表的惯用方法是什么?,您可以包装您的类型并将其存储在一个集合容器中:

use std::collections::BTreeSet;

#[derive(Debug, PartialEq, Eq)]
struct Player {
    name: String,
    hit_points: u8,
}

#[derive(Debug, Eq)]
struct PlayerByName(Player);

impl PlayerByName {
    fn key(&self) -> &str {
        &self.0.name
    }
}

impl PartialOrd for PlayerByName {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for PlayerByName {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.key().cmp(&other.key())
    }
}

impl PartialEq for PlayerByName {
    fn eq(&self, other: &Self) -> bool {
        self.key() == other.key()
    }
}

impl std::borrow::Borrow<str> for PlayerByName {
    fn borrow(&self) -> &str {
        self.key()
    }
}

#[derive(Debug)]
struct Players(BTreeSet<PlayerByName>);

impl Players {
    fn new<I>(iter: I) -> Self
    where
        I: IntoIterator,
        I::Item: Into<String>,
    {
        let players = iter
            .into_iter()
            .map(|name| {
                PlayerByName(Player {
                    name: name.into(),
                    hit_points: 100,
                })
            })
            .collect();
        Players(players)
    }

    fn get(&self, name: &str) -> Option<&Player> {
        self.0.get(name).map(|pbn| &pbn.0)
    }
}

fn main() {
    let names = ["alice", "bob", "clarice", "danny", "eustice", "frank"];

    let players = Players::new(names.iter().copied());

    for player in &players.0 {
        println!("{:?}", player.0);
    }

    println!("{:?}", players.get("eustice"));
}

不使用Rc或增加运行时间RefCell

在不执行分析的情况下猜测性能特征绝不是一个好主意。老实说,我不相信当一个值被克隆或删除时增加一个整数会导致明显的性能损失。如果问题需要索引和向量,那么我会寻求某种共享所有权。

于 2017-04-23T01:00:22.577 回答
5

不要使用Rcor增加运行时间RefCell

@Shepmaster 已经演示了使用 来完成此操作,一旦您拥有,我会鼓励您检查实际花费unsafe了多少。Rc这是一个完整的版本Rc

use std::{
    collections::{hash_map::Entry, HashMap},
    rc::Rc,
};

#[derive(Debug)]
struct Foo {
    v: Rc<str>,
}

#[derive(Debug)]
struct Collection {
    vec: Vec<Foo>,
    index: HashMap<Rc<str>, usize>,
}

impl Foo {
    fn new(s: &str) -> Foo {
        Foo {
            v: s.into(),
        }
    }
}

impl Collection {
    fn new() -> Collection {
        Collection {
            vec: Vec::new(),
            index: HashMap::new(),
        }
    }

    fn insert(&mut self, foo: Foo) {
        match self.index.entry(foo.v.clone()) {
            Entry::Occupied(o) => panic!(
                "Duplicate entry for: {}, {:?} inserted before {:?}",
                foo.v,
                o.get(),
                foo
            ),
            Entry::Vacant(v) => v.insert(self.vec.len()),
        };
        self.vec.push(foo)
    }
}

fn main() {
    let mut collection = Collection::new();

    for foo in vec![Foo::new("Hello"), Foo::new("World"), Foo::new("Go!")] {
        collection.insert(foo)
    }

    println!("{:?}", collection);
}
于 2017-04-27T11:38:53.553 回答
1

错误是:

error: `s` does not live long enough
  --> <anon>:27:5
   |
16 |         let idx: usize = match hash.entry(&s) { //a
   |                                            - borrow occurs here
...
27 |     }
   |     ^ `s` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

最后note:就是答案所在。

s 必须寿命更长hash,因为您&sHashMap. s删除时,此引用将变为无效。但是,正如注释所说,hash s. 一个快速的解决方法是交换它们的声明顺序:

let s = "aaa".to_string();
let mut hash = HashMap::<&str, usize>::new();

但是现在你有另一个问题:

error[E0505]: cannot move out of `s` because it is borrowed
  --> <anon>:22:33
   |
17 |         let idx: usize = match hash.entry(&s) { //a
   |                                            - borrow of `s` occurs here
...
22 |                 l.push(Foo { v: s }); //b
   |                                 ^ move out of `s` occurs here

这个比较明显。s被 借用Entry,它将一直存在到块的末尾。克隆s将解决这个问题:

l.push(Foo { v: s.clone() }); //b

我只想分配 s 一次,而不是克隆它

但是类型Foo.v是,所以无论如何String它都会拥有自己的副本。str只是那种类型意味着你必须复制s.

您可以用 a 替换它,&str这将允许它作为对 的引用s

struct Foo<'a> {
    v: &'a str,
}

pub fn main() {
    // s now lives longer than l
    let s = "aaa".to_string();
    let mut l = Vec::<Foo>::new();
    {
        let mut hash = HashMap::<&str, usize>::new();

        let idx: usize = match hash.entry(&s) {
            Occupied(ent) => {
                *ent.get()
            }
            Vacant(ent) => {
                l.push(Foo { v: &s });
                ent.insert(l.len() - 1);
                l.len() - 1
            }
        };
    }
}

请注意,以前我必须将声明s移至 before hash,以便它的寿命更长。但是现在,l拥有对 的引用s,因此必须更早地声明它,以使其寿命更长l

于 2017-04-17T22:47:45.827 回答