| Vec |
A dynamic array that can grow and shrink in size. |
Access: O(1), Insert/Remove at end: O(1) |
Fast access by index, efficient for stack-like behavior |
Slower for insertions/removals in the middle (O(n)), can grow large memory blocks |
N/A |
| LinkedList |
A doubly linked list allowing efficient insertion/removal at both ends. |
Access: O(n), Insert/Remove: O(1) |
Efficient insertion/removal at ends, no memory reallocation |
Slow random access (O(n)), higher memory overhead due to pointers |
N/A |
| VecDeque |
A double-ended queue implemented with a growable ring buffer. |
Access: O(1), Insert/Remove: O(1) at ends |
Efficient insertion/removal at both ends |
Inefficient for mid-list insertions/removals, may require resizing |
Extends Vec |
| BinaryHeap |
A max-heap by default, used for priority queue functionality. |
Access max: O(1), Insert: O(log n), Remove max: O(log n) |
Always maintains max or min element at the top |
Not sorted for all elements, only supports efficient retrieval of max/min element |
N/A |
| HashMap |
A key-value store with fast lookups by key. |
Insert/Remove: O(1), Lookup: O(1) |
Fast lookups, flexible with key-value pairs |
Keys must implement Eq and Hash, unordered elements |
N/A |
| BTreeMap |
A sorted key-value store, keeps elements in ascending key order. |
Insert/Remove: O(log n), Lookup: O(log n) |
Sorted keys, good for range queries |
Slower access compared to HashMap, requires Ord trait for keys |
N/A |
| HashSet |
A set of unique values with no specific order. |
Insert/Remove: O(1), Lookup: O(1) |
Fast membership checks, flexible with any Eq and Hash type |
Unordered, only unique elements |
Based on HashMap |
| BTreeSet |
An ordered set of unique values, keeps elements in ascending order. |
Insert/Remove: O(log n), Lookup: O(log n) |
Sorted elements, good for range queries |
Slower access compared to HashSet, requires Ord trait for elements |
Based on BTreeMap |
| Option |
Represents a value that can either be Some (present) or None (absent). |
N/A |
Prevents null pointer errors, clear handling of optional values |
Limited to handling optional values, not a collection by itself |
Standard Rust type |
| Result |
Represents success (Ok) or failure (Err) of an operation. |
N/A |
Ensures explicit error handling, works well in chained operations |
Limited to handling results and errors, not a collection by itself |
Standard Rust type |
| Rc |
Reference-counted pointer, enables multiple ownership of data. |
Clone: O(1), Drop: O(1) |
Shared ownership of data, useful for tree-like structures |
Not thread-safe, potential for reference cycles (use Weak to prevent) |
Standard Rust type |
| Arc |
Atomically reference-counted pointer, enables thread-safe multiple ownership. |
Clone: O(1), Drop: O(1) |
Shared ownership across threads, thread-safe |
Higher overhead than Rc, potential for reference cycles (use Weak to prevent) |
Extends Rc, atomic operations |
| Weak |
Non-owning reference to data managed by Rc or Arc. |
N/A |
Prevents reference cycles in Rc or Arc structures |
Cannot directly access data (must be upgraded to Rc or Arc to use) |
Used with Rc and Arc |
| RefCell |
Allows mutable borrows checked at runtime, even within immutable data structures. |
Borrow: O(1) |
Allows interior mutability, useful with Rc for shared mutability |
Runtime borrow-checking, which can cause panics if rules are violated |
N/A |
| Cell |
Allows mutable borrows within single-threaded contexts, designed for small Copy types. |
Set/Get: O(1) |
Efficient for small Copy types, provides interior mutability |
Limited to Copy types only, lacks runtime checks |
N/A |
| Box |
A smart pointer for heap allocation, useful for large or recursive types. |
Deref: O(1), Allocation: O(1) |
Efficient heap allocation, simplifies recursive structures |
Adds a level of indirection for access, manual memory management needed |
Standard Rust type |