18.5 Performance and Memory Considerations

  • Vec<T>:

    • Amortized O(1) insertion at the end.
    • Good cache locality.
    • Inserting in the middle or removing from the front can be O(n).

  • String:

    • Similar to Vec<u8> in complexity.
    • Appending may cause reallocations.
    • Handling Unicode can be complex.

  • HashMap<K, V>:

    • Average O(1) lookups/inserts.
    • Requires hashing, may need resizing.
    • Unordered iteration.

  • BTreeMap<K, V>:

    • O(log n) lookups/inserts.
    • Maintains sorted keys and stable iteration order.

  • VecDeque<T>:

    • O(1) insertion/removal at both ends.
    • Ideal for queue-like structures.

  • LinkedList<T>:

    • O(1) insertion/removal at known nodes.
    • Poorer cache locality and O(n) traversal.