Collections Highlights Summary

Every highlight bullet from the 11 pages in this section, gathered on one page and grouped by the page it came from.

The Iterator Model in Rust

• Iterators are lazy - an adapter chain does nothing until something consumes it
• iter, iter_mut, and into_iter are the same idea expressed through three ownership modes
• Zero-cost abstraction means the compiled chain competes with a hand-written loop, not that it is free to write
• Adapter chains are just nested structs; collect is what finally drives them

Collections Basics

• Use Vec as the default growable heap array for lists
• Use HashMap for fast key lookups with average O(1) performance
• Use BTreeMap for sorted keys and ordered iteration with O(log n) operations
• Use HashSet or BTreeSet for collections of unique elements
• Use VecDeque for efficient pushes and pops from both ends of a collection
• Use BinaryHeap for priority queue implementations, which is a max-heap by default

Vec & Slices

• Vec<T> owns a growable buffer and is the default dynamic array
• &[T] borrows a contiguous view into Vec, arrays, or other data
• Expose &[T] in read APIs for flexible data access
• Avoid index panics by using get(i) instead of direct indexing
• Use shrink_to_fit to reduce memory after building a large Vec
• Consider SmallVec for usually small collections to avoid heap allocations

HashMap & BTreeMap

• HashMap offers fast average lookups
• BTreeMap keeps keys sorted for range queries and deterministic iteration
• Use the entry API to avoid double lookups
• Floats require a wrapper like OrderedFloat for BTreeMap keys
• Consider ahash or fxhash crates for better HashMap performance
• HashMap::with_capacity(n) reduces reallocations

VecDeque, BinaryHeap & LinkedList

• VecDeque is a double-ended queue for O(1) amortized front/back operations
• BinaryHeap is a max-priority queue; implement Ord for custom types
• Avoid LinkedList unless profiling shows a specific need
• For min-heap behavior, reverse the Ord implementation or use std::cmp::Reverse
• Pop from an empty BinaryHeap returns None
• VecDeque's ring buffer growth is amortized efficient

The Iterator Trait

• Implement next method to define an iterator's behavior
• Iterator trait requires fn next(&mut self) -> OptionSelf::Item
• Adapters like map and filter chain lazily until consumption
• Avoid infinite iterators with collect by using take(n)
• IntoIterator trait enables use of for loops
• FusedIterator documents when next will always return None

Iterator Adapters

• Iterator adapters transform iterators lazily
• Chain order matters for efficiency, filter before map
• Iterators are consumed after a single pass
• Use filter_map for a single pass with filtering and mapping
• collect() can infer types, but sometimes needs turbofish
• zip ends on the shortest iterator

Consuming Iterators

• Consuming iterators runs the pipeline after adapters
• Use collect as a final step to gather items into a collection
• sum returns zero for numeric types on an empty iterator
• reduce on an empty iterator returns None
• Provide a type hint for collect to avoid ambiguity
• Avoid needless collect calls to prevent extra allocations

Entry API & In-Place Updates

• Use HashMap::entry to avoid double lookups for inserts or updates
• Entry API is useful for counters, memoization, and grouping operations
• or_default inserts a default value if the entry is vacant
• and_modify mutates an entry in-place without reinsertion
• Avoid allocating new keys with entry(key.to_string()) in hot paths
• Entry mutably borrows the map until the entry is dropped

IntoIterator & Owned vs Borrowed

• IntoIterator converts collections into iterators
• iter() provides a shared borrow of elements
• iter_mut() provides a mutable borrow of elements
• into_iter() consumes the collection, yielding owned elements
• for x in collection calls into_iter on the collection
• for x in vec moves vec, making it unusable afterward

Collections & Iterators Best Practices

• Profile before micro-optimizing iterators
• Default to Vec for sequences; use specialized containers when needed
• Prefer iterators over manual index loops
• Use the entry API for map updates to avoid double lookups
• Reserve capacity when the collection size is known
• Do not mutate a vec during non-adapter iteration