1//! Collection types.
2//!
3//! Rust's standard collection library provides efficient implementations of the
4//! most common general purpose programming data structures. By using the
5//! standard implementations, it should be possible for two libraries to
6//! communicate without significant data conversion.
7//!
8//! To get this out of the way: you should probably just use [`Vec`] or [`HashMap`].
9//! These two collections cover most use cases for generic data storage and
10//! processing. They are exceptionally good at doing what they do. All the other
11//! collections in the standard library have specific use cases where they are
12//! the optimal choice, but these cases are borderline *niche* in comparison.
13//! Even when `Vec` and `HashMap` are technically suboptimal, they're probably a
14//! good enough choice to get started.
15//!
16//! Rust's collections can be grouped into four major categories:
17//!
18//! * Sequences: [`Vec`], [`VecDeque`], [`LinkedList`]
19//! * Maps: [`HashMap`], [`BTreeMap`]
20//! * Sets: [`HashSet`], [`BTreeSet`]
21//! * Misc: [`BinaryHeap`]
22//!
23//! # When Should You Use Which Collection?
24//!
25//! These are fairly high-level and quick break-downs of when each collection
26//! should be considered. Detailed discussions of strengths and weaknesses of
27//! individual collections can be found on their own documentation pages.
28//!
29//! ### Use a `Vec` when:
30//! * You want to collect items up to be processed or sent elsewhere later, and
31//! don't care about any properties of the actual values being stored.
32//! * You want a sequence of elements in a particular order, and will only be
33//! appending to (or near) the end.
34//! * You want a stack.
35//! * You want a resizable array.
36//! * You want a heap-allocated array.
37//!
38//! ### Use a `VecDeque` when:
39//! * You want a [`Vec`] that supports efficient insertion at both ends of the
40//! sequence.
41//! * You want a queue.
42//! * You want a double-ended queue (deque).
43//!
44//! ### Use a `LinkedList` when:
45//! * You want a [`Vec`] or [`VecDeque`] of unknown size, and can't tolerate
46//! amortization.
47//! * You want to efficiently split and append lists.
48//! * You are *absolutely* certain you *really*, *truly*, want a doubly linked
49//! list.
50//!
51//! ### Use a `HashMap` when:
52//! * You want to associate arbitrary keys with an arbitrary value.
53//! * You want a cache.
54//! * You want a map, with no extra functionality.
55//!
56//! ### Use a `BTreeMap` when:
57//! * You want a map sorted by its keys.
58//! * You want to be able to get a range of entries on-demand.
59//! * You're interested in what the smallest or largest key-value pair is.
60//! * You want to find the largest or smallest key that is smaller or larger
61//! than something.
62//!
63//! ### Use the `Set` variant of any of these `Map`s when:
64//! * You just want to remember which keys you've seen.
65//! * There is no meaningful value to associate with your keys.
66//! * You just want a set.
67//!
68//! ### Use a `BinaryHeap` when:
69//!
70//! * You want to store a bunch of elements, but only ever want to process the
71//! "biggest" or "most important" one at any given time.
72//! * You want a priority queue.
73//!
74//! # Performance
75//!
76//! Choosing the right collection for the job requires an understanding of what
77//! each collection is good at. Here we briefly summarize the performance of
78//! different collections for certain important operations. For further details,
79//! see each type's documentation, and note that the names of actual methods may
80//! differ from the tables below on certain collections.
81//!
82//! Throughout the documentation, we will adhere to the following conventions
83//! for operation notation:
84//!
85//! * The collection's size is denoted by `n`.
86//! * If a second collection is involved, its size is denoted by `m`.
87//! * Item indices are denoted by `i`.
88//! * Operations which have an *amortized* cost are suffixed with a `*`.
89//! * Operations with an *expected* cost are suffixed with a `~`.
90//!
91//! Calling operations that add to a collection will occasionally require a
92//! collection to be resized - an extra operation that takes *O*(*n*) time.
93//!
94//! *Amortized* costs are calculated to account for the time cost of such resize
95//! operations *over a sufficiently large series of operations*. An individual
96//! operation may be slower or faster due to the sporadic nature of collection
97//! resizing, however the average cost per operation will approach the amortized
98//! cost.
99//!
100//! Rust's collections never automatically shrink, so removal operations aren't
101//! amortized.
102//!
103//! [`HashMap`] uses *expected* costs. It is theoretically possible, though very
104//! unlikely, for [`HashMap`] to experience significantly worse performance than
105//! the expected cost. This is due to the probabilistic nature of hashing - i.e.
106//! it is possible to generate a duplicate hash given some input key that will
107//! requires extra computation to correct.
108//!
109//! ## Cost of Collection Operations
110//!
111//!
112//! | | get(i) | insert(i) | remove(i) | append(Vec(m)) | split_off(i) | range | append |
113//! |----------------|------------------------|-------------------------|------------------------|-------------------|------------------------|-----------------|--------------|
114//! | [`Vec`] | *O*(1) | *O*(*n*-*i*)* | *O*(*n*-*i*) | *O*(*m*)* | *O*(*n*-*i*) | N/A | N/A |
115//! | [`VecDeque`] | *O*(1) | *O*(min(*i*, *n*-*i*))* | *O*(min(*i*, *n*-*i*)) | *O*(*m*)* | *O*(min(*i*, *n*-*i*)) | N/A | N/A |
116//! | [`LinkedList`] | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(1) | *O*(min(*i*, *n*-*i*)) | N/A | N/A |
117//! | [`HashMap`] | *O*(1)~ | *O*(1)~* | *O*(1)~ | N/A | N/A | N/A | N/A |
118//! | [`BTreeMap`] | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | N/A | N/A | *O*(log(*n*)) | *O*(*n*+*m*) |
119//!
120//! Note that where ties occur, [`Vec`] is generally going to be faster than
121//! [`VecDeque`], and [`VecDeque`] is generally going to be faster than
122//! [`LinkedList`].
123//!
124//! For Sets, all operations have the cost of the equivalent Map operation.
125//!
126//! # Correct and Efficient Usage of Collections
127//!
128//! Of course, knowing which collection is the right one for the job doesn't
129//! instantly permit you to use it correctly. Here are some quick tips for
130//! efficient and correct usage of the standard collections in general. If
131//! you're interested in how to use a specific collection in particular, consult
132//! its documentation for detailed discussion and code examples.
133//!
134//! ## Capacity Management
135//!
136//! Many collections provide several constructors and methods that refer to
137//! "capacity". These collections are generally built on top of an array.
138//! Optimally, this array would be exactly the right size to fit only the
139//! elements stored in the collection, but for the collection to do this would
140//! be very inefficient. If the backing array was exactly the right size at all
141//! times, then every time an element is inserted, the collection would have to
142//! grow the array to fit it. Due to the way memory is allocated and managed on
143//! most computers, this would almost surely require allocating an entirely new
144//! array and copying every single element from the old one into the new one.
145//! Hopefully you can see that this wouldn't be very efficient to do on every
146//! operation.
147//!
148//! Most collections therefore use an *amortized* allocation strategy. They
149//! generally let themselves have a fair amount of unoccupied space so that they
150//! only have to grow on occasion. When they do grow, they allocate a
151//! substantially larger array to move the elements into so that it will take a
152//! while for another grow to be required. While this strategy is great in
153//! general, it would be even better if the collection *never* had to resize its
154//! backing array. Unfortunately, the collection itself doesn't have enough
155//! information to do this itself. Therefore, it is up to us programmers to give
156//! it hints.
157//!
158//! Any `with_capacity` constructor will instruct the collection to allocate
159//! enough space for the specified number of elements. Ideally this will be for
160//! exactly that many elements, but some implementation details may prevent
161//! this. See collection-specific documentation for details. In general, use
162//! `with_capacity` when you know exactly how many elements will be inserted, or
163//! at least have a reasonable upper-bound on that number.
164//!
165//! When anticipating a large influx of elements, the `reserve` family of
166//! methods can be used to hint to the collection how much room it should make
167//! for the coming items. As with `with_capacity`, the precise behavior of
168//! these methods will be specific to the collection of interest.
169//!
170//! For optimal performance, collections will generally avoid shrinking
171//! themselves. If you believe that a collection will not soon contain any more
172//! elements, or just really need the memory, the `shrink_to_fit` method prompts
173//! the collection to shrink the backing array to the minimum size capable of
174//! holding its elements.
175//!
176//! Finally, if ever you're interested in what the actual capacity of the
177//! collection is, most collections provide a `capacity` method to query this
178//! information on demand. This can be useful for debugging purposes, or for
179//! use with the `reserve` methods.
180//!
181//! ## Iterators
182//!
183//! [Iterators][crate::iter]
184//! are a powerful and robust mechanism used throughout Rust's
185//! standard libraries. Iterators provide a sequence of values in a generic,
186//! safe, efficient and convenient way. The contents of an iterator are usually
187//! *lazily* evaluated, so that only the values that are actually needed are
188//! ever actually produced, and no allocation need be done to temporarily store
189//! them. Iterators are primarily consumed using a `for` loop, although many
190//! functions also take iterators where a collection or sequence of values is
191//! desired.
192//!
193//! All of the standard collections provide several iterators for performing
194//! bulk manipulation of their contents. The three primary iterators almost
195//! every collection should provide are `iter`, `iter_mut`, and `into_iter`.
196//! Some of these are not provided on collections where it would be unsound or
197//! unreasonable to provide them.
198//!
199//! `iter` provides an iterator of immutable references to all the contents of a
200//! collection in the most "natural" order. For sequence collections like [`Vec`],
201//! this means the items will be yielded in increasing order of index starting
202//! at 0. For ordered collections like [`BTreeMap`], this means that the items
203//! will be yielded in sorted order. For unordered collections like [`HashMap`],
204//! the items will be yielded in whatever order the internal representation made
205//! most convenient. This is great for reading through all the contents of the
206//! collection.
207//!
208//! ```
209//! let vec = vec![1, 2, 3, 4];
210//! for x in vec.iter() {
211//! println!("vec contained {x:?}");
212//! }
213//! ```
214//!
215//! `iter_mut` provides an iterator of *mutable* references in the same order as
216//! `iter`. This is great for mutating all the contents of the collection.
217//!
218//! ```
219//! let mut vec = vec![1, 2, 3, 4];
220//! for x in vec.iter_mut() {
221//! *x += 1;
222//! }
223//! ```
224//!
225//! `into_iter` transforms the actual collection into an iterator over its
226//! contents by-value. This is great when the collection itself is no longer
227//! needed, and the values are needed elsewhere. Using `extend` with `into_iter`
228//! is the main way that contents of one collection are moved into another.
229//! `extend` automatically calls `into_iter`, and takes any <code>T: [IntoIterator]</code>.
230//! Calling `collect` on an iterator itself is also a great way to convert one
231//! collection into another. Both of these methods should internally use the
232//! capacity management tools discussed in the previous section to do this as
233//! efficiently as possible.
234//!
235//! ```
236//! let mut vec1 = vec![1, 2, 3, 4];
237//! let vec2 = vec![10, 20, 30, 40];
238//! vec1.extend(vec2);
239//! ```
240//!
241//! ```
242//! use std::collections::VecDeque;
243//!
244//! let vec = [1, 2, 3, 4];
245//! let buf: VecDeque<_> = vec.into_iter().collect();
246//! ```
247//!
248//! Iterators also provide a series of *adapter* methods for performing common
249//! threads to sequences. Among the adapters are functional favorites like `map`,
250//! `fold`, `skip` and `take`. Of particular interest to collections is the
251//! `rev` adapter, which reverses any iterator that supports this operation. Most
252//! collections provide reversible iterators as the way to iterate over them in
253//! reverse order.
254//!
255//! ```
256//! let vec = vec![1, 2, 3, 4];
257//! for x in vec.iter().rev() {
258//! println!("vec contained {x:?}");
259//! }
260//! ```
261//!
262//! Several other collection methods also return iterators to yield a sequence
263//! of results but avoid allocating an entire collection to store the result in.
264//! This provides maximum flexibility as
265//! [`collect`][crate::iter::Iterator::collect] or
266//! [`extend`][crate::iter::Extend::extend] can be called to
267//! "pipe" the sequence into any collection if desired. Otherwise, the sequence
268//! can be looped over with a `for` loop. The iterator can also be discarded
269//! after partial use, preventing the computation of the unused items.
270//!
271//! ## Entries
272//!
273//! The `entry` API is intended to provide an efficient mechanism for
274//! manipulating the contents of a map conditionally on the presence of a key or
275//! not. The primary motivating use case for this is to provide efficient
276//! accumulator maps. For instance, if one wishes to maintain a count of the
277//! number of times each key has been seen, they will have to perform some
278//! conditional logic on whether this is the first time the key has been seen or
279//! not. Normally, this would require a `find` followed by an `insert`,
280//! effectively duplicating the search effort on each insertion.
281//!
282//! When a user calls `map.entry(key)`, the map will search for the key and
283//! then yield a variant of the `Entry` enum.
284//!
285//! If a `Vacant(entry)` is yielded, then the key *was not* found. In this case
286//! the only valid operation is to `insert` a value into the entry. When this is
287//! done, the vacant entry is consumed and converted into a mutable reference to
288//! the value that was inserted. This allows for further manipulation of the
289//! value beyond the lifetime of the search itself. This is useful if complex
290//! logic needs to be performed on the value regardless of whether the value was
291//! just inserted.
292//!
293//! If an `Occupied(entry)` is yielded, then the key *was* found. In this case,
294//! the user has several options: they can `get`, `insert` or `remove` the
295//! value of the occupied entry. Additionally, they can convert the occupied
296//! entry into a mutable reference to its value, providing symmetry to the
297//! vacant `insert` case.
298//!
299//! ### Examples
300//!
301//! Here are the two primary ways in which `entry` is used. First, a simple
302//! example where the logic performed on the values is trivial.
303//!
304//! #### Counting the number of times each character in a string occurs
305//!
306//! ```
307//! use std::collections::btree_map::BTreeMap;
308//!
309//! let mut count = BTreeMap::new();
310//! let message = "she sells sea shells by the sea shore";
311//!
312//! for c in message.chars() {
313//! *count.entry(c).or_insert(0) += 1;
314//! }
315//!
316//! assert_eq!(count.get(&'s'), Some(&8));
317//!
318//! println!("Number of occurrences of each character");
319//! for (char, count) in &count {
320//! println!("{char}: {count}");
321//! }
322//! ```
323//!
324//! When the logic to be performed on the value is more complex, we may simply
325//! use the `entry` API to ensure that the value is initialized and perform the
326//! logic afterwards.
327//!
328//! #### Tracking the inebriation of customers at a bar
329//!
330//! ```
331//! use std::collections::btree_map::BTreeMap;
332//!
333//! // A client of the bar. They have a blood alcohol level.
334//! struct Person { blood_alcohol: f32 }
335//!
336//! // All the orders made to the bar, by client ID.
337//! let orders = vec![1, 2, 1, 2, 3, 4, 1, 2, 2, 3, 4, 1, 1, 1];
338//!
339//! // Our clients.
340//! let mut blood_alcohol = BTreeMap::new();
341//!
342//! for id in orders {
343//! // If this is the first time we've seen this customer, initialize them
344//! // with no blood alcohol. Otherwise, just retrieve them.
345//! let person = blood_alcohol.entry(id).or_insert(Person { blood_alcohol: 0.0 });
346//!
347//! // Reduce their blood alcohol level. It takes time to order and drink a beer!
348//! person.blood_alcohol *= 0.9;
349//!
350//! // Check if they're sober enough to have another beer.
351//! if person.blood_alcohol > 0.3 {
352//! // Too drunk... for now.
353//! println!("Sorry {id}, I have to cut you off");
354//! } else {
355//! // Have another!
356//! person.blood_alcohol += 0.1;
357//! }
358//! }
359//! ```
360//!
361//! # Insert and complex keys
362//!
363//! If we have a more complex key, calls to `insert` will
364//! not update the value of the key. For example:
365//!
366//! ```
367//! use std::cmp::Ordering;
368//! use std::collections::BTreeMap;
369//! use std::hash::{Hash, Hasher};
370//!
371//! #[derive(Debug)]
372//! struct Foo {
373//! a: u32,
374//! b: &'static str,
375//! }
376//!
377//! // we will compare `Foo`s by their `a` value only.
378//! impl PartialEq for Foo {
379//! fn eq(&self, other: &Self) -> bool { self.a == other.a }
380//! }
381//!
382//! impl Eq for Foo {}
383//!
384//! // we will hash `Foo`s by their `a` value only.
385//! impl Hash for Foo {
386//! fn hash<H: Hasher>(&self, h: &mut H) { self.a.hash(h); }
387//! }
388//!
389//! impl PartialOrd for Foo {
390//! fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.a.partial_cmp(&other.a) }
391//! }
392//!
393//! impl Ord for Foo {
394//! fn cmp(&self, other: &Self) -> Ordering { self.a.cmp(&other.a) }
395//! }
396//!
397//! let mut map = BTreeMap::new();
398//! map.insert(Foo { a: 1, b: "baz" }, 99);
399//!
400//! // We already have a Foo with an a of 1, so this will be updating the value.
401//! map.insert(Foo { a: 1, b: "xyz" }, 100);
402//!
403//! // The value has been updated...
404//! assert_eq!(map.values().next().unwrap(), &100);
405//!
406//! // ...but the key hasn't changed. b is still "baz", not "xyz".
407//! assert_eq!(map.keys().next().unwrap().b, "baz");
408//! ```
409
410#![stable(feature = "rust1", since = "1.0.0")]
411
412#[stable(feature = "try_reserve", since = "1.57.0")]
413pub use alloc_crate::collections::TryReserveError;
414#[unstable(
415 feature = "try_reserve_kind",
416 reason = "Uncertain how much info should be exposed",
417 issue = "48043"
418)]
419pub use alloc_crate::collections::TryReserveErrorKind;
420#[stable(feature = "rust1", since = "1.0.0")]
421pub use alloc_crate::collections::{BTreeMap, BTreeSet, BinaryHeap};
422#[stable(feature = "rust1", since = "1.0.0")]
423pub use alloc_crate::collections::{LinkedList, VecDeque};
424#[stable(feature = "rust1", since = "1.0.0")]
425pub use alloc_crate::collections::{binary_heap, btree_map, btree_set};
426#[stable(feature = "rust1", since = "1.0.0")]
427pub use alloc_crate::collections::{linked_list, vec_deque};
428
429#[stable(feature = "rust1", since = "1.0.0")]
430#[doc(inline)]
431pub use self::hash_map::HashMap;
432#[stable(feature = "rust1", since = "1.0.0")]
433#[doc(inline)]
434pub use self::hash_set::HashSet;
435#[stable(feature = "rust1", since = "1.0.0")]
436// FIXME(#82080) The deprecation here is only theoretical, and does not actually produce a warning.
437#[deprecated(note = "moved to `std::ops::Bound`", since = "1.26.0")]
438#[doc(hidden)]
439pub use crate::ops::Bound;
440
441mod hash;
442
443#[stable(feature = "rust1", since = "1.0.0")]
444pub mod hash_map {
445 //! A hash map implemented with quadratic probing and SIMD lookup.
446 #[stable(feature = "rust1", since = "1.0.0")]
447 pub use super::hash::map::*;
448 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
449 pub use crate::hash::random::DefaultHasher;
450 #[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
451 pub use crate::hash::random::RandomState;
452}
453
454#[stable(feature = "rust1", since = "1.0.0")]
455pub mod hash_set {
456 //! A hash set implemented as a `HashMap` where the value is `()`.
457 #[stable(feature = "rust1", since = "1.0.0")]
458 pub use super::hash::set::*;
459}
460