18.6 Performance and Memory Considerations

Below is a brief overview of typical performance characteristics:

  • Vec<T>

    • Contiguous and cache-friendly.
    • Amortized O(1) insertions at the end.
    • O(n) insertion/removal elsewhere (due to shifting).
    • Usually the best default choice for a growable list.

  • String

    • Essentially Vec<u8> with UTF-8 enforcement.
    • Can reallocate when growing.
    • Complex Unicode operations might require external crates.

  • HashMap<K, V>

    • Average O(1) lookups/inserts.
    • Higher memory overhead due to hashing and potential collisions.
    • Unordered; iteration order may change between program runs.

  • BTreeMap<K, V>

    • O(log n) lookups/inserts, sorted keys, predictable iteration.

  • HashSet<T> / BTreeSet<T>

    • Similar performance characteristics to HashMap / BTreeMap, but store individual values rather than key-value pairs.

  • VecDeque<T>

    • O(1) insertion/removal at both ends.
    • Good for queue or deque usage.

  • LinkedList<T>

    • O(1) insertion/removal at known nodes.
    • Not often a default choice in Rust due to poor locality and the efficiency of Vec<T> in most scenarios.