doc/tutorial-container.md

   1 % Containers and iterators
   2
   3 # Containers
   4
   5 The container traits are defined in the `std::container` module.
   6
   7 ## Unique and managed vectors
   8
   9 Vectors have `O(1)` indexing and removal from the end, along with `O(1)`
  10 amortized insertion. Vectors are the most common container in Rust, and are
  11 flexible enough to fit many use cases.
  12
  13 Vectors can also be sorted and used as efficient lookup tables with the
  14 `std::vec::bsearch` function, if all the elements are inserted at one time and
  15 deletions are unnecessary.
  16
  17 ## Maps and sets
  18
  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.
  22
  23 The standard library provides three owned map/set types:
  24
  25 * `std::hashmap::HashMap` and `std::hashmap::HashSet`, requiring the keys to
  26   implement `Eq` and `Hash`
  27 * `std::trie::TrieMap` and `std::trie::TrieSet`, requiring the keys to be `uint`
  28 * `extra::treemap::TreeMap` and `extra::treemap::TreeSet`, requiring the keys
  29   to implement `TotalOrd`
  30
  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
  33 to be copyable.
  34
  35 The `TrieMap` and `TreeMap` maps are ordered, while `HashMap` uses an arbitrary
  36 order.
  37
  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 `IterBytes` trait.
  42
  43 ## Double-ended queues
  44
  45 The `extra::deque` module implements a double-ended queue with `O(1)` amortized
  46 inserts and removals from both ends of the container. It also has `O(1)`
  47 indexing like a vector. The contained elements are not required to be copyable,
  48 and the queue will be sendable if the contained type is sendable.
  49
  50 ## Priority queues
  51
  52 The `extra::priority_queue` module implements a queue ordered by a key.  The
  53 contained elements are not required to be copyable, and the queue will be
  54 sendable if the contained type is sendable.
  55
  56 Insertions have `O(log n)` time complexity and checking or popping the largest
  57 element is `O(1)`. Converting a vector to a priority queue can be done
  58 in-place, and has `O(n)` complexity. A priority queue can also be converted to
  59 a sorted vector in-place, allowing it to be used for an `O(n log n)` in-place
  60 heapsort.
  61
  62 # Iterators
  63
  64 ## Iteration protocol
  65
  66 The iteration protocol is defined by the `Iterator` trait in the
  67 `std::iterator` module. The minimal implementation of the trait is a `next`
  68 method, yielding the next element from an iterator object:
  69
  70 ~~~
  71 /// An infinite stream of zeroes
  72 struct ZeroStream;
  73
  74 impl Iterator<int> for ZeroStream {
  75     fn next(&mut self) -> Option<int> {
  76         Some(0)
  77     }
  78 }
  79 ~~~~
  80
  81 Reaching the end of the iterator is signalled by returning `None` instead of
  82 `Some(item)`:
  83
  84 ~~~
  85 /// A stream of N zeroes
  86 struct ZeroStream {
  87     priv remaining: uint
  88 }
  89
  90 impl ZeroStream {
  91     fn new(n: uint) -> ZeroStream {
  92         ZeroStream { remaining: n }
  93     }
  94 }
  95
  96 impl Iterator<int> for ZeroStream {
  97     fn next(&mut self) -> Option<int> {
  98         if self.remaining == 0 {
  99             None
 100         } else {
 101             self.remaining -= 1;
 102             Some(0)
 103         }
 104     }
 105 }
 106 ~~~
 107
 108 ## Container iterators
 109
 110 Containers implement iteration over the contained elements by returning an
 111 iterator object. For example, vector slices have four iterators available:
 112
 113 * `vector.iter()`, for immutable references to the elements
 114 * `vector.mut_iter()`, for mutable references to the elements
 115 * `vector.rev_iter()`, for immutable references to the elements in reverse order
 116 * `vector.mut_rev_iter()`, for mutable references to the elements in reverse order
 117
 118 ### Freezing
 119
 120 Unlike most other languages with external iterators, Rust has no *iterator
 121 invalidation*. As long an iterator is still in scope, the compiler will prevent
 122 modification of the container through another handle.
 123
 124 ~~~
 125 let mut xs = [1, 2, 3];
 126 {
 127     let _it = xs.iter();
 128
 129     // the vector is frozen for this scope, the compiler will statically
 130     // prevent modification
 131 }
 132 // the vector becomes unfrozen again at the end of the scope
 133 ~~~
 134
 135 These semantics are due to most container iterators being implemented with `&`
 136 and `&mut`.
 137
 138 ## Iterator adaptors
 139
 140 The `IteratorUtil` trait implements common algorithms as methods extending
 141 every `Iterator` implementation. For example, the `fold` method will accumulate
 142 the items yielded by an `Iterator` into a single value:
 143
 144 ~~~
 145 let xs = [1, 9, 2, 3, 14, 12];
 146 let result = xs.iter().fold(0, |accumulator, item| accumulator - *item);
 147 assert_eq!(result, -41);
 148 ~~~
 149
 150 Some adaptors return an adaptor object implementing the `Iterator` trait itself:
 151
 152 ~~~
 153 let xs = [1, 9, 2, 3, 14, 12];
 154 let ys = [5, 2, 1, 8];
 155 let sum = xs.iter().chain_(ys.iter()).fold(0, |a, b| a + *b);
 156 assert_eq!(sum, 57);
 157 ~~~
 158
 159 Note that some adaptors like the `chain_` method above use a trailing
 160 underscore to work around an issue with method resolve. The underscores will be
 161 dropped when they become unnecessary.
 162
 163 ## For loops
 164
 165 The `for` loop syntax is currently in transition, and will switch from the old
 166 closure-based iteration protocol to iterator objects. For now, the `advance`
 167 adaptor is required as a compatibility shim to use iterators with for loops.
 168
 169 ~~~
 170 let xs = [2, 3, 5, 7, 11, 13, 17];
 171
 172 // print out all the elements in the vector
 173 for xs.iter().advance |x| {
 174     println(x.to_str())
 175 }
 176
 177 // print out all but the first 3 elements in the vector
 178 for xs.iter().skip(3).advance |x| {
 179     println(x.to_str())
 180 }
 181 ~~~
 182
 183 For loops are *often* used with a temporary iterator object, as above. They can
 184 also advance the state of an iterator in a mutable location:
 185
 186 ~~~
 187 let xs = [1, 2, 3, 4, 5];
 188 let ys = ["foo", "bar", "baz", "foobar"];
 189
 190 // create an iterator yielding tuples of elements from both vectors
 191 let mut it = xs.iter().zip(ys.iter());
 192
 193 // print out the pairs of elements up to (&3, &"baz")
 194 for it.advance |(x, y)| {
 195     println(fmt!("%d %s", *x, *y));
 196
 197     if *x == 3 {
 198         break;
 199     }
 200 }
 201
 202 // yield and print the last pair from the iterator
 203 println(fmt!("last: %?", it.next()));
 204
 205 // the iterator is now fully consumed
 206 assert!(it.next().is_none());
 207 ~~~
 208
 209 ## Conversion
 210
 211 Iterators offer generic conversion to containers with the `collect` adaptor:
 212
 213 ~~~
 214 let xs = [0, 1, 1, 2, 3, 5, 8];
 215 let ys = xs.rev_iter().skip(1).transform(|&x| x * 2).collect::<~[int]>();
 216 assert_eq!(ys, ~[10, 6, 4, 2, 2, 0]);
 217 ~~~
 218
 219 The method requires a type hint for the container type, if the surrounding code
 220 does not provide sufficient information.
 221
 222 Containers can provide conversion from iterators through `collect` by
 223 implementing the `FromIterator` trait. For example, the implementation for
 224 vectors is as follows:
 225
 226 ~~~
 227 impl<A, T: Iterator<A>> FromIterator<A, T> for ~[A] {
 228     pub fn from_iterator(iterator: &mut T) -> ~[A] {
 229         let (lower, _) = iterator.size_hint();
 230         let mut xs = with_capacity(lower);
 231         for iterator.advance |x| {
 232             xs.push(x);
 233         }
 234         xs
 235     }
 236 }
 237 ~~~
 238
 239 ### Size hints
 240
 241 The `Iterator` trait provides a `size_hint` default method, returning a lower
 242 bound and optionally on upper bound on the length of the iterator:
 243
 244 ~~~
 245 fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
 246 ~~~
 247
 248 The vector implementation of `FromIterator` from above uses the lower bound
 249 to pre-allocate enough space to hold the minimum number of elements the
 250 iterator will yield.
 251
 252 The default implementation is always correct, but it should be overridden if
 253 the iterator can provide better information.
 254
 255 The `ZeroStream` from earlier can provide an exact lower and upper bound:
 256
 257 ~~~
 258 /// A stream of N zeroes
 259 struct ZeroStream {
 260     priv remaining: uint
 261 }
 262
 263 impl ZeroStream {
 264     fn new(n: uint) -> ZeroStream {
 265         ZeroStream { remaining: n }
 266     }
 267
 268     fn size_hint(&self) -> (uint, Option<uint>) {
 269         (self.remaining, Some(self.remaining))
 270     }
 271 }
 272
 273 impl Iterator<int> for ZeroStream {
 274     fn next(&mut self) -> Option<int> {
 275         if self.remaining == 0 {
 276             None
 277         } else {
 278             self.remaining -= 1;
 279             Some(0)
 280         }
 281     }
 282 }
 283 ~~~
 284
 285 ## Double-ended iterators
 286
 287 The `DoubleEndedIterator` trait represents an iterator able to yield elements
 288 from either end of a range. It inherits from the `Iterator` trait and extends
 289 it with the `next_back` function.
 290
 291 A `DoubleEndedIterator` can be flipped with the `invert` adaptor, returning
 292 another `DoubleEndedIterator` with `next` and `next_back` exchanged.
 293
 294 ~~~
 295 let xs = [1, 2, 3, 4, 5, 6];
 296 let mut it = xs.iter();
 297 println(fmt!("%?", it.next())); // prints `Some(&1)`
 298 println(fmt!("%?", it.next())); // prints `Some(&2)`
 299 println(fmt!("%?", it.next_back())); // prints `Some(&6)`
 300
 301 // prints `5`, `4` and `3`
 302 for it.invert().advance |&x| {
 303     println(fmt!("%?", x))
 304 }
 305 ~~~
 306
 307 The `rev_iter` and `mut_rev_iter` methods on vectors just return an inverted
 308 version of the standard immutable and mutable vector iterators.