Как реализовать итератор, дающий изменчивые ссылки

Question

Я пытаюсь реализовать простой итератор поиска:

pub struct LookupIterMut<'a, D> {
    data : &'a mut [D],
    indices : &'a [usize],
    i: usize
}

impl<'a, D> Iterator for LookupIterMut<'a, D> {
    type Item = &'a mut D;

    fn next(&mut self) -> Option<Self::Item> {
        if self.i >= self.indices.len() {
            None
        } else {
            let index = self.indices[self.i] as usize;
            self.i += 1;
            Some(&mut self.data[index]) // error here
        }
    }
}

Идея состояла в том, чтобы разрешить вызывающему абоненту последовательный изменяемый доступ к внутренней памяти. Однако я получаю сообщение об ошибке cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements.

Насколько я понимаю, мне придется изменить сигнатуру функции на next(&'a mut self) -> .., но это больше не будет Итератор.

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

// ...
type Item = *mut D;
// ...

Спасибо за вашу помощь

Answer 1

Использование unsafe

Напоминание: необязательно иметь в любое время две доступные изменяемые ссылки на одно и то же базовое значение.

Суть проблема заключается в том, что язык не может гарантировать, что код будет соответствовать вышеуказанному правилу, если indices будет содержать любой дубликат, то реализованный итератор позволит одновременно получать две изменяемые ссылки на один и тот же элемент в срезе, что нецелесообразно.

Если язык не может дать гарантию сам по себе, то вам нужно либо найти альтернативный подход, либо вам нужно провести юридическую проверку и затем использовать unsafe.

В этом случае на игровой площадке :

impl<'a, D> LookupIterMut<'a, D> {
    pub fn new(data: &'a mut [D], indices: &'a [usize]) -> Self {
        let set: HashSet<usize> = indices.iter().copied().collect();
        assert!(indices.len() == set.len(), "Duplicate indices!");

        Self { data, indices, i: 0 }
    }
}

impl<'a, D> Iterator for LookupIterMut<'a, D> {
    type Item = &'a mut D;

    fn next(&mut self) -> Option<Self::Item> {
        if self.i >= self.indices.len() {
            None
        } else {
            let index = self.indices[self.i];
            assert!(index < self.data.len());

            self.i += 1;

            //  Safety:
            //  -   index is guaranteed to be within bounds.
            //  -   indices is guaranteed not to contain duplicates.
            Some(unsafe { &mut *self.data.as_mut_ptr().offset(index as isize) })
        }
    }
}

С точки зрения производительности, построение HashSet в конструкторе довольно неудовлетворительно, но на самом деле его нельзя избежать в целом . Например, если гарантируется сортировка indices, то проверка может выполняться без выделения.

Answer 2

Ваш код недействителен, потому что вы пытаетесь вернуть несколько изменяемых ссылок на один и тот же фрагмент с одним и тем же временем жизни 'a.

Чтобы это работало, вам потребуется разное время жизни для каждого возвращаемого значения Item, чтобы не хранить 2 изменяемые ссылки на один и тот же фрагмент. Вы не можете сделать это сейчас, потому что для этого требуются Generi c Связанные типы:

type Item<'item> = &'item mut D; // Does not work today

Одним из решений является проверка уникальности индексов и повторное связывание времени жизни ссылочного элемента с 'a в unsafe блок. Это безопасно, потому что все индексы уникальны, поэтому пользователь не может хранить 2 изменяемые ссылки на один и тот же элемент.

Не забудьте инкапсулировать весь код внутри модуля, чтобы структура не могла быть собрана без проверка new:

mod my_mod {
    pub struct LookupIterMut<'a, D> {
        data: &'a mut [D],
        indices: &'a [usize],
        i: usize,
    }

    impl<'a, D> LookupIterMut<'a, D> {
        pub fn new(data: &'a mut [D], indices: &'a [usize]) -> Result<Self, ()> {
            let mut uniq = std::collections::HashSet::new();
            let all_distinct = indices.iter().all(move |&x| uniq.insert(x));

            if all_distinct {
                Ok(LookupIterMut {
                    data,
                    indices,
                    i: 0,
                })
            } else {
                Err(())
            }
        }
    }

    impl<'a, D> Iterator for LookupIterMut<'a, D> {
        type Item = &'a mut D;

        fn next(&mut self) -> Option<Self::Item> {
            self.indices.get(self.i).map(|&index| {
                self.i += 1;

                unsafe { std::mem::transmute(&mut self.data[index]) }
            })
        }
    }
}

Обратите внимание, что ваш код будет Pani c, если один индекс выходит за пределы.