迭代器项的生命周期的"冲突要求"作为参数传递给方法

Question

我正在尝试编译这段代码:

use std::collections::HashMap;

#[derive(PartialEq, Eq, Hash, Clone)]
struct Key<'a> {
    v: &'a str
}

fn make_key_iter(s: &str) -> Box<Iterator<Item = Key>> {
    Box::new(s.split('.').map(|e| Key { v: e }))
}

struct Node<'a> {
    children: HashMap<Key<'a>, Box<Node<'a>>>
}

impl<'a> Node<'a> {
    fn lookup<'b>(&self, mut iter: Box<Iterator<Item = Key<'b>>>) -> bool {
        match iter.next() {
            Some(key) => match self.children.get(&key) {
                             Some(node) => node.lookup(iter),
                             None => false
                         },
            None => true
        }
    }
}

fn main() {
    let s = "a.b.c.d".to_string();
    let iter = make_key_iter(s.as_slice());
    let node = Node { children: HashMap::new() };
    node.lookup(iter);
}

围栏链接

编译时会出现以下错误:

<anon>:18:20: 18:26 error: cannot infer an appropriate lifetime due to conflicting requirements
<anon>:18         match iter.next() {
                         ^~~~~~
<anon>:17:5: 25:6 help: consider using an explicit lifetime parameter as shown: fn lookup(&self, mut iter: Box<Iterator<Item = Key<'b>>>) -> bool

令人困惑的是,编译器建议的签名完全无效,因为它使用了未定义的生命周期.

Answer 1

首先,一个建议:由于盒装迭代器也是迭代器,您可以将查找函数更改为

fn lookup<'b, I: Iterator<Item = Key<'b>>>(&self, mut iter: I) -> bool {
    match iter.next() {
        Some(key) => match self.children.get(&key) {
                         Some(node) => node.lookup(iter),
                         None => false
                     },
        None => true
    }
}

这有点笼统.但问题仍然存在.你试图将一个&Key<'b>in 传递self.children.get(&key)给HashMap,它实际上需要一个&Qwhere Qimplements BorrowFrom<Key<'a>>.编译器的建议现在'b用'a这样替换:

fn lookup<I: Iterator<Item = Key<'a>>>(&self, mut iter: I) -> bool { //'
    match iter.next() {
        Some(key) => match self.children.get(&key) {
                         Some(node) => node.lookup(iter),
                         None => false
                     },
        None => true
    }
}

这肯定会让编译器开心.但这不是你想要的!它会不必要地限制您可以用作查找参数的字符串切片集.这样,您只能使用引用内存的字符串切片,该内存至少与'a引用的作用域一样长.但是对于查找,实际上并不需要这种限制.

解决方案是完全摆脱QHashMap get函数的type参数中的任何生命周期参数.Q=Key<'something>我们实际上可以使用,而不是使用Q=str.我们只需要添加以下BorrowFrom实现

impl<'a> BorrowFrom<Key<'a>> for str {
    fn borrow_from<'s>(owned: &'s Key<'a>) -> &'s str {
        owned.v
    }
}

并将Key类型设为public(因为它在公共特征中用作参数).对我有用的查找功能如下所示:

fn lookup_iter<'b, I: Iterator<Item = Key<'b>>>(&self, mut i: I) -> bool {
    if let Some(key) = i.next() {
        match self.children.get(key.v) {
            Some(node_box_ref) => node_box_ref.lookup_iter(i),
            None => false
        }
    } else {
        true
    }
}

如果我们把所有东西拼凑起来,我们就会得到

#![feature(core)]
#![feature(hash)]
#![feature(std_misc)]
#![feature(collections)]

use std::collections::HashMap;
use std::collections::hash_map::Entry::{ Occupied, Vacant };
use std::borrow::BorrowFrom;

#[derive(PartialEq, Eq, Hash, Clone)]
pub struct Key<'a> {
    v: &'a str
}

impl<'a> BorrowFrom<Key<'a>> for str {
    fn borrow_from<'s>(owned: &'s Key<'a>) -> &'s str {
        owned.v
    }
}

fn str_to_key(s: &str) -> Key { 
    Key { v: s }
}

struct Node<'a> {
    children: HashMap<Key<'a>, Box<Node<'a>>>
}

impl<'a> Node<'a> {
    fn add_str(&mut self, s: &'a str) {
        self.add_iter(s.split('.').map(str_to_key))
    }

    fn add_iter<I>(&mut self, mut i: I) where I: Iterator<Item = Key<'a>> { //'
        if let Some(key) = i.next() {
            let noderef =
                match self.children.entry(key) {
                    Vacant(e) => {
                        let n = Node { children: HashMap::new() };
                        e.insert(Box::new(n))
                    }
                    Occupied(e) => {
                        e.into_mut()
                    }
                };
            noderef.add_iter(i);
        }
    }

    fn lookup_str(&self, s: &str) -> bool {
        self.lookup_iter(s.split('.').map(str_to_key))
    }

    fn lookup_iter<'b, I>(&self, mut i: I) -> bool where I: Iterator<Item = Key<'b>> {
        if let Some(key) = i.next() {
            match self.children.get(key.v) {
                Some(node_box_ref) => node_box_ref.lookup_iter(i),
                None => false
            }
        } else {
            true
        }
    }
}

fn main() {
    let mut node: Node<'static> = Node { children: HashMap::new() }; //'
    node.add_str("one.two.three");
    { // <-- "inner scope"
        let s = String::from_str("one.two.three");
        println!("lookup: {:?}", node.lookup_str(&*s));
    }
    println!("The End");
}

正如你所看到的,我故意做node了一个Node<'static>,所以节点的生命周期参数'a实际上指的是整个程序的生命周期.在这个例子中没关系,因为它将存储的唯一字符串切片是字符串文字.请注意,对于查找,我创建了一个短期String对象.因此,生命周期参数'bin node.lookup_str将指的是明显短于的"内部范围" 'a='static.一切顺利!:)

哦,我也摆脱了迭代拳击.