18.5 Other Standard Collection Types

Beyond the three main types, Rust’s standard library (std::collections) offers several other useful collections:

  • BTreeMap<K, V>: A map implemented using a B-Tree. Unlike HashMap, BTreeMap stores keys in sorted order. Operations (insert, get, remove) have O(log n) time complexity. It’s useful when you need to iterate over key-value pairs in sorted key order or perform range queries. Keys must implement the Ord trait (total ordering) in addition to Eq.
  • HashSet<T> / BTreeSet<T>: Set collections that store unique elements T.
    • HashSet<T> uses hashing (like HashMap) for average O(1) insertion, removal, and membership checking (contains). Elements must implement Eq and Hash. Order is arbitrary.
    • BTreeSet<T> uses a B-Tree (like BTreeMap) for O(log n) operations and stores elements in sorted order. Elements must implement Ord and Eq. Both are useful for efficiently checking if an item exists in a collection, removing duplicates, or performing set operations (union, intersection, difference).
  • VecDeque<T>: A double-ended queue (deque) implemented using a growable ring buffer. It provides efficient amortized O(1) push and pop operations at both the front and the back of the queue. Accessing elements by index is possible but can be O(n) in the worst case if the element is far from the ends in the ring buffer layout. Useful for implementing FIFO queues, LIFO stacks (though Vec is often simpler for stacks), or algorithms needing efficient access to both ends.
  • LinkedList<T>: A classic doubly-linked list. It offers O(1) insertion and removal if you already have a cursor pointing to the node before or after the desired location. It also allows efficient splitting and merging of lists. However, accessing an element by index requires traversing the list (O(n)), and its node-based allocation pattern generally leads to poorer cache performance compared to Vec or VecDeque. In idiomatic Rust, LinkedList is used less frequently than Vec or VecDeque, reserved for specific algorithms where its unique properties are genuinely advantageous.
  • BinaryHeap<T>: A max-heap implementation (priority queue). It allows efficiently pushing elements (O(log n)) and popping (O(log n)) the largest element according to its Ord implementation. Useful for algorithms like Dijkstra’s or A*, or anytime you need quick access to the maximum item in a collection. Elements must implement Ord and Eq.

All these standard collections manage their memory automatically and uphold Rust’s safety guarantees through the ownership and borrowing system.