• Start Date: 2014-10-29
• RFC PR #: rust-lang/rfcs#235
• Rust Issue #: rust-lang/rust#18424

Summary

This is a combined

The major components

• Removing most of the traits in collections.

• A general

  一般
  proposal for solving the "equiv" problem, as well as improving MaybeOwned.

• Patterns for overloading on by-need values and predicates.

• Initial,

  初期
  forwards-compatible steps toward Iterable.

• A coherent set

  セットする、集合
  of API conventions across the full variety of collections.

A big thank-you to @Gankro, who helped collect API information and worked through an initial

Motivation

This RFC aims to improve the design

Collection traits

The collections module defines

• Collection
• Mutable
• MutableSeq
• Deque
• Map, MutableMap
• Set,
  セットする、集合
  MutableSet

There are several problems with the current trait design:

• Most important: the traits do not provide iterator methods like iter. It is not possible to do so in a clean way without higher-kinded types, as the RFC explains in more detail below.

• The split between mutable and immutable

  不変の
  traits is not well-motivated by any of the existing collections.

• The methods defined

  定義する
  in these traits are somewhat anemic compared
  比較する
  to the suite of methods provided
  与える
  on the concrete
  具体的な/具象的な
  collections that implement
  実装する
  them.

Divergent APIs

Despite the current collection traits, the APIs of various

One problem in particular is the lack of clear guiding principles for the API design.

Providing

与える

slice APIs on Vec and String

The String and Vec types each provide a limited subset

The Equiv problem

There is a more subtle problem related to slices. It's common to use a HashMap with owned String keys, but then the natural API for things like lookup is not very usable:

#![allow(unused)]
fn main() {
fn find(&self, k: &K) -> Option<&V>
}

The problem is that, since K will be String, the find function requests a &String value -- whereas one typically

#![allow(unused)]
fn main() {
map.find(&"some literal".to_string())
}

which is unergonomic and requires an extra allocation

The current HashMap API works around this problem by providing

#![allow(unused)]
fn main() {
pub trait Equiv<T> {
    fn equiv(&self, other: &T) -> bool;
}

impl Equiv<str> for String {
    fn equiv(&self, other: &str) -> bool {
        self.as_slice() == other
    }
}

fn find_equiv<Q: Hash<S> + Equiv<K>>(&self, k: &Q) -> Option<&V>
}

There are a few downsides to this approach:

• It requires a duplicated _equiv variant of each method taking

  とる
  a reference
  参照
  to the key. (This downside could likely be mitigated using multidispatch.)

• Its correctness depends on equivalent

  等価
  values producing
  産出、産出する
  the same hash, which is not checked.

• String-keyed hash maps are very common, so newcomers are likely to run headlong into the problem. First, find will fail to work in the expected way. But the signature

  シグネチャ
  of find_equiv is more difficult to understand than find, and it it's not immediately
  直後に、直接的に
  obvious that it solves the problem.

• It is the right API for HashMap, but not helpful for e.g. TreeMap, which would want an analog for Ord.

The TreeMap API currently deals with this problem in an entirely different way:

#![allow(unused)]
fn main() {
/// Returns the value for which f(key) returns Equal.
/// f is invoked with current key and guides tree navigation.
/// That means f should be aware of natural ordering of the tree.
fn find_with(&self, f: |&K| -> Ordering) -> Option<&V>
}

Besides being less convenient -- you cannot write map.find_with("some literal") -- this function navigates the tree according

MaybeOwned

Sometimes a function does not know in advance whether it will need or produce

#![allow(unused)]
fn main() {
fn from_utf8_lossy<'a>(v: &'a [u8]) -> MaybeOwned<'a>
}

This function will return a string slice if the input was correctly utf8 encoded

#![allow(unused)]
fn main() {
pub enum MaybeOwned<'a> {
    Slice(&'a str),
    Owned(String),
}
}

This interface makes it possible to allocate only when necessary, but the MaybeOwned type (and connected machinery) are somewhat ad

Iterable

A frequently-requested feature for the collections module is an Iterable trait for "values that can be iterated

• Abstraction. Today, you can write a function that takes

  とる
  a single
  単一の
  Iterator, but you cannot write a function that takes
  とる
  a container and then iterates
  繰り返す、反復する
  over it multiple
  複数の
  times (perhaps with differing mutability levels). An Iterable trait could allow
  許可する、可能にする
  that.

• Ergonomics. You'd be able to write

  
  #![allow(unused)]
  fn main() {
  for v in some_vec { ... }
  }
  

  rather than

  
  #![allow(unused)]
  fn main() {
  for v in some_vec.iter() { ... }
  }
  

  and consume_iter(some_vec) rather than consume_iter(some_vec.iter()).

Detailed design

設計（する）

The collections today

The concrete

• Sequences

  連なり、並び
  • Vec
  • String
  • Slices
  • Bitv
  • DList
  • RingBuf
  • PriorityQueue

• Sets

  セットする、集合
  • HashSet
  • TreeSet
  • TrieSet
  • EnumSet
  • BitvSet

• Maps

  • HashMap
  • TreeMap
  • TrieMap
  • LruCache
  • SmallIntMap

The primary

Before diving into the details, there is one high-level changes that should be made to these collections. The PriorityQueue collection should be renamed to BinaryHeap, following the convention that concrete

The LruCache could be renamed for a similar

Design

設計（する）

principles

• Centering on Iterators. The Iterator trait is a strength of Rust's collections library. Because so many APIs can produce

  産出する
  iterators, adding
  たす
  an API that consumes one is very powerful -- and conversely as well. Moreover,
  その上
  iterators are highly efficient,
  効率のよい
  since you can chain several layers of modification without having to materialize intermediate
  中間の、中級の
  results.
  結果、戻り値
  Thus,
  それゆえに、従って、
  whenever possible, collection APIs should strive to work with iterators.

  In particular, some existing convenience methods avoid

  避ける、回避する
  iterators for either performance or ergonomic reasons. We should instead improve the ergonomics and performance of iterators, so that these extra convenience methods are not necessary and so that all collections can benefit.

• Minimizing method variants. One problem with some of the current collection APIs is the proliferation of method variants. For example, HashMap include seven methods that begin with the name find! While each method has a motivation, the API as a whole can be bewildering, especially to newcomers.

  When possible, we should leverage the trait system, or find other abstractions, to reduce the need for method variants while retaining their ergonomics and power.

  累乗

• Conservatism. It is easier to add APIs than to take

  とる
  them away. This RFC takes
  とる
  a fairly conservative stance on what should be included in the collections APIs. In general,
  一般
  APIs should be very clearly motivated by a wide variety of use cases, either for expressiveness, performance, or ergonomics.

Removing the traits

This RFC proposes a somewhat radical step for the collections traits: rather than reform them, we should eliminate them altogether -- for now.

Unlike inherent methods, which can easily be added

Lack of iterator methods

In particular, there is one way in which the current traits are clearly wrong: they do not provide standard methods like iter, despite these being fundamental to working with collections in Rust. Sadly, this gap is due to inexpressiveness in the language,

#![allow(unused)]
fn main() {
trait Iter {
    type A;
    type I: Iterator<&'a A>;    // what is the lifetime here?
    fn iter<'a>(&'a self) -> I; // and how to connect it to self?
}
}

The problem is that, when implementing this trait, the return type I of iter should depend on the lifetime of self. For example, the corresponding

#![allow(unused)]
fn main() {
impl<T> Vec<T> {
    fn iter(&'a self) -> Items<'a, T> { ... }
}
}

This means that, given

#![allow(unused)]
fn main() {
trait Iter {
    type A;
    type I<'a>: Iterator<&'a A>;
    fn iter<'a>(&self) -> I<'a>;
}
}

In this case, I is parameterized

In general,

HKT would also allow

Thus,

Persistent/immutable collections

Another problem with the current collection traits is the split between immutable

However, persistent collection APIs have not been thoroughly explored in Rust; it would be hasty to standardize on a set

Downsides of removal

There are two main downsides to removing the traits without a replacement:

1. It becomes impossible to write code using generics over a "kind" of collection (like Map).

2. It becomes more difficult to ensure

   保証する
   that the collections share a common API.

For point (1), first, if the APIs are sufficiently

For point (2), first, the current traits have failed to keep the APIs in line, as we will see below. Second, this RFC is the antidote: we establish a clear set

Why not leave the traits as "experimental"?

An alternative

Such a strategy doesn't buy much relative to removal (given the arguments

Solving the _equiv and MaybeOwned problems

The basic problem that leads to _equiv methods is that:

• &String and &str are not the same type.
• The &str type is more flexible and hence more widely used.
• Code written for a generic type T that takes
  とる
  a reference
  参照
  &T will therefore not be suitable when T is instantiated with String.

A similar

The Borrow trait

This RFC proposes to use a trait, Borrow to connect borrowed and owned data in a generic fashion:

#![allow(unused)]
fn main() {
/// A trait for borrowing.
trait Borrow<Sized? B> {
    /// Immutably borrow from an owned value.
    fn borrow(&self) -> &B;

    /// Mutably borrow from an owned value.
    fn borrow_mut(&mut self) -> &mut B;
}

// The Sized bound means that this impl does not overlap with the impls below.
impl<T: Sized> Borrow<T> for T {
    fn borrow(a: &T) -> &T {
        a
    }
    fn borrow_mut(a: &mut T) -> &mut T {
        a
    }
}

impl Borrow<str> for String {
    fn borrow(s: &String) -> &str {
        s.as_slice()
    }
    fn borrow_mut(s: &mut String) -> &mut str {
        s.as_mut_slice()
    }
}

impl<T> Borrow<[T]> for Vec<T> {
    fn borrow(s: &Vec<T>) -> &[T] {
        s.as_slice()
    }
    fn borrow_mut(s: &mut Vec<T>) -> &mut [T] {
        s.as_mut_slice()
    }
}
}

(Note: thanks to @epdtry for suggesting this variation! The original proposal is listed

A primary

Because of the blanket impl, the Borrow trait can largely be ignored

Using Borrow to replace _equiv methods

With the Borrow trait in place, we can eliminate the _equiv method variants by asking map keys to be Borrow:

#![allow(unused)]
fn main() {
impl<K,V> HashMap<K,V> where K: Hash + Eq {
    fn find<Q>(&self, k: &Q) -> &V where K: Borrow<Q>, Q: Hash + Eq { ... }
    fn contains_key<Q>(&self, k: &Q) -> bool where K: Borrow<Q>, Q: Hash + Eq { ... }
    fn insert(&mut self, k: K, v: V) -> Option<V> { ... }

    ...
}
}

The benefits of this approach over _equiv are:

• The Borrow trait captures the borrowing relationship between an owned data structure and both references

  参照
  to it and slices from it -- once and for all. This means that it can be used anywhere
  どこでも
  we need to program generically over "borrowed" data. In particular, the single
  単一の
  trait works for both HashMap and TreeMap, and should work for other kinds of data structures as well. It also helps generalize MaybeOwned, for similar
  似ている、同様の
  reasons (see below.)

  A very important consequence

  結果
  is that the map methods using Borrow can potentially be put into a common Map trait that's implemented
  実装する
  by HashMap, TreeMap, and others. While we do not propose to do so now, we definitely want to do so later on.

• When using a HashMap<String, T>, all of the basic methods like find, contains_key and insert "just work", without forcing you to think about &String vs &str.

• We don't need separate _equiv variants of methods. (However, this could probably be addressed with multidispatch by providing

  与える
  a blanket Equiv implementation.)

On the other hand, this approach retains some of the downsides of _equiv:

• The signature

  シグネチャ
  for methods like find and contains_key is more complex
  複素数、複文の
  than their current signatures.
  シグネチャ
  There are two counterpoints. First, over time the Borrow trait is likely to become a well-known concept, so the signature
  シグネチャ
  will not appear
  現れる
  completely alien. Second, what is perhaps more important than the signature
  シグネチャ
  is that, when using find on HashMap<String, T>, various
  さまざまな
  method arguments
  引数
  just work as expected.

• The API does not guarantee

  保証する
  "coherence": the Hash and Eq (or Ord, for TreeMap) implementations
  実装
  for the owned and borrowed keys might differ, breaking key invariants of the data structure. This is already the case with _equiv.

The Alternatives

Clone-on-write (Cow) pointers

A side-benefit of the Borrow trait is that we can give a more general

#![allow(unused)]
fn main() {
/// A generalization of Clone.
trait FromBorrow<Sized? B>: Borrow<B> {
    fn from_borrow(b: &B) -> Self;
}

/// A clone-on-write smart pointer
pub enum Cow<'a, T, B> where T: FromBorrow<B> {
    Shared(&'a B),
    Owned(T)
}

impl<'a, T, B> Cow<'a, T, B> where T: FromBorrow<B> {
    pub fn new(shared: &'a B) -> Cow<'a, T, B> {
        Shared(shared)
    }

    pub fn new_owned(owned: T) -> Cow<'static, T, B> {
        Owned(owned)
    }

    pub fn is_owned(&self) -> bool {
        match *self {
            Owned(_) => true,
            Shared(_) => false
        }
    }

    pub fn to_owned_mut(&mut self) -> &mut T {
        match *self {
            Shared(shared) => {
                *self = Owned(FromBorrow::from_borrow(shared));
                self.to_owned_mut()
            }
            Owned(ref mut owned) => owned
        }
    }

    pub fn into_owned(self) -> T {
        match self {
            Shared(shared) => FromBorrow::from_borrow(shared),
            Owned(owned) => owned
        }
    }
}

impl<'a, T, B> Deref<B> for Cow<'a, T, B> where T: FromBorrow<B>  {
    fn deref(&self) -> &B {
        match *self {
            Shared(shared) => shared,
            Owned(ref owned) => owned.borrow()
        }
    }
}

impl<'a, T, B> DerefMut<B> for Cow<'a, T, B> where T: FromBorrow<B> {
    fn deref_mut(&mut self) -> &mut B {
        self.to_owned_mut().borrow_mut()
    }
}
}

The type Cow<'a, String, str> is roughly equivalent

By implementing Deref and DerefMut, the Cow type acts

One slight gotcha with the design

Thus,

Note that, by not using into_owned, the Cow pointer itself may be owned by some other data structure (perhaps as part of a collection) and will internally track whether an owned copy is available.

Altogether, this RFC proposes to introduce

IntoIterator (and Iterable)

As discussed in earlier, some form

In particular, the following two traits work fine (with associated

#![allow(unused)]
fn main() {
trait Iterator {
    type A;
    fn next(&mut self) -> Option<A>;
    ...
}

trait IntoIterator {
    type A;
    type I: Iterator<A = A>;

    fn into_iter(self) -> I;
}
}

Because IntoIterator consumes self, lifetimes are not an issue.

It's tempting to also define

#![allow(unused)]
fn main() {
trait Iterable<'a> {
    type A;
    type I: Iterator<&'a A>;

    fn iter(&'a self) -> I;
}
}

(along the lines of those proposed by an earlier RFC).

The problem with Iterable as defined

#![allow(unused)]
fn main() {
fn iter_through_rc<I>(c: Rc<I>) where I: Iterable<?> {
    // the lifetime of the borrow is established here,
    // so cannot even be named in the function signature
    for x in c.iter() {
        // ...
    }
}
}

To make this kind of example work, you'd need to be able to say something like:

#![allow(unused)]
fn main() {
where <'a> I: Iterable<'a>
}

that is, that I implements

Fortunately, we can have our cake and eat it too. This RFC proposes the IntoIterator trait above, together with the following blanket impl:

#![allow(unused)]
fn main() {
impl<I: Iterator> IntoIterator for I {
    type A = I::A;
    type I = I;
    fn into_iter(self) -> I {
        self
    }
}
}

which means that taking

For individual

#![allow(unused)]
fn main() {
impl<T> IntoIterator for Vec<T> {
    type A = T;
    type I = MoveItems<T>;
    fn into_iter(self) -> MoveItems<T> { ... }
}

impl<'a, T> IntoIterator for &'a Vec<T> {
    type A = &'a T;
    type I = Items<'a, T>;
    fn into_iter(self) -> Items<'a, T> { ... }
}

impl<'a, T> IntoIterator for &'a mut Vec<T> {
    type A = &'a mut T;
    type I = ItemsMut<'a, T>;
    fn into_iter(self) -> ItemsMut<'a, T> { ... }
}
}

If/when HKT is added

#![allow(unused)]
fn main() {
// the HKT version
trait Iterable {
    type A;
    type I<'a>: Iterator<&'a A>;
    fn iter<'a>(&'a self) -> I<'a>;
}

impl<'a, C: Iterable> IntoIterator for &'a C {
    type A = &'a C::A;
    type I = C::I<'a>;
    fn into_iter(self) -> I {
        self.iter()
    }
}
}

This gives a clean migration path: once Vec implements

Likewise, if we add a feature like the "universal" where clause

Benefits of IntoIterator

What do we gain by incorporating IntoIterator today?

This RFC proposes that for loops should use IntoIterator rather than Iterator. With the blanket impl of IntoIterator for any Iterator, this is not a breaking change. However, given

#![allow(unused)]
fn main() {
let v: Vec<Foo> = ...

for x in &v { ... }     // iterate over &Foo
for x in &mut v { ... } // iterate over &mut Foo
for x in v { ... }      // iterate over Foo
}

Similarly,

In general,

Additional

追加の

methods

Another typical desire for an Iterable trait is to offer defaulted versions of methods that basically re-export iterator methods on containers (see the earlier RFC). Usually these methods would go through a reference

It is possible to add such methods using the design

This RFC only proposes to add the following method via IntoIterator, as a convenience for a common pattern:

#![allow(unused)]
fn main() {
trait IterCloned {
    type A;
    type I: Iterator<A>;
    fn iter_cloned(self) -> I;
}

impl<'a, T, I: IntoIterator> IterCloned for I where I::A = &'a T {
    type A = T;
    type I = ClonedItems<I>;
    fn into_iter(self) -> I { ... }
}
}

(The iter_cloned method will help reduce the number of method variants in general

We will leave to later RFCs the incorporation of additional

Minimizing variants: ByNeed and Predicate traits

There are several kinds of methods that, in their most general

• Taking

  とる
  values by need. For example, consider
  考える、みなす
  the unwrap_or and unwrap_or_else methods in Option:

  
  #![allow(unused)]
  fn main() {
  fn unwrap_or(self, def: T) -> T
  fn unwrap_or_else(self, f: || -> T) -> T
  }
  

  The unwrap_or_else method is the most general:

  一般
  it invokes
  呼び出す
  the closure to compute a default value only when self is None. When the default value is expensive to compute, this by-need approach helps. But often the default value is cheap, and closures are somewhat annoying to write, so unwrap_or provides
  与える
  a convenience wrapper.

• Taking

  とる
  predicates. For example, a method like contains
  含む
  often shows up (inconsistently!) in two variants:

  
  #![allow(unused)]
  fn main() {
  fn contains(&self, elem: &T) -> bool; // where T: PartialEq
  fn contains_fn(&self, pred: |&T| -> bool) -> bool;
  }
  

  Again, the contains_fn version is the more general,

  一般
  but it's convenient to provide a specialized variant when the element
  要素
  type can be compared
  比較する
  for equality,
  同一性、等式
  to avoid
  避ける、回避する
  writing explicit
  明示的な
  closures.

As it turns out, with multidispatch) it is possible to use a trait to express these variants through overloading:

#![allow(unused)]
fn main() {
trait ByNeed<T> {
    fn compute(self) -> T;
}

impl<T> ByNeed<T> for T {
    fn compute(self) -> T {
        self
    }
}

// Due to multidispatch, this impl does NOT overlap with the above one
impl<T> ByNeed<T> for || -> T {
    fn compute(self) -> T {
        self()
    }
}

impl<T> Option<T> {
    fn unwrap_or<U>(self, def: U) where U: ByNeed<T> { ... }
    ...
}
}

#![allow(unused)]
fn main() {
trait Predicate<T> {
    fn check(&self, &T) -> bool;
}

impl<T: Eq> Predicate<T> for &T {
    fn check(&self, t: &T) -> bool {
        *self == t
    }
}

impl<T> Predicate<T> for |&T| -> bool {
    fn check(&self, t: &T) -> bool {
        (*self)(t)
    }
}

impl<T> Vec<T> {
    fn contains<P>(&self, pred: P) where P: Predicate<T> { ... }
    ...
}
}

Since these two patterns are particularly common throughout std, this RFC proposes adding

In particular, some methods on string slices currently work with CharEq, which is similar

#![allow(unused)]
fn main() {
pub trait CharEq {
    fn matches(&mut self, char) -> bool;
    fn only_ascii(&self) -> bool;
}
}

The difference is the only_ascii method, which is used to optimize

To keep these optimizations intact while connecting to Predicate, this RFC proposes the following restructuring of CharEq:

#![allow(unused)]
fn main() {
pub trait CharPredicate: Predicate<char> {
    fn only_ascii(&self) -> bool {
        false
    }
}
}

Why not leverage unboxed closures?

A natural question is: why not use the traits for unboxed closures to achieve a similar

The problem is that these blanket impls will often conflict. In particular, any type T could implement

In addition,

The APIs

Now we'll delve into the detailed APIs for the various

• We will assume

  仮定する
  a type parameter
  仮引数
  T for Vec, BinaryHeap, DList and RingBuf; we will also use this parameter
  仮引数
  for APIs on String, where it should be understood as char.

• We will assume

  仮定する
  type parameters
  仮引数
  K: Borrow and V for HashMap and TreeMap; for TrieMap and SmallIntMap the K is assumed to be uint

• We will assume

  仮定する
  a type parameter
  仮引数
  K: Borrow for HashSet and TreeSet; for BitvSet it is assumed to be uint.

We will begin by outlining the most widespread APIs in tables, making it easy to compare names and signatures

Construction

構築

All of the collections should support a static

#![allow(unused)]
fn main() {
fn new() -> Self
}

that creates an empty

Several collections also support separate constructors

The FromIterator trait

All of the collections should implement

#![allow(unused)]
fn main() {
pub trait FromIterator {
    type A:
    fn from_iter<T>(T) -> Self where T: IntoIterator<A = A>;
}
}

Note that this varies from today's FromIterator by consuming an IntoIterator rather than Iterator. As explained above, this choice is strictly more general

This constructor

Insertion

挿入

The table below gives methods for inserting

There are a few changes here from the current state of affairs:

• The DList and RingBuf data structures no longer provide push, but rather push_front and push_back. This change is based

  基となる、基底(の)
  on (1) viewing them as deques and (2) not giving priority to the "front" or the "back".

• The insert method on maps returns the value previously associated

  関連付けられた
  with the key, if any. Previously, this functionality was provided
  与える
  by a swap method, which has been dropped (consolidating needless method variants.)

Aside from these changes, a number of insertion

The Extend trait (was: Extendable)

In addition

The Extend trait allows

#![allow(unused)]
fn main() {
pub trait Extend: FromIterator {
    fn extend<T>(&mut self, T) where T: IntoIterator<A = Self::A>;
}
}

As with FromIterator, this trait has been modified to take

Deletion

The table below gives methods for removing items into various

As with the insertion

• The DList and RingBuf data structures no longer provide pop, but rather pop_front and pop_back -- similarly

  同様に
  to the push methods.

• The remove method on maps returns the value previously associated

  関連付けられた
  with the key, if any. Previously, this functionality was provided
  与える
  by a separate pop method, which has been dropped (consolidating needless method variants.)

• The retain method takes

  とる
  a Predicate.

• The truncate, retain and dedup methods are offered more widely.

Again, some of the more specialized methods are not discussed here; see "specialized operations"

Inspection/mutation

The next table gives methods for inspection and mutation of existing items in collections:

The biggest changes from the current APIs are:

• The find and find_mut methods have been renamed to get and get_mut. Further,

  さらなる、それ以上
  all get methods return Option values and do not invoke fail!. This is part of a general
  一般
  convention described
  記述する
  in the next section
  節
  (on the Index traits).

• The contains

  含む
  method is offered more widely.

• There is no longer an equivalent

  等価
  of find_copy (which should be called
  呼び出し
  find_clone). Instead, we propose to add the following method to the Option<&'a T> type where T: Clone:

  
  #![allow(unused)]
  fn main() {
  fn cloned(self) -> Option<T> {
      self.map(|x| x.clone())
  }
  }
  

  so that some_map.find_copy(key) will instead be written some_map.find(key).cloned(). This method chain is slightly longer, but is more clear and allows

  許可する、可能にする
  us to drop the _copy variants. Moreover,
  その上
  all users of Option benefit from the new convenience method.

The Index trait

The Index and IndexMut traits provide indexing notation

#![allow(unused)]
fn main() {
pub trait Index {
    type Index;
    type Result;
    fn index(&'a self, index: &Index) -> &'a Result;
}

pub trait IndexMut {
    type Index;
    type Result;
    fn index_mut(&'a mut self, index: &Index) -> &'a mut Result;
}
}

These traits will be implemented

As a general