1 # SOME DESCRIPTIVE TITLE
2 # Copyright (C) YEAR The Rust Project Developers
3 # This file is distributed under the same license as the Rust package.
4 # FIRST AUTHOR <EMAIL@ADDRESS>, YEAR.
9 "Project-Id-Version: Rust 0.8-pre\n"
10 "POT-Creation-Date: 2013-08-05 19:40+0900\n"
11 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
12 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
13 "Language-Team: LANGUAGE <LL@li.org>\n"
16 "Content-Type: text/plain; charset=UTF-8\n"
17 "Content-Transfer-Encoding: 8bit\n"
20 #: doc/tutorial-container.md:2
21 msgid "% Containers and iterators"
25 #: doc/tutorial-container.md:4
30 #: doc/tutorial-container.md:6
31 msgid "The container traits are defined in the `std::container` module."
35 #: doc/tutorial-container.md:8
36 msgid "## Unique and managed vectors"
40 #: doc/tutorial-container.md:12
42 "Vectors have `O(1)` indexing and removal from the end, along with `O(1)` "
43 "amortized insertion. Vectors are the most common container in Rust, and are "
44 "flexible enough to fit many use cases."
48 #: doc/tutorial-container.md:16
50 "Vectors can also be sorted and used as efficient lookup tables with the "
51 "`std::vec::bsearch` function, if all the elements are inserted at one time "
52 "and deletions are unnecessary."
56 #: doc/tutorial-container.md:18
57 msgid "## Maps and sets"
61 #: doc/tutorial-container.md:22
63 "Maps are collections of unique keys with corresponding values, and sets are "
64 "just unique keys without a corresponding value. The `Map` and `Set` traits "
65 "in `std::container` define the basic interface."
69 #: doc/tutorial-container.md:24
70 msgid "The standard library provides three owned map/set types:"
74 #: doc/tutorial-container.md:30
76 "`std::hashmap::HashMap` and `std::hashmap::HashSet`, requiring the keys to "
77 "implement `Eq` and `Hash`"
81 #: doc/tutorial-container.md:30
83 "`std::trie::TrieMap` and `std::trie::TrieSet`, requiring the keys to be "
88 #: doc/tutorial-container.md:30
90 "`extra::treemap::TreeMap` and `extra::treemap::TreeSet`, requiring the keys "
91 "to implement `TotalOrd`"
95 #: doc/tutorial-container.md:34
97 "These maps do not use managed pointers so they can be sent between tasks as "
98 "long as the key and value types are sendable. Neither the key or value type "
103 #: doc/tutorial-container.md:37
105 "The `TrieMap` and `TreeMap` maps are ordered, while `HashMap` uses an "
110 #: doc/tutorial-container.md:42
112 "Each `HashMap` instance has a random 128-bit key to use with a keyed hash, "
113 "making the order of a set of keys in a given hash table randomized. Rust "
114 "provides a [SipHash](https://131002.net/siphash/) implementation for any "
115 "type implementing the `IterBytes` trait."
119 #: doc/tutorial-container.md:44
120 msgid "## Double-ended queues"
124 #: doc/tutorial-container.md:49
126 "The `extra::deque` module implements a double-ended queue with `O(1)` "
127 "amortized inserts and removals from both ends of the container. It also has "
128 "`O(1)` indexing like a vector. The contained elements are not required to be "
129 "copyable, and the queue will be sendable if the contained type is sendable."
133 #: doc/tutorial-container.md:51
134 msgid "## Priority queues"
138 #: doc/tutorial-container.md:55
140 "The `extra::priority_queue` module implements a queue ordered by a key. The "
141 "contained elements are not required to be copyable, and the queue will be "
142 "sendable if the contained type is sendable."
146 #: doc/tutorial-container.md:61
148 "Insertions have `O(log n)` time complexity and checking or popping the "
149 "largest element is `O(1)`. Converting a vector to a priority queue can be "
150 "done in-place, and has `O(n)` complexity. A priority queue can also be "
151 "converted to a sorted vector in-place, allowing it to be used for an `O(n "
152 "log n)` in-place heapsort."
156 #: doc/tutorial-container.md:63
161 #: doc/tutorial-container.md:65
162 msgid "## Iteration protocol"
166 #: doc/tutorial-container.md:69
168 "The iteration protocol is defined by the `Iterator` trait in the `std::"
169 "iterator` module. The minimal implementation of the trait is a `next` "
170 "method, yielding the next element from an iterator object:"
174 #: doc/tutorial-container.md:73
175 msgid "~~~ /// An infinite stream of zeroes struct ZeroStream;"
179 #: doc/tutorial-container.md:80
182 "impl Iterator<int> for ZeroStream {\n"
183 " fn next(&mut self) -> Option<int> {\n"
191 #: doc/tutorial-container.md:83
193 "Reaching the end of the iterator is signalled by returning `None` instead of "
198 #: doc/tutorial-container.md:89 doc/tutorial-container.md:262
202 "/// A stream of N zeroes\n"
203 "struct ZeroStream {\n"
204 " priv remaining: uint\n"
209 #: doc/tutorial-container.md:95
212 "impl ZeroStream {\n"
213 " fn new(n: uint) -> ZeroStream {\n"
214 " ZeroStream { remaining: n }\n"
220 #: doc/tutorial-container.md:107 doc/tutorial-container.md:284
223 "impl Iterator<int> for ZeroStream {\n"
224 " fn next(&mut self) -> Option<int> {\n"
225 " if self.remaining == 0 {\n"
228 " self.remaining -= 1;\n"
237 #: doc/tutorial-container.md:109
238 msgid "## Container iterators"
242 #: doc/tutorial-container.md:112
244 "Containers implement iteration over the contained elements by returning an "
245 "iterator object. For example, vector slices several iterators available:"
248 #. type: Bullet: '* '
249 #: doc/tutorial-container.md:116
250 msgid "`iter()` and `rev_iter()`, for immutable references to the elements"
253 #. type: Bullet: '* '
254 #: doc/tutorial-container.md:116
256 "`mut_iter()` and `mut_rev_iter()`, for mutable references to the elements"
259 #. type: Bullet: '* '
260 #: doc/tutorial-container.md:116
262 "`consume_iter()` and `consume_rev_iter`, to move the elements out by-value"
266 #: doc/tutorial-container.md:119
268 "A typical mutable container will implement at least `iter()`, `mut_iter()` "
269 "and `consume_iter()` along with the reverse variants if it maintains an "
274 #: doc/tutorial-container.md:121
279 #: doc/tutorial-container.md:125
281 "Unlike most other languages with external iterators, Rust has no *iterator "
282 "invalidation*. As long an iterator is still in scope, the compiler will "
283 "prevent modification of the container through another handle."
287 #: doc/tutorial-container.md:130
291 "let mut xs = [1, 2, 3];\n"
293 " let _it = xs.iter();\n"
297 #: doc/tutorial-container.md:136
300 " // the vector is frozen for this scope, the compiler will statically\n"
301 " // prevent modification\n"
303 "// the vector becomes unfrozen again at the end of the scope\n"
308 #: doc/tutorial-container.md:139
310 "These semantics are due to most container iterators being implemented with "
315 #: doc/tutorial-container.md:141
316 msgid "## Iterator adaptors"
320 #: doc/tutorial-container.md:145
322 "The `IteratorUtil` trait implements common algorithms as methods extending "
323 "every `Iterator` implementation. For example, the `fold` method will "
324 "accumulate the items yielded by an `Iterator` into a single value:"
328 #: doc/tutorial-container.md:151
330 "~~~ let xs = [1, 9, 2, 3, 14, 12]; let result = xs.iter().fold(0, |"
331 "accumulator, item| accumulator - *item); assert_eq!(result, -41); ~~~"
335 #: doc/tutorial-container.md:153
337 "Some adaptors return an adaptor object implementing the `Iterator` trait "
342 #: doc/tutorial-container.md:160
344 "~~~ let xs = [1, 9, 2, 3, 14, 12]; let ys = [5, 2, 1, 8]; let sum = xs."
345 "iter().chain_(ys.iter()).fold(0, |a, b| a + *b); assert_eq!(sum, 57); ~~~"
349 #: doc/tutorial-container.md:164
351 "Note that some adaptors like the `chain_` method above use a trailing "
352 "underscore to work around an issue with method resolve. The underscores will "
353 "be dropped when they become unnecessary."
357 #: doc/tutorial-container.md:166
362 #: doc/tutorial-container.md:168
364 "The `for` keyword can be used as sugar for iterating through any iterator:"
368 #: doc/tutorial-container.md:171
369 msgid "~~~ let xs = [2, 3, 5, 7, 11, 13, 17];"
373 #: doc/tutorial-container.md:176
376 "// print out all the elements in the vector\n"
377 "for x in xs.iter() {\n"
378 " println(x.to_str())\n"
383 #: doc/tutorial-container.md:182
386 "// print out all but the first 3 elements in the vector\n"
387 "for x in xs.iter().skip(3) {\n"
388 " println(x.to_str())\n"
394 #: doc/tutorial-container.md:185
396 "For loops are *often* used with a temporary iterator object, as above. They "
397 "can also advance the state of an iterator in a mutable location:"
401 #: doc/tutorial-container.md:189
403 "~~~ let xs = [1, 2, 3, 4, 5]; let ys = [\"foo\", \"bar\", \"baz\", \"foobar"
408 #: doc/tutorial-container.md:192
410 "// create an iterator yielding tuples of elements from both vectors let mut "
411 "it = xs.iter().zip(ys.iter());"
415 #: doc/tutorial-container.md:196
418 "// print out the pairs of elements up to (&3, &\"baz\")\n"
419 "for (x, y) in it {\n"
420 " printfln!(\"%d %s\", *x, *y);\n"
424 #: doc/tutorial-container.md:201
434 #: doc/tutorial-container.md:204
436 "// yield and print the last pair from the iterator printfln!(\"last: %?\", "
441 #: doc/tutorial-container.md:208
442 msgid "// the iterator is now fully consumed assert!(it.next().is_none()); ~~~"
446 #: doc/tutorial-container.md:210
447 msgid "## Conversion"
451 #: doc/tutorial-container.md:212
453 "Iterators offer generic conversion to containers with the `collect` adaptor:"
457 #: doc/tutorial-container.md:218
459 "~~~ let xs = [0, 1, 1, 2, 3, 5, 8]; let ys = xs.rev_iter().skip(1)."
460 "transform(|&x| x * 2).collect::<~[int]>(); assert_eq!(ys, ~[10, 6, 4, 2, 2, "
465 #: doc/tutorial-container.md:221
467 "The method requires a type hint for the container type, if the surrounding "
468 "code does not provide sufficient information."
472 #: doc/tutorial-container.md:225
474 "Containers can provide conversion from iterators through `collect` by "
475 "implementing the `FromIterator` trait. For example, the implementation for "
476 "vectors is as follows:"
480 #: doc/tutorial-container.md:238
484 "impl<A> FromIterator<A> for ~[A] {\n"
485 " pub fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> ~[A] {\n"
486 " let (lower, _) = iterator.size_hint();\n"
487 " let mut xs = with_capacity(lower);\n"
488 " for x in iterator {\n"
498 #: doc/tutorial-container.md:240
499 msgid "### Size hints"
503 #: doc/tutorial-container.md:243
505 "The `Iterator` trait provides a `size_hint` default method, returning a "
506 "lower bound and optionally on upper bound on the length of the iterator:"
510 #: doc/tutorial-container.md:247
511 msgid "~~~ fn size_hint(&self) -> (uint, Option<uint>) { (0, None) } ~~~"
515 #: doc/tutorial-container.md:251
517 "The vector implementation of `FromIterator` from above uses the lower bound "
518 "to pre-allocate enough space to hold the minimum number of elements the "
519 "iterator will yield."
523 #: doc/tutorial-container.md:254
525 "The default implementation is always correct, but it should be overridden if "
526 "the iterator can provide better information."
530 #: doc/tutorial-container.md:256
532 "The `ZeroStream` from earlier can provide an exact lower and upper bound:"
536 #: doc/tutorial-container.md:267
539 "impl ZeroStream {\n"
540 " fn new(n: uint) -> ZeroStream {\n"
541 " ZeroStream { remaining: n }\n"
546 #: doc/tutorial-container.md:272
549 " fn size_hint(&self) -> (uint, Option<uint>) {\n"
550 " (self.remaining, Some(self.remaining))\n"
556 #: doc/tutorial-container.md:286
557 msgid "## Double-ended iterators"
561 #: doc/tutorial-container.md:290
563 "The `DoubleEndedIterator` trait represents an iterator able to yield "
564 "elements from either end of a range. It inherits from the `Iterator` trait "
565 "and extends it with the `next_back` function."
569 #: doc/tutorial-container.md:293
571 "A `DoubleEndedIterator` can be flipped with the `invert` adaptor, returning "
572 "another `DoubleEndedIterator` with `next` and `next_back` exchanged."
576 #: doc/tutorial-container.md:300
578 "~~~ let xs = [1, 2, 3, 4, 5, 6]; let mut it = xs.iter(); printfln!(\"%?\", "
579 "it.next()); // prints `Some(&1)` printfln!(\"%?\", it.next()); // prints "
580 "`Some(&2)` printfln!(\"%?\", it.next_back()); // prints `Some(&6)`"
584 #: doc/tutorial-container.md:306
587 "// prints `5`, `4` and `3`\n"
588 "for &x in it.invert() {\n"
589 " printfln!(\"%?\", x)\n"
595 #: doc/tutorial-container.md:309
597 "The `rev_iter` and `mut_rev_iter` methods on vectors just return an inverted "
598 "version of the standard immutable and mutable vector iterators."
602 #: doc/tutorial-container.md:312
604 "The `chain_`, `transform`, `filter`, `filter_map` and `peek` adaptors are "
605 "`DoubleEndedIterator` implementations if the underlying iterators are."
609 #: doc/tutorial-container.md:317
611 "~~~ let xs = [1, 2, 3, 4]; let ys = [5, 6, 7, 8]; let mut it = xs.iter()."
612 "chain_(ys.iter()).transform(|&x| x * 2);"
616 #: doc/tutorial-container.md:319
617 msgid "printfln!(\"%?\", it.next()); // prints `Some(2)`"
621 #: doc/tutorial-container.md:325
624 "// prints `16`, `14`, `12`, `10`, `8`, `6`, `4`\n"
625 "for x in it.invert() {\n"
626 " printfln!(\"%?\", x);\n"
632 #: doc/tutorial-container.md:327
633 msgid "## Random-access iterators"
637 #: doc/tutorial-container.md:331
639 "The `RandomAccessIterator` trait represents an iterator offering random "
640 "access to the whole range. The `indexable` method retrieves the number of "
641 "elements accessible with the `idx` method."
645 #: doc/tutorial-container.md:334
647 "The `chain_` adaptor is an implementation of `RandomAccessIterator` if the "
648 "underlying iterators are."
652 #: doc/tutorial-container.md:343
654 "~~~ let xs = [1, 2, 3, 4, 5]; let ys = ~[7, 9, 11]; let mut it = xs.iter()."
655 "chain_(ys.iter()); printfln!(\"%?\", it.idx(0)); // prints `Some(&1)` "
656 "printfln!(\"%?\", it.idx(5)); // prints `Some(&7)` printfln!(\"%?\", it."
657 "idx(7)); // prints `Some(&11)` printfln!(\"%?\", it.idx(8)); // prints `None`"
661 #: doc/tutorial-container.md:348
663 "// yield two elements from the beginning, and one from the end it.next(); it."
664 "next(); it.next_back();"
668 #: doc/tutorial-container.md:352
670 "printfln!(\"%?\", it.idx(0)); // prints `Some(&3)` printfln!(\"%?\", it."
671 "idx(4)); // prints `Some(&9)` printfln!(\"%?\", it.idx(6)); // prints `None` "