How to create an empty iterator for a certain collection type (list/set/map) in Rust?

Question

I want to write a method which returns an iterator for a collection (e.g. LinkedList). But in some cases there's no suitable collection to return an iterator for. In such cases I'd like to return an "empty" iterator which iterates over no elements. But I couldn't find any associated function to construct a linked_list::Iter in the documentation.

Consider the following example:

use std::collections::HashMap;
use std::collections::LinkedList;
use std::collections::linked_list;

pub struct Graph {
    nodes: HashMap<usize, LinkedList<usize>>,
}

impl Graph {
    pub fn adjacent_nodes(&self, node: usize) -> linked_list::Iter<usize> {
        match self.nodes.get(&node) {
            Some(x) => x.iter(),
            _ => linked_list::Iter::<usize>::new()
        }
    }
}

I'd like to return an iterator over adjacent nodes from the adjacent_nodes method. But when asked for neighbours of a non-existing node, the method should return an iterator over nothing, obviously. But how could I create it? The code I gave doesn't compile actually:

src/graph.rs:13:18: 13:49 error: no associated item named `new` found for type
        `collections::linked_list::Iter<'_, usize>` in the current scope
src/graph.rs:13             _ => linked_list::Iter::<usize>::new()
                                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I guess, I could solve the problem with boxed::Box but it is clearly a suboptimal solution because of unnecessary heap allocation that I try to avoid.

So, my question is: Is it possible in Rust to create an iterator-over-nothing of specific type?

Answer 1

You cannot do it, not with by-reference iterators, because they are always tied to a concrete collection instance.

What you can do is to return boxed iterator as a trait object:

pub fn adjacent_nodes<'a>(&'a self, node: usize) -> Box<Iterator<Item=usize>+'a> {
    match self.nodes.get(&node) {
        Some(x) => Box::new(x.iter()),
        _ => Box::new(::std::iter::empty())
    }
}

std::iter::empty() returns an empty iterator, but of course its type is different from those of collection iterators, so you have to use a trait object. I also had to add a lifetime parameter because the iterator returned by iter() is tied to self.nodes, and you need to explain it to the compiler.