the trait `for<'r> core::ops::FnMut<(&'r &(K, T),)>` is not implemented for the type `P`

Question

I want a sorted vector of (Key, Type), which is sorted only by Key.

I came up with the code below:

struct SortedVec<K, T> {
    data: Vec<(K, T)>
}

impl<K: Ord, T> SortedVec<K, T> {
    fn new() -> SortedVec<K, T> {
        SortedVec { data: Vec::new() }
    }

    fn add(&mut self, k: K, t: T) {
        self.data.push((k, t));
        self.data.sort_by(|a, b| a.0.cmp(&b.0));
    }

    fn find<P>(&self, predicate: P) -> Option<&(K, T)> where P: FnMut(&(K, T)) -> bool {
        self.data.iter().find(predicate)
    }
}

But this doesn't compile with the following errors:

anon>:16:30: 16:45 error: the trait `for<'r> core::ops::FnMut<(&'r &(K, T),)>` is not implemented for the type `P` [E0277]
anon>:16             self.data.iter().find(predicate)
                                       ^~~~~~~~~~~~~~~
<anon>:16:30: 16:45 error: the trait `for<'r> core::ops::FnOnce<(&'r &(K, T),)>` is not implemented for the type `P` [E0277]
<anon>:16             self.data.iter().find(predicate)
                                       ^~~~~~~~~~~~~~~
error: aborting due to 2 previous errors
playpen: application terminated with error code 101

I can't find anything wrong with the type 'P'.

How can I fix it?

Matthieu M. Matthieu M. · Accepted Answer · 2015-05-17T14:51:11

Let's compare the bound on P and that required the compiler:

// P
        FnMut(    &(K, T)) -> bool

// required
for<'r> FnMut(&'r &(K, T)) -> bool

If you change the where clause to match the signature asked for by the compiler, it works (see here).

I believe the extra reference (and lifetime) are introduced by the use of iter, and thus linked to the lifetime of the iterator, but don't take my word for it.

I would point out, though, that Vec has a binary_search_by which is bound to be more efficient than a linear find:

fn binary_search_by<F>(&self, f: F) -> Result<usize, usize>
    where F: FnMut(&T) -> Ordering

You may wish to use that instead, since you went to the trouble of sorting it.

the trait `for<'r> core::ops::FnMut<(&'r &(K, T),)>` is not implemented for the type `P`

2 Answers