1 // Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 //! Rust's standard collection library provides efficient implementations of the
14 //! most common general purpose programming data structures. By using the
15 //! standard implementations, it should be possible for two libraries to
16 //! communicate without significant data conversion.
18 //! To get this out of the way: you should probably just use `Vec` or `HashMap`.
19 //! These two collections cover most use cases for generic data storage and
20 //! processing. They are exceptionally good at doing what they do. All the other
21 //! collections in the standard library have specific use cases where they are
22 //! the optimal choice, but these cases are borderline *niche* in comparison.
23 //! Even when `Vec` and `HashMap` are technically suboptimal, they're probably a
24 //! good enough choice to get started.
26 //! Rust's collections can be grouped into four major categories:
28 //! * Sequences: `Vec`, `VecDeque`, `LinkedList`
29 //! * Maps: `HashMap`, `BTreeMap`
30 //! * Sets: `HashSet`, `BTreeSet`
31 //! * Misc: `BinaryHeap`
33 //! # When Should You Use Which Collection?
35 //! These are fairly high-level and quick break-downs of when each collection
36 //! should be considered. Detailed discussions of strengths and weaknesses of
37 //! individual collections can be found on their own documentation pages.
39 //! ### Use a `Vec` when:
40 //! * You want to collect items up to be processed or sent elsewhere later, and
41 //! don't care about any properties of the actual values being stored.
42 //! * You want a sequence of elements in a particular order, and will only be
43 //! appending to (or near) the end.
44 //! * You want a stack.
45 //! * You want a resizable array.
46 //! * You want a heap-allocated array.
48 //! ### Use a `VecDeque` when:
49 //! * You want a `Vec` that supports efficient insertion at both ends of the
51 //! * You want a queue.
52 //! * You want a double-ended queue (deque).
54 //! ### Use a `LinkedList` when:
55 //! * You want a `Vec` or `VecDeque` of unknown size, and can't tolerate
57 //! * You want to efficiently split and append lists.
58 //! * You are *absolutely* certain you *really*, *truly*, want a doubly linked
61 //! ### Use a `HashMap` when:
62 //! * You want to associate arbitrary keys with an arbitrary value.
63 //! * You want a cache.
64 //! * You want a map, with no extra functionality.
66 //! ### Use a `BTreeMap` when:
67 //! * You're interested in what the smallest or largest key-value pair is.
68 //! * You want to find the largest or smallest key that is smaller or larger
70 //! * You want to be able to get all of the entries in order on-demand.
71 //! * You want a sorted map.
73 //! ### Use the `Set` variant of any of these `Map`s when:
74 //! * You just want to remember which keys you've seen.
75 //! * There is no meaningful value to associate with your keys.
76 //! * You just want a set.
78 //! ### Use a `BinaryHeap` when:
80 //! * You want to store a bunch of elements, but only ever want to process the
81 //! "biggest" or "most important" one at any given time.
82 //! * You want a priority queue.
86 //! Choosing the right collection for the job requires an understanding of what
87 //! each collection is good at. Here we briefly summarize the performance of
88 //! different collections for certain important operations. For further details,
89 //! see each type's documentation, and note that the names of actual methods may
90 //! differ from the tables below on certain collections.
92 //! Throughout the documentation, we will follow a few conventions. For all
93 //! operations, the collection's size is denoted by n. If another collection is
94 //! involved in the operation, it contains m elements. Operations which have an
95 //! *amortized* cost are suffixed with a `*`. Operations with an *expected*
96 //! cost are suffixed with a `~`.
98 //! All amortized costs are for the potential need to resize when capacity is
99 //! exhausted. If a resize occurs it will take O(n) time. Our collections never
100 //! automatically shrink, so removal operations aren't amortized. Over a
101 //! sufficiently large series of operations, the average cost per operation will
102 //! deterministically equal the given cost.
104 //! Only HashMap has expected costs, due to the probabilistic nature of hashing.
105 //! It is theoretically possible, though very unlikely, for HashMap to
106 //! experience worse performance.
110 //! | | get(i) | insert(i) | remove(i) | append | split_off(i) |
111 //! |--------------|----------------|-----------------|----------------|--------|----------------|
112 //! | Vec | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) |
113 //! | VecDeque | O(1) | O(min(i, n-i))* | O(min(i, n-i)) | O(m)* | O(min(i, n-i)) |
114 //! | LinkedList | O(min(i, n-i)) | O(min(i, n-i)) | O(min(i, n-i)) | O(1) | O(min(i, n-i)) |
116 //! Note that where ties occur, Vec is generally going to be faster than VecDeque, and VecDeque
117 //! is generally going to be faster than LinkedList.
121 //! For Sets, all operations have the cost of the equivalent Map operation.
123 //! | | get | insert | remove | predecessor |
124 //! |----------|-----------|----------|----------|-------------|
125 //! | HashMap | O(1)~ | O(1)~* | O(1)~ | N/A |
126 //! | BTreeMap | O(log n) | O(log n) | O(log n) | O(log n) |
128 //! Note that BTreeMap's precise performance depends on the value of B.
130 //! # Correct and Efficient Usage of Collections
132 //! Of course, knowing which collection is the right one for the job doesn't
133 //! instantly permit you to use it correctly. Here are some quick tips for
134 //! efficient and correct usage of the standard collections in general. If
135 //! you're interested in how to use a specific collection in particular, consult
136 //! its documentation for detailed discussion and code examples.
138 //! ## Capacity Management
140 //! Many collections provide several constructors and methods that refer to
141 //! "capacity". These collections are generally built on top of an array.
142 //! Optimally, this array would be exactly the right size to fit only the
143 //! elements stored in the collection, but for the collection to do this would
144 //! be very inefficient. If the backing array was exactly the right size at all
145 //! times, then every time an element is inserted, the collection would have to
146 //! grow the array to fit it. Due to the way memory is allocated and managed on
147 //! most computers, this would almost surely require allocating an entirely new
148 //! array and copying every single element from the old one into the new one.
149 //! Hopefully you can see that this wouldn't be very efficient to do on every
152 //! Most collections therefore use an *amortized* allocation strategy. They
153 //! generally let themselves have a fair amount of unoccupied space so that they
154 //! only have to grow on occasion. When they do grow, they allocate a
155 //! substantially larger array to move the elements into so that it will take a
156 //! while for another grow to be required. While this strategy is great in
157 //! general, it would be even better if the collection *never* had to resize its
158 //! backing array. Unfortunately, the collection itself doesn't have enough
159 //! information to do this itself. Therefore, it is up to us programmers to give
162 //! Any `with_capacity` constructor will instruct the collection to allocate
163 //! enough space for the specified number of elements. Ideally this will be for
164 //! exactly that many elements, but some implementation details may prevent
165 //! this. `Vec` and `VecDeque` can be relied on to allocate exactly the
166 //! requested amount, though. Use `with_capacity` when you know exactly how many
167 //! elements will be inserted, or at least have a reasonable upper-bound on that
170 //! When anticipating a large influx of elements, the `reserve` family of
171 //! methods can be used to hint to the collection how much room it should make
172 //! for the coming items. As with `with_capacity`, the precise behavior of
173 //! these methods will be specific to the collection of interest.
175 //! For optimal performance, collections will generally avoid shrinking
176 //! themselves. If you believe that a collection will not soon contain any more
177 //! elements, or just really need the memory, the `shrink_to_fit` method prompts
178 //! the collection to shrink the backing array to the minimum size capable of
179 //! holding its elements.
181 //! Finally, if ever you're interested in what the actual capacity of the
182 //! collection is, most collections provide a `capacity` method to query this
183 //! information on demand. This can be useful for debugging purposes, or for
184 //! use with the `reserve` methods.
188 //! Iterators are a powerful and robust mechanism used throughout Rust's
189 //! standard libraries. Iterators provide a sequence of values in a generic,
190 //! safe, efficient and convenient way. The contents of an iterator are usually
191 //! *lazily* evaluated, so that only the values that are actually needed are
192 //! ever actually produced, and no allocation need be done to temporarily store
193 //! them. Iterators are primarily consumed using a `for` loop, although many
194 //! functions also take iterators where a collection or sequence of values is
197 //! All of the standard collections provide several iterators for performing
198 //! bulk manipulation of their contents. The three primary iterators almost
199 //! every collection should provide are `iter`, `iter_mut`, and `into_iter`.
200 //! Some of these are not provided on collections where it would be unsound or
201 //! unreasonable to provide them.
203 //! `iter` provides an iterator of immutable references to all the contents of a
204 //! collection in the most "natural" order. For sequence collections like `Vec`,
205 //! this means the items will be yielded in increasing order of index starting
206 //! at 0. For ordered collections like `BTreeMap`, this means that the items
207 //! will be yielded in sorted order. For unordered collections like `HashMap`,
208 //! the items will be yielded in whatever order the internal representation made
209 //! most convenient. This is great for reading through all the contents of the
213 //! let vec = vec![1, 2, 3, 4];
214 //! for x in vec.iter() {
215 //! println!("vec contained {}", x);
219 //! `iter_mut` provides an iterator of *mutable* references in the same order as
220 //! `iter`. This is great for mutating all the contents of the collection.
223 //! let mut vec = vec![1, 2, 3, 4];
224 //! for x in vec.iter_mut() {
229 //! `into_iter` transforms the actual collection into an iterator over its
230 //! contents by-value. This is great when the collection itself is no longer
231 //! needed, and the values are needed elsewhere. Using `extend` with `into_iter`
232 //! is the main way that contents of one collection are moved into another.
233 //! `extend` automatically calls `into_iter`, and takes any `T: IntoIterator`.
234 //! Calling `collect` on an iterator itself is also a great way to convert one
235 //! collection into another. Both of these methods should internally use the
236 //! capacity management tools discussed in the previous section to do this as
237 //! efficiently as possible.
240 //! let mut vec1 = vec![1, 2, 3, 4];
241 //! let vec2 = vec![10, 20, 30, 40];
242 //! vec1.extend(vec2);
246 //! use std::collections::VecDeque;
248 //! let vec = vec![1, 2, 3, 4];
249 //! let buf: VecDeque<_> = vec.into_iter().collect();
252 //! Iterators also provide a series of *adapter* methods for performing common
253 //! threads to sequences. Among the adapters are functional favorites like `map`,
254 //! `fold`, `skip`, and `take`. Of particular interest to collections is the
255 //! `rev` adapter, that reverses any iterator that supports this operation. Most
256 //! collections provide reversible iterators as the way to iterate over them in
260 //! let vec = vec![1, 2, 3, 4];
261 //! for x in vec.iter().rev() {
262 //! println!("vec contained {}", x);
266 //! Several other collection methods also return iterators to yield a sequence
267 //! of results but avoid allocating an entire collection to store the result in.
268 //! This provides maximum flexibility as `collect` or `extend` can be called to
269 //! "pipe" the sequence into any collection if desired. Otherwise, the sequence
270 //! can be looped over with a `for` loop. The iterator can also be discarded
271 //! after partial use, preventing the computation of the unused items.
275 //! The `entry` API is intended to provide an efficient mechanism for
276 //! manipulating the contents of a map conditionally on the presence of a key or
277 //! not. The primary motivating use case for this is to provide efficient
278 //! accumulator maps. For instance, if one wishes to maintain a count of the
279 //! number of times each key has been seen, they will have to perform some
280 //! conditional logic on whether this is the first time the key has been seen or
281 //! not. Normally, this would require a `find` followed by an `insert`,
282 //! effectively duplicating the search effort on each insertion.
284 //! When a user calls `map.entry(&key)`, the map will search for the key and
285 //! then yield a variant of the `Entry` enum.
287 //! If a `Vacant(entry)` is yielded, then the key *was not* found. In this case
288 //! the only valid operation is to `insert` a value into the entry. When this is
289 //! done, the vacant entry is consumed and converted into a mutable reference to
290 //! the value that was inserted. This allows for further manipulation of the
291 //! value beyond the lifetime of the search itself. This is useful if complex
292 //! logic needs to be performed on the value regardless of whether the value was
295 //! If an `Occupied(entry)` is yielded, then the key *was* found. In this case,
296 //! the user has several options: they can `get`, `insert`, or `remove` the
297 //! value of the occupied entry. Additionally, they can convert the occupied
298 //! entry into a mutable reference to its value, providing symmetry to the
299 //! vacant `insert` case.
303 //! Here are the two primary ways in which `entry` is used. First, a simple
304 //! example where the logic performed on the values is trivial.
306 //! #### Counting the number of times each character in a string occurs
309 //! use std::collections::btree_map::BTreeMap;
311 //! let mut count = BTreeMap::new();
312 //! let message = "she sells sea shells by the sea shore";
314 //! for c in message.chars() {
315 //! *count.entry(c).or_insert(0) += 1;
318 //! assert_eq!(count.get(&'s'), Some(&8));
320 //! println!("Number of occurrences of each character");
321 //! for (char, count) in &count {
322 //! println!("{}: {}", char, count);
326 //! When the logic to be performed on the value is more complex, we may simply
327 //! use the `entry` API to ensure that the value is initialized, and perform the
328 //! logic afterwards.
330 //! #### Tracking the inebriation of customers at a bar
333 //! use std::collections::btree_map::BTreeMap;
335 //! // A client of the bar. They have a blood alcohol level.
336 //! struct Person { blood_alcohol: f32 }
338 //! // All the orders made to the bar, by client id.
339 //! let orders = vec![1,2,1,2,3,4,1,2,2,3,4,1,1,1];
342 //! let mut blood_alcohol = BTreeMap::new();
344 //! for id in orders {
345 //! // If this is the first time we've seen this customer, initialize them
346 //! // with no blood alcohol. Otherwise, just retrieve them.
347 //! let person = blood_alcohol.entry(id).or_insert(Person { blood_alcohol: 0.0 });
349 //! // Reduce their blood alcohol level. It takes time to order and drink a beer!
350 //! person.blood_alcohol *= 0.9;
352 //! // Check if they're sober enough to have another beer.
353 //! if person.blood_alcohol > 0.3 {
354 //! // Too drunk... for now.
355 //! println!("Sorry {}, I have to cut you off", id);
358 //! person.blood_alcohol += 0.1;
363 //! # Insert and complex keys
365 //! If we have a more complex key, calls to `insert()` will
366 //! not update the value of the key. For example:
369 //! use std::cmp::Ordering;
370 //! use std::collections::BTreeMap;
371 //! use std::hash::{Hash, Hasher};
379 //! // we will compare `Foo`s by their `a` value only.
380 //! impl PartialEq for Foo {
381 //! fn eq(&self, other: &Self) -> bool { self.a == other.a }
384 //! impl Eq for Foo {}
386 //! // we will hash `Foo`s by their `a` value only.
387 //! impl Hash for Foo {
388 //! fn hash<H: Hasher>(&self, h: &mut H) { self.a.hash(h); }
391 //! impl PartialOrd for Foo {
392 //! fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.a.partial_cmp(&other.a) }
395 //! impl Ord for Foo {
396 //! fn cmp(&self, other: &Self) -> Ordering { self.a.cmp(&other.a) }
399 //! let mut map = BTreeMap::new();
400 //! map.insert(Foo { a: 1, b: "baz" }, ());
402 //! // We already have a Foo with an a of 1, so this will be updating the value.
403 //! map.insert(Foo { a: 1, b: "xyz" }, ());
405 //! // ... but the key hasn't changed. b is still "baz", not "xyz"
406 //! assert_eq!(map.keys().next().unwrap().b, "baz");
409 #![stable(feature = "rust1", since = "1.0.0")]
411 #[stable(feature = "rust1", since = "1.0.0")]
412 pub use core_collections::Bound;
413 #[stable(feature = "rust1", since = "1.0.0")]
414 pub use core_collections::{BinaryHeap, BTreeMap, BTreeSet};
415 #[stable(feature = "rust1", since = "1.0.0")]
416 pub use core_collections::{LinkedList, VecDeque};
417 #[stable(feature = "rust1", since = "1.0.0")]
418 pub use core_collections::{binary_heap, btree_map, btree_set};
419 #[stable(feature = "rust1", since = "1.0.0")]
420 pub use core_collections::{linked_list, vec_deque};
422 #[stable(feature = "rust1", since = "1.0.0")]
423 pub use self::hash_map::HashMap;
424 #[stable(feature = "rust1", since = "1.0.0")]
425 pub use self::hash_set::HashSet;
429 #[stable(feature = "rust1", since = "1.0.0")]
432 #[stable(feature = "rust1", since = "1.0.0")]
433 pub use super::hash::map::*;
436 #[stable(feature = "rust1", since = "1.0.0")]
439 #[stable(feature = "rust1", since = "1.0.0")]
440 pub use super::hash::set::*;
443 /// Experimental support for providing custom hash algorithms to a HashMap and
445 #[unstable(feature = "hashmap_hasher", reason = "module was recently added",
448 pub use super::hash::state::*;