1 % The Rust Containers and Iterators Guide
5 The container traits are defined in the `std::container` module.
9 Vectors have `O(1)` indexing, push (to the end) and pop (from the end). Vectors
10 are the most common container in Rust, and are flexible enough to fit many use
13 Vectors can also be sorted and used as efficient lookup tables with the
14 `bsearch()` method, if all the elements are inserted at one time and
15 deletions are unnecessary.
19 Maps are collections of unique keys with corresponding values, and sets are
20 just unique keys without a corresponding value. The `Map` and `Set` traits in
21 `std::container` define the basic interface.
23 The standard library provides three owned map/set types:
25 * `collections::HashMap` and `collections::HashSet`, requiring the keys to
26 implement `Eq` and `Hash`
27 * `collections::TrieMap` and `collections::TrieSet`, requiring the keys to be `uint`
28 * `collections::TreeMap` and `collections::TreeSet`, requiring the keys
29 to implement `TotalOrd`
31 These maps do not use managed pointers so they can be sent between tasks as
32 long as the key and value types are sendable. Neither the key or value type has
35 The `TrieMap` and `TreeMap` maps are ordered, while `HashMap` uses an arbitrary
38 Each `HashMap` instance has a random 128-bit key to use with a keyed hash,
39 making the order of a set of keys in a given hash table randomized. Rust
40 provides a [SipHash](https://131002.net/siphash/) implementation for any type
41 implementing the `Hash` trait.
43 ## Double-ended queues
45 The `collections::ringbuf` module implements a double-ended queue with `O(1)`
46 amortized inserts and removals from both ends of the container. It also has
47 `O(1)` indexing like a vector. The contained elements are not required to be
48 copyable, and the queue will be sendable if the contained type is sendable.
49 Its interface `Deque` is defined in `collections`.
51 The `extra::dlist` module implements a double-ended linked list, also
52 implementing the `Deque` trait, with `O(1)` removals and inserts at either end,
53 and `O(1)` concatenation.
57 The `collections::priority_queue` module implements a queue ordered by a key. The
58 contained elements are not required to be copyable, and the queue will be
59 sendable if the contained type is sendable.
61 Insertions have `O(log n)` time complexity and checking or popping the largest
62 element is `O(1)`. Converting a vector to a priority queue can be done
63 in-place, and has `O(n)` complexity. A priority queue can also be converted to
64 a sorted vector in-place, allowing it to be used for an `O(n log n)` in-place
71 The iteration protocol is defined by the `Iterator` trait in the
72 `std::iter` module. The minimal implementation of the trait is a `next`
73 method, yielding the next element from an iterator object:
76 /// An infinite stream of zeroes
79 impl Iterator<int> for ZeroStream {
80 fn next(&mut self) -> Option<int> {
86 Reaching the end of the iterator is signalled by returning `None` instead of
91 /// A stream of N zeroes
97 fn new(n: uint) -> ZeroStream {
98 ZeroStream { remaining: n }
102 impl Iterator<int> for ZeroStream {
103 fn next(&mut self) -> Option<int> {
104 if self.remaining == 0 {
114 In general, you cannot rely on the behavior of the `next()` method after it has
115 returned `None`. Some iterators may return `None` forever. Others may behave
118 ## Container iterators
120 Containers implement iteration over the contained elements by returning an
121 iterator object. For example, vector slices several iterators available:
123 * `iter()` for immutable references to the elements
124 * `mut_iter()` for mutable references to the elements
125 * `move_iter()` to move the elements out by-value
127 A typical mutable container will implement at least `iter()`, `mut_iter()` and
128 `move_iter()`. If it maintains an order, the returned iterators will be
129 `DoubleEndedIterator`s, which are described below.
133 Unlike most other languages with external iterators, Rust has no *iterator
134 invalidation*. As long as an iterator is still in scope, the compiler will prevent
135 modification of the container through another handle.
138 let mut xs = [1, 2, 3];
142 // the vector is frozen for this scope, the compiler will statically
143 // prevent modification
145 // the vector becomes unfrozen again at the end of the scope
148 These semantics are due to most container iterators being implemented with `&`
153 The `Iterator` trait provides many common algorithms as default methods. For
154 example, the `fold` method will accumulate the items yielded by an `Iterator`
158 let xs = [1, 9, 2, 3, 14, 12];
159 let result = xs.iter().fold(0, |accumulator, item| accumulator - *item);
160 assert_eq!(result, -41);
163 Most adaptors return an adaptor object implementing the `Iterator` trait itself:
166 let xs = [1, 9, 2, 3, 14, 12];
167 let ys = [5, 2, 1, 8];
168 let sum = xs.iter().chain(ys.iter()).fold(0, |a, b| a + *b);
172 Some iterator adaptors may return `None` before exhausting the underlying
173 iterator. Additionally, if these iterator adaptors are called again after
174 returning `None`, they may call their underlying iterator again even if the
175 adaptor will continue to return `None` forever. This may not be desired if the
176 underlying iterator has side-effects.
178 In order to provide a guarantee about behavior once `None` has been returned, an
179 iterator adaptor named `fuse()` is provided. This returns an iterator that will
180 never call its underlying iterator again once `None` has been returned:
183 let xs = [1,2,3,4,5];
187 let it = xs.iter().scan((), |_, x| {
189 if *x < 3 { Some(x) } else { None }});
191 // the iterator will only yield 1 and 2 before returning None
192 // If we were to call it 5 times, calls would end up as 5, despite
193 // only 2 values being yielded (and therefore 3 unique calls being
194 // made). The fuse() adaptor can fix this.
196 let mut it = it.fuse();
204 assert_eq!(calls, 3);
209 The function `range` (or `range_inclusive`) allows to simply iterate through a given range:
212 for i in range(0, 5) {
213 print!("{} ", i) // prints "0 1 2 3 4"
216 for i in std::iter::range_inclusive(0, 5) { // needs explicit import
217 print!("{} ", i) // prints "0 1 2 3 4 5"
221 The `for` keyword can be used as sugar for iterating through any iterator:
224 let xs = [2u, 3, 5, 7, 11, 13, 17];
226 // print out all the elements in the vector
231 // print out all but the first 3 elements in the vector
232 for x in xs.iter().skip(3) {
237 For loops are *often* used with a temporary iterator object, as above. They can
238 also advance the state of an iterator in a mutable location:
241 let xs = [1, 2, 3, 4, 5];
242 let ys = ["foo", "bar", "baz", "foobar"];
244 // create an iterator yielding tuples of elements from both vectors
245 let mut it = xs.iter().zip(ys.iter());
247 // print out the pairs of elements up to (&3, &"baz")
249 println!("{} {}", *x, *y);
256 // yield and print the last pair from the iterator
257 println!("last: {:?}", it.next());
259 // the iterator is now fully consumed
260 assert!(it.next().is_none());
265 Iterators offer generic conversion to containers with the `collect` adaptor:
268 let xs = [0, 1, 1, 2, 3, 5, 8];
269 let ys = xs.iter().rev().skip(1).map(|&x| x * 2).collect::<~[int]>();
270 assert_eq!(ys, ~[10, 6, 4, 2, 2, 0]);
273 The method requires a type hint for the container type, if the surrounding code
274 does not provide sufficient information.
276 Containers can provide conversion from iterators through `collect` by
277 implementing the `FromIterator` trait. For example, the implementation for
278 vectors is as follows:
281 impl<A> FromIterator<A> for ~[A] {
282 pub fn from_iter<T: Iterator<A>>(iterator: &mut T) -> ~[A] {
283 let (lower, _) = iterator.size_hint();
284 let mut xs = with_capacity(lower);
295 The `Iterator` trait provides a `size_hint` default method, returning a lower
296 bound and optionally on upper bound on the length of the iterator:
299 fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
302 The vector implementation of `FromIterator` from above uses the lower bound
303 to pre-allocate enough space to hold the minimum number of elements the
306 The default implementation is always correct, but it should be overridden if
307 the iterator can provide better information.
309 The `ZeroStream` from earlier can provide an exact lower and upper bound:
313 /// A stream of N zeroes
319 fn new(n: uint) -> ZeroStream {
320 ZeroStream { remaining: n }
323 fn size_hint(&self) -> (uint, Option<uint>) {
324 (self.remaining, Some(self.remaining))
328 impl Iterator<int> for ZeroStream {
329 fn next(&mut self) -> Option<int> {
330 if self.remaining == 0 {
340 ## Double-ended iterators
342 The `DoubleEndedIterator` trait represents an iterator able to yield elements
343 from either end of a range. It inherits from the `Iterator` trait and extends
344 it with the `next_back` function.
346 A `DoubleEndedIterator` can have its direction changed with the `rev` adaptor,
347 returning another `DoubleEndedIterator` with `next` and `next_back` exchanged.
350 let xs = [1, 2, 3, 4, 5, 6];
351 let mut it = xs.iter();
352 println!("{:?}", it.next()); // prints `Some(&1)`
353 println!("{:?}", it.next()); // prints `Some(&2)`
354 println!("{:?}", it.next_back()); // prints `Some(&6)`
356 // prints `5`, `4` and `3`
362 The `chain`, `map`, `filter`, `filter_map` and `inspect` adaptors are
363 `DoubleEndedIterator` implementations if the underlying iterators are.
366 let xs = [1, 2, 3, 4];
367 let ys = [5, 6, 7, 8];
368 let mut it = xs.iter().chain(ys.iter()).map(|&x| x * 2);
370 println!("{:?}", it.next()); // prints `Some(2)`
372 // prints `16`, `14`, `12`, `10`, `8`, `6`, `4`
378 The `reverse_` method is also available for any double-ended iterator yielding
379 mutable references. It can be used to reverse a container in-place. Note that
380 the trailing underscore is a workaround for issue #5898 and will be removed.
383 let mut ys = [1, 2, 3, 4, 5];
384 ys.mut_iter().reverse_();
385 assert!(ys == [5, 4, 3, 2, 1]);
388 ## Random-access iterators
390 The `RandomAccessIterator` trait represents an iterator offering random access
391 to the whole range. The `indexable` method retrieves the number of elements
392 accessible with the `idx` method.
394 The `chain` adaptor is an implementation of `RandomAccessIterator` if the
395 underlying iterators are.
398 let xs = [1, 2, 3, 4, 5];
399 let ys = ~[7, 9, 11];
400 let mut it = xs.iter().chain(ys.iter());
401 println!("{:?}", it.idx(0)); // prints `Some(&1)`
402 println!("{:?}", it.idx(5)); // prints `Some(&7)`
403 println!("{:?}", it.idx(7)); // prints `Some(&11)`
404 println!("{:?}", it.idx(8)); // prints `None`
406 // yield two elements from the beginning, and one from the end
411 println!("{:?}", it.idx(0)); // prints `Some(&3)`
412 println!("{:?}", it.idx(4)); // prints `Some(&9)`
413 println!("{:?}", it.idx(6)); // prints `None`