RFC 1552: contains-method-for-various-collections

libs (collections)

Summary

Add a contains method to VecDeque and LinkedList that checks if the collection contains a given item.

Motivation

A contains method exists for the slice type [T] and for Vec through Deref, but there is no easy way to check if a VecDeque or LinkedList contains a specific item. Currently, the shortest way to do it is something like:

vec_deque.iter().any(|e| e == item)

While this is not insanely verbose, a contains method has the following advantages:

Detailed design

Add the following method to std::collections::VecDeque:

impl<T> VecDeque<T> {
    /// Returns `true` if the `VecDeque` contains an element equal to the
    /// given value.
    pub fn contains(&self, x: &T) -> bool
        where T: PartialEq<T>
    {
        // implementation with a result equivalent to the result
        // of `self.iter().any(|e| e == x)`
    }
}

Add the following method to std::collections::LinkedList:

impl<T> LinkedList<T> {
    /// Returns `true` if the `LinkedList` contains an element equal to the
    /// given value.
    pub fn contains(&self, x: &T) -> bool
        where T: PartialEq<T>
    {
        // implementation with a result equivalent to the result
        // of `self.iter().any(|e| e == x)`
    }
}

The new methods should probably be marked as unstable initially and be stabilized later.

Drawbacks

Obviously more methods increase the complexity of the standard library, but in case of this RFC the increase is rather tiny.

While VecDeque::contains should be (nearly) as fast as [T]::contains, LinkedList::contains will probably be much slower due to the cache inefficient nature of a linked list. Offering a method that is short to write and convenient to use could lead to excessive use of said method without knowing about the problems mentioned above.

Alternatives

There are a few alternatives:

Unresolved questions

None so far.