Исключить параметр времени жизни из черты, реализация которой оборачивает HashMap?

Question

Я бы хотел обернуть несколько методов HashMap, таких как insert и keys. Эта попытка компилируется, и тесты проходят:

use std::collections::HashMap;
use std::hash::Hash;

pub trait Map<'a, N: 'a> {
    type ItemIterator: Iterator<Item=&'a N>;

    fn items(&'a self) -> Self::ItemIterator;
    fn insert(&mut self, item: N);
}

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

impl<N: Eq + Hash> MyMap<N> {
    fn new() -> Self {
        MyMap { map: HashMap::new() }
    }
}

impl<'a, N: 'a + Eq + Hash> Map<'a, N> for MyMap<N> {
    type ItemIterator = std::collections::hash_map::Keys<'a, N, ()>;

    fn items(&'a self) -> Self::ItemIterator {
        self.map.keys()
    }

    fn insert(&mut self, item: N) {
        self.map.insert(item, ());
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Eq, Hash, PartialEq, Debug)]
    struct MyItem;

    #[test]
    fn test() {
        let mut map = MyMap::new();
        let item = MyItem { };

        map.insert(&item);

        let foo = map.items().collect::<Vec<_>>();

        for it_item in map.items() {
            assert_eq!(it_item, &&item);
        }

        assert_eq!(foo, vec![&&item]);
    }
}

Я бы хотел исключить необходимость в параметре времени жизни в Map, если это возможно, но до сих пор не нашел пути. Похоже, проблема связана с определением std::collections::hash_map::Keys, для которого требуется параметр времени жизни.

Попытки переопределить работу черты Map, пока не возникнет необходимость в предоставлении параметра времени жизни для Keys:

use std::collections::HashMap;
use std::hash::Hash;

pub trait Map<N> {
    type ItemIterator: Iterator<Item=N>;

    fn items(&self) -> Self::ItemIterator;
    fn insert(&mut self, item: N);
}

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

impl<N: Eq + Hash> MyMap<N> {
    fn new() -> Self {
        MyMap { map: HashMap::new() }
    }
}

// ERROR: "unconstrained lifetime parameter"
impl<'a, N> Map<N> for MyMap<N> {
    type ItemIterator = std::collections::hash_map::Keys<'a, N, ()>;
}

Компилятор выдает ошибку о неограниченном параметре времени жизни, которую я не смог исправить без повторного введения времени жизни в черту Map.

Основная цель этого Эксперимент состоял в том, чтобы увидеть, как я могу исключить Box из предыдущих попыток. Как объясняет этот вопрос , это еще один способ вернуть итератор. Так что в данный момент меня не интересует такой подход.

Как настроить Map и реализацию без , вводящего параметр времени жизни или использующего Box?

Answer 1

Нужно подумать о том, что, поскольку hash_map::Keys имеет универсальный c параметр времени жизни, он, вероятно, необходим по какой-то причине, поэтому ваша черта для абстрагирования над Keys, вероятно, понадобится.

В этом случае в определении Map вам нужно каким-то образом указать, как долго живет ItemIterator s Item. (Item - &'a N).

Это было ваше определение:

type ItemIterator: Iterator<Item=&'a N>

Вы пытаетесь сказать, что для любой структуры, которая реализует Map, структура связана ItemIterator должен быть итератором ссылок; однако одно только это ограничение бесполезно без какой-либо дополнительной информации: нам также нужно знать, как долго действует ссылка (следовательно, type ItemIterator: Iterator<Item=&N> выдает ошибку: она пропускает эту информацию и в настоящее время не может быть исключена AFAIK).

Итак, вы выбираете 'a, чтобы указать общее время жизни c, которое, как вы гарантируете, будет действительным для каждого &'a N. Теперь, чтобы выполнить проверку заимствования, докажите, что &'a N будет действительным для 'a, и установите sh некоторые полезные обещания о 'a, вы указываете, что:

1. Любой значение для ссылки &self, присвоенное items(), должно жить как минимум столько же, сколько 'a. Это гарантирует, что для каждого из возвращенных элементов (&'a N) ссылка &self должна оставаться действительной, чтобы ссылка элемента оставалась действительной, иными словами, элементы должны иметь срок действия self. Этот инвариант позволяет ссылаться на &self в возвращаемом значении items(). Вы указали это с помощью fn items(&'a self). (Примечание: my_map.items() - это сокращение от MyMap::items(&my_map)).
2. Каждый из N должен также оставаться действительным до тех пор, пока 'a. Это важно, если объекты содержат какие-либо ссылки, которые не будут существовать вечно (или не-1043 * ссылки); это гарантирует, что все ссылки, содержащиеся в элементе N, будут жить как минимум до 1045 *. Вы указали это с помощью ограничения N: 'a.

Итак, для повторения, определение Map<'a, N> требует, чтобы функция items() разработчика возвращала ItemIterator ссылок, которые действительно для 'a для элементов, которые действительны для 'a. Теперь ваша реализация:

impl<'a, N: 'a + Eq + Hash> Map<'a, N> for MyMap<N> { ... }

Как видите, параметр 'a полностью не ограничен, поэтому вы можете использовать любой 'a с методами из Map в экземпляре MyMap До тех пор, пока N выполняет свои ограничения N: 'a + Eq + Hash. 'a должен автоматически стать самым длинным временем жизни, для которого действительны и N, и карта, переданная в items().

В любом случае, то, что вы здесь описываете, называется потоковым итератором, который был проблема в годах. Для некоторого уместного обсуждения см. Одобренный, но в настоящее время невыполненный RF C 1598 (но готовьтесь быть пораженными).

Наконец, как прокомментировали некоторые люди, возможно, что ваш Map черта может быть плохим дизайном с самого начала, поскольку она может быть лучше выражена как комбинация встроенного IntoIterator<Item=&'a N> и отдельной черты для insert(). Это будет означать, что итератор по умолчанию используется в for loop, et c. будет итератором предметов, что не согласуется со встроенным HashMap, но я не совсем понимаю цель вашей черты, поэтому думаю, что ваш дизайн, скорее всего, имеет смысл.