Rust for C-Programmers

18.7 Selecting the Appropriate Collection

Here’s a quick guide based on common needs:

• Need a growable list of items accessed primarily by an integer index? -> Use Vec<T>. This is the most common general-purpose sequence collection.
• Need to store and manipulate growable text data? -> Use String (owned) and work with &str (borrowed slices).
• Need to associate unique keys with values for fast lookups, and order doesn’t matter? -> Use HashMap<K, V>. Requires keys to be hashable (Hash + Eq).
• Need key-value storage where keys must be kept in sorted order, or you need to find items within a range of keys? -> Use BTreeMap<K, V>. Requires keys to be orderable (Ord + Eq). Slower than HashMap for individual lookups.
• Need to store unique items efficiently and quickly check if an item is present (order doesn’t matter)? -> Use HashSet<T>. Requires elements to be hashable (Hash + Eq).
• Need to store unique items in sorted order? -> Use BTreeSet<T>. Requires elements to be orderable (Ord + Eq).
• Need a queue (First-In, First-Out) or stack (Last-In, First-Out) with efficient additions/removals at both ends? -> Use VecDeque<T>.
• Need a priority queue (always retrieving the largest/smallest item)? -> Use BinaryHeap<T>. Requires elements to be orderable (Ord + Eq).
• Need efficient insertion/removal in the middle of a sequence at a known location, and don’t need fast random access by index? -> LinkedList<T> might be suitable, but carefully consider if Vec<T> (with O(n) insertion/removal) or VecDeque<T> might still be faster overall due to better cache performance, especially for moderate n. Benchmark if performance is critical.

When in doubt for sequences, start with Vec<T>. For key-value lookups, start with HashMap<K, V>. Choose other collections when their specific properties (ordering, double-ended access, uniqueness) are required.