Как вернуть итератор по ключам HashMap из реализации черты? - PullRequest
Новая
       10

Как вернуть итератор по ключам HashMap из реализации черты?

1 голос
/ 29 октября 2019

Я пытаюсь создать простую библиотеку графов в Rust. Есть черта Graph, которую должен реализовать любой граф. Эта черта имеет только одну функцию на данный момент, nodes, которая позволяет выполнять итерацию узлов графа с использованием цикла for-in.

Реализация Graph, MapGraph, является облегченной оболочкой вокругHashMap. MapGraph должен реализовывать метод черты Graph nodes. У меня проблемы с тем, чтобы заставить это работать.

Вот код для Graph: 

pub trait Graph<N> {
    fn nodes(&self) -> Box<dyn Iterator<Item = &N>>;
}

А вот код для MapGraph: 

use std::collections::HashMap;

use crate::rep::Graph;

pub struct MapGraph<N> {
    map: HashMap<N, HashMap<N, ()>>
}

impl<N> MapGraph<N> {
    pub fn new(map: HashMap<N, HashMap<N, ()>>) -> Self {
        MapGraph { map }
    }
}

impl<N> Graph<N> for MapGraph<N> {
    fn nodes(&self) -> Box<dyn Iterator<Item=&N>> {
        let keys = self.map.keys();

        Box::new(keys)
    }
}

Компилятор выдает эту ошибку: 

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:19:29
   |
19 |         let keys = self.map.keys();
   |                             ^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
  --> src/lib.rs:18:5
   |
18 | /     fn nodes(&self) -> Box<dyn Iterator<Item = &N>> {
19 | |         let keys = self.map.keys();
20 | |
21 | |         Box::new(keys)
22 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:19:20
   |
19 |         let keys = self.map.keys();
   |                    ^^^^^^^^
   = note: but, the lifetime must be valid for the static lifetime...
   = note: ...so that the expression is assignable:
           expected std::boxed::Box<(dyn std::iter::Iterator<Item = &N> + 'static)>
              found std::boxed::Box<dyn std::iter::Iterator<Item = &N>>

Я нашел другие ссылки на эту ошибку, но эти случаи, похоже, не похожи на те, что у меня здесь.

I 'используя Box, потому что черта Graph имеет функцию, которая сама возвращает черту. Как правильно вернуть итератор (или любую другую черту)? дает такой подход в качестве одного из вариантов, и я не смог реализовать ни один из остальных. Если есть другой способ сделать это, это будет хорошо.

Какие у меня есть варианты решения этой конкретной проблемы?

1 Ответ

2 голосов
/ 29 октября 2019

Это работает, если вы явно указываете, что возвращаемый объект признака (dyn Iterator) содержит ссылки, привязанные к времени жизни self.

Без добавления этой границы компилятор не может сделать выводиз сигнатуры функции, что итератор не может быть использован после перемещения или уничтожения self. Поскольку компилятор не может вывести это, он не может безопасно использовать self.map.keys() в выходных данных функции.

Рабочий пример с добавленной границей: 

pub trait Graph<N> {
    fn nodes<'a>(&'a self) -> Box<dyn Iterator<Item = &N> + 'a>;
}

use std::collections::HashMap;

pub struct MapGraph<N> {
    map: HashMap<N, HashMap<N, ()>>,
}

impl<N> MapGraph<N> {
    pub fn new(map: HashMap<N, HashMap<N, ()>>) -> Self {
        MapGraph { map }
    }
}

impl<N> Graph<N> for MapGraph<N> {
    fn nodes<'a>(&'a self) -> Box<dyn Iterator<Item = &N> + 'a> {
        let keys = self.map.keys();

        Box::new(keys)
    }
}

Playground

Я думал, что также потребуется граница Item = &'a N, но я думаю, что это уже охватывается "+ 'a" ...

NB, чтобы иметь смыслошибка типа: 

expected std::boxed::Box<(dyn std::iter::Iterator<Item = &N> + 'static)>
   found std::boxed::Box<dyn std::iter::Iterator<Item = &N>>

Вы должны понимать, что компилятор по эргономическим причинам автоматически добавляет квалификатор времени жизни + 'static к любому неквалифицированному объекту черты. Это означает, что неквалифицированный Box<dyn MyTrait> преобразуется компилятором в Box<(dyn MyTrait + 'static)>, что, в свою очередь, означает, что объект не может содержать любых ссылок, кроме тех, которые существуют в течение всего времени жизни программы. Имея это в виду, вы можете понять, почему self.map.keys() не соответствует этой строгой границе, и требуется более конкретная явная граница.

...